每日算法 — 使用java实现Flappy Bird：混合系统可达集分析与区间算术安全包络

可莉爸爸 AI算法

玩 Flappy Bird 的难点不是”要不要点”，而是”点了之后还活不活得下去”。这其实是一个混合系统（hybrid system）问题：鸟的纵向运动是连续动力学（重力 + 速度脉冲），管道是离散出现的几何障碍。本文不谈强化学习，而是用逆向可达集分析 + 区间算术，算出每帧”还存在活路”的高度带，并据此给出一个带保证的操控策略。

这套方法的价值在于：它给的是逻辑保证，不是训练出来的经验概率。RL 会说”这个状态我 99.7% 能活”，可达性分析会说”这个状态无论你怎么点，都活不到 3 秒后”——后者才是能写进安全规范的结论。

一、把游戏写成混合自动机

连续状态 x = (y, v)（高度、竖直速度）。离散事件是管道间隙序列。

单帧的演化规则（固定步长 dt）：

控制 u = flap： v' = vJump                 （拍翅，速度直接重置）
控制 u = fall： v' = clamp(v + g·dt)       （自由下落，速度受限）
两种情况的位移： y' = y + v'·dt

用 y 向下为正的屏幕坐标，vJump 取负值（向上），g 取正值（向下）。这就是一个标准的两模态混合自动机：模态由 u 决定，守卫条件是速度的上下限。

安全问题定义为：存在一个操控序列，使鸟在所有管道到来时都不碰撞。这比”存在最优路径”要强：我们要的不是最短通关，而是”确认有活路”。

二、逆向可达集：从终点往前算”还有救的 y”

正向算”我可能在哪”（前向可达集）会爆炸：状态连续、分支逐帧翻倍，几百帧后集合退化成整个屏幕。真正有用的是逆向可达集：

SafeY(t) = { y : ∃u，使 y' = y + v'·dt 落在 SafeY(t+1) 内，且 y' 本身不撞管道 }

把分支显式化。两个控制分支对应的 y 到 y’ 映射：

  • flap 分支：v' = vJump 与当前 v 无关，所以 y' = y + vJump·dt，即 y = y' - vJump·dt。这是一个纯平移。
  • fall 分支：v' = clamp(v+g·dt)，而 v 是状态的一部分（可取 [vMin, vMax] 内任意值），所以 y' = y + v'·dt 中 v’ 可取 [vMin+g·dt, vMax+g·dt]。于是 y' ∈ y + [Δmin, Δmax]，反向看就是 y ∈ SafeY(t+1) ⊕ [-Δmax, -Δmin] —— 一个区间膨胀（Minkowski 和）。

两个分支的结果取并集，再与本帧”可站区”（全体高度减去被管道占据的高度）取交集。交集只会让集合变小，这就是逆向分析不会发散的根本原因。

三、区间算术：把”不确定性”写成会膨胀的区间

区间运算规则朴素但极重要：

[a,b] ⊕ [c,d] = [a+c, b+d]         （Minkowski 和 = 平移/膨胀）
[a,b] ∩ [c,d] = [max(a,c), min(b,d)] （交集，可能为空）
[a,b] ∪ [c,d] = 排序合并（可能产生多段，用列表表示）
[a,b] \ [c,d] = 差集（管道占位）

关键的工程纪律是：所有取整必须向外。因为浮点误差会让真实安全状态被判成”不安全”——这比保守地多保留一些状态危险得多。安全分析里，所有保守都必须朝”更大危害”方向。

四、为什么不用”单点模拟”

一个诱人的简化是：既然 v 可以自由选，那就把 fall 分支当成一个固定位移。这是错的。

v' = clamp(v+g) 中的 v 是历史积累下来的，不是自由变量。如果你假设”v 总是某个典型值”，得出的安全带会覆盖不到极端情况（比如连续拍翅后立刻松手，v 从 -12 开始下落）。用区间 [vMin+g, vMax+g] 包住全部可能，虽然保守，但保证正确。

同样的道理，bird 半径不能省。把鸟当质点会让安全带变宽 2r，在 140px 的间隙上这直接导致明显的假安全率。

五、Java 完整实现

flappy-reachability/
├── src/main/java/com/example/flappy/
│   ├── HybridModel.java      // 连续动力学与离散化参数
│   ├── Intervals.java        // 区间算术（并/交/差/膨胀，全部向外取整）
│   ├── PipeSchedule.java     // 管道序列（确定性种子）
│   ├── ReachabilitySet.java  // 逆向可达集递推 + 时间剖面
│   ├── SafeController.java   // 基于安全集的前瞻控制器
│   └── FlappyDemo.java       // 主流程与统计
└── pom.xml

5.1 混合模型

package com.example.flappy;

/** 混合自动机的连续部分：y 位置、v 速度，按固定 dt 离散演化（y 向下为正） */
public class HybridModel {

    public final double dt;       // 每帧时长
    public final double gravity;  // 每帧加速度（向下为正）
    public final double vJump;    // 拍翅赋予的速度（负 = 向上）
    public final double vMin, vMax;
    public final double yMin, yMax;
    public final double birdR;    // 鸟的碰撞半径

    public HybridModel() {
        this.dt = 1.0;
        this.gravity = 0.42;
        this.vJump = -7.0;
        this.vMin = -12.0;
        this.vMax = 8.0;
        this.yMin = 0.0;
        this.yMax = 480.0;
        this.birdR = 10.0;
    }

    /** 给定当前速度与控制，返回下一帧速度 */
    public double nextVelocity(double v, boolean flap) {
        double nv = flap ? vJump : v + gravity * dt;
        return clamp(nv, vMin, vMax);
    }

    /** 该速度对应的位移量 */
    public double deltaY(double v) { return v * dt; }

    /** 鸟可活动的高度范围（保证整个碰撞包络都在屏幕内） */
    public double bodyMin() { return yMin + birdR; }
    public double bodyMax() { return yMax - birdR; }

    public double clamp(double x, double lo, double hi) {
        return Math.max(lo, Math.min(hi, x));
    }
}

5.2 区间算术

package com.example.flappy;

import java.util.*;

/**
 * 一维区间算术。所有运算按 EPS 向外膨胀，保证结果永远"过分保守"：
 * 宁可变宽，也不产生假安全。
 */
public class Intervals {

    public static final double EPS = 0.5;

    public static class Interval {
        public final double lo, hi;

        private Interval(double lo, double hi) { this.lo = lo; this.hi = hi; }

        /** 工厂方法：向外膨胀 EPS（所有"算出来的"区间都用这个） */
        public static Interval of(double lo, double hi) {
            return new Interval(Math.min(lo, hi) - EPS, Math.max(lo, hi) + EPS);
        }

        /** 工厂方法：不膨胀（用于本身就确定的边界，如屏幕边界、管道边界） */
        public static Interval exact(double lo, double hi) {
            return new Interval(Math.min(lo, hi), Math.max(lo, hi));
        }

        public double width() { return hi - lo; }

        /** 区间膨胀（Minkowski 和）：[a,b] ⊕ [c,d] = [a+c, b+d] */
        public Interval inflate(double c, double d) {
            return Interval.of(lo + c, hi + d);
        }

        public Interval shift(double d) { return inflate(d, d); }

        public Interval intersect(Interval o) {
            double l = Math.max(lo, o.lo), h = Math.min(hi, o.hi);
            return l <= h ? Interval.exact(l, h) : null;
        }

        @Override public String toString() {
            return String.format("[%.1f,%.1f]", lo, hi);
        }
    }

    /** 多段区间的并集：排序后合并相邻段 */
    public static List<Interval> union(List<Interval> a, List<Interval> b) {
        List<Interval> all = new ArrayList<>(a);
        all.addAll(b);
        all.removeIf(Objects::isNull);
        all.sort(Comparator.comparingDouble(i -> i.lo));

        List<Interval> merged = new ArrayList<>();
        for (Interval i : all) {
            if (merged.isEmpty()) { merged.add(i); continue; }
            Interval last = merged.get(merged.size() - 1);
            if (i.lo <= last.hi) {
                merged.set(merged.size() - 1, Interval.exact(last.lo, Math.max(last.hi, i.hi)));
            } else {
                merged.add(i);
            }
        }
        return merged;
    }

    /** 差集 a \ b，可能把一个段切成两段 */
    public static List<Interval> difference(List<Interval> a, List<Interval> b) {
        List<Interval> cur = new ArrayList<>(a);
        for (Interval hole : b) {
            List<Interval> next = new ArrayList<>();
            for (Interval seg : cur) {
                if (hole.hi <= seg.lo || hole.lo >= seg.hi) { next.add(seg); continue; }
                if (hole.lo > seg.lo) next.add(Interval.exact(seg.lo, hole.lo));
                if (hole.hi < seg.hi) next.add(Interval.exact(hole.hi, seg.hi));
            }
            cur = next;
        }
        return cur;
    }
}

5.3 管道序列

package com.example.flappy;

import java.util.*;

/** 第 i 段间隙在 arriveAt(i) 到来，其下沿由种子决定的伪随机序列给出 */
public class PipeSchedule {

    public final double gapEvery = 88.0;    // 相邻管道间隔帧数
    public final double gapHeight = 140.0;  // 间隙高度
    public final double pipeWidth = 60.0;
    public final int count;

    private final double[] gapLo;
    private final double[] arrival;

    public PipeSchedule(long seed, int count) {
        this.count = count;
        Random rnd = new Random(seed);
        gapLo = new double[count];
        arrival = new double[count];
        for (int i = 0; i < count; i++) {
            gapLo[i] = 60 + rnd.nextDouble() * 200;   // 下沿在 [60, 260]
            arrival[i] = 200 + i * gapEvery;
        }
    }

    public double gapLow(int i) { return gapLo[i]; }
    public double gapHigh(int i) { return gapLo[i] + gapHeight; }
    public double arriveAt(int i) { return arrival[i]; }

    /**
     * 时刻 t 被管道占据的高度区间（按"鸟心位置不可取"来表达，已扣掉鸟半径）。
     * 下侧管体：y ≤ gapLo - r；上侧管体：y ≥ gapHi + r。
     */
    public List<Intervals.Interval> occupied(double t, HybridModel m) {
        List<Intervals.Interval> occ = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            double a = arrival[i], b = arrival[i] + pipeWidth;
            if (t < a - m.birdR || t > b + m.birdR) continue;   // 鸟未进入管道宽度
            occ.add(Intervals.Interval.exact(Double.NEGATIVE_INFINITY, gapLo[i] - m.birdR));
            occ.add(Intervals.Interval.exact(gapLo[i] + gapHeight + m.birdR, Double.POSITIVE_INFINITY));
        }
        return occ;
    }
}

5.4 逆向可达集递推

package com.example.flappy;

import java.util.*;

/**
 * 逆向可达性：
 *   SafeY(t) = ( shiftFlap(SafeY(t+1)) ∪ inflateFall(SafeY(t+1)) ) ∩ allowed(t)
 * shiftFlap  对应"拍翅"分支的纯平移；
 * inflateFall 对应"下落"分支的区间膨胀（v 可取值区间导致）。
 */
public class ReachabilitySet {

    private final HybridModel m;
    private final PipeSchedule pipes;
    private final List<List<Intervals.Interval>> safeByFrame = new ArrayList<>();
    private final int horizon;

    public ReachabilitySet(HybridModel m, PipeSchedule pipes, int horizon) {
        this.m = m;
        this.pipes = pipes;
        this.horizon = horizon;
        compute();
    }

    private void compute() {
        // 终局：无管道威胁，任何合法 y 都安全
        List<Intervals.Interval> next = new ArrayList<>();
        next.add(Intervals.Interval.exact(m.bodyMin(), m.bodyMax()));

        for (int t = horizon; t >= 0; t--) {
            // flap 分支：y' = y + vJump·dt  =>  y = y' - vJump·dt
            double flapShift = -m.deltaY(m.vJump);
            List<Intervals.Interval> fromFlap = new ArrayList<>();
            for (Intervals.Interval s : next) fromFlap.add(s.shift(flapShift));

            // fall 分支：v' ∈ [vMin+g·dt, vMax+g·dt]，y' = y + v'·dt
            double vLo = m.clamp(m.vMin + m.gravity * m.dt, m.vMin, m.vMax);
            double vHi = m.clamp(m.vMax + m.gravity * m.dt, m.vMin, m.vMax);
            double dLo = m.deltaY(vLo), dHi = m.deltaY(vHi);
            List<Intervals.Interval> fromFall = new ArrayList<>();
            for (Intervals.Interval s : next) fromFall.add(s.inflate(-dHi, -dLo));

            List<Intervals.Interval> merged = Intervals.union(fromFlap, fromFall);

            // 与本帧可站区取交：全体合法高度 - 管道占位
            List<Intervals.Interval> allowed = new ArrayList<>();
            allowed.add(Intervals.Interval.exact(m.bodyMin(), m.bodyMax()));
            allowed = Intervals.difference(allowed, pipes.occupied(t, m));

            List<Intervals.Interval> safeT = new ArrayList<>();
            for (Intervals.Interval a : allowed) {
                for (Intervals.Interval s : merged) {
                    Intervals.Interval x = a.intersect(s);
                    if (x != null && x.hi > x.lo) safeT.add(x);
                }
            }

            safeByFrame.add(0, Intervals.union(safeT, Collections.emptyList()));
            next = safeByFrame.get(0);
        }
    }

    public List<Intervals.Interval> safeAt(int t) {
        if (t < 0 || t >= safeByFrame.size()) return Collections.emptyList();
        return safeByFrame.get(t);
    }

    /** 整段碰撞包络是否都落在某段安全带内 */
    public boolean isSafe(int t, double y) {
        double lo = y - m.birdR, hi = y + m.birdR;
        for (Intervals.Interval seg : safeAt(t)) {
            if (seg.lo <= lo && seg.hi >= hi) return true;
        }
        return false;
    }

    /** 到安全带边界的余量：越大越安全 */
    public double margin(int t, double y) {
        double best = Double.NEGATIVE_INFINITY;
        for (Intervals.Interval seg : safeAt(t)) {
            if (y < seg.lo || y > seg.hi) continue;
            best = Math.max(best, Math.min(y - seg.lo, seg.hi - y));
        }
        return best;
    }

    public void printProfile(int step) {
        System.out.println("帧    安全高度带（width 表示带的总宽度）");
        for (int t = 0; t <= horizon; t += step) {
            List<Intervals.Interval> s = safeAt(t);
            if (s.isEmpty()) { System.out.printf("%-5d （死区：无活路）%n", t); continue; }
            StringBuilder sb = new StringBuilder();
            double w = 0;
            for (Intervals.Interval i : s) { sb.append(i).append(' '); w += i.width(); }
            System.out.printf("%-5d %s 宽=%.1f%n", t, sb, w);
        }
    }

    public int horizon() { return horizon; }
}

5.5 前瞻控制器

package com.example.flappy;

import java.util.*;

/**
 * 基于安全集的控制器：
 * 两个分支都逐个试算下一帧的 y，选"下一帧仍在安全带内、且余量更大"的那个；
 * 若都安全，则偏向让速度更接近 0 的选择（避免极端速度积累）。
 */
public class SafeController {

    private final HybridModel m;
    private final ReachabilitySet reach;

    public int deadZoneHits = 0;

    public SafeController(HybridModel m, ReachabilitySet reach) {
        this.m = m;
        this.reach = reach;
    }

    public boolean decide(int t, double y, double v) {
        boolean bestFlap = false;
        double bestScore = Double.NEGATIVE_INFINITY;
        boolean anyFeasible = false;

        for (boolean flap : new boolean[]{true, false}) {
            double nv = m.nextVelocity(v, flap);
            double ny = y + m.deltaY(nv);

            if (ny < m.bodyMin() || ny > m.bodyMax()) continue;     // 直接撞地/出顶
            if (!reach.isSafe(t + 1, ny)) continue;                 // 下一帧不在安全带内

            anyFeasible = true;
            // 评分：安全带余量 - 速度偏离惩罚（偏好温和的速度）
            double score = reach.margin(t + 1, ny) - 0.5 * Math.abs(nv);
            if (score > bestScore) { bestScore = score; bestFlap = flap; }
        }

        if (!anyFeasible) {
            deadZoneHits++;
            // 死区：退化为"离地面更近就拍翅"的兜底策略
            return y > (m.yMin + m.yMax) / 2;
        }
        return bestFlap;
    }
}

5.6 主流程

package com.example.flappy;

public class FlappyDemo {

    public static void main(String[] args) {
        HybridModel model = new HybridModel();
        int horizon = 900;

        int deaths = 0, clears = 0;
        double totalAlive = 0;

        for (long seed = 1; seed <= 20; seed++) {
            PipeSchedule pipes = new PipeSchedule(seed, 10);
            ReachabilitySet reach = new ReachabilitySet(model, pipes, horizon);
            SafeController ctrl = new SafeController(model, reach);

            double y = 240, v = 0;
            int alive = 0;
            boolean dead = false;

            for (int t = 0; t < horizon; t++) {
                boolean flap = ctrl.decide(t, y, v);
                v = model.nextVelocity(v, flap);
                y = y + model.deltaY(v);

                if (y - model.birdR < model.yMin || y + model.birdR > model.yMax) { dead = true; break; }
                if (collide(t, y, pipes, model)) { dead = true; break; }
                alive++;
            }

            totalAlive += alive;
            if (dead) deaths++; else clears++;
            System.out.printf("seed=%2d  存活 %4d 帧  %s  死区触发 %d 次%n",
                    seed, alive, dead ? "✗ 坠毁" : "✓ 通关", ctrl.deadZoneHits);
        }

        System.out.printf("%n平均存活 %.1f 帧，通关 %d/20，坠毁 %d/20%n",
                totalAlive / 20.0, clears, deaths);

        // 打印一条安全带剖面
        PipeSchedule p0 = new PipeSchedule(1, 10);
        new ReachabilitySet(model, p0, 400).printProfile(40);
    }

    static boolean collide(int t, double y, PipeSchedule pipes, HybridModel m) {
        for (int i = 0; i < pipes.count; i++) {
            double a = pipes.arriveAt(i), b = a + pipes.pipeWidth;
            if (t < a - m.birdR || t > b + m.birdR) continue;
            if (y - m.birdR < pipes.gapLow(i)) return true;                       // 撞下侧管体
            if (y + m.birdR > pipes.gapLow(i) + pipes.gapHeight) return true;     // 撞上侧管体
        }
        return false;
    }
}

六、区间算术 vs 位图：怎么选

维度 区间列表 BitSet 位图
精度控制 需 EPS 向外膨胀，会保守地变宽 分辨率固定，无膨胀
单帧计算 O(段数 × 段数)，段数稀疏时很快 O(高度格 / 64)，位并行
表达多段 天然支持 天然支持
适用场景 连续动力学、管道稀疏 高度分辨率固定、需要极快迭代

实践中常做混合：先用区间列表粗筛（快速判定整帧死区），再用位图精算。本文为了讲清原理只用区间法。

七、为什么”逆向”比”正向”有用

很多教程教前向可达集：从当前状态往前推，算出”可能到达的所有状态”。这条路在 Flappy Bird 上会失败：

  • 前向集合会随帧数指数增宽（每帧一个分支，集合宽度单调膨胀），几百帧后退化成整个屏幕。
  • 即使不爆炸，它只告诉你”可能在哪”，不告诉你”哪里还有活路”。

逆向可达集的集合收敛而不发散：每往前推一步都是”并集再取交”，交集负责收缩。这是可达性分析在实时系统、自动驾驶安全验证里被广泛使用的根本原因。

八、三个工程坑

  1. EPS 必须向外。向内取整（lo+EPS, hi-EPS）会漏掉真实安全状态，得出”这个状态必死”的假结论。安全分析里所有保守都必须朝”更大危害”方向。
  2. fall 分支必须用速度区间而非单点。因为 v 是历史积累的状态量，不是自由变量。本文用 [vMin+g, vMax+g] 包住全部可能——保守但正确。
  3. 不要省掉鸟半径。把鸟当质点会让安全带变宽 2r，在 140px 间隙上直接带来明显的假安全率。

九、小结

Flappy Bird 看起来是个”手速游戏”，本质上是个混合系统的可达安全决策问题。用区间算术表达不确定性、用逆向可达集算出每帧的安全带、用前瞻回溯把安全带变成操控序列——这套流程不依赖训练和大量试错，结论带逻辑保证。想更进一步，可把本模型换成带守卫条件的显式混合自动机，接入 SpaceEx / Flow* 这类验证工具，就能处理更复杂的连续控制系统。

Tagged with: