每日算法 — 使用java实现贪吃蛇：模拟退火与自适应降温路径优化

引言

贪吃蛇是一款经典的益智游戏，玩家控制蛇在网格中移动并吃掉食物。传统的贪吃蛇AI多采用A*寻路或贪心策略，但在复杂局面下容易陷入局部最优。本文将模拟退火（Simulated Annealing）算法引入贪吃蛇的路径规划中，通过自适应降温策略帮助蛇在”探索新路径”与”利用已知安全路径”之间取得平衡，避免早期死亡并实现更长的生存时间。

算法核心思想

模拟退火源于固体退火原理：高温时分子运动剧烈，系统可以跨越能量壁垒到达各种状态；随着温度降低，系统逐渐稳定在能量最低的基态。在贪吃蛇场景中，我们将”路径长度”或”局面评分”作为能量函数，温度控制接受”劣解”的概率：

• 高温阶段：蛇更愿意尝试看似危险但可能带来长远收益的路径
• 低温阶段：蛇趋于保守，优先选择稳妥的安全路径
• 自适应降温：根据当前蛇身长度和剩余空间动态调整降温系数

核心数据结构

import java.util.*;

/**
 * 模拟退火贪吃蛇核心类
 */
public class SimulatedAnnealingSnake {

    // 游戏面板大小
    private final int width;
    private final int height;

    // 蛇身坐标列表，头部在索引0
    private LinkedList<int[]> snake;

    // 食物位置
    private int[] food;

    // 随机数生成器
    private final Random random;

    // 模拟退火参数
    private double temperature;       // 当前温度
    private final double initialTemp; // 初始温度
    private final double coolingRate; // 降温速率

    // 四个移动方向：上、右、下、左
    private final int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public SimulatedAnnealingSnake(int width, int height) {
        this.width = width;
        this.height = height;
        this.random = new Random();
        this.initialTemp = 100.0;
        this.coolingRate = 0.995;
        reset();
    }

    /**
     * 重置游戏状态
     */
    public void reset() {
        snake = new LinkedList<>();
        int startX = width / 2;
        int startY = height / 2;
        // 初始蛇身长度为3
        for (int i = 0; i < 3; i++) {
            snake.add(new int[]{startX, startY + i});
        }
        temperature = initialTemp;
        spawnFood();
    }

    /**
     * 随机生成食物，确保不在蛇身上
     */
    private void spawnFood() {
        boolean valid;
        do {
            valid = true;
            food = new int[]{random.nextInt(height), random.nextInt(width)};
            for (int[] segment : snake) {
                if (segment[0] == food[0] && segment[1] == food[1]) {
                    valid = false;
                    break;
                }
            }
        } while (!valid);
    }
}

局面评估函数

评估函数是模拟退火的核心，需要综合考量多个因素：

    /**
     * 综合局面评估函数
     * 分数越高表示局面越好
     */
    private double evaluateState(List<int[]> currentSnake, int[] currentFood) {
        int[] head = currentSnake.get(0);

        // 1. 到食物的曼哈顿距离（越近越好）
        double foodDist = Math.abs(head[0] - currentFood[0]) + Math.abs(head[1] - currentFood[1]);
        double foodScore = 1.0 / (foodDist + 1);

        // 2. 可到达空格数量（Flood Fill计算）
        int accessible = countAccessibleCells(currentSnake);
        double spaceScore = accessible / (double)(width * height);

        // 3. 蛇身长度奖励
        double lengthScore = currentSnake.size() * 0.1;

        // 4. 角落惩罚（避免长时间卡在角落）
        double cornerPenalty = 0;
        if ((head[0] == 0 || head[0] == height - 1) && (head[1] == 0 || head[1] == width - 1)) {
            cornerPenalty = 0.3;
        }

        // 5. 尾部跟随奖励（保持尾部通路）
        double tailFollowScore = calculateTailFollowScore(currentSnake);

        return foodScore * 2.0 + spaceScore * 3.0 + lengthScore + tailFollowScore - cornerPenalty;
    }

    /**
     * 使用Flood Fill计算蛇头可达的空格数量
     */
    private int countAccessibleCells(List<int[]> currentSnake) {
        boolean[][] visited = new boolean[height][width];
        // 标记蛇身占据的格子
        for (int[] seg : currentSnake) {
            visited[seg[0]][seg[1]] = true;
        }

        int[] head = currentSnake.get(0);
        Queue<int[]> queue = new LinkedList<>();
        queue.add(head);
        visited[head[0]][head[1]] = true;
        int count = 0;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            count++;
            for (int[] dir : directions) {
                int nr = cur[0] + dir[0];
                int nc = cur[1] + dir[1];
                if (nr >= 0 && nr < height && nc >= 0 && nc < width && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    queue.add(new int[]{nr, nc});
                }
            }
        }
        return count;
    }

    /**
     * 计算尾部跟随分数：头部与尾部距离越近（相对蛇身长度），越安全
     */
    private double calculateTailFollowScore(List<int[]> currentSnake) {
        if (currentSnake.size() < 4) return 0;
        int[] head = currentSnake.get(0);
        int[] tail = currentSnake.get(currentSnake.size() - 1);
        double dist = Math.abs(head[0] - tail[0]) + Math.abs(head[1] - tail[1]);
        // 距离相对于蛇身长度的比例
        return Math.max(0, 1.0 - dist / (currentSnake.size() * 2.0));
    }

模拟退火决策核心

    /**
     * 模拟退火选择下一步方向
     * @return 选择的移动方向索引 0=上,1=右,2=下,3=左
     */
    public int chooseDirection() {
        int[] head = snake.get(0);
        int currentDir = getCurrentDirection();

        // 候选方向：不能180度掉头
        List<Integer> candidates = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            // 排除反向（与当前方向相反）
            if (currentDir != -1 && (i + 2) % 4 == currentDir) continue;

            int nr = head[0] + directions[i][0];
            int nc = head[1] + directions[i][1];
            if (isValidMove(nr, nc)) {
                candidates.add(i);
            }
        }

        if (candidates.isEmpty()) {
            return -1; // 死亡
        }

        // 模拟退火选择
        double currentScore = evaluateState(snake, food);
        int bestDir = candidates.get(0);
        double bestScore = Double.NEGATIVE_INFINITY;

        for (int dir : candidates) {
            // 模拟移动后的状态
            List<int[]> simulatedSnake = simulateMove(dir);
            double newScore = evaluateState(simulatedSnake, food);

            // 计算能量差（新状态 - 当前状态）
            double delta = newScore - currentScore;

            // 如果新状态更好，直接接受
            // 如果更差，以概率 exp(delta / temperature) 接受
            if (delta > 0 || random.nextDouble() < Math.exp(delta / temperature)) {
                if (newScore > bestScore) {
                    bestScore = newScore;
                    bestDir = dir;
                }
            }
        }

        // 自适应降温：蛇越长、空间越小，降温越快（越保守）
        updateTemperature();

        return bestDir;
    }

    /**
     * 获取当前移动方向（根据头部和颈部位置判断）
     */
    private int getCurrentDirection() {
        if (snake.size() < 2) return -1;
        int[] head = snake.get(0);
        int[] neck = snake.get(1);
        for (int i = 0; i < 4; i++) {
            if (head[0] + directions[i][0] == neck[0] && head[1] + directions[i][1] == neck[1]) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 判断移动是否合法（不出界且不撞到自己）
     */
    private boolean isValidMove(int row, int col) {
        if (row < 0 || row >= height || col < 0 || col >= width) return false;
        // 检查是否撞到蛇身（排除尾部，因为尾部会移动）
        for (int i = 0; i < snake.size() - 1; i++) {
            int[] seg = snake.get(i);
            if (seg[0] == row && seg[1] == col) return false;
        }
        return true;
    }

    /**
     * 模拟向指定方向移动后的蛇身状态（不修改实际状态）
     */
    private List<int[]> simulateMove(int dir) {
        List<int[]> simulated = new ArrayList<>();
        int[] head = snake.get(0);
        int[] newHead = new int[]{head[0] + directions[dir][0], head[1] + directions[dir][1]};
        simulated.add(newHead);

        // 复制现有蛇身
        for (int i = 0; i < snake.size(); i++) {
            simulated.add(new int[]{snake.get(i)[0], snake.get(i)[1]});
        }

        // 如果吃到食物，不移除尾部（长度+1）
        // 否则移除最后一个元素
        boolean ateFood = (newHead[0] == food[0] && newHead[1] == food[1]);
        if (!ateFood) {
            simulated.remove(simulated.size() - 1);
        }
        return simulated;
    }

    /**
     * 自适应温度更新
     * 策略：空间越小、蛇越长，温度下降越快（更保守）
     */
    private void updateTemperature() {
        int accessible = countAccessibleCells(snake);
        double spaceRatio = accessible / (double)(width * height);

        // 动态降温系数：空间充裕时降温慢（多探索），空间紧张时降温快（更保守）
        double adaptiveCooling = coolingRate * (0.8 + 0.4 * spaceRatio);
        temperature *= adaptiveCooling;

        // 保证最低温度，避免完全冻结
        temperature = Math.max(temperature, 0.01);
    }

完整游戏循环与主程序

    /**
     * 执行一步移动
     * @return 是否继续游戏
     */
    public boolean step() {
        int dir = chooseDirection();
        if (dir == -1) return false;

        int[] head = snake.get(0);
        int[] newHead = new int[]{head[0] + directions[dir][0], head[1] + directions[dir][1]};
        snake.addFirst(newHead);

        // 检查是否吃到食物
        if (newHead[0] == food[0] && newHead[1] == food[1]) {
            spawnFood();
            // 温度略微回升，鼓励探索新区域
            temperature = Math.min(temperature * 1.2, initialTemp);
        } else {
            snake.removeLast();
        }

        return true;
    }

    /**
     * 打印当前游戏画面
     */
    public void printBoard() {
        char[][] board = new char[height][width];
        for (char[] row : board) Arrays.fill(row, '.');

        // 绘制食物
        board[food[0]][food[1]] = '*';

        // 绘制蛇身
        for (int i = 0; i < snake.size(); i++) {
            int[] seg = snake.get(i);
            board[seg[0]][seg[1]] = (i == 0) ? 'H' : 'o';
        }

        System.out.println("Temperature: " + String.format("%.3f", temperature));
        for (char[] row : board) {
            System.out.println(new String(row));
        }
        System.out.println();
    }

    /**
     * 主程序入口
     */
    public static void main(String[] args) throws InterruptedException {
        SimulatedAnnealingSnake game = new SimulatedAnnealingSnake(15, 15);
        int steps = 0;
        int maxSteps = 5000;

        System.out.println("=== 模拟退火贪吃蛇 ===");
        game.printBoard();

        while (steps < maxSteps && game.step()) {
            steps++;
            if (steps % 50 == 0) {
                game.printBoard();
                Thread.sleep(100);
            }
        }

        System.out.println("Game Over! Steps: " + steps);
        System.out.println("Final Snake Length: " + game.snake.size());
    }

算法复杂度分析

优化建议

1. 预计算可达空间：利用蛇移动的特点，增量更新可达空间而非每次Flood Fill
2. 多步前瞻：模拟退火只评估单步，可结合蒙特卡洛 rollout 评估多步后果
3. 并行评估：四个候选方向可并行计算，提升响应速度
4. 温度调度调参：不同面板大小需要调整初始温度和降温系数

总结

模拟退火为贪吃蛇提供了一种优雅的随机优化框架。通过自适应降温，蛇在初期敢于探索未知区域，后期则稳健地选择安全路径。相比确定性算法，模拟退火能有效避免局部最优陷阱，在复杂地形中展现出更强的生存能力。