每日算法 — 使用java实现贪吃蛇：A星寻路与贪心策略

游戏简介

贪吃蛇是诞生于1976年的经典街机游戏，玩家通过方向键控制一条不断移动的蛇，目标是吃掉随机出现的食物。每吃一个食物，蛇身增长一格，游戏难度随之提升。当蛇头撞到墙壁或自身时游戏结束。

本文将用Java实现一个带AI的贪吃蛇程序，核心是让蛇自动寻找食物。我们采用A星（A*）寻路算法计算蛇头到食物的最短安全路径，并结合贪心策略决策吃食物的最佳时机，避免蛇因急于吃食物而把自己逼入死胡同。

核心算法

A星寻路算法

A*算法是Dijkstra算法的启发式扩展，通过引入估价函数加速搜索：

f(n) = g(n) + h(n)

• g(n)：从起点到节点n的实际代价（步数）
• h(n)：从节点n到目标点的启发式估计代价（曼哈顿距离）

在贪吃蛇场景中，地图被离散为网格，蛇只能上下左右移动，因此曼哈顿距离是理想的启发函数。

贪心安全策略

单纯的最短路径可能让蛇吃掉食物后无路可走。为此引入安全评估：

1. 模拟吃食物：假设蛇沿A*路径吃到食物，预测蛇身新状态
2. 尾部可达性检查：吃完食物后，蛇尾必须能从蛇头位置到达（保证蛇头不 trapped）
3. 最长路径备选：若吃食物路径不安全，改走追随蛇尾的最长路径，拖延时间等待局面改善

Java完整实现

import java.util.*;

/**
 * 贪吃蛇AI - A星寻路 + 贪心安全策略
 */
public class SnakeAI {

    // 方向向量：上、下、左、右
    static final int[][] DIRS = {{-1,0}, {1,0}, {0,-1}, {0,1}};
    static final int UP = 0, DOWN = 1, LEFT = 2, RIGHT = 3;

    int rows, cols;
    Deque<int[]> snake; // 蛇身队列，头部在末尾
    int[] food;
    boolean[][] occupied; // 当前被蛇身占据的格子
    Random rand = new Random();

    public SnakeAI(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        this.snake = new ArrayDeque<>();
        this.occupied = new boolean[rows][cols];
        // 初始蛇位于左上角，长度3
        for (int i = 0; i < 3; i++) {
            int[] cell = {0, i};
            snake.addLast(cell);
            occupied[0][i] = true;
        }
        spawnFood();
    }

    /** 随机生成食物 */
    void spawnFood() {
        List<int[]> free = new ArrayList<>();
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++)
                if (!occupied[r][c]) free.add(new int[]{r, c});
        if (free.isEmpty()) { food = null; return; }
        food = free.get(rand.nextInt(free.size()));
    }

    /** 计算曼哈顿距离启发值 */
    int heuristic(int r, int c, int tr, int tc) {
        return Math.abs(r - tr) + Math.abs(c - tc);
    }

    /**
     * A星寻路：返回从起点到终点的方向序列
     * @param start 起点 [r,c]
     * @param target 终点 [r,c]
     * @param occ 占据矩阵（模拟状态）
     * @return 方向列表，不可达返回null
     */
    List<Integer> aStar(int[] start, int[] target, boolean[][] occ) {
        PriorityQueue<Node> open = new PriorityQueue<>(Comparator.comparingInt(n -> n.f));
        boolean[][] closed = new boolean[rows][cols];
        Map<String, Node> openMap = new HashMap<>();

        Node startNode = new Node(start[0], start[1], 0, heuristic(start[0], start[1], target[0], target[1]), null, -1);
        open.add(startNode);
        openMap.put(key(start[0], start[1]), startNode);

        while (!open.isEmpty()) {
            Node cur = open.poll();
            openMap.remove(key(cur.r, cur.c));
            if (cur.r == target[0] && cur.c == target[1]) {
                return reconstructPath(cur);
            }
            closed[cur.r][cur.c] = true;

            for (int d = 0; d < 4; d++) {
                int nr = cur.r + DIRS[d][0];
                int nc = cur.c + DIRS[d][1];
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                if (occ[nr][nc] || closed[nr][nc]) continue;

                int ng = cur.g + 1;
                String k = key(nr, nc);
                Node existing = openMap.get(k);
                if (existing == null || ng < existing.g) {
                    Node neighbor = new Node(nr, nc, ng, heuristic(nr, nc, target[0], target[1]), cur, d);
                    if (existing != null) open.remove(existing);
                    open.add(neighbor);
                    openMap.put(k, neighbor);
                }
            }
        }
        return null; // 不可达
    }

    List<Integer> reconstructPath(Node node) {
        LinkedList<Integer> path = new LinkedList<>();
        while (node.parent != null) {
            path.addFirst(node.dir);
            node = node.parent;
        }
        return path;
    }

    String key(int r, int c) { return r + "," + c; }

    static class Node {
        int r, c, g, h, f, dir;
        Node parent;
        Node(int r, int c, int g, int h, Node parent, int dir) {
            this.r = r; this.c = c; this.g = g; this.h = h;
            this.f = g + h; this.parent = parent; this.dir = dir;
        }
    }

    /**
     * 贪心决策：判断吃食物是否安全
     * 安全定义：吃完食物后，蛇头仍能到达蛇尾（保证不 trapped）
     */
    boolean isSafeToEat() {
        int[] head = snake.peekLast();
        List<Integer> pathToFood = aStar(head, food, occupied);
        if (pathToFood == null) return false;

        // 模拟吃食物后的状态
        boolean[][] simOcc = new boolean[rows][cols];
        for (int r = 0; r < rows; r++) simOcc[r] = occupied[r].clone();

        // 沿路径移动蛇头到食物位置
        int[] simHead = head.clone();
        for (int dir : pathToFood) {
            simHead[0] += DIRS[dir][0];
            simHead[1] += DIRS[dir][1];
        }
        // 吃食物：头部到达食物，尾部不收缩（长度+1）
        simOcc[simHead[0]][simHead[1]] = true;

        // 检查从新的蛇头能否到达蛇尾（蛇尾此时仍保持原位，因为长度+1）
        int[] tail = snake.peekFirst();
        List<Integer> pathToTail = aStar(simHead, tail, simOcc);
        return pathToTail != null;
    }

    /**
     * 寻找通往蛇尾的最长路径（BFS + 优先扩展远离食物的方向）
     * 用于拖延时间，等待安全吃食物的机会
     */
    List<Integer> longestPathToTail() {
        int[] head = snake.peekLast();
        int[] tail = snake.peekFirst();
        // 使用BFS找到所有到尾部的路径，选最长的一条
        Queue<PathNode> queue = new LinkedList<>();
        queue.add(new PathNode(head[0], head[1], new ArrayList<>(), new boolean[rows][cols]));
        List<Integer> longest = null;

        while (!queue.isEmpty()) {
            PathNode cur = queue.poll();
            if (cur.r == tail[0] && cur.c == tail[1]) {
                if (longest == null || cur.path.size() > longest.size())
                    longest = new ArrayList<>(cur.path);
                continue;
            }
            for (int d = 0; d < 4; d++) {
                int nr = cur.r + DIRS[d][0];
                int nc = cur.c + DIRS[d][1];
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                if (cur.visited[nr][nc]) continue;
                // 不能穿过自己的身体（尾部除外，因为尾部会移动）
                if (occupied[nr][nc] && !(nr == tail[0] && nc == tail[1])) continue;

                boolean[][] newVis = new boolean[rows][cols];
                for (int i = 0; i < rows; i++) newVis[i] = cur.visited[i].clone();
                newVis[nr][nc] = true;
                List<Integer> newPath = new ArrayList<>(cur.path);
                newPath.add(d);
                queue.add(new PathNode(nr, nc, newPath, newVis));
            }
        }
        return longest;
    }

    static class PathNode {
        int r, c;
        List<Integer> path;
        boolean[][] visited;
        PathNode(int r, int c, List<Integer> path, boolean[][] visited) {
            this.r = r; this.c = c; this.path = path; this.visited = visited;
        }
    }

    /** AI决策下一步方向 */
    int decideMove() {
        if (food == null) return -1;

        if (isSafeToEat()) {
            int[] head = snake.peekLast();
            List<Integer> path = aStar(head, food, occupied);
            if (path != null && !path.isEmpty()) return path.get(0);
        }

        // 不安全时走最长路径到尾部
        List<Integer> longPath = longestPathToTail();
        if (longPath != null && !longPath.isEmpty()) return longPath.get(0);

        //  fallback：随便找个安全方向
        int[] head = snake.peekLast();
        for (int d = 0; d < 4; d++) {
            int nr = head[0] + DIRS[d][0];
            int nc = head[1] + DIRS[d][1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !occupied[nr][nc])
                return d;
        }
        return -1;
    }

    /** 执行一步移动 */
    boolean step(int dir) {
        if (dir < 0) return false;
        int[] head = snake.peekLast();
        int nr = head[0] + DIRS[dir][0];
        int nc = head[1] + DIRS[dir][1];
        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) return false;
        if (occupied[nr][nc]) return false; // 撞自己

        snake.addLast(new int[]{nr, nc});
        occupied[nr][nc] = true;

        if (food != null && nr == food[0] && nc == food[1]) {
            spawnFood(); // 吃到食物，不缩尾，长度+1
        } else {
            int[] tail = snake.pollFirst();
            occupied[tail[0]][tail[1]] = false; // 缩尾
        }
        return true;
    }

    /** 打印当前盘面 */
    void printBoard() {
        char[][] board = new char[rows][cols];
        for (char[] row : board) Arrays.fill(row, '.');
        for (int[] s : snake) board[s[0]][s[1]] = 'S';
        int[] head = snake.peekLast();
        board[head[0]][head[1]] = 'H';
        if (food != null) board[food[0]][food[1]] = 'F';
        for (char[] row : board) System.out.println(new String(row));
        System.out.println();
    }

    public static void main(String[] args) throws InterruptedException {
        SnakeAI game = new SnakeAI(10, 10);
        System.out.println("=== 贪吃蛇AI演示 ===");
        game.printBoard();

        int moves = 0;
        while (moves < 200) {
            int dir = game.decideMove();
            if (!game.step(dir)) {
                System.out.println("Game Over! Total moves: " + moves);
                break;
            }
            game.printBoard();
            moves++;
            Thread.sleep(300);
        }
    }
}

算法复杂度分析

总结

本文通过Java实现了带AI的贪吃蛇，核心亮点在于：

1. A星寻路确保蛇以最短步数接近食物，相比盲目BFS效率更高
2. 贪心安全策略在”吃”与”活”之间做出平衡：只有当吃完食物后仍能保证尾部可达时才吃，否则改走最长路径拖延
3. 代码提供了可直接运行的完整项目，包含盘面渲染与AI演示

读者可在此基础上扩展：引入哈密顿回路实现永不死亡的蛇，或尝试深度强化学习（DQN）让AI自主学习更优策略。