最近把贪吃蛇用 C 重新写了一遍数据容器选的是 set 和 deque。这个小项目做完我对这两个容器的理解比看十页文档都深。如果你也在准备课程设计或者想借一个游戏项目把 STL 容器用熟这篇文章可以参考着抄作业。贪吃蛇看起来简单但它的数据需求其实挺有意思它不仅要维护一条“身体顺序”还要随时回答“某个坐标是不是被身体占着”。deque 和 set 的组合正好各管一项。我先把结论放前面deque 管蛇身的先后顺序和两端的进出set 管碰撞检测和食物生成时的坐标查询。两个容器里存的是同一组坐标必须同步更新。1. 贪吃蛇的数据难题身体要动身体也要查1.1 蛇的两种核心操作任何一版贪吃蛇玩法都绕不开两件事。第一件事是移动。每一帧蛇头向前一格蛇身跟着走普通移动时尾巴同步收缩身体长度不变吃到食物时尾巴保留身体长度加一。从数据操作上看这就是“头部插入一个新坐标尾部看情况删除一个旧坐标”。第二件事是判定。每走一步之前必须回答三个问题新蛇头是不是撞墙了新蛇头是不是咬到了自己的尾巴新蛇头是不是正好踩在食物上这两个需求对数据结构提出的要求是相反的移动要求两端操作都高效判定要求“给定一个坐标快速判断它当前有没有被蛇身占领”。如果你用一个数组从头到尾存蛇身移动勉强能做但查询就得从头遍历到尾。如果你用二维数组标记地图移动和查询都快但地图状态和蛇身状态混在一起后面加多蛇、穿墙、障碍物时很难扩展。所以我在这个版本里选择了 deque 加 set 的组合deque 管“顺序和形状”set 管“坐标是否存在”。1.2 数组与 vector 方案的问题很多课设版本的贪吃蛇用的是vectorpairint,int每条蛇是一个坐标数组蛇头放在 back移动时push_back新头再用erase(begin())删掉旧尾巴。问题出在erase(begin())这一步vector 删除头部元素时要把后面所有元素整体往前搬一格复杂度是 O(n)。蛇短的时候无所谓蛇一长就能感受到卡顿虽然不是量级上的崩溃但这种“每次移动都要搬移整条身体”的写法看着就不太对。还有更常见的“二维数组染色”方案开一个int map[H][W]蛇身的每个格子标成 1移动时把旧尾巴位置改成 0新头位置改成 1。这个方案查询很快但它把“蛇身”和“地图”耦合在一个数组里。如果你以后想支持两条蛇对战或者蛇身有不同部位、不同颜色就得在这个数组里塞一堆额外状态越写越复杂。而且数组方案很难回答“这条蛇第 5 节到底在哪”因为数组里只有标记没有顺序信息。1.3 set 和 deque 的分工逻辑我的方案很直接用std::dequePoint按顺序保存蛇身坐标用std::setPoint保存同样这一组坐标的无序集合。deque 是蛇身体的“骨架顺序”set 是“身份登记表”。打个比方deque 像一条真实的蛇骨架每一节从尾巴到脑袋排得清清楚楚set 像一张花名册你报一个坐标它立刻告诉你这个坐标是不是蛇的地盘。查碰撞时用花名册维护顺序时用骨架各司其职。要付出的代价是两份数据同步deque 里新增一节set 里也要 insertdeque 里删掉尾部set 里也要 erase。这套同步契约是所有后续代码的基础后面我会专门讲这里踩过的坑。2. deque 做蛇身头插尾删才是移动的本质2.1 deque 容器特性回顾std::deque是双端队列允许在头部和尾部都以 O(1) 复杂度插入、删除元素同时支持下标随机访问也就是body[2]这种操作依然成立。它内部通常是分段连续内存数据被切成固定大小的块块与块之间由一个中控数组管理。所以往两端插入删除时不需要像 vector 那样把所有元素搬走只需要操作对应内存块也不像 list 那样每个节点单独分配内存导致位置分散、缓存命中率低。这种“两端都能动、又能按下标取元素”的特性正是贪吃蛇蛇身需要的。2.2 蛇的移动就是标准的头插尾删蛇移动的本质是“头往前走一格尾巴跟上来一格”。不加速的时候新头坐标算出来body.push_front(newHead)把新头插到最前面然后body.pop_back()把旧尾巴删掉。整个过程中蛇身元素数量不变但 deque 内部头尾各操作一次都是 O(1)每一步移动都非常干净。加速的时候吃到食物只做body.push_front(newHead)不删尾巴。头部多出一格身体长度加一。这个“只看尾巴动不动”的模型比用长度计数器去修改数组要直观得多。在 C 里写出来就是body.push_front(newHead); if (!eat) { body.pop_back(); }就这么两行没有循环没有元素搬移。deque 的接口设计几乎是为这个场景量身定做的。2.3 为什么不选 vector 和 list选容器的时候其实我列过一个对比表容器头部插入尾部删除随机访问对贪吃蛇的适配vectorO(n)搬移全部元素O(1)O(1)头插成本高只适合尾部操作为主的任务listO(1)但节点分散O(1)O(n)要遍历随机取第 k 节蛇身很慢缓存也不友好dequeO(1)O(1)O(1)两头操作和随机访问兼得正合适list也是个容易被新手选中的选项因为蛇身看起来就是“一串节点”。但 list 最大的问题是不能随机访问以后你想让蛇身第 5 节变个颜色、让第 10 节变成宝石身list 就得从头遍历到目标位置。deque 直接用下标就能取到。所以在“顺序容器”这个维度上deque 是最合适的选择。3. set 做碰撞检测把自撞判定变成一次查找3.1 碰撞检测本质是“坐标是否在集合里”算出新头位置之后判断有没有撞到身体本质上就是回答一个问题这个坐标现在是不是属于蛇身这就是经典的集合成员查询。如果你只在 deque 里存蛇身就要写一个循环从头到尾查一遍bool hit false; for (const auto p : body) { if (p newHead) { hit true; break; } }这段代码能跑但它把“判断某个坐标是不是蛇身”这个问题退化成了一遍线性扫描。而 set 生来就是干这件事的find、count、insert、erase的时间复杂度都是 O(log n)n 是蛇身长度。自撞判定变成一次查找if (occupied.find(newHead) ! occupied.end()) { // 撞到自己了 }更重要的是代码意图非常清楚。读代码的人不需要从一个循环里推导“这是在查碰撞”看到occupied.find就知道你在做成员判断。3.2 为什么用 set 而不是 unordered_setset 底层通常是一棵红黑树元素自动有序。我优先选 set 而不是unordered_set有几个原因。第一蛇身坐标需要定义排序关系也就是operatorset 正好需要unordered_set还需要额外写哈希函数对Point这种小结构来说有点多余。第二红黑树的插入、删除、查找复杂度稳定不会有哈希表扩容、重哈希的最坏情况。在贪吃蛇这个规模下O(log n) 和 O(1) 的差别感知不到但代码更简单。第三set 的有序性在调试时很友好。我经常打日志看occupied里都有哪些元素set 打印出来是一串有序坐标一眼能看出 set 和 deque 是否同步。如果用哈希表打印出来的顺序是乱的排查问题时反而不方便。3.3 生成食物同样依赖 set食物生成也必须判断“随机选出来的格子是不是已经被蛇占了”。最简单的写法是不断随机坐标直到落在空位上。蛇身短时这个策略很快但蛇快占满地图时随机命中空位的概率很低极端情况下会死循环。所以我干脆遍历整个地图把不在occupied里的坐标收集到一个vector再从vector里随机选一个作为食物vectorPoint emptyCells; for (int y 0; y height; y) { for (int x 0; x width; x) { Point p(x, y); if (occupied.find(p) occupied.end()) { emptyCells.push_back(p); } } } if (!emptyCells.empty()) { food emptyCells[rand() % emptyCells.size()]; }这个做法是稳定的不会出现随机死循环。而且每次判断都用 set不需要针对每个空格再去遍历一遍 deque。4. 核心逻辑串起来移动、进食、死亡判定4.1 坐标类型与方向状态机坐标用Point结构体包含 x、y 两个 int。它必须实现operatorset 依赖这个排序关系还要实现operator用来判断蛇头是否踩到食物、绘制时比较坐标。方向用两个 int 表示单位向量dirX和dirY。按 W 时dirY-1按 S 时dirY1按 A 时dirX-1按 D 时dirX1。按键处理里必须有一个“禁止原地掉头”的判断if (ndx -dirX ndy -dirY) return;为什么这个判断重要因为蛇向左走时你按 D 想去右边新头会直接穿回自己脖子那一节这是游戏规则不允许的。挡住掉头比在 tick 里再处理要好因为改方向时直接拒绝游戏逻辑更清晰。4.2 一步移动的完整流程每帧执行的 tick 函数按这个顺序处理取蛇头body.front()根据当前方向算出newHead。撞墙判定newHead超出地图范围就置 running 为 false。判断是否吃到食物newHead food。自撞判定在occupied里查找newHead。执行移动body.push_front(newHead)同时occupied.insert(newHead)。没吃到食物就删尾巴吃到食物就保留尾巴。吃到食物时得分加一重新生成食物并检查胜利。排列顺序上要注意所有碰撞判定都发生在真正修改蛇身之前。你不能先 push_front 再查碰撞因为那样等于把新头当成自己的身体去查永远查不到。4.3 “尾巴特判”最容易写错的碰撞分支自撞判定有一个非常隐蔽的细节新蛇头撞上自己尾巴时如果这一帧没有吃到食物其实是合法的。原因是下一秒尾巴就要被 pop_back 移走蛇头进入的位置正好空出来不会撞上。但如果这一帧吃到食物尾巴保留不动那么新头踩到尾巴就是真撞上。所以判断不能写死成“集合里有这个坐标就死”if (occupied.find(newHead) ! occupied.end()) { Point tail body.back(); // 不吃食物时尾巴马上会移走撞尾巴是允许的 if (!(newHead tail !eat)) { running false; return false; } }我第一次实现时漏掉了这个特判蛇越长越容易在转身时离奇死亡排查了很久才发现是这里的问题。这也是 set 和 deque 必须同步维护的又一个体现判断需要用 deque 的back()拿到尾巴坐标结合是否吃食物来修正结果。4.4 食物生成与胜利条件胜利条件不是“分数到了某个固定值”而是蛇身长度占满整个地图。初始长度是 1每吃一个食物长度加一所以胜利时score width * height - 1。这个判断要放在生成食物之前否则地图满了时spawnFood的emptyCells是空的随机取食物会失败。代码里是这样if (score width * height - 1) { victory true; running false; return true; } spawnFood();5. 完整可运行的控制台版贪吃蛇5.1 完整代码C17到这里我把完整代码贴出来。这个版本是 Windows 控制台版用conio.h处理即时按键用windows.h的Sleep控制帧间隔。核心的 deque 和 set 逻辑不依赖平台。// snake.cpp 贪吃蛇set deque 版本 #include cctype #include conio.h #include cstdlib #include ctime #include deque #include iostream #include set #include vector #include windows.h using namespace std; struct Point { int x, y; Point(int px 0, int py 0) : x(px), y(py) {} bool operator(const Point other) const { if (x ! other.x) return x other.x; return y other.y; } bool operator(const Point other) const { return x other.x y other.y; } }; class SnakeGame { int width, height; dequePoint body; setPoint occupied; Point food; int dirX, dirY; int score; bool running; bool victory; public: SnakeGame(int w 24, int h 12) : width(w), height(h), dirX(1), dirY(0), score(0), running(true), victory(false) { Point start(width / 2, height / 2); body.push_back(start); occupied.insert(start); spawnFood(); } void changeDir(char key) { int ndx 0, ndy 0; switch (tolower(key)) { case w: ndx 0; ndy -1; break; case s: ndx 0; ndy 1; break; case a: ndx -1; ndy 0; break; case d: ndx 1; ndy 0; break; default: return; } if (ndx -dirX ndy -dirY) return; dirX ndx; dirY ndy; } bool tick() { if (!running) return false; Point head body.front(); Point newHead(head.x dirX, head.y dirY); if (newHead.x 0 || newHead.x width || newHead.y 0 || newHead.y height) { running false; return false; } bool eat (newHead food); if (occupied.find(newHead) ! occupied.end()) { Point tail body.back(); if (!(newHead tail !eat)) { running false; return false; } } body.push_front(newHead); occupied.insert(newHead); if (eat) { score; if (score width * height - 1) { victory true; running false; return true; } spawnFood(); } else { Point tail body.back(); body.pop_back(); occupied.erase(tail); } return true; } void draw() const { system(cls); for (int y -1; y height; y) { for (int x -1; x width; x) { if (x -1 || x width || y -1 || y height) { cout #; continue; } Point p(x, y); if (p body.front()) { cout ; } else if (occupied.find(p) ! occupied.end()) { cout O; } else if (p food) { cout *; } else { cout ; } } cout \n; } cout Score: score \n; } bool isRunning() const { return running; } bool isVictory() const { return victory; } int getScore() const { return score; } private: void spawnFood() { vectorPoint emptyCells; for (int y 0; y height; y) { for (int x 0; x width; x) { Point p(x, y); if (occupied.find(p) occupied.end()) { emptyCells.push_back(p); } } } if (!emptyCells.empty()) { food emptyCells[rand() % emptyCells.size()]; } } }; int main() { srand((unsigned)time(nullptr)); SnakeGame game(24, 12); while (game.isRunning()) { game.draw(); while (_kbhit()) { char key _getch(); if (key q || key Q) { cout Quit.\n; return 0; } game.changeDir(key); } game.tick(); Sleep(150); } game.draw(); if (game.isVictory()) { cout You Win! Final Score: game.getScore() \n; } else { cout Game Over! Final Score: game.getScore() \n; } return 0; }5.2 编译与运行方式在 Windows 控制台或 MinGW 环境下用这条命令编译g -stdc17 snake.cpp -o snake.exe运行起来之后地图是一个 24 乘 12 的方框蛇头是蛇身是O食物是*。WASD 控制方向按 Q 直接退出。程序默认每 150 毫秒走一步蛇会一直向当前方向前进直到你按键转向或者撞上边界、撞上自己。如果你在 Linux 或者 macOS 上想跑conio.h和windows.h都不能直接用。最省事的方案是把输入改成termios非阻塞模式把Sleep换成nanosleep或者干脆装 ncurses 重写输入部分。核心的 deque 和 set 逻辑完全可以原样搬过去平台差异只影响输入输出层不影响数据结构和游戏逻辑。5.3 运行效果与结构说明跑起来之后你会发现几个细节食物不会生成在蛇身上因为生成逻辑用occupied做了判断。蛇头碰到自己尾巴的前一刻如果尾巴即将移走游戏不会误判死亡。蛇身越来越长之后移动依然流畅因为每次移动只做常数次 deque 操作和几次 O(log n) 的 set 操作。地图被占满时游戏提示 You Win而不是进入死循环等食物。结构上我把数据和逻辑都封在SnakeGame类里。body和occupied两个成员就是核心数据结构tick负责一步的状态推进draw负责渲染spawnFood负责生成食物。以后想加功能比如速度递进、穿墙模式、障碍物都是在这个类上做增量修改。6. 实测中踩过的坑set 和 deque 的同步维护6.1 改了 deque 忘了改 set碰撞判定直接失效这套组合容器最大的坑就是两份数据不同步。我有一次重构时只写了body.push_front(newHead)忘了同时occupied.insert(newHead)。结果画面里蛇正常移动但 set 里始终只有最初几个坐标。后果是蛇头撞上后半段身体时set 根本查不到那个坐标蛇直接从自己身上穿过去怎么死的都不知道。反过来也一样只body.pop_back()但忘了occupied.erase(tail)set 里会残留一堆已经不存在的坐标蛇走到某个空位会莫名判定死亡。我的经验是把“同步更新”当成一个固定动作每次写移动代码时把这两个容器的操作放在一起push_front 和 insert 在同一段pop_back 和 erase 在同一段。宁可代码看起来啰嗦也不要把同步拆得太散。6.2 键盘方向与逻辑方向打架另一个容易出问题的地方是按键方向和 tick 的执行顺序。如果你把按键处理放在 tick 之后按下的方向要到下一帧才生效手感会明显迟钝。我的写法是每帧先绘制然后立刻清空键盘缓冲区读取最新方向最后才 tick。这样按键到下一条指令之间的延迟只有一个 Sleep 间隔。还有一个取舍问题用if (_kbhit())一次只读一个键连续快速按键时会丢操作用while (_kbhit())循环读会把同一帧里的多次按键归并成最后一次。我的代码选择后者确实会有“上、左”变成“只剩左”的情况但至少蛇不会出现慢半拍转向。如果你更追求跟手可以改成一次只读一个键把帧率调高。这个取舍没有绝对标准。6.3 随机生成食物的死循环隐患食物生成如果写成下面这样while (true) { Point p(rand() % width, rand() % height); if (occupied.find(p) occupied.end()) { food p; break; } }蛇身短的时候没问题但蛇快占满地图时随机命中空位的概率越来越低循环次数会指数上升极端情况下直接卡死。我的spawnFood改成收集所有空格再随机选从根本上避免了这个问题。空位收集也正好用 set 的查找一举两得。6.4 绘制地图时 set 的另一个用武之地draw函数里遍历整个地图对每个格子都要判断“这是不是蛇身”。如果没有 set就得在 deque 里再写一层循环。地图 24 乘 12 有 288 格蛇长 100 时是 28800 次比较代码还会嵌套得很深。有了 set一个find搞定绘制逻辑清清楚楚。这个场景顺带说明了一件事只要游戏里的任意位置需要回答“某个坐标在不在蛇身上”都可以直接交给 set。撞墙判断、食物生成、地图绘制、以后要做雷达图、碰撞特效都是同一个查询接口。6.5 一个诚实的结论性能不是唯一理由最后补一句实话以贪吃蛇的地图规模就算你用 vector 加 find每帧做几次线性扫描计算机也不会卡。蛇身最长也就几百个格子性能根本不是瓶颈。我坚持用 set 配 deque更看重的是容器语义和代码可读性deque 天然表达“两端操作的身体序列”set 天然表达“坐标是否存在”的集合。你写代码的时候不用去想“这里应该用哪个容器”而是“这个问题需要什么样的操作”容器自己就跳出来了。最后说一个我个人的习惯我把 set 成员命名为occupied而不是bodySet。因为 set 里保存的语义是“哪些坐标已经被占用”这样在spawnFood、draw、tick里读代码时意图非常明确。容器命名跟着语义走比跟着类型走好维护得多。你以后写自己的游戏也可以试试这个习惯。
C++贪吃蛇实战：用deque+set搞定蛇身与碰撞检测
最近把贪吃蛇用 C 重新写了一遍数据容器选的是 set 和 deque。这个小项目做完我对这两个容器的理解比看十页文档都深。如果你也在准备课程设计或者想借一个游戏项目把 STL 容器用熟这篇文章可以参考着抄作业。贪吃蛇看起来简单但它的数据需求其实挺有意思它不仅要维护一条“身体顺序”还要随时回答“某个坐标是不是被身体占着”。deque 和 set 的组合正好各管一项。我先把结论放前面deque 管蛇身的先后顺序和两端的进出set 管碰撞检测和食物生成时的坐标查询。两个容器里存的是同一组坐标必须同步更新。1. 贪吃蛇的数据难题身体要动身体也要查1.1 蛇的两种核心操作任何一版贪吃蛇玩法都绕不开两件事。第一件事是移动。每一帧蛇头向前一格蛇身跟着走普通移动时尾巴同步收缩身体长度不变吃到食物时尾巴保留身体长度加一。从数据操作上看这就是“头部插入一个新坐标尾部看情况删除一个旧坐标”。第二件事是判定。每走一步之前必须回答三个问题新蛇头是不是撞墙了新蛇头是不是咬到了自己的尾巴新蛇头是不是正好踩在食物上这两个需求对数据结构提出的要求是相反的移动要求两端操作都高效判定要求“给定一个坐标快速判断它当前有没有被蛇身占领”。如果你用一个数组从头到尾存蛇身移动勉强能做但查询就得从头遍历到尾。如果你用二维数组标记地图移动和查询都快但地图状态和蛇身状态混在一起后面加多蛇、穿墙、障碍物时很难扩展。所以我在这个版本里选择了 deque 加 set 的组合deque 管“顺序和形状”set 管“坐标是否存在”。1.2 数组与 vector 方案的问题很多课设版本的贪吃蛇用的是vectorpairint,int每条蛇是一个坐标数组蛇头放在 back移动时push_back新头再用erase(begin())删掉旧尾巴。问题出在erase(begin())这一步vector 删除头部元素时要把后面所有元素整体往前搬一格复杂度是 O(n)。蛇短的时候无所谓蛇一长就能感受到卡顿虽然不是量级上的崩溃但这种“每次移动都要搬移整条身体”的写法看着就不太对。还有更常见的“二维数组染色”方案开一个int map[H][W]蛇身的每个格子标成 1移动时把旧尾巴位置改成 0新头位置改成 1。这个方案查询很快但它把“蛇身”和“地图”耦合在一个数组里。如果你以后想支持两条蛇对战或者蛇身有不同部位、不同颜色就得在这个数组里塞一堆额外状态越写越复杂。而且数组方案很难回答“这条蛇第 5 节到底在哪”因为数组里只有标记没有顺序信息。1.3 set 和 deque 的分工逻辑我的方案很直接用std::dequePoint按顺序保存蛇身坐标用std::setPoint保存同样这一组坐标的无序集合。deque 是蛇身体的“骨架顺序”set 是“身份登记表”。打个比方deque 像一条真实的蛇骨架每一节从尾巴到脑袋排得清清楚楚set 像一张花名册你报一个坐标它立刻告诉你这个坐标是不是蛇的地盘。查碰撞时用花名册维护顺序时用骨架各司其职。要付出的代价是两份数据同步deque 里新增一节set 里也要 insertdeque 里删掉尾部set 里也要 erase。这套同步契约是所有后续代码的基础后面我会专门讲这里踩过的坑。2. deque 做蛇身头插尾删才是移动的本质2.1 deque 容器特性回顾std::deque是双端队列允许在头部和尾部都以 O(1) 复杂度插入、删除元素同时支持下标随机访问也就是body[2]这种操作依然成立。它内部通常是分段连续内存数据被切成固定大小的块块与块之间由一个中控数组管理。所以往两端插入删除时不需要像 vector 那样把所有元素搬走只需要操作对应内存块也不像 list 那样每个节点单独分配内存导致位置分散、缓存命中率低。这种“两端都能动、又能按下标取元素”的特性正是贪吃蛇蛇身需要的。2.2 蛇的移动就是标准的头插尾删蛇移动的本质是“头往前走一格尾巴跟上来一格”。不加速的时候新头坐标算出来body.push_front(newHead)把新头插到最前面然后body.pop_back()把旧尾巴删掉。整个过程中蛇身元素数量不变但 deque 内部头尾各操作一次都是 O(1)每一步移动都非常干净。加速的时候吃到食物只做body.push_front(newHead)不删尾巴。头部多出一格身体长度加一。这个“只看尾巴动不动”的模型比用长度计数器去修改数组要直观得多。在 C 里写出来就是body.push_front(newHead); if (!eat) { body.pop_back(); }就这么两行没有循环没有元素搬移。deque 的接口设计几乎是为这个场景量身定做的。2.3 为什么不选 vector 和 list选容器的时候其实我列过一个对比表容器头部插入尾部删除随机访问对贪吃蛇的适配vectorO(n)搬移全部元素O(1)O(1)头插成本高只适合尾部操作为主的任务listO(1)但节点分散O(1)O(n)要遍历随机取第 k 节蛇身很慢缓存也不友好dequeO(1)O(1)O(1)两头操作和随机访问兼得正合适list也是个容易被新手选中的选项因为蛇身看起来就是“一串节点”。但 list 最大的问题是不能随机访问以后你想让蛇身第 5 节变个颜色、让第 10 节变成宝石身list 就得从头遍历到目标位置。deque 直接用下标就能取到。所以在“顺序容器”这个维度上deque 是最合适的选择。3. set 做碰撞检测把自撞判定变成一次查找3.1 碰撞检测本质是“坐标是否在集合里”算出新头位置之后判断有没有撞到身体本质上就是回答一个问题这个坐标现在是不是属于蛇身这就是经典的集合成员查询。如果你只在 deque 里存蛇身就要写一个循环从头到尾查一遍bool hit false; for (const auto p : body) { if (p newHead) { hit true; break; } }这段代码能跑但它把“判断某个坐标是不是蛇身”这个问题退化成了一遍线性扫描。而 set 生来就是干这件事的find、count、insert、erase的时间复杂度都是 O(log n)n 是蛇身长度。自撞判定变成一次查找if (occupied.find(newHead) ! occupied.end()) { // 撞到自己了 }更重要的是代码意图非常清楚。读代码的人不需要从一个循环里推导“这是在查碰撞”看到occupied.find就知道你在做成员判断。3.2 为什么用 set 而不是 unordered_setset 底层通常是一棵红黑树元素自动有序。我优先选 set 而不是unordered_set有几个原因。第一蛇身坐标需要定义排序关系也就是operatorset 正好需要unordered_set还需要额外写哈希函数对Point这种小结构来说有点多余。第二红黑树的插入、删除、查找复杂度稳定不会有哈希表扩容、重哈希的最坏情况。在贪吃蛇这个规模下O(log n) 和 O(1) 的差别感知不到但代码更简单。第三set 的有序性在调试时很友好。我经常打日志看occupied里都有哪些元素set 打印出来是一串有序坐标一眼能看出 set 和 deque 是否同步。如果用哈希表打印出来的顺序是乱的排查问题时反而不方便。3.3 生成食物同样依赖 set食物生成也必须判断“随机选出来的格子是不是已经被蛇占了”。最简单的写法是不断随机坐标直到落在空位上。蛇身短时这个策略很快但蛇快占满地图时随机命中空位的概率很低极端情况下会死循环。所以我干脆遍历整个地图把不在occupied里的坐标收集到一个vector再从vector里随机选一个作为食物vectorPoint emptyCells; for (int y 0; y height; y) { for (int x 0; x width; x) { Point p(x, y); if (occupied.find(p) occupied.end()) { emptyCells.push_back(p); } } } if (!emptyCells.empty()) { food emptyCells[rand() % emptyCells.size()]; }这个做法是稳定的不会出现随机死循环。而且每次判断都用 set不需要针对每个空格再去遍历一遍 deque。4. 核心逻辑串起来移动、进食、死亡判定4.1 坐标类型与方向状态机坐标用Point结构体包含 x、y 两个 int。它必须实现operatorset 依赖这个排序关系还要实现operator用来判断蛇头是否踩到食物、绘制时比较坐标。方向用两个 int 表示单位向量dirX和dirY。按 W 时dirY-1按 S 时dirY1按 A 时dirX-1按 D 时dirX1。按键处理里必须有一个“禁止原地掉头”的判断if (ndx -dirX ndy -dirY) return;为什么这个判断重要因为蛇向左走时你按 D 想去右边新头会直接穿回自己脖子那一节这是游戏规则不允许的。挡住掉头比在 tick 里再处理要好因为改方向时直接拒绝游戏逻辑更清晰。4.2 一步移动的完整流程每帧执行的 tick 函数按这个顺序处理取蛇头body.front()根据当前方向算出newHead。撞墙判定newHead超出地图范围就置 running 为 false。判断是否吃到食物newHead food。自撞判定在occupied里查找newHead。执行移动body.push_front(newHead)同时occupied.insert(newHead)。没吃到食物就删尾巴吃到食物就保留尾巴。吃到食物时得分加一重新生成食物并检查胜利。排列顺序上要注意所有碰撞判定都发生在真正修改蛇身之前。你不能先 push_front 再查碰撞因为那样等于把新头当成自己的身体去查永远查不到。4.3 “尾巴特判”最容易写错的碰撞分支自撞判定有一个非常隐蔽的细节新蛇头撞上自己尾巴时如果这一帧没有吃到食物其实是合法的。原因是下一秒尾巴就要被 pop_back 移走蛇头进入的位置正好空出来不会撞上。但如果这一帧吃到食物尾巴保留不动那么新头踩到尾巴就是真撞上。所以判断不能写死成“集合里有这个坐标就死”if (occupied.find(newHead) ! occupied.end()) { Point tail body.back(); // 不吃食物时尾巴马上会移走撞尾巴是允许的 if (!(newHead tail !eat)) { running false; return false; } }我第一次实现时漏掉了这个特判蛇越长越容易在转身时离奇死亡排查了很久才发现是这里的问题。这也是 set 和 deque 必须同步维护的又一个体现判断需要用 deque 的back()拿到尾巴坐标结合是否吃食物来修正结果。4.4 食物生成与胜利条件胜利条件不是“分数到了某个固定值”而是蛇身长度占满整个地图。初始长度是 1每吃一个食物长度加一所以胜利时score width * height - 1。这个判断要放在生成食物之前否则地图满了时spawnFood的emptyCells是空的随机取食物会失败。代码里是这样if (score width * height - 1) { victory true; running false; return true; } spawnFood();5. 完整可运行的控制台版贪吃蛇5.1 完整代码C17到这里我把完整代码贴出来。这个版本是 Windows 控制台版用conio.h处理即时按键用windows.h的Sleep控制帧间隔。核心的 deque 和 set 逻辑不依赖平台。// snake.cpp 贪吃蛇set deque 版本 #include cctype #include conio.h #include cstdlib #include ctime #include deque #include iostream #include set #include vector #include windows.h using namespace std; struct Point { int x, y; Point(int px 0, int py 0) : x(px), y(py) {} bool operator(const Point other) const { if (x ! other.x) return x other.x; return y other.y; } bool operator(const Point other) const { return x other.x y other.y; } }; class SnakeGame { int width, height; dequePoint body; setPoint occupied; Point food; int dirX, dirY; int score; bool running; bool victory; public: SnakeGame(int w 24, int h 12) : width(w), height(h), dirX(1), dirY(0), score(0), running(true), victory(false) { Point start(width / 2, height / 2); body.push_back(start); occupied.insert(start); spawnFood(); } void changeDir(char key) { int ndx 0, ndy 0; switch (tolower(key)) { case w: ndx 0; ndy -1; break; case s: ndx 0; ndy 1; break; case a: ndx -1; ndy 0; break; case d: ndx 1; ndy 0; break; default: return; } if (ndx -dirX ndy -dirY) return; dirX ndx; dirY ndy; } bool tick() { if (!running) return false; Point head body.front(); Point newHead(head.x dirX, head.y dirY); if (newHead.x 0 || newHead.x width || newHead.y 0 || newHead.y height) { running false; return false; } bool eat (newHead food); if (occupied.find(newHead) ! occupied.end()) { Point tail body.back(); if (!(newHead tail !eat)) { running false; return false; } } body.push_front(newHead); occupied.insert(newHead); if (eat) { score; if (score width * height - 1) { victory true; running false; return true; } spawnFood(); } else { Point tail body.back(); body.pop_back(); occupied.erase(tail); } return true; } void draw() const { system(cls); for (int y -1; y height; y) { for (int x -1; x width; x) { if (x -1 || x width || y -1 || y height) { cout #; continue; } Point p(x, y); if (p body.front()) { cout ; } else if (occupied.find(p) ! occupied.end()) { cout O; } else if (p food) { cout *; } else { cout ; } } cout \n; } cout Score: score \n; } bool isRunning() const { return running; } bool isVictory() const { return victory; } int getScore() const { return score; } private: void spawnFood() { vectorPoint emptyCells; for (int y 0; y height; y) { for (int x 0; x width; x) { Point p(x, y); if (occupied.find(p) occupied.end()) { emptyCells.push_back(p); } } } if (!emptyCells.empty()) { food emptyCells[rand() % emptyCells.size()]; } } }; int main() { srand((unsigned)time(nullptr)); SnakeGame game(24, 12); while (game.isRunning()) { game.draw(); while (_kbhit()) { char key _getch(); if (key q || key Q) { cout Quit.\n; return 0; } game.changeDir(key); } game.tick(); Sleep(150); } game.draw(); if (game.isVictory()) { cout You Win! Final Score: game.getScore() \n; } else { cout Game Over! Final Score: game.getScore() \n; } return 0; }5.2 编译与运行方式在 Windows 控制台或 MinGW 环境下用这条命令编译g -stdc17 snake.cpp -o snake.exe运行起来之后地图是一个 24 乘 12 的方框蛇头是蛇身是O食物是*。WASD 控制方向按 Q 直接退出。程序默认每 150 毫秒走一步蛇会一直向当前方向前进直到你按键转向或者撞上边界、撞上自己。如果你在 Linux 或者 macOS 上想跑conio.h和windows.h都不能直接用。最省事的方案是把输入改成termios非阻塞模式把Sleep换成nanosleep或者干脆装 ncurses 重写输入部分。核心的 deque 和 set 逻辑完全可以原样搬过去平台差异只影响输入输出层不影响数据结构和游戏逻辑。5.3 运行效果与结构说明跑起来之后你会发现几个细节食物不会生成在蛇身上因为生成逻辑用occupied做了判断。蛇头碰到自己尾巴的前一刻如果尾巴即将移走游戏不会误判死亡。蛇身越来越长之后移动依然流畅因为每次移动只做常数次 deque 操作和几次 O(log n) 的 set 操作。地图被占满时游戏提示 You Win而不是进入死循环等食物。结构上我把数据和逻辑都封在SnakeGame类里。body和occupied两个成员就是核心数据结构tick负责一步的状态推进draw负责渲染spawnFood负责生成食物。以后想加功能比如速度递进、穿墙模式、障碍物都是在这个类上做增量修改。6. 实测中踩过的坑set 和 deque 的同步维护6.1 改了 deque 忘了改 set碰撞判定直接失效这套组合容器最大的坑就是两份数据不同步。我有一次重构时只写了body.push_front(newHead)忘了同时occupied.insert(newHead)。结果画面里蛇正常移动但 set 里始终只有最初几个坐标。后果是蛇头撞上后半段身体时set 根本查不到那个坐标蛇直接从自己身上穿过去怎么死的都不知道。反过来也一样只body.pop_back()但忘了occupied.erase(tail)set 里会残留一堆已经不存在的坐标蛇走到某个空位会莫名判定死亡。我的经验是把“同步更新”当成一个固定动作每次写移动代码时把这两个容器的操作放在一起push_front 和 insert 在同一段pop_back 和 erase 在同一段。宁可代码看起来啰嗦也不要把同步拆得太散。6.2 键盘方向与逻辑方向打架另一个容易出问题的地方是按键方向和 tick 的执行顺序。如果你把按键处理放在 tick 之后按下的方向要到下一帧才生效手感会明显迟钝。我的写法是每帧先绘制然后立刻清空键盘缓冲区读取最新方向最后才 tick。这样按键到下一条指令之间的延迟只有一个 Sleep 间隔。还有一个取舍问题用if (_kbhit())一次只读一个键连续快速按键时会丢操作用while (_kbhit())循环读会把同一帧里的多次按键归并成最后一次。我的代码选择后者确实会有“上、左”变成“只剩左”的情况但至少蛇不会出现慢半拍转向。如果你更追求跟手可以改成一次只读一个键把帧率调高。这个取舍没有绝对标准。6.3 随机生成食物的死循环隐患食物生成如果写成下面这样while (true) { Point p(rand() % width, rand() % height); if (occupied.find(p) occupied.end()) { food p; break; } }蛇身短的时候没问题但蛇快占满地图时随机命中空位的概率越来越低循环次数会指数上升极端情况下直接卡死。我的spawnFood改成收集所有空格再随机选从根本上避免了这个问题。空位收集也正好用 set 的查找一举两得。6.4 绘制地图时 set 的另一个用武之地draw函数里遍历整个地图对每个格子都要判断“这是不是蛇身”。如果没有 set就得在 deque 里再写一层循环。地图 24 乘 12 有 288 格蛇长 100 时是 28800 次比较代码还会嵌套得很深。有了 set一个find搞定绘制逻辑清清楚楚。这个场景顺带说明了一件事只要游戏里的任意位置需要回答“某个坐标在不在蛇身上”都可以直接交给 set。撞墙判断、食物生成、地图绘制、以后要做雷达图、碰撞特效都是同一个查询接口。6.5 一个诚实的结论性能不是唯一理由最后补一句实话以贪吃蛇的地图规模就算你用 vector 加 find每帧做几次线性扫描计算机也不会卡。蛇身最长也就几百个格子性能根本不是瓶颈。我坚持用 set 配 deque更看重的是容器语义和代码可读性deque 天然表达“两端操作的身体序列”set 天然表达“坐标是否存在”的集合。你写代码的时候不用去想“这里应该用哪个容器”而是“这个问题需要什么样的操作”容器自己就跳出来了。最后说一个我个人的习惯我把 set 成员命名为occupied而不是bodySet。因为 set 里保存的语义是“哪些坐标已经被占用”这样在spawnFood、draw、tick里读代码时意图非常明确。容器命名跟着语义走比跟着类型走好维护得多。你以后写自己的游戏也可以试试这个习惯。
