← Back to the notebookVEINSURE / WRITING

Technical Articles

教贪吃蛇思考:游戏中的经典算法

用 BFS 寻找食物,用追尾策略脱离困境,再用哈密顿回路实现稳定存活,并通过实时交互动画观察贪吃蛇的行动。

贪吃蛇看起来是个小游戏,背后却藏着一个完整的算法问题。规则十秒就能讲清,但要让 AI 玩得好,就需要寻路、生存判断,甚至图论。本文按照智能程度逐步介绍几种方法,这也是我最初编写自动贪吃蛇时经历的过程。

相关的网格搜索方法(BFS、A* 和 DFS)已在网格寻路文章中通过动画地图介绍,这里重点讨论贪吃蛇特有的难点。

问题定义

蛇生活在网格上,每个时间步移动一格,不能反向撞进自己的身体。每吃到一份食物就增长一格,撞到墙壁或蛇身就会死亡。

两个观察让它成为了算法问题:

  1. 寻找食物是图上的最短路径问题,蛇身占据的格子视为障碍。
  2. 保持存活才是难点:贪心追逐食物可能让蛇进入无法逃离的角落。

第一级:只会贪心追逐食物

最简单的“智能”蛇会忽略身体,只依据曼哈顿距离朝食物移动:

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.
....      进入之后就再也无法离开。

可以按以下顺序逐步改进:

  1. 行动前检查能否到达尾巴。 吃到食物之后蛇会变长。如果模拟走完路径后,蛇头无法再到达尾巴,就应当拒绝这条危险路径。
  2. 加入前瞻启发式。 例如比较候选格子到最远可达食物的距离,尽量保留后续选择。
  3. 食物不可达时追逐尾巴。 暂时无法到达食物,就朝尾巴移动,等待尾部前进、腾出新的通道。
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 秒的间隔更新画面,直到陷入死路、填满棋盘,或者你点击停止。亮绿色表示蛇头、深绿色表示蛇身、红色表示食物,具体见下方图例。

让贪吃蛇动起来

Python
算法
游戏
render
OUTPUTLoading editor…

Your output will appear here.

Runs locally in your browser · Pyodide 0.26.4 · 10s execution limit / 30s for visualizations · 64 KiB output

接下来可以探索什么

经典算法构成了解决问题的基础,而贪吃蛇也是强化学习的合适入门题目:把游戏网格作为观测,让 DQN 学习如何生存。对小型棋盘和合适的状态表示,笔记本电脑也能进行训练实验。

从 BFS 开始,加入尾巴可达性检查,再尝试有效的哈密顿回路和安全捷径。四种策略围绕同一个游戏展开,它们共同依赖的寻路工具都可以在网格搜索中找到。

END OF NOTEBack to top ↑

Search the notebook

Search published writing. Use ↑ ↓ to select, Enter to open.