游戏介绍
贪吃蛇是一款经典的益智游戏，玩家控制一条蛇在网格中移动，通过吃食物来增长身体。本文将用Java实现一个带AI的贪吃蛇，核心是让蛇自动寻找食物并避免撞到自己或墙壁。
核心算法
A星寻路算法
A星（A*）算法是启发式搜索算法，通过评估函数 f(n) = g(n) + h(n) 来找到最短路径：
– g(n)：从起点到当前节点的实际代价
– h(n)：从当前节点到目标节点的估计代价（启发函数，这里用曼哈顿距离）
贪心策略
蛇的AI决策流程：
1. 使用A*计算到食物的最短路径
2. 模拟走该路径后，检查蛇尾是否仍有可达空间
3. 如果安全则执行，否则转向最长路径策略，沿墙壁游走保证生存空间
Java实现
import java.util.*;
public class SnakeAI {
// 游戏配置
static final int WIDTH = 20;
static final int HEIGHT = 20;
static final int[][] DIRS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 上、下、左、右
static final String[] DIR_NAMES = {"UP", "DOWN", "LEFT", "RIGHT"};
// 蛇身和食物
Deque<int[]> snake = new ArrayDeque<>();
boolean[][] occupied = new boolean[HEIGHT][WIDTH];
int[] food;
Random rand = new Random();
public SnakeAI() {
// 初始化蛇在中心位置
int cx = WIDTH / 2, cy = HEIGHT / 2;
snake.addFirst(new int[]{cx, cy});
occupied[cy][cx] = true;
spawnFood();
}
// 生成食物
void spawnFood() {
List<int[]> empty = new ArrayList<>();
for (int y = 0; y < HEIGHT; y++) {
for (int x = 0; x < WIDTH; x++) {
if (!occupied[y][x]) empty.add(new int[]{x, y});
}
}
if (empty.isEmpty()) {
food = null;
return;
}
food = empty.get(rand.nextInt(empty.size()));
}
// A*寻路：返回从蛇头到食物的方向序列
List<int[]> aStar(int[] start, int[] goal) {
PriorityQueue<Node> open = new PriorityQueue<>(Comparator.comparingInt(n -> n.f));
Map<String, Node> openMap = new HashMap<>();
Map<String, Node> closed = new HashMap<>();
Node startNode = new Node(start[0], start[1], 0, heuristic(start, goal), null);
open.add(startNode);
openMap.put(key(start), startNode);
while (!open.isEmpty()) {
Node cur = open.poll();
openMap.remove(key(cur));
closed.put(key(cur), cur);
if (cur.x == goal[0] && cur.y == goal[1]) {
return reconstructPath(cur);
}
for (int[] d : DIRS) {
int nx = cur.x + d[0], ny = cur.y + d[1];
if (!inBounds(nx, ny) || occupied[ny][nx]) continue;
if (closed.containsKey(key(nx, ny))) continue;
int ng = cur.g + 1;
String nk = key(nx, ny);
Node neighbor = openMap.get(nk);
if (neighbor == null || ng < neighbor.g) {
Node newNode = new Node(nx, ny, ng, heuristic(new int[]{nx, ny}, goal), cur);
if (neighbor != null) open.remove(neighbor);
open.add(newNode);
openMap.put(nk, newNode);
}
}
}
return null; // 无路径
}
// 启发函数：曼哈顿距离
int heuristic(int[] a, int[] b) {
return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
}
// 重建路径
List<int[]> reconstructPath(Node node) {
List<int[]> path = new ArrayList<>();
while (node != null) {
path.add(new int[]{node.x, node.y});
node = node.parent;
}
Collections.reverse(path);
return path;
}
// 检查坐标是否合法
boolean inBounds(int x, int y) {
return x >= 0 && x < WIDTH && y >= 0 && y < HEIGHT;
}
String key(int[] p) { return p[0] + "," + p[1]; }
String key(int x, int y) { return x + "," + y; }
// 模拟移动后的可达区域（BFS flood fill）
int floodFillCount(int[] head, boolean[][] occ) {
boolean[][] vis = new boolean[HEIGHT][WIDTH];
Queue<int[]> q = new LinkedList<>();
q.add(head);
vis[head[1]][head[0]] = true;
int count = 0;
while (!q.isEmpty()) {
int[] cur = q.poll();
count++;
for (int[] d : DIRS) {
int nx = cur[0] + d[0], ny = cur[1] + d[1];
if (inBounds(nx, ny) && !occ[ny][nx] && !vis[ny][nx]) {
vis[ny][nx] = true;
q.add(new int[]{nx, ny});
}
}
}
return count;
}
// 蛇的AI决策
String decideMove() {
if (food == null) return null;
int[] head = snake.peekFirst();
List<int[]> path = aStar(head, food);
if (path != null && path.size() > 1) {
// 模拟走该路径到食物后的状态
int[] next = path.get(1);
boolean[][] simOcc = copyOccupied();
simOcc[next[1]][next[0]] = true;
// 吃食物后蛇增长，不释放尾部；否则释放尾部
if (!(next[0] == food[0] && next[1] == food[1])) {
int[] tail = snake.peekLast();
simOcc[tail[1]][tail[0]] = false;
}
int reachable = floodFillCount(next, simOcc);
// 如果可达区域足够大（至少剩余空格的一半），则走最短路径
if (reachable >= (WIDTH * HEIGHT - snake.size()) / 2) {
return dirName(head, next);
}
}
// fallback：选择最远的邻居，沿墙壁走（最长路径策略）
int bestDir = -1, maxDist = -1;
for (int i = 0; i < DIRS.length; i++) {
int nx = head[0] + DIRS[i][0], ny = head[1] + DIRS[i][1];
if (!inBounds(nx, ny) || occupied[ny][nx]) continue;
int dist = heuristic(new int[]{nx, ny}, food);
if (dist > maxDist) {
maxDist = dist;
bestDir = i;
}
}
return bestDir >= 0 ? DIR_NAMES[bestDir] : null;
}
String dirName(int[] from, int[] to) {
int dx = to[0] - from[0], dy = to[1] - from[1];
for (int i = 0; i < DIRS.length; i++) {
if (DIRS[i][0] == dx && DIRS[i][1] == dy) return DIR_NAMES[i];
}
return "UP";
}
boolean[][] copyOccupied() {
boolean[][] c = new boolean[HEIGHT][WIDTH];
for (int y = 0; y < HEIGHT; y++) {
System.arraycopy(occupied[y], 0, c[y], 0, WIDTH);
}
return c;
}
// 执行移动
boolean move(String dir) {
int[] head = snake.peekFirst();
int idx = Arrays.asList(DIR_NAMES).indexOf(dir);
int nx = head[0] + DIRS[idx][0], ny = head[1] + DIRS[idx][1];
if (!inBounds(nx, ny) || occupied[ny][nx]) return false;
snake.addFirst(new int[]{nx, ny});
occupied[ny][nx] = true;
if (food != null && nx == food[0] && ny == food[1]) {
spawnFood(); // 吃到食物，不删除尾部
} else {
int[] tail = snake.pollLast();
occupied[tail[1]][tail[0]] = false;
}
return true;
}
// 节点类
static class Node {
int x, y, g, f;
Node parent;
Node(int x, int y, int g, int h, Node parent) {
this.x = x; this.y = y; this.g = g;
this.f = g + h;
this.parent = parent;
}
}
public static void main(String[] args) {
SnakeAI ai = new SnakeAI();
int steps = 0;
while (ai.food != null && steps < 10000) {
String move = ai.decideMove();
if (move == null) {
System.out.println("无路可走，步数: " + steps + "，蛇长: " + ai.snake.size());
break;
}
if (!ai.move(move)) {
System.out.println("碰撞，步数: " + steps + "，蛇长: " + ai.snake.size());
break;
}
steps++;
}
System.out.println("完成！总步数: " + steps + "，最终蛇长: " + ai.snake.size());
}
}
复杂度分析
- A*寻路时间复杂度：$O(b^d)$，$b$为分支因子，$d$为解的深度。在最优启发函数下接近 $O(d)$
- 空间复杂度：$O(WIDTH \times HEIGHT)$，用于存储open/closed集合
- Flood Fill检测：每次决策额外执行一次BFS，时间 $O(WH)$，确保蛇不会把自己困住
总结
本文通过A*算法让贪吃蛇智能寻找食物，配合贪心策略和Flood Fill可达性检测，有效避免了蛇陷入死胡同。读者可以在此基础上扩展更高级的策略，如哈密尔顿回路实现无限通关。
