引言
贪吃蛇的终极挑战是在不撞墙、不咬到自己的前提下，尽可能吃掉更多食物。对于追求”不死”的AI而言，Hamiltonian回路策略是一种经典且优雅的方法：蛇身沿着一条覆盖整个棋盘的闭合回路移动，只要食物出现在回路上，蛇就能安全地到达并吃掉它，同时始终保持身体在回路上，永远不会与自己相撞。
核心算法原理
1. Hamiltonian回路
Hamiltonian回路是经过图中每个顶点恰好一次并回到起点的闭合路径。在 $m \times n$ 的网格图中，当 $m \times n$ 为偶数时一定存在Hamiltonian回路。贪吃蛇棋盘通常为偶数格（如 $20 \times 20 = 400$），因此可以构造这样的回路。
2. 棋盘覆盖策略
本文采用一种简单有效的Hamiltonian回路构造方法——”蛇形往返”策略：
– 第0行从左到右
– 第1行从右到左
– 第2行从左到右
– 依此类推
– 最后一行到达右下角后，沿最右列向上回到起点
这种构造方式在偶数行棋盘上形成一条完整的Hamiltonian回路。
3. 路径跟随与食物追踪
蛇始终沿着Hamiltonian回路移动。当食物出现时，计算蛇头沿回路到食物的路径距离，以及蛇尾的位置关系，确保吃掉食物后蛇身不会阻断回路。
Java实现
import java.util.*;
/**
* 贪吃蛇 Hamiltonian回路AI
* 构造覆盖整个棋盘的闭合回路，蛇沿回路移动即可永不死亡
*/
public class SnakeHamiltonianAI {
private int rows, cols;
private int[] hamiltonianPath; // 每个格子的下一个方向: 0=上,1=右,2=下,3=左
private int[][] nextCell; // 每个格子的下一个格子坐标
public SnakeHamiltonianAI(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.hamiltonianPath = new int[rows * cols];
this.nextCell = new int[rows * cols][2];
buildHamiltonianCycle();
}
/**
* 构建Hamiltonian回路——蛇形往返法
* 适用于行数为偶数的棋盘
*/
private void buildHamiltonianCycle() {
// 按蛇形顺序为每个格子编号并确定下一个方向
for (int r = 0; r < rows; r++) {
if (r % 2 == 0) {
// 偶数行：从左到右
for (int c = 0; c < cols; c++) {
int idx = r * cols + c;
if (c < cols - 1) {
// 向右
hamiltonianPath[idx] = 1;
nextCell[idx] = new int[]{r, c + 1};
} else if (r < rows - 1) {
// 向下换行
hamiltonianPath[idx] = 2;
nextCell[idx] = new int[]{r + 1, c};
} else {
// 最后一个格子，向上回到起点
hamiltonianPath[idx] = 0;
nextCell[idx] = new int[]{0, 0};
}
}
} else {
// 奇数行：从右到左
for (int c = cols - 1; c >= 0; c--) {
int idx = r * cols + c;
if (c > 0) {
// 向左
hamiltonianPath[idx] = 3;
nextCell[idx] = new int[]{r, c - 1};
} else if (r < rows - 1) {
// 向下换行
hamiltonianPath[idx] = 2;
nextCell[idx] = new int[]{r + 1, c};
} else {
// 最后一行奇数行（理论上不应到达，因为总行数应为偶数）
hamiltonianPath[idx] = 0;
nextCell[idx] = new int[]{0, 0};
}
}
}
}
// 修正：最后一行如果是奇数行，需要连接到第一列并向上
if (rows % 2 == 0) {
// 偶数行完美闭合：右下角格子应连接到最右列向上
int lastRow = rows - 1;
if (lastRow % 2 == 1) {
// 最后一行是奇数行，从右向左走到(LastRow, 0)
// 需要从这里向上到(0, 0)形成闭合
// 实际蛇形法需要在最左列建立向上的连接
for (int r = rows - 1; r > 0; r--) {
int idx = r * cols + 0;
hamiltonianPath[idx] = 0; // 向上
nextCell[idx] = new int[]{r - 1, 0};
}
}
}
}
/**
* 获取从当前位置沿Hamiltonian回路到目标位置的步数
*/
public int distanceAlongCycle(int sr, int sc, int tr, int tc) {
int steps = 0;
int r = sr, c = sc;
int maxSteps = rows * cols * 2;
while (!(r == tr && c == tc) && steps < maxSteps) {
int idx = r * cols + c;
int[] nxt = nextCell[idx];
r = nxt[0];
c = nxt[1];
steps++;
}
return steps;
}
/**
* 获取沿Hamiltonian回路的下一个移动方向
*/
public int getNextDirection(int r, int c) {
return hamiltonianPath[r * cols + c];
}
/**
* 打印Hamiltonian回路路径顺序
*/
public void printCycle() {
boolean[] visited = new boolean[rows * cols];
int r = 0, c = 0;
int count = 0;
StringBuilder sb = new StringBuilder();
while (!visited[r * cols + c] && count < rows * cols) {
visited[r * cols + c] = true;
sb.append(String.format("(%d,%d)->", r, c));
int[] nxt = nextCell[r * cols + c];
r = nxt[0];
c = nxt[1];
count++;
}
sb.append(String.format("(%d,%d)", r, c));
System.out.println("Hamiltonian回路: " + sb.toString());
System.out.println("覆盖格子数: " + count);
}
/**
* 贪吃蛇游戏模拟器
*/
static class SnakeGame {
private int rows, cols;
private Deque<int[]> snake; // 蛇身，头部在前
private boolean[][] occupied;
private int[] food;
private SnakeHamiltonianAI ai;
private int score;
public SnakeGame(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.snake = new ArrayDeque<>();
this.occupied = new boolean[rows][cols];
this.ai = new SnakeHamiltonianAI(rows, cols);
// 初始蛇身长度为1，位于左上角
snake.addFirst(new int[]{0, 0});
occupied[0][0] = true;
spawnFood();
this.score = 0;
}
private void spawnFood() {
Random rand = new Random();
do {
food = new int[]{rand.nextInt(rows), rand.nextInt(cols)};
} while (occupied[food[0]][food[1]]);
}
/**
* 基于Hamiltonian回路的移动决策
*/
public boolean move() {
int[] head = snake.peekFirst();
int dir = ai.getNextDirection(head[0], head[1]);
int nr = head[0], nc = head[1];
switch (dir) {
case 0: nr--; break; // 上
case 1: nc++; break; // 右
case 2: nr++; break; // 下
case 3: nc--; break; // 左
}
// 检查碰撞
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) return false;
if (occupied[nr][nc]) {
// 只有尾部即将离开时才允许碰撞尾部
int[] tail = snake.peekLast();
if (!(nr == tail[0] && nc == tail[1])) return false;
}
// 移动头部
snake.addFirst(new int[]{nr, nc});
occupied[nr][nc] = true;
// 检查是否吃到食物
if (nr == food[0] && nc == food[1]) {
score++;
spawnFood();
// 吃到食物不删除尾部，蛇身增长
} else {
// 删除尾部
int[] tail = snake.removeLast();
occupied[tail[0]][tail[1]] = false;
}
return true;
}
public void printBoard() {
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (r == snake.peekFirst()[0] && c == snake.peekFirst()[1]) {
System.out.print("H "); // 头部
} else if (occupied[r][c]) {
System.out.print("S "); // 蛇身
} else if (r == food[0] && c == food[1]) {
System.out.print("F "); // 食物
} else {
System.out.print(". ");
}
}
System.out.println();
}
System.out.println("Score: " + score);
System.out.println();
}
public int runSimulation(int maxSteps) {
for (int i = 0; i < maxSteps; i++) {
if (!move()) {
System.out.println("Game Over at step " + i);
break;
}
if (i % 50 == 0) printBoard();
}
return score;
}
}
public static void main(String[] args) {
// 创建8x8棋盘的Hamiltonian回路
SnakeHamiltonianAI ai = new SnakeHamiltonianAI(8, 8);
ai.printCycle();
// 运行游戏模拟
System.out.println("\n开始游戏模拟...");
SnakeGame game = new SnakeGame(8, 8);
int finalScore = game.runSimulation(500);
System.out.println("最终得分: " + finalScore);
}
}
复杂度分析
- 回路构造：$O(R \times C)$，只需遍历棋盘一次确定每个格子的下一个方向。
- 距离计算：$O(R \times C)$，最坏情况沿整个回路遍历一圈。
- 每步移动决策：$O(1)$，直接查表获取方向。
- 空间复杂度：$O(R \times C)$，存储每个格子的下一个方向。
策略优化与局限
Hamiltonian回路策略虽然保证不死，但由于严格按照固定路径移动，平均吃食物的时间较长，得分效率不高。进阶优化包括：
– shortcut优化：当蛇身较短时，允许偏离回路走捷径直接前往食物。
– 动态回路重构：根据当前蛇身和食物位置，动态调整局部路径。
总结
Hamiltonian回路为贪吃蛇提供了一种数学上完美的生存策略。通过构造覆盖整个棋盘的空间填充曲线，蛇的每一次移动都安全可控。虽然该方法在得分效率上不如A*寻路等贪心策略，但其”绝对不死”的特性使其成为理解图论与路径规划的经典案例。
