引言
《雪人兄弟》是一款经典的街机动作游戏，玩家控制雪人角色在多层平台上移动，通过推雪球消灭敌人并清理关卡。虽然表面上是动作游戏，但其核心关卡推进策略蕴含丰富的算法思想：如何在复杂地形中规划最短移动路径？如何在多敌人场景中确定最优消灭顺序？本文用Java实现一个简化版雪人兄弟AI，运用BFS路径搜索进行地形导航，结合动态规划评估最优清理策略。
核心算法思路
关卡地图建模
将游戏关卡抽象为一个二维网格地图，每个格子具有不同属性：空地（可行走）、平台（可站立）、敌人、雪球障碍物。雪人只能左右移动和跳跃（跳跃具有固定高度限制）。
BFS路径搜索
雪人在平台上移动时，需要找到前往目标敌人或安全位置的最短路径。采用广度优先搜索（BFS）在状态空间 $(x, y, \text{是否在空中})$ 中进行搜索，状态转移包括：左移、右移、跳跃（上升）、下落。BFS保证在无权图中找到最少步数路径。
动态规划最优清理策略
当存在多个敌人时，消灭顺序直接影响通关效率与安全性。定义状态为已消灭敌人的集合掩码，使用状态压缩动态规划求解最优消灭顺序。代价函数综合考虑：移动到敌人的路径长度、敌人威胁等级、消灭后的雪球连锁效应。
完整Java实现
import java.util.*;
/**
* 雪人兄弟AI —— BFS路径搜索与动态规划最优清理策略
*/
public class SnowBrosAI {
// 地图单元格类型
public static final int EMPTY = 0;
public static final int PLATFORM = 1;
public static final int ENEMY = 2;
public static final int SNOWBALL = 3;
public static final int WALL = 4;
private final int rows, cols;
private final int[][] grid;
private final List<Enemy> enemies = new ArrayList<>();
public SnowBrosAI(int[][] grid) {
this.grid = grid;
this.rows = grid.length;
this.cols = grid[0].length;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == ENEMY) {
enemies.add(new Enemy(r, c, 1)); // 默认威胁等级1
}
}
}
}
/**
* 状态类：用于BFS搜索
*/
record State(int row, int col, boolean inAir, int steps) {}
/**
* BFS搜索从起点到目标点的最短路径步数
* 移动规则：可左右移动；若下方是平台可站立；可跳跃上升最多2格
*/
public int bfsShortestPath(int sr, int sc, int tr, int tc) {
boolean[][][] visited = new boolean[rows][cols][2];
Queue<State> queue = new LinkedList<>();
queue.offer(new State(sr, sc, false, 0));
visited[sr][sc][0] = true;
int[][] dirs = {{0, 1}, {0, -1}}; // 左右移动
while (!queue.isEmpty()) {
State cur = queue.poll();
if (cur.row == tr && cur.col == tc) {
return cur.steps;
}
// 左右移动
for (int[] d : dirs) {
int nr = cur.row + d[0];
int nc = cur.col + d[1];
if (inBounds(nr, nc) && !visited[nr][nc][0] && canStand(nr, nc)) {
visited[nr][nc][0] = true;
queue.offer(new State(nr, nc, false, cur.steps + 1));
}
}
// 跳跃（向上最多2格）
if (!cur.inAir) {
for (int jump = 1; jump <= 2; jump++) {
int nr = cur.row - jump;
if (inBounds(nr, cur.col) && grid[nr][cur.col] != WALL && !visited[nr][cur.col][1]) {
visited[nr][cur.col][1] = true;
queue.offer(new State(nr, cur.col, true, cur.steps + jump));
}
}
}
// 下落
int nr = cur.row + 1;
while (inBounds(nr, cur.col) && grid[nr][cur.col] == EMPTY) {
nr++;
}
if (inBounds(nr, cur.col) && canStand(nr, cur.col) && !visited[nr][cur.col][0]) {
visited[nr][cur.col][0] = true;
queue.offer(new State(nr, cur.col, false, cur.steps + (nr - cur.row)));
}
}
return -1; // 不可达
}
private boolean inBounds(int r, int c) {
return r >= 0 && r < rows && c >= 0 && c < cols;
}
private boolean canStand(int r, int c) {
return grid[r][c] == PLATFORM || grid[r][c] == EMPTY || grid[r][c] == ENEMY;
}
/**
* 状态压缩动态规划：求解最优敌人消灭顺序
* dp[mask][i] = 从起点出发，消灭mask集合中的敌人后停在敌人i的最小代价
*/
public List<Integer> findOptimalKillOrder(int startR, int startC) {
int n = enemies.size();
if (n == 0) return Collections.emptyList();
// 预计算所有点之间的距离
int[][] dist = new int[n + 1][n + 1];
int[][] pos = new int[n + 1][2];
pos[0] = new int[]{startR, startC};
for (int i = 0; i < n; i++) {
pos[i + 1] = new int[]{enemies.get(i).row, enemies.get(i).col};
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
if (i == j) {
dist[i][j] = 0;
} else {
dist[i][j] = bfsShortestPath(pos[i][0], pos[i][1], pos[j][0], pos[j][1]);
if (dist[i][j] == -1) dist[i][j] = Integer.MAX_VALUE / 2;
}
}
}
int[][] dp = new int[1 << n][n];
int[][] parent = new int[1 << n][n];
for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE / 2);
for (int[] row : parent) Arrays.fill(row, -1);
// 初始化：从起点到每个敌人的距离
for (int i = 0; i < n; i++) {
dp[1 << i][i] = dist[0][i + 1];
}
// 状态转移
for (int mask = 1; mask < (1 << n); mask++) {
for (int last = 0; last < n; last++) {
if ((mask & (1 << last)) == 0) continue;
if (dp[mask][last] >= Integer.MAX_VALUE / 2) continue;
for (int next = 0; next < n; next++) {
if ((mask & (1 << next)) != 0) continue;
int newMask = mask | (1 << next);
int cost = dp[mask][last] + dist[last + 1][next + 1];
// 加入威胁惩罚：优先消灭高威胁敌人
cost += enemies.get(next).threatLevel * 2;
if (cost < dp[newMask][next]) {
dp[newMask][next] = cost;
parent[newMask][next] = last;
}
}
}
}
// 回溯最优路径
int fullMask = (1 << n) - 1;
int bestLast = 0;
for (int i = 1; i < n; i++) {
if (dp[fullMask][i] < dp[fullMask][bestLast]) {
bestLast = i;
}
}
List<Integer> order = new ArrayList<>();
int mask = fullMask;
int cur = bestLast;
while (cur != -1) {
order.add(cur);
int prev = parent[mask][cur];
mask ^= (1 << cur);
cur = prev;
}
Collections.reverse(order);
return order;
}
public static void main(String[] args) {
// 构造示例地图：6行10列
// 0=空地, 1=平台, 2=敌人, 3=雪球, 4=墙
int[][] map = {
{4, 4, 4, 4, 4, 4, 4, 4, 4, 4},
{4, 0, 0, 0, 1, 1, 2, 0, 0, 4},
{4, 0, 0, 0, 0, 0, 0, 0, 0, 4},
{4, 1, 1, 2, 0, 0, 1, 1, 0, 4},
{4, 0, 0, 0, 0, 0, 0, 0, 0, 4},
{4, 4, 4, 4, 4, 4, 4, 4, 4, 4},
};
SnowBrosAI ai = new SnowBrosAI(map);
System.out.println("=== BFS路径搜索测试 ===");
int pathLen = ai.bfsShortestPath(1, 1, 1, 6);
System.out.println("从(1,1)到敌人(1,6)的最短路径步数: " + pathLen);
System.out.println("\n=== 动态规划最优消灭顺序 ===");
List<Integer> order = ai.findOptimalKillOrder(1, 1);
System.out.println("最优消灭顺序（敌人索引）: " + order);
System.out.println("敌人位置: ");
for (int i = 0; i < ai.enemies.size(); i++) {
Enemy e = ai.enemies.get(i);
System.out.printf(" 敌人%d: (%d, %d), 威胁等级=%d%n", i, e.row, e.col, e.threatLevel);
}
}
record Enemy(int row, int col, int threatLevel) {}
}
复杂度分析
- BFS时间复杂度：$O(R \cdot C \cdot 2)$，$R$ 为行数，$C$ 为列数，状态包含是否在空中，故乘以2。
- BFS空间复杂度：$O(R \cdot C \cdot 2)$，用于访问标记数组与队列。
- 状态压缩DP时间复杂度：$O(2^n \cdot n^2)$，$n$ 为敌人数量，适用于 $n \leq 15$ 的场景。
- 状态压缩DP空间复杂度：$O(2^n \cdot n)$。
扩展方向
- A*搜索优化：引入曼哈顿距离启发式函数，将BFS替换为A*，在大型地图中显著加速路径搜索。
- 雪球连锁效应建模：将敌人被雪球击中后的滚动路径纳入消灭代价评估，提升策略准确性。
- 多智能体协同：当存在多个雪人角色时，使用博弈论或任务分配算法实现协同清理。
总结
本文通过BFS与状态压缩动态规划，为《雪人兄弟》类平台动作游戏构建了一套完整的AI决策框架。BFS负责处理复杂地形中的精确导航，而动态规划则在组合爆炸的消灭顺序空间中找出全局最优解。读者可将此框架迁移到其他具有路径规划与任务序列优化需求的游戏AI或机器人导航场景中。
