每日算法 — 使用java实现贪吃蛇：影子跟随策略与安全距离评估

贪吃蛇看起来简单，AI 却很容易”饿死”：明明有一条通往食物的最短路径，蛇头一头扎进去后却把自己困死。原因不是寻路算法不够好，而是决策时忽略了”吃完之后我还能不能活”。本文用 Java 实现一个能稳定拿高分的贪吃蛇 AI，核心是影子跟随策略（Shadow Following）：先用”虚拟蛇”预演吃食物的后果，再用”蛇尾影子”验证自己是否仍有一条逃生路径。

一、问题拆解：贪吃蛇 AI 的三层判断

一个能长期存活的贪吃蛇 AI，通常需要回答三个递进的问题：

1. 可达性：食物能不能走到？——用 BFS 在空地上求最短路径。
2. 安全性：吃完之后，蛇头还能不能碰到自己的蛇尾？——用”虚拟蛇”模拟吃完后的身体分布，再跑一次 BFS。
3. 生存性：如果食物不可安全获取，如何拖延？——沿”蛇尾影子”逐格跟随，把身体压缩到最小空间。

影子跟随是业界验证过的经典启发式，最早由社区玩家在 Nokia 时代的贪吃蛇程序中使用，后被强化学习论文作为 baseline 对照。它的关键洞察是：蛇尾是唯一会”消失”的身体格子，跟着尾巴走，蛇身就永远不会被自己堵死。

二、算法设计

2.1 数据结构

• 蛇身用 ArrayDeque<Point> 存储，队头为蛇头，队尾为蛇尾。
• 棋盘用 int[][] 表示占用，0 为空、1 为蛇身、2 为食物。
• 每次决策前将蛇身投影到 boolean[][] blocked，避免反复遍历队列。

2.2 决策流程

每帧:
  1. pathToFood = BFS(蛇头 → 食物, 障碍=蛇身)
  2. if pathToFood != null:
        虚拟蛇 = 复制当前蛇身
        沿 pathToFood 逐格前进；(吃到食物则尾巴不动，否则尾巴收缩)
        if 虚拟蛇能 BFS 到自己的尾巴:
            走 pathToFood 的第一步  ← 安全吃食
        else:
            走影子路径
  3. else:
        走影子路径（追尾）

“影子路径”就是把 BFS 的目标换成蛇尾：BFS(蛇头 → 蛇尾, 障碍=蛇身去掉尾格)。由于尾巴这一格每步都会腾空，追尾永远是可执行的保守动作。

2.3 安全距离评估

仅仅”能追到尾巴”还不够——距离过近时（比如蛇头与尾巴仅隔 1 格），一旦尾巴移动方向改变，蛇头可能立刻被围死。因此加一个安全距离阈值：BFS 到尾巴的步数 d 必须满足 d >= 蛇身长度 / 2，否则视为不安全，转而执行追尾动作，让蛇身逐渐收敛。

这个阈值是可调的超参数：调大更保守（活得久但吃得慢），调小更激进（得分快但易猝死）。

三、完整项目结构

snake-ai/
├── pom.xml
└── src/main/java/com/example/snake/
    ├── Point.java
    ├── SnakeGame.java      // 游戏主循环与规则
    ├── BfsPathFinder.java  // BFS 最短路径
    └── ShadowAi.java       // 影子跟随 AI

无第三方依赖，javac 直接编译即可运行。

四、核心代码

4.1 坐标点

package com.example.snake;

import java.util.Objects;

/** 棋盘坐标，行 row 从上到下，列 col 从左到右 */
public final class Point {
    public final int row;
    public final int col;

    public Point(int row, int col) {
        this.row = row;
        this.col = col;
    }

    public Point move(int dRow, int dCol) {
        return new Point(row + dRow, col + dCol);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Point)) return false;
        Point p = (Point) o;
        return row == p.row && col == p.col;
    }

    @Override
    public int hashCode() {
        return Objects.hash(row, col);
    }

    @Override
    public String toString() {
        return "(" + row + "," + col + ")";
    }
}

4.2 BFS 寻路

BFS 在无权网格上求最短路径，天然得到”步数最少”的解，同时能通过 prev 数组回溯出完整路径。

package com.example.snake;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.List;

/** 网格上的 BFS 最短路径搜索 */
public class BfsPathFinder {

    private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    /**
     * @param rows     行数
     * @param cols     列数
     * @param blocked  障碍矩阵，true 表示不可通行
     * @param start    起点
     * @param goal     终点
     * @return 从 start 到 goal 的路径（含端点），不可达返回 null
     */
    public static List<Point> findPath(int rows, int cols, boolean[][] blocked,
                                       Point start, Point goal) {
        if (start.equals(goal)) return Collections.singletonList(start);
        if (blocked[goal.row][goal.col]) return null;   // 目标被占用直接剪枝

        boolean[][] visited = new boolean[rows][cols];
        Point[][] prev = new Point[rows][cols];
        Deque<Point> queue = new ArrayDeque<>();

        visited[start.row][start.col] = true;
        queue.add(start);

        while (!queue.isEmpty()) {
            Point cur = queue.poll();
            for (int[] d : DIRS) {
                Point next = cur.move(d[0], d[1]);
                if (next.row < 0 || next.row >= rows || next.col < 0 || next.col >= cols) continue;
                if (visited[next.row][next.col]) continue;
                if (blocked[next.row][next.col]) continue;

                visited[next.row][next.col] = true;
                prev[next.row][next.col] = cur;
                if (next.equals(goal)) {
                    return rebuild(prev, start, goal);
                }
                queue.add(next);
            }
        }
        return null;
    }

    /** 沿 prev 指针回溯路径 */
    private static List<Point> rebuild(Point[][] prev, Point start, Point goal) {
        List<Point> path = new ArrayList<>();
        Point cur = goal;
        while (cur != null) {
            path.add(cur);
            if (cur.equals(start)) break;
            cur = prev[cur.row][cur.col];
        }
        Collections.reverse(path);
        return path;
    }

    /** 返回可达终点所需的步数，不可达返回 Integer.MAX_VALUE */
    public static int distance(int rows, int cols, boolean[][] blocked, Point start, Point goal) {
        List<Point> path = findPath(rows, cols, blocked, start, goal);
        return path == null ? Integer.MAX_VALUE : path.size() - 1;
    }
}

4.3 游戏规则容器

package com.example.snake;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Random;

/** 贪吃蛇规则的纯逻辑实现（不含界面） */
public class SnakeGame {
    public final int rows;
    public final int cols;
    public final Deque<Point> body = new ArrayDeque<>();  // 队头蛇头，队尾蛇尾
    public Point food;
    private final Random random = new Random(42);

    public SnakeGame(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        // 初始蛇长 3，水平放置在中部
        body.addLast(new Point(rows / 2, cols / 2));
        body.addLast(new Point(rows / 2, cols / 2 - 1));
        body.addLast(new Point(rows / 2, cols / 2 - 2));
        spawnFood();
    }

    /** 判断某格是否被蛇身占用 */
    public boolean[][] occupy() {
        boolean[][] blocked = new boolean[rows][cols];
        for (Point p : body) blocked[p.row][p.col] = true;
        return blocked;
    }

    /** 蛇头按方向前进一步，返回 true 表示存活 */
    public boolean step(int dRow, int dCol, boolean grow) {
        Point head = body.peekFirst();
        Point next = head.move(dRow, dCol);
        if (next.row < 0 || next.row >= rows || next.col < 0 || next.col >= cols) return false;

        boolean eat = next.equals(food);
        // 允许移动到"当前尾巴"，因为尾巴会同步腾空
        Point tail = body.peekLast();
        if (!next.equals(tail)) {
            for (Point p : body) {
                if (p.equals(next)) return false;  // 撞到自己
            }
        }

        body.addFirst(next);
        if (!eat && !grow) body.removeLast();
        if (eat) spawnFood();
        return true;
    }

    public boolean isWin() {
        return body.size() == rows * cols;
    }

    /** 在空闲格随机放置食物 */
    public void spawnFood() {
        boolean[][] blocked = occupy();
        int free = rows * cols - body.size();
        if (free <= 0) { food = null; return; }
        int pick = random.nextInt(free);
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (!blocked[r][c]) {
                    if (pick-- == 0) { food = new Point(r, c); return; }
                }
            }
        }
    }

    public int length() {
        return body.size();
    }

    /** 用于模拟的深拷贝 */
    public SnakeGame copy() {
        SnakeGame g = new SnakeGame(this.rows, this.cols);
        g.body.clear();
        g.body.addAll(this.body);
        g.food = this.food;
        return g;
    }
}

4.4 影子跟随 AI（核心）

package com.example.snake;

import java.util.List;

/** 影子跟随策略 AI：先验食物安全性，不安全则追尾自保 */
public class ShadowAi {

    private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    /** 安全距离系数：到尾巴的距离需不小于 蛇长 * SAFE_RATIO 才算安全 */
    private final double safeRatio;

    public ShadowAi(double safeRatio) {
        this.safeRatio = safeRatio;
    }

    public ShadowAi() {
        this(0.5);
    }

    /**
     * 依据当前局面给出下一步方向
     * @return 编码方向 {dRow, dCol}
     */
    public int[] decide(SnakeGame game) {
        boolean[][] blocked = game.occupy();
        Point head = game.body.peekFirst();
        Point tail = game.body.peekLast();

        // 第一层：尝试吃食物
        if (game.food != null) {
            List<Point> toFood = BfsPathFinder.findPath(
                    game.rows, game.cols, blocked, head, game.food);
            if (toFood != null && toFood.size() > 1) {
                if (isSafeAfterEating(game, toFood)) {
                    return dirOf(head, toFood.get(1));
                }
            }
        }

        // 第二层：食物不安全，转而追尾，保持生存
        List<Point> toTail = tailPath(game, blocked, head, tail);
        if (toTail != null && toTail.size() > 1) {
            return dirOf(head, toTail.get(1));
        }

        // 第三层：无路可走时选择空格最多的邻居，尽量延缓死亡
        return fallback(head, blocked, game.rows, game.cols);
    }

    /**
     * 虚拟蛇预演：沿 toFood 前进到底，再验证吃完后能否追到自己的尾巴
     */
    private boolean isSafeAfterEating(SnakeGame game, List<Point> toFood) {
        SnakeGame virtual = game.copy();
        // 沿路径逐步推进，吃到食物则增长
        for (int i = 1; i < toFood.size(); i++) {
            Point cur = toFood.get(i - 1);
            Point next = toFood.get(i);
            if (!virtual.step(next.row - cur.row, next.col - cur.col, false)) {
                return false;   // 虚拟演进过程中直接撞死，说明路径有坑
            }
        }
        // 吃完后检查"蛇头 → 蛇尾"的可达性
        boolean[][] blocked = virtual.occupy();
        Point vHead = virtual.body.peekFirst();
        Point vTail = virtual.body.peekLast();
        blocked[vTail.row][vTail.col] = false;  // 尾巴同步腾空，可视为通路
        int dist = BfsPathFinder.distance(virtual.rows, virtual.cols, blocked, vHead, vTail);
        if (dist == Integer.MAX_VALUE) return false;
        // 安全距离要求：追尾距离不能过短，否则转身空间不足
        return dist >= (int) Math.ceil(virtual.length() * safeRatio);
    }

    /**
     * 追尾路径。把尾巴格视为可通行（下一步它就会腾空）
     */
    private List<Point> tailPath(SnakeGame game, boolean[][] blocked, Point head, Point tail) {
        boolean[][] copy = new boolean[game.rows][game.cols];
        for (int r = 0; r < game.rows; r++) {
            for (int c = 0; c < game.cols; c++) copy[r][c] = blocked[r][c];
        }
        copy[tail.row][tail.col] = false;
        return BfsPathFinder.findPath(game.rows, game.cols, copy, head, tail);
    }

    private int[] dirOf(Point from, Point to) {
        return new int[]{to.row - from.row, to.col - from.col};
    }

    /** 无路可走时，选自由度最大的邻居 */
    private int[] fallback(Point head, boolean[][] blocked, int rows, int cols) {
        int[] best = {0, 1};
        int bestFree = -1;
        for (int[] d : DIRS) {
            int nr = head.row + d[0];
            int nc = head.col + d[1];
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
            if (blocked[nr][nc]) continue;
            int free = 0;
            for (int[] e : DIRS) {
                int r2 = nr + e[0], c2 = nc + e[1];
                if (r2 >= 0 && r2 < rows && c2 >= 0 && c2 < cols && !blocked[r2][c2]) free++;
            }
            if (free > bestFree) {
                bestFree = free;
                best = d;
            }
        }
        return best;
    }
}

4.5 主程序（控制台渲染 + 自动运行）

package com.example.snake;

/** 无界面自动对局演示：观察 AI 的存活步数与得分 */
public class Main {
    public static void main(String[] args) {
        int rows = 20, cols = 30;
        SnakeGame game = new SnakeGame(rows, cols);
        ShadowAi ai = new ShadowAi(0.5);

        int steps = 0;
        int limit = 5000;
        while (steps < limit && !game.isWin()) {
            int[] dir = ai.decide(game);
            if (!game.step(dir[0], dir[1], false)) {
                System.out.println("AI 死亡，存活步数=" + steps + "，最终长度=" + game.length());
                break;
            }
            steps++;
            if (steps % 500 == 0) {
                System.out.println("步数=" + steps + " 长度=" + game.length() + " 食物=" + game.food);
            }
        }
        if (game.isWin()) System.out.println("全屏通关！长度=" + game.length());
        render(game);
    }

    /** 用字符打印棋盘，便于目视检查 */
    private static void render(SnakeGame game) {
        boolean[][] blocked = game.occupy();
        StringBuilder sb = new StringBuilder();
        for (int r = 0; r < game.rows; r++) {
            for (int c = 0; c < game.cols; c++) {
                if (game.body.peekFirst().row == r && game.body.peekFirst().col == c) sb.append('@');
                else if (game.food != null && game.food.row == r && game.food.col == c) sb.append('*');
                else if (blocked[r][c]) sb.append('o');
                else sb.append('.');
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }
}

五、关键点解读

虚拟蛇预演的代价：每次决策要跑 1 次”食物 BFS” + 1 次”路径模拟” + 1 次”追尾 BFS”，最坏是 O(N) 级别，N 为棋盘格数。20×30 的棋盘单帧通常低于 1 毫秒，完全够用。若追求更高帧率，可把 BFS 换成增量式 A*，或对食物路径做缓存。

为什么必须把尾巴格视为可通行：蛇每走一步，尾巴都同步收缩一格。若把尾巴当作硬障碍，BFS 会误判”死路”，导致 AI 明明能活却放弃。

安全距离阈值的作用：不加阈值时，AI 常在窄通道内吃食物，吃完发现头尾相邻，转弯即死。加上 dist >= len * 0.5 后，AI 会主动先”绕圈逃生”把空间腾出来，再回头吃食物。

六、复杂度分析

其中 R、C 为棋盘行列数，L 为蛇身长度。整体对局为 O(T·R·C)，T 为总步数。

七、可以继续优化的方向

1. 多步前瞻：把 safeRatio 从固定值改为随蛇长动态调整，蛇越长越保守。
2. 空间连通块评估：吃食物前计算”吃完后蛇头所在连通块的大小”，若连通块小于蛇长则拒绝。
3. 混合强化学习：影子跟随作为动作掩码（action mask），把不可能的动作直接屏蔽，再交给 DQN 决策，是当前公开排行榜上最稳的组合方式之一。

影随尾动，蛇不被己困——这句朴素的经验，其实就是”先验证后行动”在设计算法时的通用范式。