写贪吃蛇自动寻路最容易被坑的地方不是A本身而是你辛辛苦苦让蛇“变聪明”之后它反而死得更快。上一篇我把基础版的手动贪吃蛇整个写完了地图、蛇身移动、食物生成、碰撞检测都齐了但玩久了总觉得差点意思——一个游戏自己不能通关写出来干嘛所以这一篇专门解决“让蛇自己吃满屏幕”的问题核心是A自动寻路算法搭配几层简单的生存策略。这篇文章适合两类人一类是Java基础还行、想找个项目练手顺便把A搞明白的同学另一类是面试前想找个能讲清楚的算法落地案例的求职者。贪吃蛇的A跟网上一堆“五子棋AI”“迷宫寻路”不太一样难点在于蛇是动态的、会变长、会把自己堵死所以算法的外壳是A*灵魂是策略。1. 先看一个反直觉的翻车现场只懂寻路的蛇活不过二十个食物很多人写自动贪吃蛇的第一版都是同一个思路每一帧用BFS或者A*算出蛇头到食物的最短路径然后沿着路径走一格。这个版本的蛇看起来确实“会追食物”速度还贼快但你会发现一个让人崩溃的现象——前十几个食物吃得很顺畅蛇身一旦超过某个长度它会在某一次吃完食物之后直接一头撞上自己的身体当场暴毙。1.1 最短路径不等于安全路径一个具体的死法我拿20x20的网格举例蛇从(5,5)出发食物在左上角(1,1)。蛇追着食物一路走因为贪吃蛇的移动规则是蛇头先走、尾巴后缩所以蛇实际会把自己拉成一条长条。假设蛇吃下食物瞬间的位置在(2,2)蛇身沿着一条狭长通道一直延伸到右下角而蛇头刚刚吃掉食物新食物又刷在了蛇头旁边的格子。这时候A*算出来的“最短路径”可能是贴着蛇身往右走但蛇身比墙还麻烦——墙是死的蛇身是跟着你走的。你往前一步尾巴缩一格但如果蛇身太长尾巴缩掉的那一格根本解不了围蛇头还是会撞上自己。这个问题的本质是你把一个动态博弈问题简化成了静态寻路问题。食物位置变了、蛇身位置每一帧都在变、甚至尾巴的移动方向都影响下一秒的可行性。纯寻路只看到“现在哪条路最短”看不到“下一步我把自己关进笼子里了”。1.2 翻车的三个典型姿势我把这个阶段踩过的坑总结成三类你大概率也会遇到第一类是“走进死胡同”。蛇头为了吃食物钻进了一个只有一两个出口的凹槽吃完回头路被自己的身子堵住。A*算的时候不觉得有问题因为路径合法但它没有考虑“路径会把蛇的剩余活动空间压没”。第二类是“包围自己”。蛇绕着地图中心盘了几圈把食物围在自己身体围成的封闭区域外面A*找不到路径直接报错。这种不是最惨的最惨的是蛇把自己和食物围在同一侧但出口太窄回不了头。第三类是“无限横跳”。某些局面下A*规划出来的路径要求蛇先向左走一步下一秒又向右走一步来回震荡看起来像是卡住了其实是因为蛇头附近的可行走空间被压缩到只剩一格任何方向都可能撞上自己或墙。1.3 问题建模的转变目标不止是“到达食物”要解决上面这些问题最关键的一步不是优化A*本身而是想清楚贪吃蛇自动控制的真实目标是什么。我一直觉得这个阶段是最重要的写AI之前先问自己这个AI的成功标准是什么。如果只是“吃到食物”那随便写都能吃但活不久。真正的目标是两条——吃到尽可能多的食物和永远保证自己有一条活路。这两者有时候是冲突的。食物就在旁边但吃完就会死远处有个食物虽然绕路但吃完还能全身而退。那种“有得吃就吃”的AI就是第一种目标的受害者。所以策略设计的核心思路变成每一次决策之前先判断“这个食物能不能吃”判断的标准不是有没有路径而是吃完之后蛇还有没有退路。这个思路贯穿整篇文章。2. A*算法在贪吃蛇网格里的落地细节代价函数、优先队列、碰撞处理既然要讲A*我就一次性把它讲透。A说白了就是“有方向感的Dijkstra”。Dijkstra从起点一圈一圈往外扩张路径一定能找到但中间会扩展很多无意义的节点。A在Dijkstra基础上加了一个“启发函数”让搜索过程偏向目标方向所以同样能找到最短路径但效率高得多。对于贪吃蛇这种网格地图A*几乎是教科书级的适用场景。2.1 A*核心三件套公式、数据结构、邻居扩展A的代价公式是 f(n) g(n) h(n)。g(n)是从起点走到当前节点已经耗费的实际步数每走一格加1。h(n)是当前节点到目标节点的“估算距离”因为贪吃蛇只能上下左右走所以用曼哈顿距离最合适h(n) |当前x - 目标x| |当前y - 目标y|。f(n)就是总估算代价每次从待处理节点里挑f值最小的先扩展这就是A“有方向感”的来源。实现层面有三个关键数据结构。openList是一个按f值从小到大排序的优先队列每次弹出队首就是当前最值得扩展的节点。closedSet是一个集合用来记录已经扩展过的节点防止回头重复计算。第三个是parent指针每个节点记录“我是从哪个节点来的”等找到目标节点后沿着parent一路回溯就是完整路径。public class Node implements ComparableNode { public int x, y; public int g, h, f; public Node parent; public Node(int x, int y) { this.x x; this.y y; } public void calcF() { this.f this.g this.h; } Override public int compareTo(Node o) { return Integer.compare(this.f, o.f); } }邻居扩展要严格限制四个方向——上下左右因为贪吃蛇不允许斜着走。每次扩展邻居时检查三件事坐标是否越界、目标格子是否是蛇身、目标格子是否已经在closedSet里。越界和蛇身都直接忽略已经在closedSet的节点也忽略因为它的g值已经被更优路径算过一遍了再算只会更差。2.2 蛇身碰撞建模是静态障碍还是动态障碍这个点非常关键也是很多初学者写出来“A没错但蛇总死”的原因。蛇身跟墙壁不一样墙壁永远不动但蛇身会移动、会缩短。如果简单地把所有蛇身格子都当成障碍物那A找到的路径往往会过于保守明明可以贴着尾巴根走的路也绕开了。但如果完全无视蛇身移动把蛇身当成空地路径算出来又可能直接穿越蛇身根本走不通。我的做法是保守优先把蛇身全部标记为障碍物。唯一的例外是蛇尾——因为蛇头每走一步尾巴就会往前缩一格所以如果目标点恰好是蛇尾当前所在的格子理论上是可以走的等蛇头到的时候尾巴已经缩走了。但这里有个条件只有当蛇不打算吃食物时尾巴才是“会移动的空地”如果这步吃了食物蛇会变长一格尾巴就不会缩短。这个细节我放在决策器里处理A*本身只接受一个“哪些格子能走”的布尔二维数组具体哪些格子算障碍由上层策略决定。2.3 启发函数的选择为什么曼哈顿距离就够有人会问用欧几里得距离算h不是更准吗在贪吃蛇这种网格地图里欧几里得距离反而可能不准确。因为蛇只能上下左右移动两点之间的实际最短距离一定是曼哈顿距离所以曼哈顿距离的h值永远不大于真实代价这叫“可采纳的启发函数”。A*使用可采纳的启发函数才能保证找到最短路径。欧几里得距离在斜向可移动的连续空间里更准确但在这里反而不合适。还有一点需要注意h的权重可以适当调大让搜索更“激进”。比如h(n)乘以1.2再算f值路径往往更贴近直线方向搜索速度变快但代价是可能牺牲最短性。贪吃蛇场景里我不建议这么干因为路径“稍微绕一点”通常无所谓但“不够安全”直接致命保持标准曼哈顿距离最稳。3. 策略层是真正的灵魂三种决策模式怎么配合算法只是工具让蛇活得久的是决策策略。我最终实现的是一个三模式决策器主寻路模式、逃生验证模式、追尾安全模式。每一帧先走主逻辑主逻辑说“这条路不能走”就降级到安全模式。这套逻辑不复杂但把“吃食物”和“保命”两个目标分得清清楚楚。3.1 策略一A*主寻路——能吃到且能全身而退才去吃主寻路的第一步是用A算出蛇头到食物的路径这部分没什么好说的。关键在于第二步——逃生验证。这个验证是我整套策略的核心做法是模拟假设蛇沿着刚算出来的路径走到食物位置吃下食物这时蛇身会变长蛇头停在食物格子蛇身各节依次前移。模拟结束后用新蛇头和新蛇身构造一个新的障碍地图再调用一次A计算“吃完食物之后的蛇头”到“吃完之后的蛇尾”之间是否存在通路。为什么检查到蛇尾因为蛇每次移动尾巴都会往前缩只要蛇头能追着尾巴的路线走就不会撞墙也不会撞到自己。换句话说存在一条从蛇头到蛇尾的路径意味着蛇在吃完这一口之后至少还有一个可以“转圈”的逃生通道暂时不会把自己困死。public boolean canEscapeAfterEating(Snake snake, Food food, Grid grid) { // 模拟吃完以后的状态 DequePoint simulatedBody new LinkedList(snake.getBody()); simulatedBody.addFirst(new Point(food.x, food.y)); // 头吃到食物 // 如果没有到增长长度上限尾巴不缩 if (snake.shouldGrow()) { // 增长时不移除尾巴 } else { simulatedBody.removeLast(); } Point newHead simulatedBody.getFirst(); Point newTail simulatedBody.getLast(); // 用模拟后的蛇身构造新的障碍地图 boolean[][] obstacles grid.cloneObstacles(); for (Point p : simulatedBody) { if (p ! newHead p ! newTail) { obstacles[p.x][p.y] true; } } // 检查新蛇头能否走到新蛇尾 AStar star new AStar(grid.getRows(), grid.getCols(), obstacles); ListNode path star.findPath(nodeAt(newHead), nodeAt(newTail)); return path ! null !path.isEmpty(); }这段代码跑一遍基本就是决策器的第一道闸门。路径不存在或者逃生路径为空就说明这口食物不能吃立刻降级。3.2 策略二逃生路径存在但很绕——考虑一下到底值不值得吃如果逃生验证通过理论上就可以放心吃了。但实际操作中我加了一个可选的优化计算一下“逃生路径长度”和“当前直接吃食物路径长度”的比值。如果逃生路径特别长——比如吃完后要绕大半个地图才能回到尾巴附近——说明这个食物虽然能吃但吃它会让蛇进入一个很被动的局面。这种时候如果地图上还有别的食物我会让蛇先吃另一个更容易吃的目标。具体做法是把地图上所有食物如果支持多食物或者当前食物周围几个备选点都跑一遍主寻路和逃生验证选择“逃生路径最短”的那个目标。实测下来这个优化能显著降低蛇在后期被围死的概率因为贪吃蛇的死亡往往不是某一次撞墙而是连续几次被迫走危险路线最后把活动空间压缩到极限。3.3 策略三追尾安全模式——没有安全食物时怎么保命当主寻路和逃生验证都不通过或者A根本找不到通往食物的路径时蛇不能傻等着也不能乱走。这时候切换到追尾模式用A计算蛇头到蛇尾的最短路径沿着这条路径走一格。追尾模式的原理很巧妙蛇的尾巴每帧都在往前缩等于说蛇尾所在的位置是一个永远“正在腾空”的格子。蛇头追着尾巴走本质上是在画一个不断收缩的螺旋只要路径存在蛇永远不会撞到自己因为前方那块地在到达之前就会被释放出来。这个模式就像你绕着一个柱子转圈柱子尾巴一直在缩小你就不会撞上它。当蛇切到追尾模式时说明当前局面上所有食物都“吃不得”正确的做法是耐住性子绕圈等食物刷新到一个更安全的位置。这个模式的唯一风险是连追尾路径都算不出来那就说明蛇已经被彻底困死了属于无解局面。3.4 决策优先级宁可不吃不可乱走决策器的整体逻辑优先级非常明确A*是否能到食物吃完后能否逃回尾巴如果能吃到且能逃脱走主寻路路径否则尝试追尾路径追尾路径也没有系统报警游戏结束等待重开。public Direction decide(Snake snake, ListFood foods, Grid grid) { // 尝试每个食物选择最优目标 Food bestFood null; ListNode bestEatPath null; double bestScore Double.MAX_VALUE; for (Food food : foods) { AStar eatStar new AStar(grid.getRows(), grid.getCols(), buildObstacles(snake, grid)); ListNode eatPath eatStar.findPath(snake.getHeadNode(), food.getNode()); if (eatPath null || eatPath.isEmpty()) continue; boolean canEscape canEscapeAfterEating(snake, food, grid); if (canEscape) { double score eatPath.size(); // 可选优化加上逃生路径长度 if (score bestScore) { bestScore score; bestFood food; bestEatPath eatPath; } } } if (bestFood ! null bestEatPath ! null) { return directionToNextNode(bestEatPath.get(1)); } // 安全模式追尾巴 AStar tailStar new AStar(grid.getRows(), grid.getCols(), buildObstacles(snake, grid)); ListNode tailPath tailStar.findPath(snake.getHeadNode(), snake.getTailNode()); if (tailPath ! null tailPath.size() 1) { return directionToNextNode(tailPath.get(1)); } return null; // 无路可走等死 }4. 核心代码实现寻路器、决策器、模拟验证三者怎么协作实现这套系统的代码量不算大关键在于三个类的职责划分清晰。我用的包结构是model包放Node、Snake、Food、Gridalgorithm包放AStar寻路器ai包放SnakeAI决策器core包放GameLoop游戏主循环。下面把最核心的代码逻辑拆开讲。4.1 网格与节点不用二维Node数组的坑我第一版实现时用了一个二维的Node数组来管理整个地图的节点每个Node存自己的g、h、f值。后来发现这有个隐患A*搜索过程中同一个节点可能被多个路径访问如果直接修改二维数组里的Node状态会互相污染。正确做法是每次寻路时在AStar内部创建新的Node对象或者给Node加一个searchId字段每次搜索递增id只有id匹配的g、h值才是本次搜索的值。public class Node implements ComparableNode { public int x, y; public int g, h, f; public Node parent; public int searchId; // 每次搜索的标号 public void reset(int id) { this.g 0; this.h 0; this.f 0; this.parent null; this.searchId id; } }这个searchId的应用非常实用省去了每次都new一个新节点的开销。寻路循环里判断一个节点是否需要重新计算先看searchId是否等于当前搜索轮次不等就重置。4.2 A*寻路主循环优先队列的正确打开方式openList用PriorityQueueclosedSet用HashSet这是最常见的组合。但有一个地方需要特别注意PriorityQueue不支持动态修改元素的优先级。当你找到了一个更短的g值路径到达某个已经在openList里的节点时你需要更新它的g值和parent但PriorityQueue不会自动重新排序。我一开始没处理这个问题导致部分场景路径不是最优的蛇偶尔会绕莫名其妙的圈子。解决方案有两个一是把更新后的节点重新入队旧节点会被稍后跳过因为它的searchId或g值已经不是最优二是用一个HashMap记录每个坐标当前的最优g值发现新g值更小时直接把新节点入队搜索过程中遇到g值不是最优的直接跳过。第二种方法更简洁我强烈推荐。public ListNode findPath(Node start, Node target) { int currentSearchId searchCounter; PriorityQueueNode openList new PriorityQueue(); SetLong closedSet new HashSet(); MapLong, Integer bestG new HashMap(); start.reset(currentSearchId); start.g 0; start.h manhattanDistance(start, target); start.calcF(); openList.offer(start); int[][] dirs {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; while (!openList.isEmpty()) { Node current openList.poll(); long currentKey key(current.x, current.y); if (closedSet.contains(currentKey)) continue; if (current.x target.x current.y target.y) { return buildPath(current); } closedSet.add(currentKey); for (int[] dir : dirs) { int nx current.x dir[0]; int ny current.y dir[1]; if (!inBounds(nx, ny) || obstacles[nx][ny]) continue; long nKey key(nx, ny); if (closedSet.contains(nKey)) continue; int newG current.g 1; Integer oldG bestG.get(nKey); if (oldG ! null newG oldG) continue; Node neighbor nodeAt(nx, ny); neighbor.reset(currentSearchId); neighbor.g newG; neighbor.h manhattanDistance(neighbor, target); neighbor.calcF(); neighbor.parent current; bestG.put(nKey, newG); openList.offer(neighbor); } } return null; // 无路 }key()函数用x * cols y转成long比用String拼接快得多在每帧跑两三次A*的前提下能明显减少垃圾回收压力。4.3 决策器的完整流程要吃还是要逃决策器把前面说的策略串起来每帧调用一次返回这一帧蛇头应该移动的方向。核心流程前面已经画出来了这里补充一个实现细节对多个食物的筛选。我的Game支持一屏多个食物食物数量跟蛇的得分挂钩算是一个难度曲线每次决策时把所有食物都跑一遍主寻路加逃生验证从中挑选逃生路径最短的作为目标。这个过程CPU开销并不大20x20的地图30条蛇身跑一次A*加验证大约在1毫秒以内Java完全可以轻松扛住每秒十次以上的决策频率。4.4 主循环决策频率和移动频率解耦主循环有一件容易忽略的事AI决策频率和蛇的移动频率不要强行绑在一起。我采用两个独立的计时器——移动计时器控制蛇每多少毫秒移动一格比如初始150ms一格随着得分升高逐渐缩短决策计时器控制AI每多少毫秒做一次决策。决策频率我设为移动频率的两倍也就是蛇每走一步之前AI已经重新计算了两次。这样做的原因是蛇身每次移动都会改变障碍地图决策越频繁路径越贴近实际情况。public void gameLoop() { long lastMoveTime 0; long lastDecisionTime 0; while (running) { long now System.currentTimeMillis(); if (now - lastDecisionTime decisionInterval) { Direction dir ai.decide(snake, foods, grid); if (dir ! null) { snake.setDirection(dir); } lastDecisionTime now; } if (now - lastMoveTime moveInterval) { snake.move(); checkCollisionAndFood(); lastMoveTime now; } // 渲染 短暂休眠 Thread.sleep(5); } }5. 实测数据与调优从“能跑”到“吃满屏”的关键几步代码写完只是第一步真正让人吐血的是调参和优化。这节把我实测过程中踩过的坑和调优经验整理出来帮大家少走弯路。5.1 网格大小和速度的匹配关系我最初的测试环境是15x15网格初始蛇长3速度200ms一格。这套参数下蛇基本能稳定吃到60-80个食物但超过这个数字经常出现“蛇尾追着蛇头跑”的怪象——蛇在追尾模式下绕圈绕到一个死角因为地图太小绕圈的半径大于剩余空间直接把自己绕死。后来我把网格扩大到20x20初始蛇长不变速度调到120ms一格稳定吃到100个以上变得轻松很多。30x30网格则适合挑战极限配合100ms一格的速度基本可以吃满整屏。如果你用的网格更大建议把速度初始值调低一些让蛇在前期有足够时间“建立体型优势”避免食物刷新位置太刁钻时反应不过来。5.2 三种策略的效果对比我做了个简单对照实验同一张30x30地图同一个随机种子分别跑三种配置配置平均吃到食物数平均存活时间主要死亡原因纯A*无策略2335秒围死或撞自己A* 逃生验证147220秒极端死角A* 逃生验证 追尾模式284420秒随机种子运气差这组数据对比非常直观逃生验证是质的飞跃追尾模式是量的提升。纯A*配置下蛇就是个愣头青见食物就冲基本活不过前期。加上逃生验证后蛇学会了“克制”不会为了一口吃的把自己搭进去。追尾模式则保证了蛇在无路可吃时能持续活着等待下一波安全机会。5.3 调优过程中遇到的两个隐蔽Bug第一个Bug是“蛇尾空格被误判”。逃生验证中我一开始把模拟后的蛇尾也算成障碍物导致逃生路径计算失败率特别高蛇经常明明能逃生却选择追尾。后来才想到蛇尾在当前帧结束时就会缩掉所以蛇尾所在格子永远应该被视为空地。修正后逃生验证的通过率明显上升。第二个Bug是“食物刷新在蛇头旁边导致的紧急转向”。有时候食物刷新在蛇头正前方一格而逃生验证通不过蛇会切到追尾模式绕一大圈后食物早就没了。后来我在决策器里加了一个floating的“尝鲜”逻辑如果食物距离蛇头不超过2格且吃到后蛇身增长不会导致下一步无路可走就直接吃不跑完整套逃生验证。这个逻辑显著减少了“到嘴的鸭子飞了”的遗憾场景。5.4 还能往哪个方向继续优化如果有人想在这个项目上继续深挖我推荐三个方向。第一个方向是“预测两步”策略当前决策不仅考虑这一步能不能走还模拟走完这一步后的棋盘状态再做一次完整决策选择两步综合最优的方案。这样蛇的走位会更加前瞻性。第二个方向是“哈密顿回路”如果地图大小和蛇的发展阶段允许可以预先计算一条覆盖所有格子的环状路径让蛇永远沿着环路走绝对安全但缺点是可能需要绕远路吃食物效率低。第三个方向是对抗性场景——改成双蛇对战A*寻路时必须把对方的蛇身也当成障碍物还要考虑拦截对方路径这就更接近一个迷你博弈AI了。我个人最推荐从“预测两步”开始因为它的实现难度比哈密顿回路小很多但对存活率的提升非常明显。我在本地测试时加入两步预测后30x30网格下平均吃到食物数从284提升到了350左右而且蛇的走位明显更“聪明”不再像之前那样偶尔出现呆滞的绕圈行为。