贪吃蛇看起来是个小游戏,背后却藏着一个完整的算法问题。规则十秒就能讲清,但要让 AI 玩得好,就需要寻路、生存判断,甚至图论。本文按照智能程度逐步介绍几种方法,这也是我最初编写自动贪吃蛇时经历的过程。
相关的网格搜索方法(BFS、A* 和 DFS)已在网格寻路文章中通过动画地图介绍,这里重点讨论贪吃蛇特有的难点。
问题定义
蛇生活在网格上,每个时间步移动一格,不能反向撞进自己的身体。每吃到一份食物就增长一格,撞到墙壁或蛇身就会死亡。
两个观察让它成为了算法问题:
- 寻找食物是图上的最短路径问题,蛇身占据的格子视为障碍。
- 保持存活才是难点:贪心追逐食物可能让蛇进入无法逃离的角落。
第一级:只会贪心追逐食物
最简单的“智能”蛇会忽略身体,只依据曼哈顿距离朝食物移动:
def direction_to_food(head, food):
dx = food[0] - head[0]
dy = food[1] - head[1]
if abs(dx) > abs(dy):
return (1 if dx > 0 else -1), 0
return 0, (1 if dy > 0 else -1)
这种蛇通常很快就会死掉。先沿 x 再沿 y 调整方向,很容易撞上不断增长的身体。纯粹的贪心策略只优化下一步,无法兼顾整局游戏。
第二级:用 BFS 找到食物
广度优先搜索能让蛇找到绕开自己身体的路。它从蛇头开始,按距离逐层探索网格,直到找到食物。关键在于把蛇身所在的格子标记成墙壁,BFS 找到的最短路径自然就会绕开它们。
from collections import deque
def bfs_path(grid, start, food):
q = deque([start])
came_from = {start: None}
while q:
cur = q.popleft()
if cur == food:
break
for nb in neighbors(cur, grid): # 网格中已标记蛇身障碍
if nb not in came_from:
came_from[nb] = cur
q.append(nb)
if food not in came_from:
return None # 不存在到达食物的路径
return reconstruct_path(came_from, food)
neighbors 和 reconstruct_path 来自网格寻路文章。在贪吃蛇棋盘上,这已经是一个能工作的策略:将身体转为障碍网格,执行 bfs_path,每一步都随着身体位置变化重新计算朝向食物的路径。它最坏需要遍历整个网格,复杂度为 O(V+E),但在 16×10 的棋盘上足够使用。相比贪心策略,核心进步是它会绕过蛇身。
第三级:与自己的尾巴周旋
单纯使用 BFS 也会死,而且不一定是找不到食物。最短路径可能把蛇引入一个陷阱:
...S 蛇沿着最短路径前进,
..#. 但食物位于一个死角。
.#F.
.... 进入之后就再也无法离开。
可以按以下顺序逐步改进:
- 行动前检查能否到达尾巴。 吃到食物之后蛇会变长。如果模拟走完路径后,蛇头无法再到达尾巴,就应当拒绝这条危险路径。
- 加入前瞻启发式。 例如比较候选格子到最远可达食物的距离,尽量保留后续选择。
- 食物不可达时追逐尾巴。 暂时无法到达食物,就朝尾巴移动,等待尾部前进、腾出新的通道。
def next_direction(snake, food, grid):
to_food = bfs_path(grid, snake[0], food)
if to_food and len(to_food) > 1:
return to_food[1] - snake[0] # 朝食物方向移动的示意
to_tail = bfs_path(grid, snake[0], snake[-1])
return to_tail[1] - snake[0] if to_tail else pick_any_safe(grid, snake[0])
网格搜索工具在这里可以重复使用:寻找食物的 bfs_path,同样能用来寻找尾巴;希望减少展开时,也可以考虑 A*。
第四级:沿哈密顿回路稳定存活
如果希望蛇在棋盘填满之前始终不撞上自己,可以使用哈密顿回路:一条恰好访问每个格子一次,并最终回到起点的闭合路径。
阅读哈密顿路径问题的介绍,想象蛇一直沿着一条覆盖全棋盘的回路前进。只要初始蛇身按顺序位于回路上,沿回路移动就不会在前方制造阻挡。
# 对满足条件的 W × H 网格,可以构造哈密顿回路;
# 下方逐行往返的遍历仅作示意,还需处理首尾连接。
def hamilton_cycle(w, h):
path = []
for y in range(h):
row = range(w) if y % 2 == 0 else range(w - 1, -1, -1)
path += [(x, y) for x in row]
return path # 需要确认最后一格与第一格相邻,才能闭合回路
需要注意,上面的示意代码展示的是逐行往返遍历;实际使用时,必须确认最后一个格子与第一个格子相邻,才能构成真正的回路。
代价是速度:沿着整条回路爬行,即使食物就在蛇头旁边,也可能需要绕很远。更完善的 AI 会组合这些方法:平时沿哈密顿回路前进,只有在保持剩余路径有效且不破坏蛇身顺序时,才用 A* 等方法抄近路。
策略比较
| 策略 | 到食物的最短路径 | 能绕过身体 | 始终存活 | 开销 |
|---|---|---|---|---|
| 贪心 | 否 | 否 | 否 | O(1) |
| BFS | 是 | 是 | 否 | O(V+E) |
| 追尾 | 视安全检查结果而定 | 是 | 通常能改善存活 | 两次搜索及可达性检查 |
| 哈密顿回路 | 否 | 是 | 满足回路条件时可以 | 构造回路 O(W·H) |
BFS 是大多数贪吃蛇 AI 的起点,追尾策略补充生存能力,哈密顿回路则用路径效率换取存活保证。A* 可以替代部分 BFS 搜索,详见网格寻路文章。
交互实验:看蛇动起来
点击 ▶ 开始,观察 BFS 如何驱动贪吃蛇。它会选择下一步蛇头的位置,并以约 0.25 秒的间隔更新画面,直到陷入死路、填满棋盘,或者你点击停止。亮绿色表示蛇头、深绿色表示蛇身、红色表示食物,具体见下方图例。
让贪吃蛇动起来
PythonYour output will appear here.
接下来可以探索什么
经典算法构成了解决问题的基础,而贪吃蛇也是强化学习的合适入门题目:把游戏网格作为观测,让 DQN 学习如何生存。对小型棋盘和合适的状态表示,笔记本电脑也能进行训练实验。
从 BFS 开始,加入尾巴可达性检查,再尝试有效的哈密顿回路和安全捷径。四种策略围绕同一个游戏展开,它们共同依赖的寻路工具都可以在网格搜索中找到。