每日算法 — 使用java实现Flappy Bird：模型预测控制MPC与滚动时域优化

Flappy Bird 的 AI 教程几乎都在讲同一件事：把”跳/不跳”当成离散动作，用 Q-Learning 或 DQN 学习一个策略。这类方法有效，但有一个共同前提——先训练，后使用，而且训练结果与管道布局强耦合。

换个思路：Bird 的运动方程是完全已知的确定性系统（重力恒定、跳跃冲量固定、管道匀速左移），那么”现在该不该跳”其实可以直接在线求解，不需要任何训练。这就是模型预测控制（Model Predictive Control, MPC）：用系统模型向前预测 N 帧，在每个预测时刻评估”若在此刻落地会不会撞管”，把满足约束的时机集合算出来，然后只执行第一步，下一帧重新预测（滚动时域 / Receding Horizon）。

本文用 Java 实现一个 MPC 版 Flappy Bird 控制器：解析式轨迹预测 + 安全窗口求解 + 滚动时域决策，并说明它相对强化学习的工程优势与局限。

一、把 Bird 变成可预测的确定性系统

Flappy Bird 的物理极简：

• 每帧 vy += g（重力累加）
• 每帧 y += vy
• 玩家点击时 vy = -jumpImpulse（瞬时速度重置，不是叠加）

用离散递推写出来就是：

public class BirdModel {
    public double y;        // 当前高度（像素，向下为正）
    public double vy;       // 当前垂直速度
    public final double g;        // 重力加速度，约 0.5 px/frame²
    public final double jump;     // 跳跃冲量，约 -8 px/frame

    public BirdModel(double y, double vy, double g, double jump) {
        this.y = y; this.vy = vy; this.g = g; this.jump = jump;
    }

    /** 不跳跃时，第 t 帧后的高度（解析式：等差数列求和） */
    public double yAfterNoJump(int t) {
        // y + vy*t + g*t*(t+1)/2 ，即每帧先加 g 再位移
        return y + vy * t + g * t * (t + 1) / 2.0;
    }

    /** 若在第 t 帧执行一次跳跃，之后持续不跳的高度 */
    public double yAfterJumpAt(int t) {
        double yAtT = yAfterNoJump(t);
        double vyAtT = vy + g * t;             // 到达该帧时的速度
        return yAtT + (vyAtT + jump);          // 跳跃把速度重置为 jump，立即位移
    }

    public BirdModel copy() { return new BirdModel(y, vy, g, jump); }
}

因为 yAfterNoJump 是 t 的二次函数，所有”未来某帧的高度”都能在 O(1) 内算出，无需逐帧模拟。这一点对 MPC 至关重要：预测 N=60 帧不需要 60 次循环，只需要解析式求值。

二、MPC 的核心：安全窗口而非单点决策

MPC 与贪心的根本区别在于约束。对 Flappy Bird 而言，约束是”bird 的整个矩形不能与管道开口边界相交”。给定前方管道的开口区间 [GAP_TOP, GAP_BOTTOM] 以及 bird 半径 R，安全高度区间是：

y ∈ [GAP_TOP + R, GAP_BOTTOM - R]

于是决策问题变成：在接下来的若干帧里，是否存在一个帧 t，使得在 t 帧跳跃后，bird 在到达管道那一帧的高度落在安全区间内。把”所有可行的 t”算出来，就得到跳跃时机的安全窗口。

import java.util.*;

public class MpcController {
    private final double gravity, jumpImpulse, birdRadius;
    private final int horizon;           // 预测帧数，通常取到达管道的帧数
    private final double gapTop, gapBottom;
    private final int framesToPipe;      // 距离管道还有几帧

    public MpcController(double gravity, double jumpImpulse, double birdRadius,
                         int horizon, double gapTop, double gapBottom, int framesToPipe) {
        this.gravity = gravity; this.jumpImpulse = jumpImpulse; this.birdRadius = birdRadius;
        this.horizon = horizon; this.gapTop = gapTop; this.gapBottom = gapBottom;
        this.framesToPipe = framesToPipe;
    }

    /** 返回"现在是否应该跳跃" */
    public boolean shouldFlap(BirdModel bird) {
        List<Integer> safeTimes = safeFlapWindow(bird);
        if (safeTimes.isEmpty()) return true;                 // 无安全解：被迫跳，尽量抢救
        // 只在窗口的最后一个可跳帧到来时才执行；提前跳会浪费高度余量
        return safeTimes.get(0) == 0;                          // 滚动时域：每次只决策当前帧
    }

    /** 计算未来 horizon 帧内，哪些帧起跳能让 bird 安全穿过管道 */
    private List<Integer> safeFlapWindow(BirdModel bird) {
        List<Integer> times = new ArrayList<>();
        double yMin = gapTop + birdRadius, yMax = gapBottom - birdRadius;

        for (int t = 0; t <= horizon; t++) {
            // 若在第 t 帧跳，则在到达管道帧 framesToPipe 时的预测高度
            double yAtPipe;
            if (framesToPipe < t) {
                // 管道已经在 t 之前到达：只关心跳之前的高度是否仍安全
                yAtPipe = bird.yAfterNoJump(framesToPipe);
            } else {
                double yAtT = bird.yAfterNoJump(t);
                double vyAtT = bird.vy + gravity * t;
                // 跳跃后速度重置为 jumpImpulse，之后剩余 (framesToPipe - t - 1) 帧自由下落
                int remain = framesToPipe - t - 1;
                yAtPipe = yAtT + (vyAtT + jumpImpulse)
                        + (vyAtT + jumpImpulse) * remain + gravity * remain * (remain + 1) / 2.0;
            }
            if (yAtPipe >= yMin && yAtPipe <= yMax) times.add(t);
        }
        return times;
    }
}

2.1 滚动时域：为什么”只执行第一步”

MPC 的标准形式是：每个控制周期求解一次有限时域最优化，只应用第一个控制量，然后状态推进、重新求解。它带来两个性质：

1. 反馈鲁棒性：模型误差、随机因素造成的偏差会在下一个周期被自动吸收，不需要额外设计补偿。
2. 约束天然满足：安全窗口是逐帧算出的，不会出现”计划很好但执行中已经撞了”的情况。

在实现上，shouldFlap 每次只判断 safeTimes.get(0) == 0——即”当前帧是否落在可行窗口的起点”。如果当前帧不跳就再也来不及，那么 t=0 必然在窗口内。

2.2 前瞻深度怎么选

horizon 不是越大越好。取 horizon = framesToPipe 时，MPC 会一直看到管道位置；但如果把 horizon 取得过小（比如 5 帧），就会出现”看起来还能自由下落，实际已经来不及”的短视问题。经验值是：

horizon ≈ framesToPipe + 10

多出的 10 帧用来覆盖”跳过头”的情形——有些高度必须在更早的时候起跳才不至于冲出上边界，这一段需要额外的前瞻才能看到。

三、目标函数：把”安全”升级为”最优”

上面的 safeFlapWindow 只判断可行性，不做优化。真正的 MPC 需要目标函数。给每个候选时机打分：

/** 代价函数：越小越好。惩罚三项：离管道中心的偏差、离上下边界的最小余量、跳跃次数 */
private double cost(BirdModel bird, int t) {
    double yMin = gapTop + birdRadius, yMax = gapBottom - birdRadius;
    double center = (yMin + yMax) / 2.0;
    double yAtPipe = predictYAtPipe(bird, t);
    double centerPenalty = Math.abs(yAtPipe - center);              // 尽量居中穿过
    double marginPenalty = Math.min(yAtPipe - yMin, yMax - yAtPipe); // 最小安全余量（越大越好，取负）
    return centerPenalty * 1.0 - marginPenalty * 0.8 + t * 0.05;     // t 越小越倾向于尽早决策
}

/** 在窗口内取代价最小的时机 */
public int bestFlapTime(BirdModel bird) {
    List<Integer> window = safeFlapWindow(bird);
    int best = -1; double bestCost = Double.MAX_VALUE;
    for (int t : window) {
        double c = cost(bird, t);
        if (c < bestCost) { bestCost = c; best = t; }
    }
    return best;
}

目标函数的三项各有含义：居中穿越让后续机动余量最大；安全余量保证不贴边；t 的小权重让决策倾向于”能做就尽早规划”，避免拖到被迫的紧急跳。

四、完整项目结构与运行

flappy-mpc/
├── src/main/java/com/example/flappy/
│   ├── BirdModel.java       # 确定性物理模型 + 解析式预测
│   ├── MpcController.java   # 安全窗口求解 + 滚动时域决策
│   ├── PipeManager.java     # 管道生成与"距离下一管道帧数"计算
│   └── Main.java            # 无渲染的纯逻辑仿真，统计存活帧数

public class Main {
    public static void main(String[] args) {
        int totalFrames = 0, runs = 100, survived = 0;

        for (int run = 0; run < runs; run++) {
            Sim sim = new Sim(1234L + run);        // 每次固定随机种子，结果可复现
            while (!sim.over && sim.frames < 100000) sim.step();
            totalFrames += sim.frames;
            if (sim.frames >= 100000) survived++;
        }
        System.out.printf("平均存活帧数 = %.1f，通关率 = %.0f%%%n",
                totalFrames / (double) runs, survived * 100.0 / runs);
    }
}

/** 极简仿真器：只跑物理与管道，不做渲染 */
class Sim {
    double y = 300, vy = 0;
    final double g = 0.5, jump = -8, radius = 10, gapH = 120;
    double gapTop = 250;
    int frames = 0; boolean over = false;

    Sim(long seed) { /* 用 seed 初始化管道序列 */ }

    void step() {
        frames++;
        // 每 N 帧推进一次管道，并重算 gapTop
        // 决策：调用 MpcController.shouldFlap，若 true 则 vy = jump
        // 碰撞检测：y - radius < 0 或 y + radius > 高度 或 与管道相交 => over = true
    }
}

Sim 省略了渲染与管道细节，核心链路只有三步：预测 → 决策 → 推进。这也是 MPC 三段式的标准结构。

五、MPC vs Q-Learning：什么时候该用哪个

结论很直接：当控制对象的动力学已知且约束清晰时，MPC 严格优于学习型方法。Flappy Bird 恰好是这类问题的最简形态——状态 2 维、动作 2 个、模型完全确定。反过来，如果模型未知（比如真实无人机的气动）、或者约束难以形式化（比如”看起来自然”），学习型方法才更有优势。

六、复杂度与工程要点

• 预测开销：解析式 yAfterNoJump 是 O(1)，因此整个安全窗口计算是 O(horizon)，horizon 取 60 时每帧约 60 次浮点运算，完全可忽略。
• 确定性：给定同一初始状态，MPC 输出的决策序列完全可复现，这比 DQN 的随机性更容易调试。
• 失败模式：如果管道间隙小于 2 × birdRadius + 最小可控位移，MPC 也会撞——但此时任何策略都不可能存活，这属于”物理上无解”而非算法缺陷。
• 可扩展：把 cost 换成”未来 3 根管道的最小余量”，MPC 就从单管避障升级为多管规划，而搜索结构完全不用改。

Flappy Bird 的价值不在于它是一个游戏，而在于它是一个完全可解析的受控动力系统。用 MPC 解它，本质上是在演示控制论与算法设计的交叉点：预测得越准，需要的”学习”就越少。