引言
接金币是一款经典的街机小游戏：玩家控制一个篮子或角色在屏幕底部左右移动，接住从上方随机落下的金币，同时避开炸弹或其他障碍物。如何在有限的时间和空间内最大化接住的分数？本文用Java实现一个带AI决策的接金币游戏，核心算法涵盖动态规划最优路径与贪心实时决策两种策略。
算法原理
1. 游戏建模
将游戏离散化为时间步t=0,1,2,…,T：
– 玩家位置：x(t) ∈ [0, W]
– 金币状态：每个金币有位置(p, y)、下落速度v、分值s
– 炸弹状态：位置与金币类似，接住则扣分或游戏结束
2. 动态规划最优路径
若已知所有金币和炸弹的完整轨迹，可将问题建模为：
– 状态：(t, x) 表示t时刻玩家在x位置
– 转移：x(t+1) = x(t) + Δx，其中|Δx| ≤ v_max
– 奖励：该时刻接住的金币分数之和减去炸弹惩罚
通过从后向前递推，可求出全局最优路径。
3. 贪心实时决策
若未来信息未知（更真实的游戏场景），AI只能基于当前可见的金币做贪心决策：
– 优先接分值最高且能在消失前到达的金币
– 同时避开轨迹会交叉的炸弹
Java实现
import java.util.*;
/**
* 接金币游戏AI实现
* 包含动态规划全局最优与贪心实时决策策略
*/
public class CoinCatcher {
// 游戏配置
static final int WIDTH = 20; // 场景宽度
static final int HEIGHT = 15; // 场景高度
static final int MAX_SPEED = 2; // 玩家每步最大移动距离
static final int GAME_STEPS = 50; // 总时间步
// 游戏对象
static class Entity {
int x, y; // 位置
int vy; // 垂直下落速度
int score; // 分值（炸弹为负）
boolean caught;
Entity(int x, int y, int vy, int score) {
this.x = x; this.y = y; this.vy = vy; this.score = score;
this.caught = false;
}
void update() {
y += vy;
}
}
List<Entity> coins = new ArrayList<>();
List<Entity> bombs = new ArrayList<>();
Random rand = new Random();
public CoinCatcher() {
generateLevel();
}
void generateLevel() {
// 生成金币
for (int i = 0; i < 30; i++) {
coins.add(new Entity(
rand.nextInt(WIDTH),
rand.nextInt(HEIGHT / 2),
1 + rand.nextInt(2),
10 + rand.nextInt(41)
));
}
// 生成炸弹
for (int i = 0; i < 8; i++) {
bombs.add(new Entity(
rand.nextInt(WIDTH),
rand.nextInt(HEIGHT / 2),
1 + rand.nextInt(2),
-50
));
}
}
/**
* 动态规划全局最优路径
* 假设已知所有对象轨迹，计算最优移动策略
*/
int[] dpOptimalPath() {
// dp[t][x] = 从t时刻在x位置出发能获得的最大分数
int[][] dp = new int[GAME_STEPS + 1][WIDTH];
int[][] path = new int[GAME_STEPS + 1][WIDTH];
// 预处理：每个时刻每个位置能获得的即时奖励
int[][] reward = new int[GAME_STEPS][WIDTH];
for (int t = 0; t < GAME_STEPS; t++) {
// 模拟到t时刻的所有对象位置
List<Entity> simCoins = simulateEntities(new ArrayList<>(coins), t);
List<Entity> simBombs = simulateEntities(new ArrayList<>(bombs), t);
for (int x = 0; x < WIDTH; x++) {
int r = 0;
for (Entity e : simCoins) {
if (!e.caught && e.y == HEIGHT - 1 && Math.abs(e.x - x) <= 1) {
r += e.score;
}
}
for (Entity e : simBombs) {
if (e.y == HEIGHT - 1 && Math.abs(e.x - x) <= 1) {
r += e.score; // 负分
}
}
reward[t][x] = r;
}
}
// 逆向DP
for (int x = 0; x < WIDTH; x++) {
dp[GAME_STEPS][x] = 0;
}
for (int t = GAME_STEPS - 1; t >= 0; t--) {
for (int x = 0; x < WIDTH; x++) {
int best = Integer.MIN_VALUE;
int bestMove = x;
for (int dx = -MAX_SPEED; dx <= MAX_SPEED; dx++) {
int nx = x + dx;
if (nx < 0 || nx >= WIDTH) continue;
int val = reward[t][nx] + dp[t + 1][nx];
if (val > best) {
best = val;
bestMove = nx;
}
}
dp[t][x] = best;
path[t][x] = bestMove;
}
}
// 重构路径
int[] trajectory = new int[GAME_STEPS];
int curX = WIDTH / 2;
for (int t = 0; t < GAME_STEPS; t++) {
curX = path[t][curX];
trajectory[t] = curX;
}
return trajectory;
}
List<Entity> simulateEntities(List<Entity> entities, int steps) {
for (int s = 0; s < steps; s++) {
for (Entity e : entities) {
if (e.y < HEIGHT - 1) e.update();
}
}
return entities;
}
/**
* 贪心实时策略：每步选择期望收益最高的方向移动
*/
int greedyStep(int playerX, int step) {
int bestMove = 0;
double bestScore = Double.NEGATIVE_INFINITY;
for (int dx = -MAX_SPEED; dx <= MAX_SPEED; dx++) {
int nx = playerX + dx;
if (nx < 0 || nx >= WIDTH) continue;
double score = 0;
// 评估移动到nx的收益
for (Entity c : coins) {
if (c.caught) continue;
// 预测几步后能否接住
int stepsToBottom = (HEIGHT - 1 - c.y + c.vy - 1) / c.vy;
if (stepsToBottom > 3) continue; // 只关心近期能接住的
int predictedX = c.x; // 简化为直线下落
int dist = Math.abs(predictedX - nx);
if (dist <= 1) {
score += c.score * (1.0 / (stepsToBottom + 1));
}
}
for (Entity b : bombs) {
int stepsToBottom = (HEIGHT - 1 - b.y + b.vy - 1) / b.vy;
if (stepsToBottom > 3) continue;
int dist = Math.abs(b.x - nx);
if (dist <= 1) {
score += b.score * 2.0; // 炸弹惩罚权重更高
}
}
if (score > bestScore) {
bestScore = score;
bestMove = dx;
}
}
return playerX + bestMove;
}
/**
* 运行贪心策略完整游戏
*/
int runGreedyGame() {
int playerX = WIDTH / 2;
int totalScore = 0;
for (int t = 0; t < GAME_STEPS; t++) {
// 更新所有对象位置
for (Entity e : coins) if (!e.caught && e.y < HEIGHT - 1) e.update();
for (Entity e : bombs) if (e.y < HEIGHT - 1) e.update();
// 贪心决策
playerX = greedyStep(playerX, t);
// 检测接住
for (Entity c : coins) {
if (!c.caught && c.y == HEIGHT - 1 && Math.abs(c.x - playerX) <= 1) {
c.caught = true;
totalScore += c.score;
}
}
for (Entity b : bombs) {
if (b.y == HEIGHT - 1 && Math.abs(b.x - playerX) <= 1) {
totalScore += b.score;
}
}
}
return totalScore;
}
/**
* 运行DP策略完整游戏
*/
int runDPGame() {
int[] trajectory = dpOptimalPath();
int totalScore = 0;
// 重置对象状态
for (Entity e : coins) e.caught = false;
// 重新生成以保持一致性（简化处理）
coins.clear();
bombs.clear();
generateLevel();
int playerX = WIDTH / 2;
for (int t = 0; t < GAME_STEPS; t++) {
for (Entity e : coins) if (!e.caught && e.y < HEIGHT - 1) e.update();
for (Entity e : bombs) if (e.y < HEIGHT - 1) e.update();
playerX = trajectory[t];
for (Entity c : coins) {
if (!c.caught && c.y == HEIGHT - 1 && Math.abs(c.x - playerX) <= 1) {
c.caught = true;
totalScore += c.score;
}
}
for (Entity b : bombs) {
if (b.y == HEIGHT - 1 && Math.abs(b.x - playerX) <= 1) {
totalScore += b.score;
}
}
}
return totalScore;
}
/**
* 对比两种策略
*/
void compareStrategies(int trials) {
int greedyTotal = 0, dpTotal = 0;
for (int i = 0; i < trials; i++) {
// 贪心策略
coins.clear(); bombs.clear();
generateLevel();
greedyTotal += runGreedyGame();
// DP策略
coins.clear(); bombs.clear();
generateLevel();
dpTotal += runDPGame();
}
System.out.println("===== 接金币策略对比 =====");
System.out.printf("模拟次数: %d%n", trials);
System.out.printf("贪心策略平均得分: %.2f%n", (double) greedyTotal / trials);
System.out.printf("DP最优策略平均得分: %.2f%n", (double) dpTotal / trials);
}
public static void main(String[] args) {
CoinCatcher game = new CoinCatcher();
game.compareStrategies(100);
}
}
复杂度分析
- 动态规划：时间O(T × W × S)，T为时间步数，W为宽度，S为最大移动速度；空间O(T × W)
- 贪心策略：每步评估O(N)，N为活跃对象数；总时间O(T × N)
- 对象模拟：每步O(N)
扩展方向
- 预测模型：若金币有水平漂移，可用卡尔曼滤波预测落点
- 多目标追踪：匈牙利算法匹配玩家与多个金币的最优分配
- 强化学习：用DQN训练端到端的接金币策略
总结
本文实现了接金币游戏的两种AI策略：动态规划在已知完整轨迹时提供全局最优解，贪心策略在信息有限时做出实时决策。通过对比实验可量化两者的性能差距，为不同游戏场景选择合适的算法提供依据。
