要做贪吃蛇却把目光盯在set和deque上这其实是一个比游戏本身更值得聊的话题。很多新手写贪吃蛇第一个直觉是用二维数组或者list存蛇身然后每次判断“下一步有没有撞到自己”就if new_head in snake_list蛇长了以后越跑越慢而且逻辑越来越绕。这次我就用一套可运行的 Python 贪吃蛇项目把set和deque这两个容器怎么配合、为什么这么配合以及实操中会遇到哪些坑全部摊开讲清楚。这篇文章既适合刚学完 Python 基础、想通过项目加深数据结构理解的人也适合准备面试时拿贪吃蛇当项目案例的人。1. 项目概述与数据结构选型思路1.1 贪吃蛇背后真正要解的问题贪吃蛇看起来就是个游戏但如果你把它当成一个纯粹的编程题目核心需求其实只有三个蛇要整体向前移动、吃到食物会长一节、任何情况下都要快速判断“下一步会不会撞墙或撞到自己”。其中“整体向前移动”这个需求决定了蛇身的存储结构必须能高效“头进尾出”。想象一下蛇每走一步头前进一格尾巴收回一格中间的身体整体平移。这本质上就是一个队列操作先进来的一节先离开。用list当然也能写但在头部做pop(0)是很吃亏的因为列表底层是连续内存弹出头部元素后后面所有元素都要往前挪时间复杂度是 O(n)。蛇短的时候无所谓一旦蛇身到几百节每一步都搬运一次肉眼可见地变卡。“撞自己”的判断则是另一个维度的需求它是纯粹的“这个坐标在不在集合里”。这种存在性查询用列表做同样是 O(n) 的遍历用set做哈希表加持均摊复杂度 O(1)。所以贪吃蛇这个项目天然地逼你做一次数据结构的选型哪一个容器管顺序哪一个容器管查重。1.2 deque set教科书级组合的底气用deque管理蛇身的顺序用set管理蛇身坐标的“存在性”这个组合几乎是贪吃蛇的标准答案。两个容器各管一件事deque保证你能在头尾两端都以 O(1) 的代价操作set保证你能用 O(1) 的代价判断“某个格子当前是不是蛇身”。一个维护“第几节在哪个位置”一个维护“哪些位置已经被占”。这就像你左手拿着一张按顺序排好的纸条右手拿着一张记录所有出现过的地点的清单。纸条负责告诉你哪一步该走哪一步该扔清单负责告诉你某个地点有没有被登记过。我直接用一张复杂度对照表来说明白为什么比纯list靠谱核心操作listdequeset尾部追加蛇头O(1) 摊还O(1)O(1)头部弹出蛇尾O(n)数据搬移O(1)不支持判断坐标是否为蛇身O(n) 遍历O(n) 遍历O(1) 哈希保持蛇身先后顺序能能不能你可能会说我再用一个list加一个set不也一样吗确实可以但顺序容器用deque比用list更贴切因为蛇的移动模型就是“两头操作”而不是“按下标随机访问”。deque的取舍也很明确它牺牲了按下标访问的速度换来了两端操作的稳定高效。贪吃蛇恰好完全用不上“按下标取中间第几节”这种能力所以这个牺牲是值得的。两个容器同步维护是整套代码里唯一需要小心翼翼的地方。新增蛇头时deque.append和set.add要同时做移除蛇尾时deque.popleft和set.remove要同时做。只要有一次只改了deque忘了改set碰检测就会集体失灵。这个坑后面我会专门展开讲。2. 先把底层机制说透deque 与 set 是怎么工作的2.1 deque 的“双端”到底强在哪deque是 Python 标准库collections模块里的双端队列全称 double-ended queue。它的底层不是 Python 的普通列表那种连续数组而是一组固定大小的块通过指针连接起来类似“块状链表”。这种设计带来的直接好处是在两端插入或删除元素时不需要像list那样把所有元素整体搬家。如果你用过list的insert(0, item)应该能感受到那种别扭数据一多明显卡顿。deque就不会它提供append、appendleft、pop、popleft四个方法两边都能高效操作。对一个非空deque理论上还可以rotate循环移位比如滚动的历史记录、循环队列都能用它做。但这里必须多说一句deque不是超集它也有短板。因为不是连续内存按下标访问dq[500]需要沿着块链表走过去复杂度 O(n)。如果你需要频繁随机读取中间元素它反而不如list。所以贪吃蛇用deque能发挥最大优势是因为我们只在两头动手新蛇头从右边进来旧蛇尾从左边出去正好全部落在它的舒适区里。2.2 set不重复集合为什么查得快set可以理解成一个没有 value 的dict底层同样是哈希表。你要判断某个元素在不在里面Python 会先对这个元素做哈希拿到一个索引位置然后直接跳过去看这个槽位有没有值。平均情况下一步定位复杂度 O(1)。这就是它和列表遍历的本质区别列表要一个个比过去最坏情况走完整个表集合是“按图索骥”几乎不用遍历。不过哈希表有一个隐含约束存入集合的元素必须是可哈希的。具体到 Python 里tuple、str、int、frozenset都可以list、dict这种可变对象不行。所以你在定义蛇身坐标时必须用元组(x, y)千万别图省事用[x, y]。我见过不少新手在这里栽跟头一运行就抛TypeError: unhashable type: list。另外要注意set是无序的它只告诉你“某个东西在不在”不告诉你“它在第几个位置”。所以它不能单独表达蛇身顺序必须和deque配合。一个负责“排好队”一个负责“快速查人”。2.3 两个容器的分工与合作逻辑我用一个更生活化的类比来总结这种协作deque是蛇的整条骨骼一根接一根顺序明确第几节在哪儿都能从队列里推出来set是蛇的“领地地图”只要某个格子被蛇身占着地图上就画一个标记。蛇每移动一次骨骼的头部多一节、尾部少一节对应的地图上也要同步新增一个标记、抹掉一个标记。这两份数据结构描述的是同一个对象的不同侧面。一个回答“蛇的形态是什么”一个回答“哪个格子不能走”。你可能会想能不能只用set记录所有蛇身坐标然后根据蛇头和方向的逻辑直接算下一步不行因为你要知道“尾巴在哪”才能确定要不要把尾巴从set里删掉。如果你只知道坐标集合却不知道哪一节是尾巴那就没法移动了。所以顺序信息必须单独保存这就凸显了deque的价值。我在实际写这个项目时给自己的要求是“动一下两个容器必须一起动”。把deque的增删和set的增删写在相邻的两行代码里一眼就能看出是一对同步操作。这比把两个容器的操作分散到不同函数里安全得多。3. 手把手实现完整贪吃蛇代码拆解3.1 运行环境与项目结构为了让更多人可以零依赖复现我选择写一个纯终端版的贪吃蛇只用 Python 标准库里的collections、random、time、os不需要安装pygame。游戏逻辑封装成一个SnakeGame类本该由图形界面负责的“键盘输入”和“画面渲染”我用终端输入和清屏打印来模拟。这个设计有个好处你可以把注意力完全放在deque和set的配合上不需要被碰撞体、精灵、帧率这些游戏概念干扰。等你理解了核心逻辑再想去套pygame只是把render()和输入监听换掉而已游戏的状态转移代码一行都不用动。完整代码如下可以直接保存成snake.py运行import os import random import time from collections import deque WIDTH, HEIGHT 12, 10 class SnakeGame: def __init__(self): # 蛇身从左到右排列deque 最后一个元素是蛇头 self.snake deque([(6, 5), (5, 5), (4, 5)]) self.snake_set set(self.snake) self.score 0 self.food self._spawn_food() self.game_over False self.op {w: (0, -1), s: (0, 1), a: (-1, 0), d: (1, 0)} def _spawn_food(self): # 用空闲坐标列表生成食物避免蛇占满棋盘时死循环 free [ (x, y) for x in range(WIDTH) for y in range(HEIGHT) if (x, y) not in self.snake_set ] return random.choice(free) if free else None def step(self, direction): if direction not in self.op or self.game_over: return dx, dy self.op[direction] head self.snake[-1] new_head (head[0] dx, head[1] dy) # 撞墙检测 if not (0 new_head[0] WIDTH and 0 new_head[1] HEIGHT): self.game_over True return ate (new_head self.food) # 没吃到食物时先把尾巴移走让出格子 if not ate: tail self.snake.popleft() self.snake_set.remove(tail) # 撞自己检测此时尾巴已经让位不会误杀 if new_head in self.snake_set: self.game_over True return # 新蛇头入队 self.snake.append(new_head) self.snake_set.add(new_head) if ate: self.score 1 self.food self._spawn_food() if self.food is None: self.game_over True def render(self): os.system(cls if os.name nt else clear) body self.snake_set for y in range(HEIGHT): for x in range(WIDTH): if (x, y) self.food: print($, end ) elif (x, y) in body: print(*, end ) else: print(., end ) print() print(score:, self.score) def main(): game SnakeGame() while not game.game_over: game.render() game.step(input(wasd? ).strip().lower()) time.sleep(0.05) game.render() print(game over! score:, game.score) if __name__ __main__: main()3.2 初始化蛇身与食物初始化蛇身时有三个关键细节。第一我规定deque的最后一个元素是蛇头这是全代码的约定后面所有逻辑都围绕这个约定展开。第二直接用set(self.snake)把整个deque丢进去初始化snake_set因为deque是可迭代对象里面的元素都是元组这一步一行代码就完成了“地图登记”。第三食物不允许生成在蛇身上所以_spawn_food()用列表推导式筛出所有空闲格子再随机选一个。用free [(x, y) for x in range(WIDTH) for y in range(HEIGHT) if (x, y) not in self.snake_set]这个写法充分利用了set的 O(1) 查询。如果不用集合你得写一个双重循环逐个比对或者反复随机采样碰运气。现在棋盘是 12×10 只有 120 个格子性能差距不明显但省下的语义成本是实打实的一眼就能看出来“食物只出现在没被蛇占用的坐标里”。3.3 移动逻辑头入尾出与吃食物特判移动的核心只有两行算出新蛇头坐标然后决定“要不要把尾巴移走”。没吃到食物时先popleft把尾巴弹出去同步从set里删掉吃到食物时尾巴不动蛇直接长一节。这段代码的顺序非常有讲究。我习惯用右侧当蛇头所以每次给deque添加新头都用append移除旧尾都用popleft。如果你反过来约定左侧是蛇头那就要用appendleft和pop。方向本身无所谓关键是全局统一不然蛇身会变成“首尾倒置”的诡异状态。ate (new_head self.food)这个判断放在“移动尾巴”之前逻辑上很自然你先要看这一步有没有吃到食物才知道要不要执行“吐尾”动作。注意这里的食物坐标是明确的元组不存在模糊匹配。3.4 碰撞检测与 set 正确顺序碰撞检测分两段边界越界检测和自撞检测。边界检测很简单新蛇头的 x 或 y 一旦超出[0, WIDTH)和[0, HEIGHT)范围直接判负。自撞检测才是set发挥威力的地方。但这里有一个很多人会忽略的细节先删尾巴再判断new_head in self.snake_set。为什么因为如果蛇没有吃到食物当前这一步里尾巴那个格子会被释放掉蛇头追着尾巴走是允许的。如果你把判断放在删尾巴之前蛇只要想钻进尾巴原本占的那一格就会被误判成撞自己实际游戏体验会显得“判定过严”。反过来想吃到食物的时候尾巴不动那么新蛇头撞到尾巴的情况理论上不会发生因为食物不可能生成在蛇身上。所以先删后判这个顺序是最稳的。我在代码里用了一个注释专门标记这一点就是提醒自己也提醒看代码的人这个顺序不是随便写的。3.5 食物生成用集合差集生成食物最简单的写法是while True随机生成坐标直到random.choice不在蛇身里。蛇短的时候没问题可一旦蛇长到接近棋盘面积空闲格子越来越少随机命中率越来越低最极端的情况下蛇占满整个棋盘时这个while会永远循环下去程序直接卡死。所以我选择了“先筛出空闲坐标再随机选一个”的方案。这个方案的背后逻辑等价于取全集和蛇身集合的差集。100 多个格子时没有性能压力但代码路数是对的。如果你以后在更大的棋盘上做类似功能也可以考虑“随机采样若干次失败再全量扫描”的折中策略不过贪吃蛇这种规模完全用不上。3.6 终端渲染与主循环render()的清屏用了os.system(cls if os.name nt else clear)跨平台够用。绘制时双重循环遍历整个棋盘遇到food打印$遇到蛇身坐标打印*其余打印.。这里判断(x, y) in body时body直接指向self.snake_set所以底层又是 O(1) 的集合查询。主循环很简单每次input读一个方向然后game.step()推进一帧。因为input本身会阻塞等待所以time.sleep(0.05)在这里并不是控制游戏速度用的只是为了渲染稳定。如果你想做成真正自动前进的贪吃蛇可以把input替换成一个非阻塞的方向键读取或者设置定时器但游戏逻辑的核心代码不需要变。4. 写代码时绕不开的坑与排查实录4.1 蛇身少一节还是顺序写反了我调试这个项目时遇到的最典型问题是移动一步之后蛇身长度不对。比如明明没吃到食物蛇却从 5 节变成了 4 节再走几步直接“缩水”到看不出原样。排查后发现问题出在有人会把append和popleft的顺序搞反。比如先append(new_head)再popleft()如果这两个操作之间没有保护逻辑在某些分支里可能会多弹一次尾巴或者少弹一次。更隐蔽的错误是popleft弹出来的尾巴变量根本没被用到你却在snake_set.remove()里写了一个硬编码的坐标两个容器各删各的蛇身和地图立刻脱节。我的建议是在调试阶段给step()的入口和出口各加一条打印print(before:, len(self.snake), len(self.snake_set)) self.snake.append(new_head) self.snake_set.add(new_head) if not ate: tail self.snake.popleft() self.snake_set.remove(tail) print(after:, len(self.snake), len(self.snake_set))正常情况下没吃食物时len不变吃到食物时两个长度同时加一。看到长度不匹配就能快速定位是哪一行少了同步操作。4.2 头撞尾巴的“冤案”先删尾还是先判重这是我认为整个贪吃蛇项目里最值得讲的一个细节。当蛇笔直向前跑的时候玩家如果按了和当前移动方向垂直的方向蛇头会走向侧前方这时不会撞到自己。但有一种情况是蛇头下一步刚好落在“尾巴即将离开”的格子上。如果先判断new_head in self.snake_set再执行popleft由于尾巴还没离开集合这个判断会返回True游戏就会判定蛇撞上了自己的尾巴。可是从玩家的视角看尾巴这格明明已经在收缩了我不应该死。这就是典型误杀。正确顺序我在前面已经反复强调没吃到食物时先把尾巴从deque和set里移除让出这个格子再检查新蛇头在不在set里。这样一来追着尾巴移动就成了合法操作。这个细节能体现你对数据结构的理解深度面试聊项目时提一句会非常加分。4.3 set 忘了同步碰撞检测集体失灵相比顺序写反更让人头疼的是set和deque不同步导致的魔幻现象。表现是蛇明明只走了一小段却突然碰撞死亡或者本来安全的路径被判定为撞墙。我排查过的最离谱一次是移动了十几步之后snake_set里的元素数量比deque多出十几个。问题根源非常简单移出尾巴时只写了self.snake.popleft()忘了写self.snake_set.remove(tail)。于是set里残留了大量“幽灵坐标”这些坐标连起来形成了一堵隐形的墙蛇一头撞上去自然就死了。这个问题的防呆做法有两个一是写一个小的_sync辅助函数把增删操作打包成不可分割的两步二是在每次操作后加断言比如assert len(self.snake) len(self.snake_set)。在开发和调试阶段这种断言能帮你第一时间抓住不同步的瞬间。4.4 食物生成卡死随机采样算法选错前文提到用while True随机采样生成食物蛇占满棋盘时会死循环。实际项目里蛇占满整个棋盘的概率很低但报错却不只有死循环这一种。另一个常见问题是随机坐标重复生成太多次导致每吃一个食物游戏就卡一下。特别是当蛇身超过棋盘一半时这种卡顿已经肉眼可见。解决办法就是我代码里写的“候选列表 random.choice”。它会把所有空闲格子一次性筛出来然后均匀随机选一个不存在重复采样问题。如果棋盘特别大、空闲格子特别多你还可以优化成“随机试 N 次失败再全量扫描”这是更工程化的做法。但对于 12×10 的棋盘全量扫描总共也就 120 个格子的循环完全不需要再优化。4.5 换到 C 或 JavaScriptset 家族差异如果你把这个贪吃蛇项目迁移到 C第一个遇到的问题就是std::set和std::unordered_set怎么选。std::set是红黑树实现的有序查找 O(logn)而且std::pairint, int天然支持比较所以你可以直接用它存坐标。std::unordered_set是哈希表查找均摊 O(1)但标准库没有给pair提供哈希函数你需要自己写一个。这是很多 C 新手在 leetcode 上写题时卡住的点。如果你用的是 JavaScriptnew Set()底层也是哈希结构可以直接存对象引用但要注意两个坐标{x: 1, y: 2}即使内容相同也不是同一个对象直接用对象放进Set去重会失效。更稳妥的做法是存字符串1,2或者元组数组。|||这里不同语言的差异很大我列个速查表容器底层结构查找复杂度保持有序pair 坐标直接用Pythonset哈希表O(1) 均摊否tuple 直接可用Cstd::set红黑树O(logn)是pair 直接用Cstd::unordered_set哈希表O(1) 均摊否需要自定义哈希JavaScriptSet哈希表O(1) 均摊按插入序迭代对象注意引用所以如果你用 C 写贪吃蛇追求简单就直接std::setstd::pairint, int追求速度就自定义哈希后用std::unordered_set。这个话题在面试里经常被追问值得提前想清楚。4.6 性能与可扩展性杂谈最后聊点我实测下来的体感。蛇身在几十节的时候用list的in判断碰撞和用set几乎没有差别反正 O(n) 里 n 也就几十。但当我做一个性能测试把蛇长度拉长到 1000 节跑 10 万步移动时list版本每一步都要遍历蛇身累计时间明显上涨set版本却一直很平稳几乎感受不到蛇变长带来的影响。这个项目最大的价值就是让你直观感受到“算法复杂度不是纸上谈兵”。另外这个“顺序容器 哈希集合”的组合能延伸到很多场景。比如 BFS 迷宫寻路时用deque做队列、用set记录已访问节点滑动窗口问题用deque维护窗口范围去重需求用set做过滤。贪吃蛇只是这些思想的一个游戏化缩影。你把这个项目的逻辑吃透了以后看到类似“既要保持顺序、又要快速查重”的需求脑子里会立刻蹦出这个组合。如果你哪天在优化自己的蛇发现明明蛇很短却卡成 PPT先别急着怪pygame回去看一眼碰撞检测是不是还在用list的in。这是我能给后来者最直接的一句建议了。