前言
前两天看到一张很有意思的图：还是大家熟悉的贪吃蛇，但它不是按部就班地找食物，而是像有思考能力一样，把矩形区域一点点填满。那种效果确实很上头，也很容易让人想追问一句：这到底是怎么写出来的？
如果只是做一个普通版贪吃蛇，思路并不复杂；真正有意思的地方，是让它'活得久一点'，甚至在局部看起来像是在主动规划路线。于是，这篇文章就从一个能跑的基础版本出发，慢慢把它推到一个更像样的 AI 版本。
先把游戏跑起来
做这类题目，我一向不建议一上来就盯着'最优解'。先让程序动起来，后面的优化才有意义。贪吃蛇本身并不难，控制台版本的实现通常也就几十到一百来行，Python 写起来尤其顺手。
这里先把问题简化成一个最基础的任务：
在一个矩形区域内，蛇头需要在不撞到自己和墙壁的前提下，找到一条能到达食物的路。路径不一定最优，但要可行。
这时可以先忽略'蛇会越来越长'这个现实，只把它看成一个从起点走到终点、同时避开障碍物的寻路问题。可选的方法很多，BFS、DFS、A* 都能用。为了先把系统跑通，我选了最直接的 BFS。
BFS 的做法很朴素：从蛇头出发，把四个方向能走到的格子不断加入队列，直到找到食物。过程中有几件事不能漏掉：
- 访问过的格子不要重复访问
- 每个格子都要记录父节点，方便回溯出路径
- 蛇身和墙壁都视为不可通行
找到食物之后，蛇只要沿着回溯出的路径移动就行。这个版本写完，贪吃蛇已经能比较正常地跑起来了。我当时用的是 curses，直接在终端里画图，虽然界面朴素，但足够说明问题。
不过，问题也很快暴露出来：如果始终只用 BFS，蛇会非常短视。它只会盯着眼前的食物，一旦局面稍微复杂一点，就容易把自己逼进死角。更准确地说，它只知道'现在能不能吃'，却完全不关心'吃完以后还能不能活'。
BFS 之外，再给它一点'缓冲时间'
既然单靠 BFS 不够用，那就得给蛇补一条策略。我写了一个 Wander 函数，名字也很直白：当 BFS 暂时找不到合适路线时，让蛇先别急着追食物，而是在空白区域里绕一绕，给局面多一点变化。
这个函数可以有不同写法。我最开始试过一种比较随意的版本：在可行区域里随机选一个方向，再随机走几步。这样确实能让蛇多活一阵子，但随机性太强，走着走着就很容易把自己送进死胡同。没有回滚机制的时候，随机走法本质上是在赌。
后来我换成了更'规矩'的版本：让蛇在 BFS 无解时，沿着空白区域做 S 形移动，步数也是随机给定的。比纯随机要稳一些，但本质问题没变——它还是只是在拖时间，而不是解决问题。
更关键的是，蛇的策略里有个很致命的点：
while 没有按下 ESC 键:
if 蛇和食物之间有路径:
直接去吃
else:
Wander 一段时间
看起来很合理，实际上不够聪明。因为它只关心'现在能不能到达食物'，却没有判断'吃掉这颗食物以后，局面是不是还安全'。有些时候，食物就在眼前，但一口吃下去，蛇头就把自己封死了。
所以，真正要解决的，不是'能不能吃到'，而是'吃完以后还能不能继续活'。
更稳一点：先判断安全性
把问题想深一点之后，思路就清楚了。
蛇当前看到食物时，不应该立刻冲过去，而是先模拟一下：如果现在吃掉它，新的蛇身布局会不会把自己困住？如果不会，才真正执行这一步；如果会，就继续等更合适的机会。
这也是我后来引入'虚拟蛇'的原因。它不负责渲染，只负责在内存里模拟一次走法，判断结果是否安全。只有模拟通过，真实的蛇才会行动。
那怎么定义'安全'呢？这里我采用的判断标准很直观：
如果蛇吃完食物后，蛇头和蛇尾之间仍然存在一条路径，那么我就认为这个布局是安全的。
