引言
大金刚（Donkey Kong）是任天堂于1981年推出的经典街机游戏，玩家控制 Jumpman（即后来的马里奥）在多层平台间跳跃，躲避大金刚投掷的滚筒，最终拯救公主。本文将用 Java 实现大金刚的 AI 控制系统，核心聚焦于平台跳跃中的 A*寻路算法 与 跳跃时机决策，让 AI 能够自主规划路径并选择最佳起跳时刻。
游戏场景建模
在大金刚的平台关卡中，场景可以抽象为一个二维网格图：
– 平台（Platform）：可站立的地面，AI 只能在平台上水平移动
– 梯子（Ladder）：连接上下层平台的垂直通道
– 空隙（Gap）：平台之间的间隙，需要通过跳跃跨越
– 障碍物（Barrel）：大金刚投掷的滚筒，AI 需要躲避
AI 的核心任务是：从当前位置出发，找到一条安全路径到达公主所在位置，同时避开移动中的滚筒。
核心算法设计
A*寻路算法
A* 算法是启发式搜索的经典代表，通过评估函数 f(n) = g(n) + h(n) 来指导搜索方向：
– g(n)：从起点到节点 n 的实际代价（移动距离 + 跳跃风险）
– h(n)：从节点 n 到终点的启发式估计（曼哈顿距离或欧几里得距离）
在大金刚场景中，传统的网格 A 需要扩展为平台图 A**：
– 节点：每个可站立位置（平台端点、梯子入口、跳跃起点）
– 边：水平移动、爬梯子、跳跃跨越空隙
– 边权：移动耗时 + 跳跃风险系数 + 滚筒威胁评估
跳跃时机决策
跳跃是大金刚中最关键的操作。AI 需要判断：
1. 何时起跳：当前平台末端前方有空隙，且目标平台在跳跃范围内
2. 跳跃角度：根据水平距离和垂直高度差计算初始速度向量
3. 落点安全：预测落点是否在目标平台上，且落点附近无滚筒
我们使用简单的抛体运动模型：
x = v0x * t
y = v0y * t - 0.5 * g * t^2
通过反解方程，得到起跳速度，再判断轨迹是否安全。
Java 实现
import java.util.*;
/**
* 大金刚 AI：A*寻路与跳跃时机决策
*/
public class DonkeyKongAI {
// 物理常量
static final double GRAVITY = 0.5;
static final double MAX_JUMP_H_SPEED = 4.0;
static final double MAX_JUMP_V_SPEED = 8.0;
// 场景元素
static class Platform {
int x1, x2, y; // 平台左端、右端、高度
Platform(int x1, int x2, int y) {
this.x1 = x1; this.x2 = x2; this.y = y;
}
boolean contains(int x) {
return x >= x1 && x <= x2;
}
}
static class Ladder {
int x, y1, y2; // 梯子水平位置、底部高度、顶部高度
Ladder(int x, int y1, int y2) {
this.x = x; this.y1 = y1; this.y2 = y2;
}
}
static class Barrel {
int x, y;
int vx; // 滚筒水平速度
Barrel(int x, int y, int vx) {
this.x = x; this.y = y; this.vx = vx;
}
// 预测 t 帧后的位置
int predictX(int t) {
return x + vx * t;
}
}
// A* 节点
static class Node implements Comparable<Node> {
int x, y; // 位置
double g; // 实际代价
double h; // 启发值
Node parent; // 父节点
String action; // 到达此节点的动作
Node(int x, int y) {
this.x = x; this.y = y;
}
double f() { return g + h; }
@Override
public int compareTo(Node o) {
return Double.compare(this.f(), o.f());
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Node)) return false;
Node n = (Node) o;
return x == n.x && y == n.y;
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
}
List<Platform> platforms;
List<Ladder> ladders;
List<Barrel> barrels;
public DonkeyKongAI(List<Platform> p, List<Ladder> l, List<Barrel> b) {
this.platforms = p;
this.ladders = l;
this.barrels = b;
}
/**
* A* 寻路主函数
*/
public List<Node> findPath(int startX, int startY, int goalX, int goalY) {
PriorityQueue<Node> open = new PriorityQueue<>();
Set<String> closed = new HashSet<>();
Map<String, Node> bestNode = new HashMap<>();
Node start = new Node(startX, startY);
start.g = 0;
start.h = heuristic(startX, startY, goalX, goalY);
open.add(start);
bestNode.put(key(startX, startY), start);
while (!open.isEmpty()) {
Node cur = open.poll();
if (cur.x == goalX && cur.y == goalY) {
return reconstructPath(cur);
}
if (closed.contains(key(cur.x, cur.y))) continue;
closed.add(key(cur.x, cur.y));
// 生成邻居：水平移动、爬梯子、跳跃
List<Node> neighbors = generateNeighbors(cur);
for (Node next : neighbors) {
if (closed.contains(key(next.x, next.y))) continue;
double edgeCost = computeEdgeCost(cur, next);
double newG = cur.g + edgeCost;
String k = key(next.x, next.y);
if (!bestNode.containsKey(k) || newG < bestNode.get(k).g) {
next.g = newG;
next.h = heuristic(next.x, next.y, goalX, goalY);
next.parent = cur;
bestNode.put(k, next);
open.add(next);
}
}
}
return Collections.emptyList(); // 无路径
}
/**
* 启发函数：考虑曼哈顿距离 + 层数差距
*/
double heuristic(int x1, int y1, int x2, int y2) {
return Math.abs(x1 - x2) + Math.abs(y1 - y2) * 2;
}
String key(int x, int y) {
return x + "," + y;
}
/**
* 生成当前节点的所有可达邻居
*/
List<Node> generateNeighbors(Node cur) {
List<Node> neighbors = new ArrayList<>();
// 1. 水平移动：向左右移动到平台边缘
Platform curPlatform = getPlatformAt(cur.x, cur.y);
if (curPlatform != null) {
// 向左走到平台左端
neighbors.add(new Node(curPlatform.x1, cur.y));
// 向右走到平台右端
neighbors.add(new Node(curPlatform.x2, cur.y));
}
// 2. 爬梯子：如果站在梯子位置，可以上下移动
for (Ladder ladder : ladders) {
if (ladder.x == cur.x && cur.y >= ladder.y1 && cur.y <= ladder.y2) {
neighbors.add(new Node(ladder.x, ladder.y1)); // 梯子底部
neighbors.add(new Node(ladder.x, ladder.y2)); // 梯子顶部
}
}
// 3. 跳跃：从平台边缘跳跃到相邻平台
if (curPlatform != null) {
for (Platform target : platforms) {
if (target == curPlatform) continue;
// 检查是否可以通过跳跃到达
if (canJump(curPlatform, target)) {
// 跳跃落点取目标平台最近点
int landX = clamp(cur.x, target.x1, target.x2);
neighbors.add(new Node(landX, target.y));
}
}
}
return neighbors;
}
/**
* 判断是否可以从一个平台跳跃到另一个平台
*/
boolean canJump(Platform from, Platform to) {
// 水平距离不能太远
int hDist = Math.min(
Math.abs(from.x1 - to.x2),
Math.abs(from.x2 - to.x1)
);
if (hDist > 120) return false; // 最大跳跃水平距离
// 垂直高度差不能太大
int vDist = Math.abs(from.y - to.y);
if (vDist > 80) return false; // 最大跳跃垂直距离
return true;
}
/**
* 计算两个节点之间的边代价
*/
double computeEdgeCost(Node from, Node to) {
double baseCost = Math.abs(from.x - to.x) + Math.abs(from.y - to.y);
// 跳跃额外代价
if (Math.abs(from.y - to.y) > 0 && !onSamePlatform(from, to)) {
baseCost += 50; // 跳跃有固定风险代价
}
// 滚筒威胁评估：预测路径上是否有滚筒
baseCost += barrelThreatCost(from, to);
return baseCost;
}
/**
* 评估滚筒对路径的威胁程度
*/
double barrelThreatCost(Node from, Node to) {
double threat = 0;
int steps = Math.max(Math.abs(to.x - from.x), Math.abs(to.y - from.y)) / 5 + 1;
for (int i = 0; i <= steps; i++) {
int px = from.x + (to.x - from.x) * i / steps;
int py = from.y + (to.y - from.y) * i / steps;
for (Barrel b : barrels) {
int predX = b.predictX(i);
int dist = Math.abs(predX - px) + Math.abs(b.y - py);
if (dist < 30) {
threat += (30 - dist) * 10; // 距离越近威胁越大
}
}
}
return threat;
}
/**
* 判断两个节点是否在同一平台上
*/
boolean onSamePlatform(Node a, Node b) {
for (Platform p : platforms) {
if (p.contains(a.x) && p.y == a.y && p.contains(b.x) && p.y == b.y) {
return true;
}
}
return false;
}
Platform getPlatformAt(int x, int y) {
for (Platform p : platforms) {
if (p.y == y && p.contains(x)) return p;
}
return null;
}
int clamp(int v, int min, int max) {
return Math.max(min, Math.min(max, v));
}
List<Node> reconstructPath(Node goal) {
List<Node> path = new ArrayList<>();
Node cur = goal;
while (cur != null) {
path.add(0, cur);
cur = cur.parent;
}
return path;
}
/**
* 跳跃时机决策：计算起跳初速度并验证轨迹安全
*/
public JumpDecision decideJump(int fromX, int fromY, int toX, int toY) {
double dx = toX - fromX;
double dy = toY - fromY; // 注意：y轴向下为正，所以目标是更高的平台时dy为负
// 使用抛体运动反解：给定水平距离dx和垂直距离dy，求初速度
// 选择最省力的起跳角度，使v0y最小
// 解方程：dy = v0y * t - 0.5 * g * t^2, dx = v0x * t
// 消去 t = dx / v0x，得到关于 v0x, v0y 的约束
double bestV0x = 0, bestV0y = 0;
double minEnergy = Double.MAX_VALUE;
boolean feasible = false;
// 在允许的速度范围内搜索最优解
for (double v0x = 1.0; v0x <= MAX_JUMP_H_SPEED; v0x += 0.2) {
double t = dx / v0x;
if (t <= 0) continue;
double v0y = (dy + 0.5 * GRAVITY * t * t) / t;
if (Math.abs(v0y) <= MAX_JUMP_V_SPEED) {
double energy = v0x * v0x + v0y * v0y;
if (energy < minEnergy) {
minEnergy = energy;
bestV0x = v0x;
bestV0y = v0y;
feasible = true;
}
}
}
if (!feasible) {
return new JumpDecision(false, 0, 0);
}
// 验证跳跃轨迹是否安全（无滚筒碰撞）
boolean safe = checkTrajectorySafe(fromX, fromY, toX, toY, bestV0x, bestV0y);
return new JumpDecision(safe, bestV0x, bestV0y);
}
/**
* 检查跳跃轨迹是否与滚筒相交
*/
boolean checkTrajectorySafe(int fromX, int fromY, int toX, int toY, double v0x, double v0y) {
double t = (toX - fromX) / v0x;
int steps = (int)(t / 2) + 1; // 每2帧检测一次
for (int i = 0; i <= steps; i++) {
double time = i * 2;
if (time > t) time = t;
double px = fromX + v0x * time;
double py = fromY + v0y * time - 0.5 * GRAVITY * time * time;
for (Barrel b : barrels) {
int bx = b.predictX((int)time);
double dist = Math.hypot(px - bx, py - b.y);
if (dist < 20) return false; // 与滚筒太近，不安全
}
}
return true;
}
static class JumpDecision {
boolean safe;
double v0x, v0y;
JumpDecision(boolean safe, double v0x, double v0y) {
this.safe = safe; this.v0x = v0x; this.v0y = v0y;
}
}
// 主程序：演示 AI 寻路
public static void main(String[] args) {
// 构建大金刚第一关的简化场景
List<Platform> platforms = Arrays.asList(
new Platform(50, 350, 400), // 最底层
new Platform(100, 300, 320), // 第二层左侧
new Platform(350, 550, 320), // 第二层右侧
new Platform(150, 450, 240), // 第三层
new Platform(200, 400, 160), // 第四层（公主所在层）
new Platform(300, 500, 80) // 顶层（大金刚位置）
);
List<Ladder> ladders = Arrays.asList(
new Ladder(120, 320, 400),
new Ladder(380, 240, 320),
new Ladder(200, 160, 240),
new Ladder(350, 80, 160)
);
List<Barrel> barrels = Arrays.asList(
new Barrel(300, 80, 2),
new Barrel(150, 400, -1)
);
DonkeyKongAI ai = new DonkeyKongAI(platforms, ladders, barrels);
// AI 从起点寻找通往公主的路径
int startX = 80, startY = 400;
int goalX = 350, goalY = 80;
List<Node> path = ai.findPath(startX, startY, goalX, goalY);
System.out.println("=== 大金刚 AI 寻路结果 ===");
System.out.println("路径节点数：" + path.size());
for (int i = 0; i < path.size(); i++) {
Node n = path.get(i);
System.out.printf("步骤 %d: (%d, %d)%n", i, n.x, n.y);
// 如果是跳跃动作，显示跳跃决策
if (i > 0) {
Node prev = path.get(i - 1);
if (!ai.onSamePlatform(prev, n)) {
JumpDecision jd = ai.decideJump(prev.x, prev.y, n.x, n.y);
System.out.printf(" → 跳跃决策: 安全=%s, 水平速度=%.2f, 垂直速度=%.2f%n",
jd.safe, jd.v0x, jd.v0y);
}
}
}
}
}
算法解析
为什么使用 A* 而不是 BFS？
在大金刚的平台场景中，状态空间虽然离散化后规模可控，但节点之间的边权并不均匀（水平移动成本低、跳跃成本高、受滚筒威胁的路径代价高）。A 的启发式函数能够快速引导搜索向目标方向前进，避免 BFS 的无差别扩展。对于 6 层平台、每层约 5 个关键节点的场景，A 通常在 20-50 次迭代内即可找到最优路径。
滚筒威胁评估的动态性
滚筒是移动障碍物，其位置随时间变化。我们的 barrelThreatCost 方法通过预测滚筒在路径各阶段的未来位置，动态调整边权。这使得 AI 能够：
– 选择滚筒远离的梯子
– 等待滚筒通过后再起跳
– 选择更安全的上层路线绕行
跳跃决策的物理约束
跳跃不是简单的瞬移，而是受重力约束的抛体运动。decideJump 方法在允许的速度范围内搜索能量最小的起跳方案，同时用 checkTrajectorySafe 验证飞行过程中不会与滚筒碰撞。这种”规划+验证”的两阶段决策确保 AI 的跳跃既物理可行又安全。
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| A* 寻路 | O(b^d)，其中 b 为分支因子（通常 ≤8），d 为解深度 | O(V)，V 为访问节点数 |
| 邻居生成 | O(P + L)，P 为平台数，L 为梯子数 | O(1) |
| 跳跃决策 | O(Vmax / Δv)，搜索速度空间 | O(1) |
| 轨迹安全检测 | O(T * B)，T 为时间步数，B 为滚筒数 | O(1) |
对于典型的平台关卡（平台数 < 20，梯子数 < 10），单次寻路可在毫秒级完成，适合实时游戏 AI。
扩展思路
- 更精细的启发函数：可以加入”离滚筒越远越好”的次目标，使路径不仅短而且安全
- 多帧规划：将滚筒运动建模为马尔可夫链，预测未来多帧的威胁分布
- 学习跳跃策略：用强化学习（Q-Learning）训练 AI 在复杂平台布局中的跳跃时机
总结
本文通过 Java 实现了一个完整的大金刚 AI 系统，核心贡献在于：
– 将平台跳跃游戏场景抽象为平台图，使 A 算法适用于非网格环境
– 引入动态威胁评估，让寻路结果能够规避移动障碍物
– 结合抛体运动模型*进行跳跃决策，确保物理可行性与安全性
读者可以从中学到：A* 算法的图抽象技巧、启发式函数的设计方法、以及物理约束与路径规划的结合方式。
