上次我们聊到用 Java 写一条能自动吃食物的贪吃蛇，核心引进了 A* 寻路。不过说实话，第一版做出来之后，它只是“能吃到”，离“吃满全屏”还差得远。因为这条蛇到了中后期，时常会把自己绕进死路，或者为了追一个食物把自己围死。所以这次我重新把整个策略层梳理了一遍，真正让这条蛇能一路吃到屏幕里塞不下的程度。这篇就把我在第二版里做的所有设计、代码细节和踩过的坑一次性交代清楚。
如果你正打算写一个带自动寻路的贪吃蛇，或者是面试前想弄明白 A* 在具体实战里怎么落地，这篇文章应该能帮你省下不少试错的时间。
1. 整体设计：为什么 A* 能吃到，但不一定能吃满
1.1 第一版留下的三大问题
第一版里，蛇每到一步就用 A* 算一条到食物的最短路径，然后照着走。单看每一步好像都很合理，但合在一起就暴露了几个致命问题。
第一个问题是只认最短路径，不认活路。蛇在比较短的时候问题不大，因为身躯小，绕来绕去都有空间。可一旦蛇身超过屏幕的一半，很多食物的方向就只有一两条很窄的通道，而这些通道往往被蛇自己堵住了。A* 只负责给你算出最短路径，它不关心你把那条路走完之后，蛇头是不是就被自己的身体包围了。结果就是蛇经常高高兴兴追到一个食物，回头一看，尾巴和身子把唯一出口堵死了。
第二个问题是食物坐标让蛇顾此失彼。如果食物出现在蛇身围成的闭合区域里，A* 依然能算出路径进去，但进去容易出来难。蛇为了吃这个食物，可能让整个身体团的更紧，最后变成一座“蛇形孤岛”，四周全是自己。
第三个问题是没有考虑蛇尾巴的移动。贪吃蛇和静态迷宫有一个本质区别，它的障碍物是会动的，尤其是尾巴。你按某一帧的蛇身布局算出的路径，走几帧之后可能已经被自己的身体挡住。A* 是一个静态规划算法，它天然不擅长处理这种动态环境。
所以，第二版的第一件事，就是不再把 A* 当“一切问题”的方案，而是把它放进一个更大的策略框架里，让 A* 只负责它擅长的事：短距离寻路。至于“这条路能不能走”“下一步该不该追这个食物”，交给上面的策略层判断。
1.2 决策层 + 执行层的分层架构
我最终把整个自动控制系统分成了三层。
决策层负责回答“接下来要干什么”。它每 0.2 秒左右做一次全局判断：当前有没有安全的食物可以去追？如果没有，是去追尾巴给自己“解围”，还是开启沿着安全区域巡游的模式？这一层决定了蛇的大方向。
规划层负责回答“怎么走到目标”。当决策层定了目标（比如某一个食物坐标、尾巴坐标、或者巡游路线的下一个转折点），规划层才祭出 A* 或者简化 BFS，把从蛇头到目标的路径算出来。注意，这里的 A* 不再需要从蛇头算到屏幕另一端，而是在一个比较合适的局部范围内工作，而且每次算完只取前几步执行，然后重新规划。
执行层是游戏主循环里最底层的部分。它拿到规划层给出的方向序列，每帧移动一格，更新地图，然后触发决策层的下一次判断。执行层还负责防止由于某种边界条件导致蛇原地不动或者撞墙。
这个分层的核心思想其实特别朴素：把“长期策略”和“短期路径”解耦。只要策略层不错得太离谱，A* 就算偶尔算得不是最优，也不会导致蛇立刻死掉。整个系统的稳定性，是靠层与层之间的缓冲换来的。这也是做机器人路径规划时常用的一套思路。
1.3 为什么要放弃“全局一条路走到底”
有人可能会问，既然都上了 A*，为什么不一次性算一条能吃满全屏的哈密尔顿回路？这样蛇只要沿着环走一圈，不就正好铺满屏幕吗？
理论上那是最稳的方案，但实现起来有两个问题。哈密尔顿回路的构造比较复杂，而且贪吃蛇每次吃完食物会变长，屏幕布局会变化，你算好的一条大环，可能吃了几口后就对不上了。动态场景下，维护一条全局环路的代价远高于“局部规划 + 策略切换”。所以我在第二版里用的是一种折衷思路：贪心 + 可达性判断 + 逃生策略。等哪天真想挑战极限，再回头研究哈密尔顿回路也不迟。
2. A* 寻路核心实现细节
2.1 Java 实现 A* 的节点定义与估价函数
我先把第一版用过的 A* 重新实现了一遍，这次更注重通用性和可调试性。节点设计如下：
public class Node implements Comparable<Node> { public int x, y; public int g; // 起点到当前节点的实际代价 public int h; // 当前节点到目标节点的估计代价 public int f; // 总代价 f = g + h public Node parent; public Node(int x, int y) { this.x = x; this.y = y; } @Override public int compareTo(Node other) { return Integer.compare(this.f, other.f); } }这里f = g + h，其中h我选的是曼哈顿距离。因为贪吃蛇只能上下左右走，不能斜着走，曼哈顿距离是比欧氏距离更贴合实际的启发函数，而且算起来非常快。
private int manhattan(int x1, int y1, int x2, int y2) { return Math.abs(x1 - x2) + Math.abs(y1 - y2); }有人会担心曼哈顿距离是不是太简单，导致 A* 搜索范围过大。其实在这个场景里，地图最多是几十乘几十的格子，曼哈顿距离已经足够高效，而且它保证启发函数不会高估实际代价，所以 A* 一定能找到最短路径。用更复杂的启发函数，收益几乎可以忽略不计。
2.2 开启列表、关闭列表与路径重构
我习惯用PriorityQueue当开启列表，用HashMap记录节点状态，避免反复遍历。
public List<Node> findPath(int startX, int startY, int targetX, int targetY, boolean[][] obstacles) { PriorityQueue<Node> openList = new PriorityQueue<>(); Map<String, Node> allNodes = new HashMap<>(); Set<String> closedList = new HashSet<>(); Node start = new Node(startX, startY); start.g = 0; start.h = manhattan(startX, startY, targetX, targetY); start.f = start.h; openList.offer(start); allNodes.put(startX + "," + startY, start); int[] dx = {0, 0, -1, 1}; int[] dy = {-1, 1, 0, 0}; while (!openList.isEmpty()) { Node current = openList.poll(); if (current.x == targetX && current.y == targetY) { return buildPath(current); } closedList.add(current.x + "," + current.y); for (int i = 0; i < 4; i++) { int nx = current.x + dx[i]; int ny = current.y + dy[i]; if (!isValid(nx, ny, obstacles) || closedList.contains(nx + "," + ny)) { continue; } int newG = current.g + 1; Node next = allNodes.get(nx + "," + ny); if (next == null) { next = new Node(nx, ny); next.g = newG; next.h = manhattan(nx, ny, targetX, targetY); next.f = next.g + next.h; next.parent = current; openList.offer(next); allNodes.put(nx + "," + ny, next); } else if (newG < next.g) { next.g = newG; next.f = next.g + next.h; next.parent = current; // 重新入队 openList.remove(next); openList.offer(next); } } } return null; // 没有可达路径 }有几个细节值得注意：
第一，PriorityQueue在节点 cost 变化时不支持原地更新，必须先移除再重新插入。不然堆序会被破坏，A* 会变慢甚至出错。
第二，我用HashMap<String, Node>记录了每个坐标对应的节点对象，这样在“更新更短路径”的时候能直接拿到旧节点，而不用重新 new 一个。这种实现比每次在队列里线性查找快得多。
第三，buildPath是从目标节点不断向上找parent，最后翻转列表。别漏了翻转这一步，不然路径是反的。
2.3 让 A* 适配贪吃蛇的移动规则
游戏里的障碍物不是静态的，需要把当前蛇身的所有坐标都标成obstacles = true。这里有个很容易踩的坑：蛇尾巴那一格是不是障碍物？
如果蛇即将移动，尾巴会先被释放，腾出新的空间。但如果你简单地“移动一格后立刻刷新障碍物”，那就和实际运行逻辑错位了。我的做法是：规划路径的时候，先把蛇尾巴那一格视为空格，同时把蛇头前方会撞到的蛇身区域做特殊标记。也就是说，规划时用的地图是一个“未来状态的地图”，可以模拟出吃到食物后尾巴不缩短、吃不到食物时尾巴会缩短这两种情况。
模拟吃食物这一点很关键。因为真正的追食物行为是“蛇身会边长”，一旦决定去吃，尾巴那格不会再释放。如果你规划时还把尾巴当普通障碍物忽略，那路线可能带着你去钻一条越走越窄的死胡同。
2.4 性能优化：别让 GC 拖垮你的游戏循环
Java 写小游戏最容易被吐槽的其实是 GC 卡顿。如果每帧都 new 大量Node对象，老年代很快就会被塞满，然后系统每隔几秒就触发一次长时间垃圾回收，画面就一卡一卡的。
我这里做了几个优化：
- 复用节点池，或者用
ArrayDeque和数组来管理待搜索节点，减少Node对象的创建。 - 障碍物地图用
boolean[][]，并且每次复用同一个二维数组，只更新坐标值，不要每次重新分配。 - 路径结果只保存“方向序列”，不保存完整
Node链表，这样执行层直接用序列即可，减少对象持有。
实测下来，连续运行超过 10 分钟，GC 几乎停顿时间可以忽略不计。对于小游戏来说这个优化足够用了。
3. 让蛇“吃满屏幕”的四层策略
3.1 策略层怎么判断“哪个食物能吃”
第二版最核心的改动，就是加了一个食物筛选流程。贪吃蛇不像普通寻路，不是哪个食物近就去吃哪个，而是要看这个食物吃了以后，蛇会不会陷入“无路可走”的境地。
我给每个食物计算两个值：
- 可达性：从蛇头用 BFS 判断能不能到达这个食物，不能到的直接丢弃。
- 安全性：假设蛇已经吃到了这个食物，身体长度加 1，再模拟一下蛇头从新的位置出发，能否到达蛇尾的方向。如果跑不出去，说明这个食物在蛇身包围的“小笼子”里，放弃。
如果多个食物都满足条件，选哪个？我选了“距离适中”的，而不一定是最短的。因为最短的食物往往在蛇身体附近，追它容易扰乱身体布局。反而稍微远一点、路线宽阔的食物，能引导蛇往开阔区域运动，降低困死的概率。
3.2 尾巴逃生策略：没食物吃时，跟着尾巴走
当所有食物都不可取，或者蛇已经长到一定程度，系统会自动切换为“尾巴逃生模式”。
这个模式的思想很简单：如果当前空间只允许蛇继续保持身位活动，那最好的策略就是让蛇头跟着自己的尾巴走，因为尾巴会不断释放空间，这样蛇就在一个局部范围内“转圈”，保持活力，等到有安全食物出现再切换回追食物的模式。
实现上，我把尾巴当作一个“虚拟目标”，调用同一套 A*。但有个细节：目标不能直接定为尾巴当前那一格，因为追到那一格的时候尾巴可能已经移开了。我选择定位在尾巴前方的几格位置，或者干脆用一条稍长的“虚拟路径”去追，确保蛇头始终在撕裂空间而不是逼近尾巴根。
尾巴逃生模式里，蛇不会变长，所以它是一条“活路探索”而不是“进食”的行为。这也符合真实贪吃蛇的策略：活下去才有得吃。
3.3 巡游模式：当蛇身几乎铺满屏幕时怎么办
到了游戏后期，屏幕上密密麻麻全是蛇身。这时候食物可能被蛇身夹在几个“孤岛”里，A* 找不到路径，尾巴逃生策略也没有足够的空间转圈。此时就必须让蛇进入巡游模式。
巡游模式的关键是：我不再为某一个具体目标寻路，而是划定一块“安全区域”，让蛇沿着区域边界做 S 形或螺旋形移动。简单说，就是让蛇贴着墙走，沿着未被占据的格子“舔”过去，一寸一寸地扫遍整块区域。
实现巡游模式时，我维护了一个“下一步候选方向”的优先级队列。优先尝试与当前方向一致的直行，其次是贴近身体方向的转弯，最后才考虑掉头。巡游过程中每走一步都要检查新位置是否被身体占据、是否撞墙，如果候选方向全被堵死，立刻回退到尾巴逃生策略。
这个模式不保证吃得到远处的食物，但能保证蛇不立刻死掉，有时候还能顺便吞掉沿途的食物，让长度继续增加。代价是它牺牲了“最短路径”的高效性，换来了“更长生存时间”的稳定性。
3.4 四层策略的执行流程与降级条件
我把上面这些策略写成一套可降级的流程：
- 收集所有食物，按“可达性 + 安全性”筛选。
- 如果有安全食物，A* 追食物，并把蛇吃食物后的状态模拟一遍。
- 如果没有安全食物，进入尾巴逃生模式，追尾巴。
- 如果尾巴逃生模式也找不到可行路径，进入巡游模式。
- 巡游模式也走不动，说明蛇已经被自己彻底困死，回到 BFS 随便找一条最长的可以走的方向，撑到最后一刻。
这个降级逻辑保证了系统在绝大多数情况下都有事可做，而不是卡在“A* 返回 null 不知道怎么办”的尴尬局面。
4. 代码落地：核心类设计与主循环实现
4.1 项目结构与地图模型
我用的仍然是 Java Swing 做界面，但核心逻辑完全和界面解耦。主要分为这几个类：
GameBoard：负责棋盘数据、蛇身、食物的存储与更新。Snake：负责蛇的移动、增长、碰撞检测。PathFinder：A* 路径搜索。StrategyLayer：决策层，负责选择当前策略。GameController：主循环，连接界面和逻辑。
GameBoard里最重要的是一张boolean[][]的占用地图，我用true表示被占据，false表示空地。每走一步更新这个地图，这样策略层和寻路层都能快速判断某格能不能走。
public class GameBoard { private int rows; private int cols; private boolean[][] occupied; private Deque<Point> snake; private Point food; public GameBoard(int rows, int cols) { this.rows = rows; this.cols = cols; this.occupied = new boolean[rows][cols]; this.snake = new ArrayDeque<>(); initSnake(); spawnFood(); } public void move(Point newHead, boolean eatFood) { snake.addFirst(newHead); occupied[newHead.x][newHead.y] = true; if (!eatFood) { Point tail = snake.removeLast(); occupied[tail.x][tail.y] = false; } } public boolean isSafe(int x, int y) { return x >= 0 && x < rows && y >= 0 && y < cols && !occupied[x][y]; } }这里用ArrayDeque作为蛇身数据结构非常合适，头部插入、尾部删除都是 O(1)。
4.2 决策层与规划层的接口设计
决策层需要知道蛇头的当前状态，以及整张地图的占用信息。我给它定义了一个nextDirection()方法，返回下一步的方向。
public class StrategyLayer { private GameBoard board; private PathFinder pathFinder; public int nextDirection() { Point head = board.getHead(); List<Point> foods = board.getFoods(); // 1. 筛选安全食物 for (Point food : foods) { if (!isReachable(head, food)) continue; if (!isSafeAfterEating(food)) continue; List<Node> path = pathFinder.findPath(head, food, board); if (path != null && path.size() > 1) { return directionFromPath(path); } } // 2. 追尾巴 Point tailTarget = board.getTailTarget(); List<Node> tailPath = pathFinder.findPath(head, tailTarget, board); if (tailPath != null && tailPath.size() > 1) { return directionFromPath(tailPath); } // 3. 巡游模式 return patrolDirection(); } }nextDirection()只返回下一步的方向，而不是一整条路径。因为每走一步之后，蛇身的状态就变了，规划结果已经部分失效，最稳妥的做法是只执行一步，然后重新调用策略层。这也是动态环境里用 A* 的标准姿势。
4.3 主循环：Timer 驱动还是线程驱动
界面刷新我用的是 Java Swing 的Timer，间隔大约 80 毫秒到 120 毫秒。这个速度下蛇移动看起来很流畅，同时给策略层留了足够的计算时间。
需要说明的是，Timer的事件回调是在事件分发线程（EDT）里执行的。如果策略层计算耗时过久，界面会卡住。所以我在策略层里做了严格的时间预算控制，所有路径搜索都限制在 15 毫秒以内。方法是限制 A* 的迭代次数，超过一定次数直接返回 null，让决策层走降级策略。
如果你想让步速更快，可以引入异步计算，但那样要考虑并发访问GameBoard的状态问题。我做过一版，完全没必要，除非你非要做到每帧毫秒级刷新，否则同步方案足够稳定。
4.4 实测效果和参数调优记录
我在一个 30×30 的棋盘上跑了完整的一局。参数如下：Timer 间隔 100 毫秒，A* 迭代上限设成 5000 次，巡游方向优先级为“保持直行 > 右转 > 左转 > 掉头”。
这条蛇最终把自己填满了 90% 左右的屏幕才因为一次策略误判死掉，主要原因是后期蛇身太长，巡游模式在一处狭窄通道里连续三次掉头，把自己绕窒息了。后面我把巡游模式中“连续掉头次数”的上限设置为 2 次，超过之后强制去追最远的尾巴位置，把那个死角让出来，存活率提高了一截。
另外我测了一个重要的参数：什么时候进入巡游模式。如果太早进入，蛇会比较保守，吃东西的效率变低。如果太晚进入，蛇已经身陷重围，巡游也救不回来。我在自己的实现里用了“当前填充率超过 70%，并且安全食物数量为 0，持续 10 帧”作为进入条件。这个阈值可以根据屏幕大小微调。
5. 常见问题与排查技巧实录
5.1 蛇突然“头铁”撞在自己身上
这个问题绝大多数时候是地图状态和真实蛇身状态不一致导致的。排查方法也比较简单：在决策层返回下一步方向前，打印蛇头坐标、蛇身占用集合、目标食物坐标，再单独跑一遍 A*，看路径是否合法。
我遇到过一次很奇怪的情况：A* 明明返回了路径，但蛇还是撞死了。后来发现是我在某次移动蛇身时，更新occupied数组的顺序写反了，导致新蛇头位置没有被标记，旧尾巴位置也没有被清除。每次移动前，我都应该“先移除尾巴，再加入新头”，顺序反了就会留下脏数据。
5.2 A* 搜索太慢导致界面卡顿
界面卡顿基本都是因为搜索范围太大了。30×30 的棋盘，理论上最多 900 个节点，不应该慢。那为什么还会卡？因为开启了列表里插入了大量重复节点，或者PriorityQueue在remove时用了线性扫描，导致复杂度从 O(logn) 退化成了 O(n)。
解决方式有两种：一是改用TreeSet或者自己维护一个支持索引的二叉堆，但这有点复杂；二是限制 A* 的搜索步数，一旦探索节点数超过比如 2000 个，就直接放弃这次搜索，走降级策略。实测下来，第二种方法简单有效，几乎不影响寻路成功率。
5.3 找不到路径时空指针或者死循环
如果findPath返回null，你需要保证上层逻辑有兜底。否则直接调用path.get(1)就会抛异常。我在StrategyLayer.nextDirection()里所有拿路径的地方都做了空判断，空路径就走降级策略，绝不在外面硬解。
另外要特别小心尾巴目标的选择。如果尾巴目标选在了蛇头周边，A* 可能反复规划出一条只有一步的路径，走完又回到原样，然后就卡住不动了。我在追尾巴模式里强制要求路径长度必须大于 5 步，否则改用巡游模式，这样能有效打破局部死循环。
5.4 调试技巧：用可视化辅助找逻辑 bug
写这类 AI 小游戏，最重要的一条经验就是一定不要只靠 System.out.println 调试，因为地图是二维的，状态又随时间变化，日志看得人眼花。
我这里建议直接在 Swing 面板上画调试信息。比如用不同颜色绘制“决策层当前选择的目标食物”、“A* 计算出的路径格子”、“被判定为不安全区域的地方”。我写了一个调试模式，按一个按键就能切换显示。这样能一眼看出蛇为什么这么走，问题出在决策层还是执行层。
调试模式的代码量大概只增加了 100 多行，但对于理解算法行为、排查边界情况帮助巨大。如果不想自己画，至少也要把“目标坐标 + 决策类型 + 当前占用率”打印成一行结构化日志，然后倒回去分析。
5.5 关于“吃满屏幕”这件事的现实预期
最后说点实在的：就算策略优化得再好，贪吃蛇“吃满全屏”在数学上也有极限。因为在有限网格中，蛇身越长，它会占掉越来越多的关键格子，最终一定会出现无论如何都无法避开的情况。除非你上一套完备的哈密尔顿回路框架，否则任何贪心 + 局部寻路的策略都只可能逼近极限，不可能永远不死。
我做这版优化的目标，其实并不是追求“永不死亡”，而是让这条蛇在无人看管的前提下，尽量玩得更久、吃得更满。如果你想在此基础上继续做，可以考虑研究一下“哈密尔顿回路 + 局部跳变优化”的组合方案。那时候，蛇的表现会接近一个“完美玩家”，不过工程量也会上一个台阶。
我个人做完这版最大的感受是：A* 本身并不难，难的是怎么把它放到一个动态环境里去用，并且设计一套能感知风险、随时准备“开溜”的策略层。希望这篇记录能帮你少走点弯路。
