地铁跑酷是一款经典的 endless runner（无尽跑酷）游戏，玩家控制角色在三条轨道上奔跑，通过左右切换和跳跃翻滚来躲避障碍物并收集金币。本文用Java实现跑酷游戏的核心AI决策系统。
游戏状态建模
跑酷游戏的状态可以抽象为一个时序决策问题：在每个时间步，AI需要基于当前视野内的障碍物分布选择最优动作。
public class SubwaySurfEngine {
// 轨道编号
enum Track { LEFT, CENTER, RIGHT }
// 动作类型
enum Action { LEFT, RIGHT, JUMP, ROLL, STAY }
// 障碍物类型
enum ObstacleType {
NONE, // 空地
BLOCK_LOW, // 低障碍（需跳跃）
BLOCK_HIGH, // 高障碍（需翻滚）
BLOCK_BOTH, // 高低都有（需切换轨道）
TRAIN, // 火车（需切换轨道）
COIN, // 金币
COIN_LINE, // 金币线（连续金币）
MAGNET, // 磁铁道具
BOOST // 加速道具
}
static class Cell {
ObstacleType type;
int z; // 纵向距离（前方距离）
Track track; // 所属轨道
Cell(ObstacleType type, int z, Track track) {
this.type = type;
this.z = z;
this.track = track;
}
}
static class GameState {
Track currentTrack; // 当前所在轨道
int score;
int speed; // 当前速度（像素/帧）
boolean isJumping;
boolean isRolling;
int jumpFrame; // 跳跃已持续帧数
// 视野内前方网格（z从0到VISUAL_RANGE）
Map<Track, List<Cell>> visibleCells;
GameState() {
this.currentTrack = Track.CENTER;
this.visibleCells = new HashMap<>();
for (Track t : Track.values()) {
visibleCells.put(t, new ArrayList<>());
}
}
}
static final int VISUAL_RANGE = 30; // 视野范围（格数）
static final int JUMP_DURATION = 12; // 跳跃持续帧数
static final int ROLL_DURATION = 8; // 翻滚持续帧数
static final int SWITCH_COOLDOWN = 3; // 切换轨道冷却帧数
private GameState state;
public SubwaySurfEngine() {
this.state = new GameState();
}
}
贪心避障决策
最基础的策略是贪心法：在每个决策点选择当前视野内最优的动作。我们设计一个综合评分函数来评估每个动作的价值。
public class SubwaySurfEngine {
/**
* 评估在指定轨道上前进的前景得分
* 综合考虑：障碍物威胁、金币收益、道具价值
*/
private double evaluateTrack(Track track, int lookAhead) {
double score = 0;
List<Cell> cells = state.visibleCells.get(track);
for (Cell cell : cells) {
if (cell.z > lookAhead) continue;
double distanceWeight = 1.0 / (cell.z + 1); // 越近的权重越高
switch (cell.type) {
case NONE -> score += 1 * distanceWeight; // 安全通行奖励
case BLOCK_LOW -> {
if (cell.z < 5) score -= 100 * distanceWeight; // 近处低障碍致命
else score -= 10 * distanceWeight;
}
case BLOCK_HIGH -> {
if (cell.z < 4) score -= 100 * distanceWeight;
else score -= 10 * distanceWeight;
}
case BLOCK_BOTH -> score -= 150 * distanceWeight; // 必须切换
case TRAIN -> score -= 200 * distanceWeight; // 火车最危险
case COIN -> score += 15 * distanceWeight; // 金币奖励
case COIN_LINE -> score += 30 * distanceWeight; // 金币线更值
case MAGNET -> score += 50 * distanceWeight; // 道具高价值
case BOOST -> score += 60 * distanceWeight;
}
}
return score;
}
/**
* 贪心决策：选择立即收益最高的动作
*/
public Action greedyDecision() {
Action bestAction = Action.STAY;
double bestScore = Double.NEGATIVE_INFINITY;
for (Action action : Action.values()) {
if (!isActionValid(action)) continue;
double score = evaluateAction(action);
if (score > bestScore) {
bestScore = score;
bestAction = action;
}
}
return bestAction;
}
/**
* 评估执行某个动作后的预期收益
*/
private double evaluateAction(Action action) {
Track targetTrack = state.currentTrack;
boolean willJump = state.isJumping;
boolean willRoll = state.isRolling;
switch (action) {
case LEFT -> targetTrack = getLeftTrack(state.currentTrack);
case RIGHT -> targetTrack = getRightTrack(state.currentTrack);
case JUMP -> willJump = true;
case ROLL -> willRoll = true;
case STAY -> {} // 保持当前
}
if (targetTrack == null) return Double.NEGATIVE_INFINITY;
// 基础轨道评分
double score = evaluateTrack(targetTrack, VISUAL_RANGE);
// 动作额外评分
if (action == Action.JUMP && !state.isJumping) {
// 跳跃可以越过近处的低障碍
score += handleJumpBonus(targetTrack);
}
if (action == Action.ROLL && !state.isRolling) {
// 翻滚可以穿过近处的高障碍
score += handleRollBonus(targetTrack);
}
// 避免频繁切换轨道（动作连贯性奖励）
if (action == Action.STAY) score += 2;
return score;
}
/**
* 跳跃的额外收益：评估可以越过的障碍物
*/
private double handleJumpBonus(Track track) {
double bonus = 0;
List<Cell> cells = state.visibleCells.get(track);
for (Cell cell : cells) {
if (cell.z >= 1 && cell.z <= JUMP_DURATION && cell.type == ObstacleType.BLOCK_LOW) {
bonus += 50; // 成功越过低障碍
}
}
return bonus;
}
/**
* 翻滚的额外收益
*/
private double handleRollBonus(Track track) {
double bonus = 0;
List<Cell> cells = state.visibleCells.get(track);
for (Cell cell : cells) {
if (cell.z >= 1 && cell.z <= ROLL_DURATION && cell.type == ObstacleType.BLOCK_HIGH) {
bonus += 50;
}
}
return bonus;
}
private boolean isActionValid(Action action) {
if (state.isJumping && (action == Action.JUMP || action == Action.ROLL)) return false;
if (state.isRolling && (action == Action.ROLL || action == Action.JUMP)) return false;
if (action == Action.LEFT && state.currentTrack == Track.LEFT) return false;
if (action == Action.RIGHT && state.currentTrack == Track.RIGHT) return false;
return true;
}
private Track getLeftTrack(Track t) {
return switch (t) {
case LEFT -> null;
case CENTER -> Track.LEFT;
case RIGHT -> Track.CENTER;
};
}
private Track getRightTrack(Track t) {
return switch (t) {
case LEFT -> Track.CENTER;
case CENTER -> Track.RIGHT;
case RIGHT -> null;
};
}
}
动态规划路径规划
贪心策略只考虑一步收益，在复杂场景下可能陷入局部最优。动态规划可以规划未来多步的最优动作序列。
public class SubwaySurfEngine {
// DP状态：(帧数, 轨道, 是否在跳跃, 是否在翻滚)
static class DPState {
int frame;
Track track;
boolean jumping;
boolean rolling;
DPState(int f, Track t, boolean j, boolean r) {
this.frame = f; this.track = t;
this.jumping = j; this.rolling = r;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof DPState)) return false;
DPState other = (DPState) o;
return frame == other.frame && track == other.track
&& jumping == other.jumping && rolling == other.rolling;
}
@Override
public int hashCode() {
return Objects.hash(frame, track, jumping, rolling);
}
}
/**
* 使用动态规划规划未来PLANNING_HORIZON步的最优动作序列
*/
public List<Action> planOptimalPath(int planningHorizon) {
// dp[state] = 从该状态出发的最大未来收益
Map<DPState, Double> dp = new HashMap<>();
Map<DPState, Action> policy = new HashMap<>();
// 逆向DP：从最后一步往前推
for (int f = planningHorizon; f >= 0; f--) {
for (Track t : Track.values()) {
for (boolean j : new boolean[]{false, true}) {
for (boolean r : new boolean[]{false, true}) {
if (j && r) continue; // 不能同时跳跃和翻滚
DPState s = new DPState(f, t, j, r);
if (f == planningHorizon) {
dp.put(s, 0.0);
continue;
}
double bestValue = Double.NEGATIVE_INFINITY;
Action bestAction = Action.STAY;
for (Action action : getValidActions(t, j, r)) {
DPState next = simulateAction(s, action);
if (next == null) continue;
double immediate = getImmediateReward(s, action);
double future = dp.getOrDefault(next, 0.0);
double total = immediate + future * 0.95; // 折扣因子
if (total > bestValue) {
bestValue = total;
bestAction = action;
}
}
dp.put(s, bestValue);
policy.put(s, bestAction);
}
}
}
}
// 回溯构造最优动作序列
List<Action> plan = new ArrayList<>();
DPState current = new DPState(0, state.currentTrack, state.isJumping, state.isRolling);
for (int f = 0; f < planningHorizon; f++) {
Action action = policy.get(current);
if (action == null) break;
plan.add(action);
current = simulateAction(current, action);
}
return plan;
}
/**
* 模拟执行一个动作，返回下一状态
*/
private DPState simulateAction(DPState s, Action action) {
Track newTrack = s.track;
boolean newJump = s.jumping;
boolean newRoll = s.rolling;
int newJumpFrame = s.jumping ? 1 : 0;
int newRollFrame = s.rolling ? 1 : 0;
switch (action) {
case LEFT -> {
newTrack = getLeftTrack(s.track);
if (newTrack == null) return null;
}
case RIGHT -> {
newTrack = getRightTrack(s.track);
if (newTrack == null) return null;
}
case JUMP -> {
if (s.jumping || s.rolling) return null;
newJump = true;
}
case ROLL -> {
if (s.rolling || s.jumping) return null;
newRoll = true;
}
case STAY -> {}
}
// 更新跳跃/翻滚状态
if (s.jumping && newJumpFrame >= JUMP_DURATION) newJump = false;
if (s.rolling && newRollFrame >= ROLL_DURATION) newRoll = false;
// 碰撞检测
if (isColliding(newTrack, s.frame + 1, newJump, newRoll)) return null;
return new DPState(s.frame + 1, newTrack, newJump, newRoll);
}
/**
* 碰撞检测
*/
private boolean isColliding(Track track, int frame, boolean jumping, boolean rolling) {
List<Cell> cells = state.visibleCells.get(track);
for (Cell cell : cells) {
if (cell.z != frame) continue;
switch (cell.type) {
case BLOCK_LOW -> { if (!jumping) return true; }
case BLOCK_HIGH -> { if (!rolling) return true; }
case BLOCK_BOTH, TRAIN -> return true; // 无法通过动作躲避
default -> {}
}
}
return false;
}
/**
* 计算立即奖励
*/
private double getImmediateReward(DPState s, Action action) {
Track track = s.track;
if (action == Action.LEFT) track = getLeftTrack(track);
if (action == Action.RIGHT) track = getRightTrack(track);
double reward = 1; // 存活奖励
List<Cell> cells = state.visibleCells.get(track);
for (Cell cell : cells) {
if (cell.z == s.frame + 1) {
switch (cell.type) {
case COIN -> reward += 10;
case COIN_LINE -> reward += 20;
case MAGNET -> reward += 30;
case BOOST -> reward += 40;
default -> {}
}
}
}
return reward;
}
private List<Action> getValidActions(Track t, boolean j, boolean r) {
List<Action> valid = new ArrayList<>();
valid.add(Action.STAY);
if (!j && !r) {
valid.add(Action.JUMP);
valid.add(Action.ROLL);
}
if (t != Track.LEFT) valid.add(Action.LEFT);
if (t != Track.RIGHT) valid.add(Action.RIGHT);
return valid;
}
}
障碍物生成与视野更新
public class SubwaySurfEngine {
private final Random random = new Random();
/**
* 生成新的视野内容（模拟游戏世界向前滚动）
*/
public void advanceFrame() {
// 更新跳跃/翻滚状态
if (state.isJumping) {
state.jumpFrame++;
if (state.jumpFrame >= JUMP_DURATION) {
state.isJumping = false;
state.jumpFrame = 0;
}
}
// 所有障碍物向前移动一格
for (List<Cell> cells : state.visibleCells.values()) {
cells.forEach(c -> c.z--);
cells.removeIf(c -> c.z < 0);
}
// 在视野远端生成新内容
generateNewContent(VISUAL_RANGE);
// 速度逐渐提升
state.speed = Math.min(state.speed + 1, 300);
}
/**
* 在指定距离生成新障碍物/金币
*/
private void generateNewContent(int z) {
// 确保至少有一条安全轨道
boolean[] safe = {true, true, true};
for (int i = 0; i < 3; i++) {
Track track = Track.values()[i];
double obstacleProb = 0.3 + state.speed / 1000.0; // 速度越快障碍越多
if (random.nextDouble() < obstacleProb) {
ObstacleType type = generateObstacleType();
state.visibleCells.get(track).add(new Cell(type, z, track));
safe[i] = (type == ObstacleType.NONE);
} else if (random.nextDouble() < 0.4) {
// 生成金币
ObstacleType coinType = random.nextBoolean() ? ObstacleType.COIN : ObstacleType.COIN_LINE;
state.visibleCells.get(track).add(new Cell(coinType, z, track));
}
}
// 如果三条轨道都有致命障碍，随机清除一条
if (!safe[0] && !safe[1] && !safe[2]) {
int clearTrack = random.nextInt(3);
state.visibleCells.get(Track.values()[clearTrack]).removeIf(c -> c.z == z);
}
}
private ObstacleType generateObstacleType() {
double r = random.nextDouble();
if (r < 0.4) return ObstacleType.BLOCK_LOW;
if (r < 0.7) return ObstacleType.BLOCK_HIGH;
if (r < 0.85) return ObstacleType.BLOCK_BOTH;
return ObstacleType.TRAIN;
}
}
运行演示
public class SubwaySurfDemo {
public static void main(String[] args) {
SubwaySurfEngine engine = new SubwaySurfEngine();
System.out.println("=== 地铁跑酷AI演示 ===");
int frames = 0;
int totalCoins = 0;
while (frames < 1000) { // 模拟1000帧
frames++;
// AI决策
SubwaySurfEngine.Action action = engine.greedyDecision();
System.out.printf("帧%4d: 动作=%s | ", frames, action);
// 执行动作并前进
engine.executeAction(action);
engine.advanceFrame();
// 统计
totalCoins += engine.getCoinsCollectedThisFrame();
if (engine.isGameOver()) {
System.out.println("\n游戏结束！存活帧数: " + frames);
break;
}
}
System.out.println("\n总存活帧数: " + frames);
System.out.println("收集金币: " + totalCoins);
}
}
算法复杂度分析
- 贪心决策：每帧评估5个动作，每个动作扫描视野内约
VISUAL_RANGE个格子，时间复杂度O(VISUAL_RANGE × ACTIONS)，即O(150)每帧，完全满足实时性要求。 - 动态规划路径规划：状态空间为
planningHorizon × tracks × jumpStates × rollStates，时间复杂度O(horizon × 3 × 2 × 2 × 5)。对于horizon=20，约1200次操作，可每几帧执行一次更新长期策略。 - 碰撞检测：每帧每个轨道检查前方一格，
O(tracks)。
扩展方向
- 强化学习升级：使用PPO或DQN训练端到端策略网络，学习超越规则引擎的复杂操作
- 多目标优化：同时优化存活时间、金币收集、道具使用效率，使用NSGA-II求解帕累托前沿
- 预测模型：基于LSTM预测障碍物的生成模式，提前规划数秒后的路径
- 物理精细模拟：引入真实的重力、惯性和碰撞体积，提升AI操作的精确度
