用set和deque重构贪吃蛇：碰撞检测从O(n)到O(1)的优化实践

做贪吃蛇这个经典小游戏时很多人会顺手用list存蛇身之后用for循环判断蛇头是否撞到自己。蛇短的时候没感觉等蛇长到几十上百格每帧都遍历整个蛇身pygame的帧率就会肉眼可见地往下掉。后来我把项目里的数据结构换成set加deque碰撞判断从O(n)变成O(1)蛇身移动也变成了简单的头尾操作代码量反而缩了不少。这篇文章就把我个人使用set和deque实现贪吃蛇的完整过程写出来包括为什么选这两个数据结构、核心逻辑怎么组织、实际踩过的坑和排查思路。适合刚学完Python基础、想用项目练手的人也适合已经在用pygame写小游戏但觉得蛇身移动和碰撞判断写得很别扭的读者。1. 贪吃蛇项目的整体思路与数据结构选型1.1 贪吃蛇到底需要处理哪些核心问题贪吃蛇看起来简单拆开看就三个核心问题蛇怎么移动、蛇怎么增长、怎么判断游戏结束。这三个问题背后对应着不同的数据结构需求。蛇的移动本质上像一个队列蛇头往前走一步蛇尾就要丢掉一节。如果没吃到食物新蛇头加进来老蛇尾弹出去蛇身长度不变吃到食物时只加新蛇头不弹老蛇尾整体长度加一。这种“先进先出”的行为天生就是deque双端队列的工作。碰撞判断则是另一件事。蛇头撞墙需要和地图边界比较蛇头撞到自己需要快速知道新蛇头的位置是否已经存在于当前蛇身。这里最烦人的是“蛇身是否包含某个坐标”这个查询如果每次都在整个蛇身列表里遍历数据量一大就卡顿。于是需要一个能快速查“某样东西在不在集合里”的数据结构这就是set。还有一个容易被忽略的需求蛇不能反向移动。比如当前向右走时用户按左键不应该生效。这个逻辑和数据结构无关但决定了方向的更新方式。整体设计时应该把“方向控制”“坐标更新”“碰撞检查”“食物生成”拆开每个环节都有自己的职责数据结构的选择才不会变成一锅粥。1.2 为什么偏偏是set和deque而不是list很多入门教程用list写贪吃蛇代码也能跑但list在特定操作上有性能短板。list的头部插入和头部删除都是O(n)操作因为每次都要把后面所有元素往前挪list的成员判断也是O(n)因为在找到之前可能要遍历一整条蛇。deque在头部和尾部的增删都是O(1)这是由双向链表或环形缓冲实现的。贪吃蛇每移动一帧恰好需要一次头部插入和一次尾部删除deque和这个场景完全匹配。set的成员判断是O(1)平均复杂度底层是哈希表可以看成一本自动分类的字典只存“有什么”不存“有几个”。下面这张表把我当时的选型逻辑列得很清楚操作listdequeset蛇身头部加一节慢插入后元素整体后移快O(1)不适用蛇尾减一节慢pop(0)整体前移快O(1)不适用判断某坐标是否在蛇身慢需要遍历慢需要遍历快O(1)按位置顺序输出蛇身快天然顺序快天然顺序不行无序蛇身坐标唯一性需要额外维护需要额外维护天然保证从这里能看出单独用list能实现但两个高频操作都是劣势单独用deque能解决移动但碰撞判断还是遍历治标不治本单独用set能实现碰撞判断但没办法知道蛇头蛇尾的顺序关系。所以正确答案是组合使用deque负责顺序和移动set负责快速判断蛇身坐标是否存在。至于为什么不用dict因为我们要存的只是“坐标这个键存在不存在”不需要额外的值。如果硬要用dict等于杀鸡用牛刀而且dict的key其实也是通过哈希表实现的本质和set一样但多存了一份无用的value占用更多内存。2. 用set管理蛇身状态碰撞检测不再慢2.1 set里到底存什么set存的是元组不是列表。在Python里set要求里面的元素必须可哈希简单理解就是这个值能换算成一个固定编号用来快速查找。整数、字符串、元组都可以列表不行因为列表可变哈希值不稳定。我当时定义蛇身坐标时是这样的snake_set {(3, 5), (3, 4), (3, 3)}注意里面每个元素都是元组比如(3, 5)表示第3行第5列。之所以用元组是因为它不可变才能放进set。同一个坐标在set里只会出现一次这正好符合蛇身“每个格子只占一次”的特性。有了这个set判断蛇头是否撞到自己的代码就非常短new_head (new_x, new_y) if new_head in snake_set: # 撞到自己游戏结束 game_over True不需要写循环不需要遍历蛇身每一个坐标。这就是set最核心的价值。更重要的是这个判断会随着蛇身变长而保持稳定不会因为蛇长大了就变慢。2.2 使用set时的三个关键坑坑一直接给set放list会报错。很多初学者会把坐标写成[3, 5]然后snake_set.add([3, 5])立刻得到TypeError: unhashable type: list。这不是set的问题是可哈希性要求。解决办法很统一所有坐标一律用元组表示。坑二set和deque不同步。这是个隐蔽bug。deque里的蛇身顺序更新了但set忘记同步或者反过来set更新了deque没更新游戏里会出现明明蛇身没碰到自己却判定死亡或者穿过了自己却没有任何反应。我后来定了一条铁律所有对蛇身的修改必须同时操作deque和set两步写在同一个函数里不许分开。坑三删除set元素前一定要确认存在。直接snake_set.remove((1, 1))如果元素不存在会抛KeyError。在贪吃蛇里尾部弹出的坐标理论上一定存在于set中但如果有逻辑bug删除时就会炸。稳妥写法是if tail in snake_set: snake_set.remove(tail)或者用discard方法因为discard不存在时不报错。这里我要提醒一句使用discard虽然安全但会悄悄掩盖同步bug所以我在正常逻辑里坚持用remove只在调试阶段用discard。set还有一个数学上的优势它可以用来快速生成随机食物位置。玩家吃掉食物后新的食物不能出现在蛇身上。如果用list每次生成食物都要if food in snake_list遍历一次用set只需要while food in snake_set循环次数极少。这个判断同样受益于O(1)的成员查询。3. 用deque管理蛇身轨迹移动和增长的核心3.1 deque如何模拟蛇的爬行deque是双端队列两端都能高效进出的容器。在Python里它位于collections模块平时用的list做不到首尾都是O(1)。贪吃蛇的移动完全可以映射成deque的操作序列向右移动一格本质是蛇头从(3, 3)走到(3, 4)蛇尾从(1, 1)消失。在deque上就是snake deque([(3, 3), (3, 2), (3, 1)]) snake.appendleft(new_head) # 新头进来 snake.pop() # 旧尾出去这比list干净很多。如果用list最直观的方式是insert(0, new_head)和pop()但insert(0, ...)会导致整个列表后移蛇长500时每帧都要把500个元素整体挪一遍完全没必要。有人可能说那我把蛇尾放在列表开头、蛇头放在列表结尾这样尾部删除就变pop()了但头部插入又变成append到末尾。不管怎么摆list总有一端操作是O(n)。deque不存在这个烦恼。3.2 移动、吃食物、碰撞的完整逻辑我把每一帧更新拆成了四个阶段。第一阶段根据当前方向算出新蛇头位置。第二阶段用set判断新蛇头是否和蛇身重叠用边界判断是否撞墙。第三阶段判断新蛇头是否和食物重叠决定要不要长一节。第四阶段统一更新deque和set。核心代码长这样from collections import deque DIRS { UP: (0, -1), DOWN: (0, 1), LEFT: (-1, 0), RIGHT: (1, 0), } def next_head(head, direction): dx, dy DIRS[direction] return (head[0] dx, head[1] dy) def move_snake(snake, snake_set, new_head, food): # 1. 先处理吃食物 if new_head food: snake.appendleft(new_head) snake_set.add(new_head) return True # 吃到食物需要重新生成食物 # 2. 没吃到食物蛇尾弹出 tail snake.pop() snake_set.remove(tail) # 3. 新蛇头加入 snake.appendleft(new_head) snake_set.add(new_head) return False这里有个细节要说明我是先popleft还是先appendleft顺序有没有影响其实没有真正有影响的是pop出的那个尾部坐标必须和set里删掉的一致。所以强烈建议把tail snake.pop()和snake_set.remove(tail)写成连续代码。我遇到过一次因为中间插了一行日志导致顺序没同步结果蛇身越走越长set越来越小最后碰撞判断完全失效。关于maxlen参数再说一句。deque可以设置deque(maxlen5)满了之后自动弹出旧元素。看上去很适合贪吃蛇但我不建议在游戏里使用maxlen因为自动弹出不会告诉你弹出的是谁你的set无法同步更新。除非你手动监听每次操作否则会陷入set和deque对不上的泥潭。手动pop的好处是你能拿到被弹出的tail方便同步。4. 完整可运行的Demo实现4.1 终端版贪吃蛇可以直接跑的最小实现为了让你看到set和deque在真实项目里的配合我写了一个不依赖pygame的终端版贪吃蛇。它通过键盘WASD控制方向每次输入后刷一帧画面。这个版本的重点是展示逻辑结构不是做一个精美游戏所以地图简单没有实时按键监听。import random import os from collections import deque WIDTH, HEIGHT 10, 10 DIRS { w: (0, -1), s: (0, 1), a: (-1, 0), d: (1, 0), } OPPOSITE {w: s, s: w, a: d, d: a} def create_food(snake_set): while True: food (random.randrange(WIDTH), random.randrange(HEIGHT)) if food not in snake_set: return food def render(snake, food): os.system(cls if os.name nt else clear) board [[. for _ in range(WIDTH)] for _ in range(HEIGHT)] board[food[1]][food[0]] * for x, y in snake: board[y][x] O board[snake[0][1]][snake[0][0]] for row in board: print( .join(row)) print(得分:, len(snake) - 3) def main(): snake deque([(2, 0), (1, 0), (0, 0)]) snake_set set(snake) food create_food(snake_set) direction d score 0 while True: render(snake, food) move input(WASD移动(Q退出): ).strip().lower() if move q: break if move not in DIRS: continue if move OPPOSITE[direction]: print(不能反向走) continue direction move dx, dy DIRS[direction] head snake[0] new_head (head[0] dx, head[1] dy) if not (0 new_head[0] WIDTH and 0 new_head[1] HEIGHT): print(撞墙了游戏结束) break if new_head in snake_set: print(撞到自己了游戏结束) break if new_head food: snake.appendleft(new_head) snake_set.add(new_head) score 1 food create_food(snake_set) else: tail snake.pop() snake_set.remove(tail) snake.appendleft(new_head) snake_set.add(new_head) print(最终得分:, score) if __name__ __main__: main()这段代码我实际跑过逻辑是完整的。你可以把WIDTH和HEIGHT调大体验不同难度。注意看snake_set set(snake)这里直接把deque转换成了set因为deque里的元素都是元组可以直接哈希。还有一点值得体会while True生成食物时如果蛇身占满了整个地图这个循环会死循环。严格的项目里应该加一个蛇身长度是否等于地图面积的判断。这个小Demo没加但我建议你加上属于一个隐蔽的边界漏洞。4.2 如果把核心逻辑迁移到pygame实际项目里我用了pygame做图形界面但核心逻辑和上面完全一致。pygame里只是多了键盘事件循环、定时器和画面绘制。最关键的是pygame的蛇身更新逻辑依然是算新头判断碰撞检查食物更新deque和set。pygame版本的事件部分大概是这样的结构for event in pygame.event.get(): if event.type pygame.KEYDOWN: if event.key pygame.K_UP and direction ! DOWN: direction UP ...方向判断要放在事件处理里但移动计算要放在下一次定时触发里。这里有一件容易搞错的事情方向不能直接改成相反的否则蛇头会穿进自己身体。所以要加direction ! DOWN这类限制。终端版本里我用了OPPOSITE字典来实现同样的效果。图形界面版的碰撞判断、蛇身更新和终端版一字不差。这也是数据结构选型的意义一旦逻辑层设计好了换界面只是换IO层。set和deque的组合是逻辑层的稳定支点。5. 常见问题与排查技巧实录5.1 TypeError: unhashable type: list十个人用set做贪吃蛇有八个会撞到这个报错。原因就是往set里放了list。比如从pygame的矩形对象取值后新手习惯写成[rect.x, rect.y]。解决办法不是改写法而是从一开始就定义“所有坐标都是元组”的约定。我自己的习惯是写一个辅助函数def to_tuple(pos): return (pos[0], pos[1])这样从外部接口拿到的list或pygame坐标都在入口处转成tuple保证set内部永远只有元组。5.2 deque和set数据不同步这个bug隐藏得很深表现也千奇百怪。有时候蛇明明没有碰到自己却突然死亡有时候蛇穿过自己的身体却没有任何反应。前者是set里有残留元素导致误判后者是set里漏了新头导致漏判断。我排查这类问题的经验是在每次移动后打印len(snake)和len(snake_set)正常情况下两者应该相等。如果不相等问题一定出在某一次移动中蛇尾弹出和set删除没有对齐。这时候可以加一个断言assert len(snake) len(snake_set)在性能要求不高的开发期断言能快速暴露问题。正式跑游戏时可以解开断言但逻辑上你不应该让断言失败。5.3 误用deque(maxlen)导致set不同步有人看到deque的maxlen觉得很酷以为贪吃蛇天然适合自动淘汰旧尾巴。其实不是。maxlen在元素超出时静默丢弃旧元素但你的set不知道丢的是哪一个结果就是set越来越大蛇身坐标一直累积最终碰撞判断把不该撞的地方也判定为撞上。我的建议是全手工操作。吞掉尾部时明确拿到tail明确从set里删掉每一步都在掌控之中。自动化越黑盒子调试越痛苦。5.4 蛇身反向穿入自己如果没有反方向限制蛇向右走时按左蛇头直接往蛇身第二段的位置走一帧之内就自我碰撞。这个不涉及set和deque但属于做贪吃蛇必踩的坑。需要在方向更新时判断def is_opposite(d1, d2): return (d1 UP and d2 DOWN) or \ (d1 DOWN and d2 UP) or \ (d1 LEFT and d2 RIGHT) or \ (d1 RIGHT and d2 LEFT)有时候玩家快速按两个键比如一帧内先按上再按左因为游戏循环处理事件的顺序最后方向可能从右变成上再变成左。pygame里如果不限制事件处理频率蛇会瞬间改变多个方向出现“转头”穿越。建议加一个简单的事件排队每帧只处理一个有效方向。下面的速查表是我整理的真实排错记录现象可能原因解决方案TypeError: unhashable typeset里放了list坐标统一转元组长度不同deque和set不同步每次移动后断言两者len相等蛇穿体不判死set漏加新蛇头所有对deque的append都同步add还没吃到食物就长一节写移动逻辑时忘写else分支检查是否同时执行了appendleft和pop生成食物时死循环蛇身占满地图先判断len(snake)是否等于地图格数按相反方向导致瞬间死亡没有阻止反向操作在方向更新处拦截反向5.5 性能实测我在一台普通笔记本上做过简单测试蛇身长度1000时使用list的new_head in snake_list大约需要十几微秒到几十微秒而使用set只需要不到一微秒。单看微秒级差异似乎不大但游戏每帧还要做碰撞判断、食物生成判断如果网格很大、蛇很长累积效应就能感觉到。贪吃蛇的规模一般不至于让list崩掉但set的写法更符合逻辑直觉写起来也更简洁。我实际感受最明显的是代码可读性。if new_head in snake_set这个句子读起来就像在问“新头在不在蛇身集合里”而if new_head in snake在list用法里虽然也能写但内部语义却要遍历。明明是线性查找表面上却像是O(1)这种语义和性能不符容易误导人。set让性能表现和代码读法一致非常舒服。最后分享一点我的个人习惯做了几次贪吃蛇之后我对数据结构的理解从“能跑就行”变成了“先想清楚操作再选容器”。贪吃蛇这个项目最好的地方在于它逼着你同时思考顺序维护和快速查找这两个需求而set和deque的组合正好提供了教科书级别的分工。我后来在写其他项目时只要遇到“需要保持顺序又要频繁判断成员是否存在”的场景第一反应就是用deque加set组合这个思路在很多缓存系统、聊天记录管理里都能复用。最后再给一个小建议如果你手头已经有了一个用list写的贪吃蛇不要急于全部重写先把碰撞判断那一行从遍历改成in snake_set再逐步把deque换进去。一个小改动就能看到清晰的效果这也是我当年觉得最有成就感的瞬间。