引言
Flappy Bird 是一款现象级的休闲游戏：玩家通过点击屏幕控制小鸟跳跃，穿过不断出现的管道间隙。看似简单，但要让 AI 无限存活却需要精密的决策算法。本文用 Java 实现该游戏的 AI 控制器，核心采用动态规划（Dynamic Programming）配合状态空间离散化，在离散的决策时点上计算最优跳跃策略，使小鸟获得理论上最长的期望生存时间。
核心算法思路
1. 状态空间建模
Flappy Bird 的连续状态空间包含：
– 小鸟垂直位置 y 和垂直速度 vy
– 下一根管道的水平距离 dx
– 下管道口上沿高度 gapY
为应用动态规划，需将连续状态离散化为网格：
– 高度分桶：将屏幕高度划分为 H 个区间
– 速度分桶：将垂直速度划分为 V 个区间
– 水平距离分桶：将到下一管道的距离划分为 D 个区间
– 间隙高度分桶：将管道间隙位置划分为 G 个区间
2. 动态规划方程
定义 V(s) 为状态 s 下的期望剩余生存步数：
– 若状态 s 导致碰撞，V(s) = 0
– 否则 V(s) = 1 + max(V(s_next_jump), V(s_next_fall))
其中 s_next_jump 和 s_next_fall 分别表示”跳跃”和”不跳”后的后继状态。
3. 值迭代求解
由于状态转移确定，可用值迭代从终止状态反向更新，直到收敛。实际游戏中采用在线查表，根据当前离散化状态直接读取预计算的决策。
Java 实现
import java.util.*;
/**
* Flappy Bird AI - 动态规划状态离散化与最优跳跃控制
*/
public class FlappyBirdDP {
// 游戏物理参数
static final double GRAVITY = 0.5; // 每帧重力加速度
static final double JUMP_VELOCITY = -6.0; // 跳跃初速度（向上为负）
static final int SCREEN_HEIGHT = 400; // 屏幕高度
static final int SCREEN_WIDTH = 300; // 屏幕宽度
static final int BIRD_SIZE = 20; // 小鸟尺寸
static final int PIPE_WIDTH = 50; // 管道宽度
static final int GAP_HEIGHT = 100; // 管道间隙高度
static final int PIPE_SPEED = 3; // 管道左移速度
static final int GROUND_Y = 380; // 地面位置
// 离散化分桶数
static final int BUCKETS_Y = 20; // 高度分桶
static final int BUCKETS_VY = 12; // 速度分桶
static final int BUCKETS_DX = 15; // 水平距离分桶
static final int BUCKETS_GAP = 10; // 间隙位置分桶
// DP 表: value[y][vy][dx][gap] = 期望剩余生存帧数
// action[y][vy][dx][gap] = true 表示应跳跃
double[][][][] value;
boolean[][][][] action;
public FlappyBirdDP() {
value = new double[BUCKETS_Y][BUCKETS_VY][BUCKETS_DX][BUCKETS_GAP];
action = new boolean[BUCKETS_Y][BUCKETS_VY][BUCKETS_DX][BUCKETS_GAP];
}
// 连续值 -> 离散桶索引
int bucketY(double y) {
int b = (int)(y / SCREEN_HEIGHT * BUCKETS_Y);
return Math.max(0, Math.min(BUCKETS_Y - 1, b));
}
int bucketVy(double vy) {
double minV = -10, maxV = 10;
int b = (int)((vy - minV) / (maxV - minV) * BUCKETS_VY);
return Math.max(0, Math.min(BUCKETS_VY - 1, b));
}
int bucketDx(double dx) {
int maxDx = SCREEN_WIDTH;
int b = (int)(dx / maxDx * BUCKETS_DX);
return Math.max(0, Math.min(BUCKETS_DX - 1, b));
}
int bucketGap(double gapY) {
int b = (int)(gapY / (SCREEN_HEIGHT - GAP_HEIGHT) * BUCKETS_GAP);
return Math.max(0, Math.min(BUCKETS_GAP - 1, b));
}
// 检查是否碰撞
boolean isCollision(double birdY, double vy, double pipeX, double gapY) {
double birdX = 50; // 小鸟水平位置固定
// 地面碰撞
if (birdY + BIRD_SIZE >= GROUND_Y) return true;
// 天花板碰撞
if (birdY < 0) return true;
// 管道碰撞（小鸟与管道水平重叠时）
if (birdX + BIRD_SIZE >= pipeX && birdX <= pipeX + PIPE_WIDTH) {
if (birdY < gapY || birdY + BIRD_SIZE > gapY + GAP_HEIGHT) {
return true;
}
}
return false;
}
/**
* 预计算 DP 表（值迭代）
* 简化为：在每一帧决定跳跃或不跳，最大化期望存活帧数
*/
public void computePolicy() {
int maxIter = 100;
double gamma = 0.995; // 折扣因子
for (int iter = 0; iter < maxIter; iter++) {
double maxDiff = 0;
for (int by = 0; by < BUCKETS_Y; by++) {
for (int bvy = 0; bvy < BUCKETS_VY; bvy++) {
for (int bdx = 0; bdx < BUCKETS_DX; bdx++) {
for (int bgap = 0; bgap < BUCKETS_GAP; bgap++) {
// 还原代表值
double y = (by + 0.5) * SCREEN_HEIGHT / BUCKETS_Y;
double minV = -10, maxV = 10;
double vy = minV + (bvy + 0.5) * (maxV - minV) / BUCKETS_VY;
double dx = (bdx + 0.5) * SCREEN_WIDTH / BUCKETS_DX;
double gapY = (bgap + 0.5) * (SCREEN_HEIGHT - GAP_HEIGHT) / BUCKETS_GAP;
// 检查当前是否已碰撞
if (isCollision(y, vy, dx, gapY)) {
double diff = Math.abs(value[by][bvy][bdx][bgap] - 0);
maxDiff = Math.max(maxDiff, diff);
value[by][bvy][bdx][bgap] = 0;
continue;
}
// 跳跃后的状态
double yJump = y + JUMP_VELOCITY + GRAVITY;
double vyJump = JUMP_VELOCITY + GRAVITY;
double dxNext = dx - PIPE_SPEED;
if (dxNext < -PIPE_WIDTH) {
// 管道已通过，生成新管道
dxNext = SCREEN_WIDTH;
gapY = 50 + Math.random() * (SCREEN_HEIGHT - GAP_HEIGHT - 100);
}
int bjY = bucketY(yJump);
int bjVy = bucketVy(vyJump);
int bjDx = bucketDx(dxNext);
int bjGap = bucketGap(gapY);
double vJump = 1 + gamma * value[bjY][bjVy][bjDx][bjGap];
if (isCollision(yJump, vyJump, dxNext, gapY)) vJump = 0;
// 不跳后的状态
double yFall = y + vy + GRAVITY;
double vyFall = vy + GRAVITY;
int bfY = bucketY(yFall);
int bfVy = bucketVy(vyFall);
int bfDx = bucketDx(dxNext);
int bfGap = bucketGap(gapY);
double vFall = 1 + gamma * value[bfY][bfVy][bfDx][bfGap];
if (isCollision(yFall, vyFall, dxNext, gapY)) vFall = 0;
double best = Math.max(vJump, vFall);
double diff = Math.abs(value[by][bvy][bdx][bgap] - best);
maxDiff = Math.max(maxDiff, diff);
value[by][bvy][bdx][bgap] = best;
action[by][bvy][bdx][bgap] = vJump > vFall;
}
}
}
}
if (maxDiff < 0.001) {
System.out.println("DP 收敛于迭代 " + iter);
break;
}
}
}
/**
* 根据当前状态查询最优动作
*/
public boolean shouldJump(double birdY, double birdVy, double pipeX, double gapY) {
int by = bucketY(birdY);
int bvy = bucketVy(birdVy);
int bdx = bucketDx(pipeX);
int bgap = bucketGap(gapY);
return action[by][bvy][bdx][bgap];
}
// 简化游戏模拟器
static class GameSimulator {
double birdY = 200;
double birdVy = 0;
double pipeX = 300;
double gapY = 150;
int score = 0;
int frames = 0;
boolean alive = true;
Random rand = new Random(123);
void reset() {
birdY = 200; birdVy = 0; pipeX = 300; gapY = 150; score = 0; frames = 0; alive = true;
}
void step(boolean jump) {
if (!alive) return;
frames++;
if (jump) birdVy = JUMP_VELOCITY;
birdVy += GRAVITY;
birdY += birdVy;
pipeX -= PIPE_SPEED;
if (pipeX < -PIPE_WIDTH) {
pipeX = SCREEN_WIDTH;
gapY = 60 + rand.nextInt(SCREEN_HEIGHT - GAP_HEIGHT - 120);
score++;
}
// 碰撞检测
if (birdY + BIRD_SIZE >= GROUND_Y || birdY < 0) alive = false;
if (50 + BIRD_SIZE >= pipeX && 50 <= pipeX + PIPE_WIDTH) {
if (birdY < gapY || birdY + BIRD_SIZE > gapY + GAP_HEIGHT) alive = false;
}
}
}
public static void main(String[] args) {
FlappyBirdDP dp = new FlappyBirdDP();
System.out.println("正在预计算 DP 策略表...");
long t1 = System.currentTimeMillis();
dp.computePolicy();
long t2 = System.currentTimeMillis();
System.out.println("预计算完成，耗时 " + (t2 - t1) + " ms");
// 运行模拟
GameSimulator sim = new GameSimulator();
int totalRuns = 10;
int totalScore = 0;
for (int run = 0; run < totalRuns; run++) {
sim.reset();
while (sim.alive && sim.frames < 10000) {
boolean jump = dp.shouldJump(sim.birdY, sim.birdVy, sim.pipeX, sim.gapY);
sim.step(jump);
}
totalScore += sim.score;
System.out.println("Run " + (run + 1) + ": 存活帧数=" + sim.frames + ", 通过管道=" + sim.score);
}
System.out.println("平均通过管道数: " + (totalScore / (double)totalRuns));
}
}
算法复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 状态空间大小 | O(H × V × D × G) | 各维度离散桶数的乘积 |
| 单次值迭代 | O(H × V × D × G) | 遍历所有状态计算最优动作 |
| 在线决策 | O(1) | 直接查表获取动作 |
| 空间复杂度 | O(H × V × D × G) | 存储 value 和 action 两张表 |
以本文参数（20×12×15×10 = 36,000 状态）为例，值迭代可在毫秒级收敛。
优化方向
- 自适应离散化：在管道附近使用更精细的网格，远处使用粗网格，减少状态数
- 函数逼近：用神经网络（DQN）代替离散表格，处理连续状态无需分桶
- 多步前瞻：结合模型预测控制（MPC），在未来数帧范围内滚动优化跳跃时机
- 参数在线调优：根据实际游戏表现动态调整离散化边界，适应不同难度设置
总结
本文将 Flappy Bird 的连续控制问题转化为离散状态空间上的动态规划问题，通过状态离散化和值迭代预计算最优策略。DP 方法的优势在于：一旦策略表计算完成，在线决策仅为 O(1) 查表，响应极快；且理论上保证了对离散模型的最优性。这一思路同样适用于各类具有确定转移模型的实时控制问题。
