超级马里奥是任天堂开发的经典平台跳跃游戏，玩家控制马里奥在横版关卡中奔跑、跳跃，躲避敌人并收集金币。本文将用Java实现一个简化版的超级马里奥AI，核心挑战在于让AI自动找到通过关卡的最优路径。
问题建模
将关卡地图抽象为二维网格，每个格子包含以下属性：空地、砖块、金币、敌人、陷阱、终点。马里奥可以执行的动作包括：左移、右移、跳跃、下蹲。我们需要找到从起点到终点的最优动作序列。
这个问题可以分解为两个层次：
– 宏观路径规划：使用A算法在关卡图上搜索最短可行路径
– 微观动作决策*：使用动态规划在每个局部区域选择最优动作组合
A*寻路算法
A*算法是启发式搜索的经典方法，通过评估函数 f(n) = g(n) + h(n) 来引导搜索方向。其中 g(n) 是从起点到当前节点的实际代价，h(n) 是到终点的启发式估计。
对于马里奥关卡，我们设计如下代价函数：
– 水平移动代价：1
– 跳跃代价：2（消耗更多能量）
– 碰到敌人代价：100（惩罚）
– 掉落陷阱代价：1000（致命）
启发函数采用曼哈顿距离变体，同时考虑垂直高度差：
public class MarioAStar {
// 地图单元格类型
enum CellType { EMPTY, BRICK, COIN, ENEMY, TRAP, GOAL, START }
static class Node {
int x, y;
int gCost; // 从起点到当前节点的实际代价
int hCost; // 启发式估计代价
int fCost() { return gCost + hCost; }
Node parent;
Node(int x, int y) {
this.x = x;
this.y = y;
}
}
private final CellType[][] map;
private final int rows, cols;
private final int startX, startY;
private final int goalX, goalY;
// 动作定义：水平移动、跳跃高度
private static final int[][] MOVES = {
{1, 0}, // 右移
{-1, 0}, // 左移
{2, 1}, // 右跳（水平2格，垂直1格）
{-2, 1}, // 左跳
{3, 2}, // 大右跳
{1, 2}, // 右上跳
};
public MarioAStar(CellType[][] map, int sx, int sy, int gx, int gy) {
this.map = map;
this.rows = map.length;
this.cols = map[0].length;
this.startX = sx;
this.startY = sy;
this.goalX = gx;
this.goalY = gy;
}
/**
* 启发函数：考虑水平和垂直距离
* 垂直距离权重更高，因为跳跃消耗大
*/
private int heuristic(int x, int y) {
int dx = Math.abs(x - goalX);
int dy = Math.abs(y - goalY);
// 垂直移动更困难，赋予更高权重
return dx + dy * 3;
}
/**
* 计算移动代价
*/
private int moveCost(int fromX, int fromY, int toX, int toY) {
// 基础移动代价
int cost = Math.abs(toX - fromX) + Math.abs(toY - fromY);
// 目标位置类型影响代价
if (!isValid(toX, toY)) return Integer.MAX_VALUE;
switch (map[toY][toX]) {
case ENEMY:
cost += 100; // 避开敌人
break;
case TRAP:
cost += 1000; // 致命陷阱
break;
case COIN:
cost -= 5; // 奖励收集金币
break;
case BRICK:
cost += 10; // 需要跳跃通过
break;
default:
break;
}
return cost;
}
/**
* 检查位置是否有效且可通行
*/
private boolean isValid(int x, int y) {
if (x < 0 || x >= cols || y < 0 || y >= rows) return false;
return map[y][x] != CellType.BRICK;
}
/**
* 执行A*搜索
*/
public List<Node> findPath() {
PriorityQueue<Node> openSet = new PriorityQueue<>(
Comparator.comparingInt(Node::fCost)
);
boolean[][] closedSet = new boolean[rows][cols];
Node start = new Node(startX, startY);
start.gCost = 0;
start.hCost = heuristic(startX, startY);
openSet.add(start);
while (!openSet.isEmpty()) {
Node current = openSet.poll();
if (current.x == goalX && current.y == goalY) {
return reconstructPath(current);
}
if (closedSet[current.y][current.x]) continue;
closedSet[current.y][current.x] = true;
// 扩展邻居节点
for (int[] move : MOVES) {
int nx = current.x + move[0];
int ny = current.y - move[1]; // 向上为y减小的方向
if (!isValid(nx, ny) || closedSet[ny][nx]) continue;
// 模拟跳跃轨迹检查碰撞
if (!isJumpValid(current.x, current.y, nx, ny)) continue;
int newG = current.gCost + moveCost(current.x, current.y, nx, ny);
if (newG < 0) continue; // 溢出检查
Node neighbor = new Node(nx, ny);
neighbor.gCost = newG;
neighbor.hCost = heuristic(nx, ny);
neighbor.parent = current;
openSet.add(neighbor);
}
}
return Collections.emptyList(); // 无路径
}
/**
* 检查跳跃轨迹是否有效（模拟抛物线）
*/
private boolean isJumpValid(int fromX, int fromY, int toX, int toY) {
int steps = Math.max(Math.abs(toX - fromX), Math.abs(toY - fromY));
for (int i = 1; i <= steps; i++) {
int px = fromX + (toX - fromX) * i / steps;
int py = fromY + (toY - fromY) * i / steps;
if (!isValid(px, py)) return false;
}
// 检查落地点是否为空地或目标
return map[toY][toX] != CellType.TRAP && map[toY][toX] != CellType.ENEMY;
}
/**
* 重建路径
*/
private List<Node> reconstructPath(Node node) {
List<Node> path = new ArrayList<>();
while (node != null) {
path.add(node);
node = node.parent;
}
Collections.reverse(path);
return path;
}
}
动态规划优化局部动作
A*给出了宏观路径，但马里奥的实际控制需要更精细的动作序列。对于每个局部区域，我们使用动态规划求解最优动作组合。
状态定义：dp[i][j][v] 表示在第i列、高度j、垂直速度为v时的最小代价。
public class MarioDP {
static final int MAX_HEIGHT = 20;
static final int MAX_VEL = 5;
static final int INF = Integer.MAX_VALUE / 2;
/**
* 局部区域最优动作规划
* @param segment 局部地图段（宽度为segment.length）
* @param startH 起始高度
* @return 最优动作序列和总代价
*/
public static Result planActions(CellType[][] segment, int startH) {
int width = segment[0].length;
int[][][] dp = new int[width][MAX_HEIGHT][MAX_VEL * 2 + 1];
char[][][] action = new char[width][MAX_HEIGHT][MAX_VEL * 2 + 1];
// 初始化
for (int i = 0; i < width; i++)
for (int h = 0; h < MAX_HEIGHT; h++)
Arrays.fill(dp[i][h], INF);
dp[0][startH][MAX_VEL] = 0; // 初始速度为0
for (int x = 0; x < width - 1; x++) {
for (int h = 0; h < MAX_HEIGHT; h++) {
for (int v = 0; v <= MAX_VEL * 2; v++) {
if (dp[x][h][v] == INF) continue;
int vel = v - MAX_VEL; // 实际速度（有正负）
// 尝试三种动作：奔跑、小跳、大跳
for (char act : new char[]{'R', 'J', 'B'}) {
int newVel = vel;
int newH = h;
int cost = dp[x][h][v];
switch (act) {
case 'R': // 奔跑
newVel = Math.max(vel - 1, -MAX_VEL);
newH = Math.max(0, h + newVel);
cost += 1;
break;
case 'J': // 小跳
newVel = Math.min(vel + 2, MAX_VEL);
newH = Math.max(0, h + newVel);
cost += 2;
break;
case 'B': // 大跳
newVel = Math.min(vel + 4, MAX_VEL);
newH = Math.max(0, h + newVel);
cost += 3;
break;
}
// 重力作用
newVel = Math.max(newVel - 1, -MAX_VEL);
newH = Math.max(0, newH - 1);
// 边界和碰撞检查
if (newH >= MAX_HEIGHT) continue;
if (newH < 0 || !isSafe(segment, x + 1, newH)) continue;
// 敌人碰撞惩罚
if (segment[newH][x + 1] == CellType.ENEMY) cost += 50;
// 金币奖励
if (segment[newH][x + 1] == CellType.COIN) cost -= 3;
int nv = newVel + MAX_VEL;
if (cost < dp[x + 1][newH][nv]) {
dp[x + 1][newH][nv] = cost;
action[x + 1][newH][nv] = act;
}
}
}
}
}
// 回溯找最优解
return backtrack(dp, action, width - 1);
}
private static boolean isSafe(CellType[][] seg, int x, int h) {
return h >= 0 && h < seg.length && seg[h][x] != CellType.BRICK && seg[h][x] != CellType.TRAP;
}
static class Result {
List<Character> actions;
int totalCost;
Result(List<Character> a, int c) { actions = a; totalCost = c; }
}
private static Result backtrack(int[][][] dp, char[][][] action, int endX) {
int minCost = INF;
int bestH = 0, bestV = 0;
for (int h = 0; h < MAX_HEIGHT; h++) {
for (int v = 0; v <= MAX_VEL * 2; v++) {
if (dp[endX][h][v] < minCost) {
minCost = dp[endX][h][v];
bestH = h;
bestV = v;
}
}
}
List<Character> acts = new ArrayList<>();
int x = endX, h = bestH, v = bestV;
while (x > 0) {
acts.add(action[x][h][v]);
// 逆向推导前一个状态（简化版）
x--;
}
Collections.reverse(acts);
return new Result(acts, minCost);
}
}
完整运行示例
public class MarioGameDemo {
public static void main(String[] args) {
// 构建一个简单关卡：S=起点, G=终点, B=砖块, E=敌人, C=金币, T=陷阱
CellType[][] level = {
{CellType.EMPTY, CellType.EMPTY, CellType.EMPTY, CellType.EMPTY, CellType.EMPTY, CellType.EMPTY, CellType.GOAL},
{CellType.EMPTY, CellType.EMPTY, CellType.COIN, CellType.EMPTY, CellType.EMPTY, CellType.EMPTY, CellType.EMPTY},
{CellType.EMPTY, CellType.BRICK, CellType.BRICK, CellType.EMPTY, CellType.ENEMY, CellType.EMPTY, CellType.EMPTY},
{CellType.START, CellType.EMPTY, CellType.EMPTY, CellType.BRICK, CellType.EMPTY, CellType.EMPTY, CellType.EMPTY},
};
// 第一步：A*规划宏观路径
MarioAStar astar = new MarioAStar(level, 0, 3, 6, 0);
List<MarioAStar.Node> path = astar.findPath();
System.out.println("A*宏观路径规划结果：");
for (MarioAStar.Node n : path) {
System.out.printf("(%d, %d) -> ", n.x, n.y);
}
System.out.println("终点");
// 第二步：对每段局部路径使用DP优化
System.out.println("\n局部DP动作规划：");
// 实际应用中将路径分段进行DP优化
}
}
算法复杂度分析
- A*算法：时间复杂度为
O(b^d)，其中b是分支因子（平均约4个有效动作），d是最优解深度。在启发函数可采纳的情况下，空间复杂度为O(b^d)。 - 动态规划：状态数为
width × height × velocity，时间复杂度O(width × height × velocity × actions)，空间复杂度相同。对于局部区域（宽度约10-20），完全在可接受范围内。
扩展思路
- 更精细的物理模拟：引入真实重力加速度和惯性，使用更复杂的运动学方程
- 敌人AI交互：预测敌人移动轨迹，使用时序A*或RRT算法
- 强化学习升级：使用DQN或PPO训练端到端的马里奥控制器，超越规则式AI的表现
- 多目标优化：同时优化通关时间、金币收集量和生命值保留，使用NSGA-II等进化算法
