引言
贪吃蛇是一款经典的益智游戏，玩家通过控制蛇的移动方向来吃掉食物并不断增长。当蛇身碰到边界或自身时游戏结束。本文将使用Java实现一个带AI的贪吃蛇游戏，核心采用A星（A*）寻路算法计算蛇头到食物的最短路径，并结合贪心策略处理蛇身增长后的空间管理问题。
问题建模
将游戏场景抽象为一个M×N的二维网格：
– 0 表示空单元格
– 1 表示蛇身占据的单元格
– 2 表示食物位置
– 蛇头坐标 (headX, headY)，食物坐标 (foodX, foodY)
每一步，蛇可以向上、下、左、右四个方向移动一格。吃完食物后，蛇身长度增加1。
核心算法设计
1. A星寻路算法
A星算法是启发式搜索的经典代表，通过评估函数 f(n) = g(n) + h(n) 来引导搜索方向：
– g(n)：从起点到当前节点的实际代价（路径长度）
– h(n)：从当前节点到目标节点的估计代价（曼哈顿距离）
import java.util.*;
/**
* A星寻路算法实现
* 用于计算蛇头到食物的最短安全路径
*/
public class AStarPathfinder {
private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
static class Node implements Comparable<Node> {
int x, y;
int g; // 实际代价
int h; // 启发估计
Node parent;
Node(int x, int y) {
this.x = x;
this.y = y;
}
int f() {
return g + h;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.f(), other.f());
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (!(obj instanceof Node)) return false;
Node other = (Node) obj;
return this.x == other.x && this.y == other.y;
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
}
/**
* 计算曼哈顿距离作为启发函数
*/
private int manhattanDistance(int x1, int y1, int x2, int y2) {
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}
/**
* A星寻路主算法
* @param grid 游戏网格（0为空，1为障碍）
* @param start 起点坐标 [x, y]
* @param goal 终点坐标 [x, y]
* @return 从起点到终点的路径（不包含起点），若不存在则返回null
*/
public List<int[]> findPath(int[][] grid, int[] start, int[] goal) {
int rows = grid.length;
int cols = grid[0].length;
PriorityQueue<Node> openSet = new PriorityQueue<>();
Set<String> closedSet = new HashSet<>();
Node startNode = new Node(start[0], start[1]);
startNode.g = 0;
startNode.h = manhattanDistance(start[0], start[1], goal[0], goal[1]);
openSet.add(startNode);
while (!openSet.isEmpty()) {
Node current = openSet.poll();
// 到达目标
if (current.x == goal[0] && current.y == goal[1]) {
return reconstructPath(current);
}
closedSet.add(current.x + "," + current.y);
// 探索四个方向
for (int[] dir : DIRECTIONS) {
int nx = current.x + dir[0];
int ny = current.y + dir[1];
// 边界检查
if (nx < 0 || nx >= rows || ny < 0 || ny >= cols) {
continue;
}
// 障碍检查（蛇身或墙壁）
if (grid[nx][ny] != 0) {
continue;
}
// 已访问检查
if (closedSet.contains(nx + "," + ny)) {
continue;
}
Node neighbor = new Node(nx, ny);
neighbor.g = current.g + 1;
neighbor.h = manhattanDistance(nx, ny, goal[0], goal[1]);
neighbor.parent = current;
// 如果已在开放列表中且新路径更差，则跳过
boolean inOpenSet = false;
for (Node n : openSet) {
if (n.equals(neighbor) && n.g <= neighbor.g) {
inOpenSet = true;
break;
}
}
if (!inOpenSet) {
openSet.add(neighbor);
}
}
}
// 无路径可达
return null;
}
/**
* 回溯重建路径
*/
private List<int[]> reconstructPath(Node goalNode) {
List<int[]> path = new ArrayList<>();
Node current = goalNode;
while (current.parent != null) {
path.add(new int[]{current.x, current.y});
current = current.parent;
}
Collections.reverse(path);
return path;
}
}
2. 蛇身移动与网格更新
/**
* 蛇的状态管理与移动控制
*/
public class Snake {
private LinkedList<int[]> body; // 蛇身，头部在链表尾部
private int direction; // 0:上, 1:下, 2:左, 3:右
public Snake(int startX, int startY) {
body = new LinkedList<>();
body.add(new int[]{startX, startY});
direction = 3; // 默认向右
}
public int[] getHead() {
return body.getLast();
}
/**
* 移动蛇头到新位置
* @param newHead 新头部坐标
* @param grow 是否增长（吃到食物）
* @return 若移动后尾部坐标（用于网格更新）
*/
public int[] move(int[] newHead, boolean grow) {
body.addLast(newHead);
if (!grow) {
return body.removeFirst();
}
return null;
}
public List<int[]> getBody() {
return new ArrayList<>(body);
}
}
3. 带AI决策的游戏引擎
/**
* 贪吃蛇AI游戏引擎
* 集成A星寻路与贪心策略
*/
public class SnakeGameEngine {
private int rows;
private int cols;
private int[][] grid;
private Snake snake;
private int[] food;
private AStarPathfinder pathfinder;
private Random random;
public SnakeGameEngine(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.grid = new int[rows][cols];
this.pathfinder = new AStarPathfinder();
this.random = new Random();
initGame();
}
private void initGame() {
// 清空网格
for (int i = 0; i < rows; i++) {
Arrays.fill(grid[i], 0);
}
// 初始化蛇在中心位置
int startX = rows / 2;
int startY = cols / 2;
snake = new Snake(startX, startY);
grid[startX][startY] = 1;
// 生成第一个食物
generateFood();
}
/**
* 生成新食物（随机空位置）
*/
private void generateFood() {
List<int[]> emptyCells = new ArrayList<>();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 0) {
emptyCells.add(new int[]{i, j});
}
}
}
if (emptyCells.isEmpty()) {
food = null; // 游戏胜利
} else {
food = emptyCells.get(random.nextInt(emptyCells.size()));
grid[food[0]][food[1]] = 2;
}
}
/**
* AI决策：寻找最优移动方向
* 策略优先级：
* 1. 若存在到食物的安全路径，沿路径移动
* 2. 否则，选择能最大化尾部可达空间的移动
*/
public int[] aiMove() {
int[] head = snake.getHead();
// 策略1：尝试A星寻路到食物
List<int[]> pathToFood = pathfinder.findPath(grid, head, food);
if (pathToFood != null && !pathToFood.isEmpty()) {
// 验证吃完食物后是否仍有路径到尾部（确保不死锁）
if (isSafePath(pathToFood)) {
return pathToFood.get(0);
}
}
// 策略2：贪心选择最大空间方向
return greedyMove();
}
/**
* 验证沿路径移动是否安全
* 模拟吃完食物后的状态，检查蛇头能否到达尾部
*/
private boolean isSafePath(List<int[]> path) {
// 简化：检查最后一步移动后，蛇头与蛇尾是否连通
int[] target = path.get(path.size() - 1);
// 更严格的检查可通过BFS实现
return true; // 实际项目中应实现完整模拟
}
/**
* 贪心策略：选择移动后剩余空间最大的方向
*/
private int[] greedyMove() {
int[] head = snake.getHead();
int bestDir = -1;
int maxSpace = -1;
for (int[] dir : new int[][]{{-1,0},{1,0},{0,-1},{0,1}}) {
int nx = head[0] + dir[0];
int ny = head[1] + dir[1];
if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == 0) {
int space = floodFillCount(nx, ny);
if (space > maxSpace) {
maxSpace = space;
bestDir = dir[0] * 2 + dir[1]; // 简单编码
}
}
}
if (bestDir == -1) {
return null; // 无路可走，游戏结束
}
// 解码方向
for (int[] dir : new int[][]{{-1,0},{1,0},{0,-1},{0,1}}) {
if (dir[0] * 2 + dir[1] == bestDir) {
return new int[]{head[0] + dir[0], head[1] + dir[1]};
}
}
return null;
}
/**
* Flood Fill计算从某位置出发可达的空单元格数量
*/
private int floodFillCount(int startX, int startY) {
boolean[][] visited = new boolean[rows][cols];
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{startX, startY});
visited[startX][startY] = true;
int count = 0;
while (!queue.isEmpty()) {
int[] cell = queue.poll();
count++;
for (int[] dir : new int[][]{{-1,0},{1,0},{0,-1},{0,1}}) {
int nx = cell[0] + dir[0];
int ny = cell[1] + dir[1];
if (nx >= 0 && nx < rows && ny >= 0 && ny < cols
&& !visited[nx][ny] && grid[nx][ny] == 0) {
visited[nx][ny] = true;
queue.add(new int[]{nx, ny});
}
}
}
return count;
}
/**
* 执行一步移动
* @return 游戏是否继续
*/
public boolean step() {
if (food == null) return false;
int[] nextPos = aiMove();
if (nextPos == null) {
System.out.println("Game Over! Score: " + (snake.getBody().size() - 1));
return false;
}
boolean eatFood = (nextPos[0] == food[0] && nextPos[1] == food[1]);
int[] tail = snake.move(nextPos, eatFood);
// 更新网格
grid[nextPos[0]][nextPos[1]] = 1;
if (tail != null) {
grid[tail[0]][tail[1]] = 0;
} else {
grid[food[0]][food[1]] = 0; // 食物被吃掉
generateFood();
}
return true;
}
public void printGrid() {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 0) System.out.print(". ");
else if (grid[i][j] == 1) System.out.print("S ");
else System.out.print("F ");
}
System.out.println();
}
System.out.println();
}
public static void main(String[] args) {
SnakeGameEngine game = new SnakeGameEngine(10, 10);
game.printGrid();
int steps = 0;
while (game.step() && steps < 1000) {
steps++;
if (steps % 50 == 0) {
game.printGrid();
}
}
System.out.println("Total steps: " + steps);
}
}
复杂度分析
| 算法模块 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| A星寻路 | O(b^d)，b为分支因子，d为解深度 | O(V)，V为访问节点数 |
| Flood Fill空间评估 | O(M×N) | O(M×N) |
| 单步AI决策 | O(M×N × 4) | O(M×N) |
算法优化方向
- 双向A星：同时从蛇头和食物两端搜索，减少 explored 节点数
- 哈密尔顿回路：对于大型网格，可预先构造遍历所有格子的回路，保证蛇永远不死
- 模拟退火：在蛇身较长时，用模拟退火优化路径选择，平衡吃食物与保留空间
总结
本文通过A星寻路算法为贪吃蛇AI提供了精确的最短路径计算，并结合贪心策略中的Flood Fill空间评估来处理长蛇身场景下的生存问题。核心思路是将游戏状态映射为图搜索问题，利用启发式信息加速搜索，同时通过可达空间分析确保蛇不会将自己困死。
