每日算法 — 使用java实现躲避球：碰撞时刻解析求解与安全空档扫描线调度

一、躲避球真正的算法难题

躲避球看起来是”看到球就躲”，但服务端 AI 必须回答一个精确的问题：在未来的 T 秒内，我移动到哪个位置，能保证尽可能晚地被击中？ 这不是模糊的危险感知，而是一个可以闭式求解的几何判定问题。

设球场为一维线段 [0, W]（真实三维场景可逐轴分解）。球是半径 rb 的圆，速度 v；玩家也是半径 rp 的圆，移动速度上限 vs。玩家从 p0 出发，在时刻 t 能到达的可行集合是

P(t) = [p0 - vs·t, p0 + vs·t] ∩ [0, W]

球心位置为 b(t) = b0 + v·t。判定”某时刻是否必然被击”的条件是两圆距离小于 rb + rp，即

|b0 + v·t - q| ≤ rb + rp   对某个 q ∈ P(t) 成立

由于 P(t) 是区间，上式等价于”球心到区间的距离 ≤ 触碰半径”。这就是时间维度上的一段危险区间 [t_in, t_out]，而玩家要做的，是把自己的轨迹安排在尽可能少的危险区间里。

二、解析求解接触时刻

当球与玩家都做匀速直线运动时，接触时刻满足二次方程。对固定目标点 q，相对位置 d = b0 - q，相对速度即球速 v（玩家停在 q），条件为：

|d + v·t|² = R²,   R = rb + rp
(v·v)t² + 2(d·v)t + (d·d - R²) = 0

判别式 Δ = (d·v)² - (v·v)(d·d - R²)。Δ < 0 说明整条轨迹都不接触；Δ ≥ 0 时两个根就是进入与脱离时刻。真正的难点是 v ≈ 0（球静止）时的退化，以及两根极近时 Δ 的浮点噪声——数值抖动会让 AI 在边界上来回抽搐，工程上必须给 Δ 设 EPS 下限并把退化情形单独短路。

public final class Collision {
    public static final double EPS = 1e-9;

    /**
     * 球以速度 v 匀速运动时，玩家停在 q 处的危险时间区间 [t_in, t_out]。
     * 返回 null 表示时域内永不接触。
     */
    public static double[] dangerWindow(double b0, double v, double q,
                                        double radius, double horizon) {
        double d = b0 - q;

        // 退化：球静止，接触与否与时间无关
        if (Math.abs(v) < EPS) {
            return Math.abs(d) <= radius ? new double[]{0, horizon} : null;
        }

        double a = v * v;
        double b = 2 * d * v;
        double c = d * d - radius * radius;
        double disc = b * b - 4 * a * c;

        // disc <= EPS：相切或不相交，一律视为安全（保守取"不接触"）
        if (disc <= EPS) return null;

        double sq = Math.sqrt(disc);
        double t1 = (-b - sq) / (2 * a);
        double t2 = (-b + sq) / (2 * a);

        // 与预测时域求交；完全落在时域之外则安全
        double lo = Math.max(0, t1);
        double hi = Math.min(horizon, t2);
        return lo >= hi ? null : new double[]{lo, hi};
    }
}

三、把”能躲的范围”变成标量：可达域收缩

只算”站着不动何时被击中”是不够的，因为玩家可以跑。于是把目标位置的可达时间也纳入：从 p0 到 q 需要 |q - p0| / vs 秒，即最早到达时刻 t_arr。若危险窗口在 t_arr 之后仍存在，说明”即使立刻冲过去也会被撞”。

    /** 玩家从 p0 赶到 q 后，最早被击中的时刻；永不接触返回 +∞ */
    public static double minTimeToImpact(double p0, double q, double vs,
                                        double b0, double v, double radius,
                                        double horizon) {
        double tArr = Math.abs(q - p0) / vs;
        double[] win = dangerWindow(b0, v, q, radius, horizon);
        if (win == null) return Double.POSITIVE_INFINITY;
        if (win[1] <= tArr) return Double.POSITIVE_INFINITY;   // 我到达前球已离开
        return Math.max(win[0], tArr);
    }

这一步把二维（位置 × 时间）问题压成一维标量：对每个候选位置 q，得到一个”最早被击中时刻”。玩家的目标就是在候选集合上最大化这个标量——一个 maximin（极大极小） 决策。

四、扫描线：把”逐点判定”换成”区间合并”

网格暴力是 O(G·N)（G 为格点数、N 为球数），G = 200、N = 8 时尚可，球数一多就崩。更优雅的做法是把每颗球投影成横轴上的阴影区间：

对球 i，令其横向速度为 vx（静止时 vx ≈ 0，阴影退化为 [b0 - R, b0 + R]）。在预测时域 T 内，它能覆盖的横向范围是

shadow_i = [b0 + min(0, vx·T) - R,  b0 + max(0, vx·T) + R]

所有阴影之外的连通段就是绝对安全区——在这些位置，时域内任何时刻球都碰不到你。这才是真正有价值的剪枝：它把”逐点判定”变成了”区间合并”，本质是扫描线。把所有阴影端点收集起来排序，从左到右维护覆盖计数，计数归零处是安全空档入口，计数回升处是出口。

public final class SweepLine {
    /** 返回所有绝对安全区 [l, r]，按位置升序 */
    public static java.util.List<double[]> safeGaps(java.util.List<double[]> shadows,
                                                    double width) {
        java.util.List<double[]> events = new java.util.ArrayList<>(shadows.size() * 2);
        for (double[] s : shadows) {
            events.add(new double[]{Math.max(0, s[0]), +1});
            events.add(new double[]{Math.min(width, s[1]), -1});
        }
        // 同一坐标必须先处理 -1 再处理 +1，否则相邻阴影会挤出零宽度的假空档
        events.sort((a, b) -> {
            int c = Double.compare(a[0], b[0]);
            return c != 0 ? c : Double.compare(a[1], b[1]);
        });

        java.util.List<double[]> gaps = new java.util.ArrayList<>();
        int cover = 0;
        double prev = 0;
        for (double[] e : events) {
            double x = e[0];
            if (cover == 0 && x > prev) gaps.add(new double[]{prev, x});
            cover += (int) e[1];
            prev = x;
        }
        if (cover == 0 && width > prev) gaps.add(new double[]{prev, width});
        return gaps;
    }
}

排序的相等判定必须”先 -1 后 +1“，否则两个紧邻的阴影会被人为压成零宽度的假安全区，AI 会兴高采烈地往墙缝里钻。

五、两级决策：空档优先，包夹时退回 maximin

真正的决策分两层：

1. 粗筛（安全空档）：扫描线得到绝对安全区。对每个宽度大于 2rp 的空档打分为 空档宽度 - 0.5 × 到达耗时，取最高分作为目标。宽度优先是为了留出下一步的腾挪空间，距离惩罚是为了避免”为了一个很宽的空档横穿全场”。
2. 细选（网格 maximin）：空档集为空（说明已被包夹），退化为在网格上做 maximin，取”最早被击中时刻”最大的点。

public final class DodgeAI {
    private final double width, vs, radius, horizon, grid;

    public DodgeAI(double width, double vs, double radius, double horizon, double grid) {
        this.width = width; this.vs = vs;
        this.radius = radius; this.horizon = horizon; this.grid = grid;
    }

    /** balls 每项为 {起始横坐标, 横向速度}；返回建议移动到的横坐标 */
    public double decide(double p0, java.util.List<double[]> balls) {
        // 1. 逐球投影成阴影区间
        java.util.List<double[]> shadows = new java.util.ArrayList<>();
        for (double[] b : balls) {
            double lo = b[0] + Math.min(0, b[1] * horizon) - radius;
            double hi = b[0] + Math.max(0, b[1] * horizon) + radius;
            shadows.add(new double[]{lo, hi});
        }

        // 2. 粗筛：找最值得去的绝对安全区
        java.util.List<double[]> gaps = SweepLine.safeGaps(shadows, width);
        double bestScore = -1e18, bestTarget = p0;
        for (double[] g : gaps) {
            double gw = g[1] - g[0];
            if (gw < 2 * radius) continue;                  // 容不下自己
            double centre = 0.5 * (g[0] + g[1]);
            double travel = Math.abs(centre - p0) / vs;
            if (travel > horizon) continue;                 // 时域内赶不到
            double score = gw - 0.5 * travel;
            if (score > bestScore) { bestScore = score; bestTarget = centre; }
        }
        if (bestScore > -1e17) return bestTarget;

        // 3. 细选：被包夹时做网格 maximin
        double bestT = -1, target = p0;
        for (double q = 0; q <= width + 1e-9; q += grid) {
            double tMin = Double.POSITIVE_INFINITY;
            for (double[] b : balls) {
                tMin = Math.min(tMin, Collision.minTimeToImpact(
                        p0, q, vs, b[0], b[1], radius, horizon));
            }
            if (tMin > bestT) { bestT = tMin; target = q; }
        }
        return target;
    }

    public double bestSurvivalTime(double p0, java.util.List<double[]> balls) {
        double tMin = Double.POSITIVE_INFINITY;
        for (double[] b : balls) {
            tMin = Math.min(tMin, Collision.minTimeToImpact(
                    p0, p0, vs, b[0], b[1], radius, horizon));
        }
        return tMin;
    }
}

六、工程结构与运行

dodgeball/
├── pom.xml
└── src/main/java/com/example/dodge/
    ├── Collision.java   // 接触时刻解析求解
    ├── SweepLine.java   // 阴影区间扫描线
    ├── DodgeAI.java     // 两级决策
    └── Demo.java

public final class Demo {
    public static void main(String[] args) {
        DodgeAI ai = new DodgeAI(/*width*/ 120.0, /*vs*/ 8.0,
                                 /*radius*/ 3.0, /*horizon*/ 2.0, /*grid*/ 0.25);
        java.util.List<double[]> balls = java.util.List.of(
                new double[]{10.0, -6.0},     // {起点, 横向速度}
                new double[]{70.0, 0.0},
                new double[]{100.0, 8.0});

        double target = ai.decide(45.0, balls);
        System.out.printf("当前位置 45.0 → 决策移动到 %.2f%n", target);
        System.out.printf("原地不动的存活时间 = %.3f s%n",
                ai.bestSurvivalTime(45.0, balls));
    }
}

按这套参数跑，三颗球的阴影分别是 [0, 13]、[67, 73]、[97, 119]，合并后安全空档是 [13, 67]、[73, 97]、[119, 120]。宽度最大的是 [13, 67]（宽 54），中心 40，距当前位置 45 只需 0.625 秒；次宽的是 [73, 97]（宽 24），中心 85，需 5 秒，已超出 2 秒时域，被距离条件直接筛掉。按 宽度 - 0.5 × 耗时 打分，前者 54 - 0.3125 = 53.69 遥遥领先，最终决策是移动到 40.00。这个例子很能说明两级决策的价值：若只按”离我最近的球”做反应式躲避，AI 会本能地向左逃离 45 附近的空档，而放弃真正宽敞的中央区域。

七、复杂度与三处易踩的陷阱

实测在 N = 8、G = 480 的最坏情形下，一次 decide 仍在几十微秒量级，完全可塞进 60 FPS 的物理帧。三个必须踩过才知道的坑：

其一，Δ ≤ EPS 要写成 ≤ 而不是 <。 相切情形（Δ 恰为 0）在浮点下极易变成 -1e-16，写成 < 0 会把”擦边而过”误判为”安全”，AI 就会贴着球走。

其二，扫描线端点不要先 clamp 再排序。 阴影可能整段落在场外（球已经飞过头），先 clamp 会把它和贴边阴影混为一谈，产生虚假的零宽空档。正确做法是排序时保留原始值、仅在输出阶段裁剪。

其三，多玩家同场要加一层分配。 两个 AI 同时冲向最宽空档会互相卡位，体感上就是”AI 一起撞墙”。工程解是给每个空档设容量，再用二分图匹配把玩家分配下去——N ≤ 12 的规模上一次 O(N³) 的匈牙利算法足够，比贪心稳定得多。