引言
贪吃蛇是计算机科学中最经典的编程练习之一。传统的贪吃蛇AI通常采用A寻路或贪心策略，但在长蛇身状态下容易陷入死胡同。本文将介绍一种基于模拟退火算法*的贪吃蛇路径规划方案，通过设计能量函数评估路径质量，在高温下接受劣解以跳出局部最优，逐步降温收敛到全局最优路径，让蛇在复杂的身板缠绕中依然能找到安全的吃食物路线。
算法原理
模拟退火核心思想
模拟退火（Simulated Annealing）借鉴了物理学中金属退火的过程：在高温下分子运动剧烈，系统可以跳出能量局部低谷；随着温度降低，系统逐渐稳定到能量最低的全局最优状态。
在贪吃蛇场景中，我们将蛇头到食物的一条路径视为一个”状态”，路径的安全性（是否会撞到自己或墙壁）和长度作为”能量函数”。算法通过随机扰动当前路径生成新路径，以一定概率接受劣解，从而避免过早陷入局部最优。
能量函数设计
能量函数是模拟退火的核心，我们设计多维度评估指标：
- 路径长度能量：路径越长能量越高（惩罚绕远路）
- 碰撞能量：如果路径会撞到蛇身或墙壁，赋予极高能量惩罚
- 空间封闭能量：评估走完路径后蛇尾是否能跟随移动，避免把自己困死
- 可达性能量：基于Flood Fill计算路径走完后剩余空间的连通性
综合能量函数：
E(path) = w1 * length + w2 * collision_penalty + w3 * enclosure_penalty + w4 * unreachable_penalty
路径扰动策略
生成邻域解的三种方式：
1. 随机偏移：在路径某点随机向垂直方向偏移一格
2. 局部反转：反转路径中的一段子路径
3. 绕路替换：将直线路径替换为绕过障碍的折线路径
接受准则
采用Metropolis准则，以概率接受劣解：
P(accept) = exp(-(E_new - E_current) / T)
其中T为当前温度，随迭代次数指数衰减。
Java实现
import java.util.*;
/**
* 基于模拟退火的贪吃蛇路径规划器
*/
public class SnakeSimulatedAnnealing {
// 棋盘大小
private static final int WIDTH = 20;
private static final int HEIGHT = 20;
// 方向向量：上、右、下、左
private static final int[][] DIRS = {{-1,0},{0,1},{1,0},{0,-1}};
// 能量函数权重
private static final double W_LENGTH = 1.0;
private static final double W_COLLISION = 10000.0;
private static final double W_ENCLOSURE = 500.0;
private static final double W_UNREACHABLE = 300.0;
// 温度参数
private static final double T_INITIAL = 1000.0;
private static final double T_MIN = 0.01;
private static final double COOLING_RATE = 0.995;
private static final int ITERATIONS_PER_TEMP = 100;
// 蛇身（头部在列表末尾）
private List<int[]> snake;
private int[] food;
private Random random;
public SnakeSimulatedAnnealing() {
this.snake = new ArrayList<>();
this.random = new Random();
initGame();
}
/**
* 初始化游戏状态
*/
private void initGame() {
snake.clear();
// 初始蛇身，长度为3，位于左上角
snake.add(new int[]{0, 0});
snake.add(new int[]{0, 1});
snake.add(new int[]{0, 2}); // 头部
spawnFood();
}
/**
* 随机生成食物位置
*/
private void spawnFood() {
boolean valid;
do {
valid = true;
food = new int[]{random.nextInt(HEIGHT), random.nextInt(WIDTH)};
for (int[] seg : snake) {
if (seg[0] == food[0] && seg[1] == food[1]) {
valid = false;
break;
}
}
} while (!valid);
}
/**
* 模拟退火主算法：寻找从蛇头到食物的最优路径
*/
public List<int[]> findPath() {
int[] head = snake.get(snake.size() - 1);
// 先用BFS找一条初始可行路径
List<int[]> currentPath = bfsPath(head, food);
if (currentPath == null || currentPath.isEmpty()) {
return null; // 无路径可达
}
List<int[]> bestPath = new ArrayList<>(currentPath);
double bestEnergy = computeEnergy(bestPath);
double currentEnergy = bestEnergy;
double T = T_INITIAL;
while (T > T_MIN) {
for (int i = 0; i < ITERATIONS_PER_TEMP; i++) {
// 生成邻域解
List<int[]> newPath = perturbPath(currentPath);
if (newPath == null) continue;
double newEnergy = computeEnergy(newPath);
double deltaE = newEnergy - currentEnergy;
// Metropolis准则
if (deltaE < 0 || random.nextDouble() < Math.exp(-deltaE / T)) {
currentPath = newPath;
currentEnergy = newEnergy;
if (currentEnergy < bestEnergy) {
bestEnergy = currentEnergy;
bestPath = new ArrayList<>(currentPath);
}
}
}
T *= COOLING_RATE; // 降温
}
return bestPath;
}
/**
* BFS寻找初始可行路径（忽略蛇身移动）
*/
private List<int[]> bfsPath(int[] start, int[] end) {
boolean[][] visited = new boolean[HEIGHT][WIDTH];
int[][][] parent = new int[HEIGHT][WIDTH][2];
for (int i = 0; i < HEIGHT; i++) {
for (int j = 0; j < WIDTH; j++) {
parent[i][j] = new int[]{-1, -1};
}
}
Queue<int[]> queue = new LinkedList<>();
queue.offer(start);
visited[start[0]][start[1]] = true;
// 将当前蛇身位置标记为障碍（除了尾部，因为蛇移动后会空出）
boolean[][] obstacle = new boolean[HEIGHT][WIDTH];
for (int idx = 0; idx < snake.size() - 1; idx++) {
int[] seg = snake.get(idx);
obstacle[seg[0]][seg[1]] = true;
}
while (!queue.isEmpty()) {
int[] cur = queue.poll();
if (cur[0] == end[0] && cur[1] == end[1]) {
// 重建路径
List<int[]> path = new ArrayList<>();
int[] node = end;
while (node[0] != -1) {
path.add(0, node);
if (node[0] == start[0] && node[1] == start[1]) break;
node = parent[node[0]][node[1]];
}
return path;
}
for (int[] d : DIRS) {
int nr = cur[0] + d[0];
int nc = cur[1] + d[1];
if (nr >= 0 && nr < HEIGHT && nc >= 0 && nc < WIDTH
&& !visited[nr][nc] && !obstacle[nr][nc]) {
visited[nr][nc] = true;
parent[nr][nc] = cur;
queue.offer(new int[]{nr, nc});
}
}
}
return null;
}
/**
* 扰动当前路径生成邻域解
*/
private List<int[]> perturbPath(List<int[]> path) {
if (path.size() <= 2) return path;
List<int[]> newPath = new ArrayList<>(path);
int perturbType = random.nextInt(3);
switch (perturbType) {
case 0: // 随机偏移中间点
int idx = random.nextInt(newPath.size() - 2) + 1;
int[] point = newPath.get(idx);
int[] dir = DIRS[random.nextInt(4)];
int nr = point[0] + dir[0];
int nc = point[1] + dir[1];
if (nr >= 0 && nr < HEIGHT && nc >= 0 && nc < WIDTH) {
newPath.set(idx, new int[]{nr, nc});
}
break;
case 1: // 局部反转
int i = random.nextInt(newPath.size());
int j = random.nextInt(newPath.size());
if (i > j) { int tmp = i; i = j; j = tmp; }
while (i < j) {
Collections.swap(newPath, i, j);
i++; j--;
}
break;
case 2: // 插入随机中间点
int insertIdx = random.nextInt(newPath.size() - 1);
int[] p1 = newPath.get(insertIdx);
int[] p2 = newPath.get(insertIdx + 1);
int[] mid = new int[]{(p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2};
if (mid[0] >= 0 && mid[0] < HEIGHT && mid[1] >= 0 && mid[1] < WIDTH) {
newPath.add(insertIdx + 1, mid);
}
break;
}
return newPath;
}
/**
* 计算路径的能量值（越低越好）
*/
private double computeEnergy(List<int[]> path) {
double energy = 0.0;
// 1. 路径长度能量
energy += W_LENGTH * path.size();
// 2. 碰撞能量：检查路径是否穿过障碍
boolean[][] obstacle = new boolean[HEIGHT][WIDTH];
for (int s = 0; s < snake.size(); s++) {
int[] seg = snake.get(s);
obstacle[seg[0]][seg[1]] = true;
}
for (int[] p : path) {
if (p[0] < 0 || p[0] >= HEIGHT || p[1] < 0 || p[1] >= WIDTH) {
energy += W_COLLISION; // 撞墙
} else if (obstacle[p[0]][p[1]]) {
// 撞到蛇身，但尾部会移动，需要判断时机
energy += W_COLLISION * 0.5;
}
}
// 3. 空间封闭能量：模拟走完后蛇头位置，Flood Fill计算可达空间
int[] finalHead = path.get(path.size() - 1);
int reachable = floodFillReachable(finalHead, path);
if (reachable < snake.size() + 5) {
energy += W_ENCLOSURE * (snake.size() + 5 - reachable);
}
// 4. 不可达惩罚：如果走完后食物不可达
if (reachable == 0) {
energy += W_UNREACHABLE;
}
return energy;
}
/**
* Flood Fill计算从某点出发可达的格子数（模拟蛇走完后）
*/
private int floodFillReachable(int[] start, List<int[]> path) {
boolean[][] occupied = new boolean[HEIGHT][WIDTH];
// 标记蛇身（假设蛇会沿着路径移动）
for (int[] seg : snake) {
occupied[seg[0]][seg[1]] = true;
}
// 简化：移除路径长度的尾部格子
int steps = path.size();
for (int i = 0; i < Math.min(steps, snake.size()); i++) {
int[] tail = snake.get(i);
occupied[tail[0]][tail[1]] = false;
}
// 标记新路径占用
for (int[] p : path) {
if (p[0] >= 0 && p[0] < HEIGHT && p[1] >= 0 && p[1] < WIDTH) {
occupied[p[0]][p[1]] = true;
}
}
boolean[][] visited = new boolean[HEIGHT][WIDTH];
Queue<int[]> queue = new LinkedList<>();
queue.offer(start);
visited[start[0]][start[1]] = true;
int count = 1;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
for (int[] d : DIRS) {
int nr = cur[0] + d[0];
int nc = cur[1] + d[1];
if (nr >= 0 && nr < HEIGHT && nc >= 0 && nc < WIDTH
&& !visited[nr][nc] && !occupied[nr][nc]) {
visited[nr][nc] = true;
count++;
queue.offer(new int[]{nr, nc});
}
}
}
return count;
}
/**
* 执行一步移动
*/
public void step() {
List<int[]> path = findPath();
if (path != null && path.size() > 1) {
int[] next = path.get(1); // 下一步位置
// 移动蛇头
snake.add(next);
// 判断是否吃到食物
if (next[0] == food[0] && next[1] == food[1]) {
spawnFood(); // 吃到食物，不删除尾部（蛇增长）
} else {
snake.remove(0); // 没吃到，删除尾部
}
}
}
/**
* 打印当前棋盘状态
*/
public void printBoard() {
boolean[][] isSnake = new boolean[HEIGHT][WIDTH];
for (int[] seg : snake) {
isSnake[seg[0]][seg[1]] = true;
}
int[] head = snake.get(snake.size() - 1);
for (int i = 0; i < HEIGHT; i++) {
for (int j = 0; j < WIDTH; j++) {
if (i == head[0] && j == head[1]) {
System.out.print("H ");
} else if (i == food[0] && j == food[1]) {
System.out.print("F ");
} else if (isSnake[i][j]) {
System.out.print("S ");
} else {
System.out.print(". ");
}
}
System.out.println();
}
System.out.println("Snake length: " + snake.size());
System.out.println();
}
public static void main(String[] args) {
SnakeSimulatedAnnealing game = new SnakeSimulatedAnnealing();
System.out.println("=== 模拟退火贪吃蛇 ===");
for (int step = 0; step < 50; step++) {
game.printBoard();
game.step();
// 检查是否死亡
int[] head = game.snake.get(game.snake.size() - 1);
if (head[0] < 0 || head[0] >= HEIGHT || head[1] < 0 || head[1] >= WIDTH) {
System.out.println("Game Over: hit wall");
break;
}
try {
Thread.sleep(200);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(k × n × m × I) | k为温度迭代次数，n×m为棋盘大小，I为每温度迭代次数 |
| 空间复杂度 | O(n × m) | 棋盘状态、BFS队列、路径存储 |
| BFS寻路 | O(n × m) | 用于生成初始解 |
| Flood Fill | O(n × m) | 每次能量评估需要执行 |
模拟退火的时间开销较大，但相比穷举搜索，它能在多项式时间内找到近似最优解。在实际游戏中，可以对参数进行调优：缩小棋盘、减少迭代次数、或使用快速冷却策略。
总结
本文介绍了基于模拟退火算法的贪吃蛇AI实现。与A*等确定性算法相比，模拟退火能够在蛇身较长、空间受限的情况下，通过概率性跳出局部最优，找到更安全的吃食物路径。关键设计要点包括：合理的能量函数定义（综合考虑路径长度、碰撞风险、空间封闭性）、有效的路径扰动策略、以及适当的温度调度方案。读者可以通过调整权重参数和冷却速率，观察不同配置下AI的行为变化，加深对启发式搜索和随机优化算法的理解。
