每日算法 — 使用java实现打砖块：连续碰撞检测与反弹角度的几何最优解

高速小球为什么会”穿墙”

打砖块（Breakout）的经典实现大多写成这样：小球每帧位移 p += v，然后判断 p 是否落在某个砖块的矩形内。这个写法在低速时看不出问题，但只要球速提高，或者砖块变薄，就会出现穿透（tunneling）——球从砖块上方瞬间移动到下方，中间过程完全没被检测到。

根因是离散采样：AABB 相交测试只在采样时刻成立，两次采样之间球走过的连续轨迹被丢弃了。设球半径 r、单帧位移长度 |v|、砖块厚度 t，穿透发生的充要条件是 |v| > t + 2r 的某个分量被跨过。

检测方式	检测精度	代价	高速稳定性
离散 AABB 相交	仅采样点	极低	会穿透
子步进（substepping）	与子步数成正比	中等	需限制子步上限
扫掠 AABB（swept AABB）	精确到首次接触时刻	低（一次 slab 求解）	稳定

本文用扫掠 AABB（连续碰撞检测，CCD）：把球在一帧内的位移看作一条线段，求这条线段（加粗为半径 r 的胶囊体）与砖块矩形的首次接触时间 t*。拿到 t* 后先推进到接触点，处理反弹，再用剩余时间继续推进——一帧内可能连续处理多次碰撞。

第一步：把线段求交拆成两个 slab

球心从 P0 走到 P1，位移 d = P1 - P0。球是半径 r 的圆，等价于把砖块矩形向外扩张 r（Minkowski 和），然后求球心线段与该扩张矩形的交点。这就是”点 vs AABB”的 slab 方法：

/** 线段与 AABB 的首次接触参数 t ∈ [0,1]，无交返回 -1 */
static double sweepPointVsAabb(double p0x, double p0y, double dx, double dy,
                               double bx, double by, double bw, double bh, double r) {
    double minX = bx - r, maxX = bx + bw + r;   // Minkowski 扩张
    double minY = by - r, maxY = by + bh + r;
    double tEnter = 0.0, tExit = 1.0;

    // ---- X 轴 slab ----
    if (Math.abs(dx) < 1e-9) {
        if (p0x < minX || p0x > maxX) return -1;   // 平行且在外侧
    } else {
        double t1 = (minX - p0x) / dx;
        double t2 = (maxX - p0x) / dx;
        if (t1 > t2) { double tmp = t1; t1 = t2; t2 = tmp; }
        tEnter = Math.max(tEnter, t1);
        tExit  = Math.min(tExit,  t2);
        if (tEnter > tExit) return -1;
    }

    // ---- Y 轴 slab ----
    if (Math.abs(dy) < 1e-9) {
        if (p0y < minY || p0y > maxY) return -1;
    } else {
        double t1 = (minY - p0y) / dy;
        double t2 = (maxY - p0y) / dy;
        if (t1 > t2) { double tmp = t1; t1 = t2; t2 = tmp; }
        tEnter = Math.max(tEnter, t1);
        tExit  = Math.min(tExit,  t2);
        if (tEnter > tExit) return -1;
    }

    return tEnter <= 1.0 && tExit >= 0.0 ? Math.max(tEnter, 0.0) : -1;
}

两个 slab 的交集就是”球心线段落在扩张矩形内”的时间区间，取左端点即首次接触时刻。复杂度 O(1)，比逐子步检测快得多，且没有穿透。

第二步：法线判定——到底是撞了哪条边

拿到 t* 后，接触点 C = P0 + t*·d。要决定反弹方向，必须知道撞的是竖直边还是水平边，否则在砖块角落会反弹错方向。

有个稳健的判据：比较穿透深度。分别计算球心穿入扩张矩形四条边的”侵入量”，侵入最深的那个面就是碰撞面。

enum Axis { X, Y }

/** 用最小穿透深度判定碰撞轴 */
static Axis resolveAxis(double cx, double cy, double bx, double by,
                        double bw, double bh, double r) {
    double depthL = (cx) - (bx - r);                 // 从左边侵入
    double depthR = (bx + bw + r) - cx;              // 从右边侵入
    double depthT = (cy) - (by - r);
    double depthB = (by + bh + r) - cy;
    double minX = Math.min(depthL, depthR);
    double minY = Math.min(depthT, depthB);
    // 穿透更浅的那一轴 = 真正进入的轴
    return minX < minY ? Axis.X : Axis.Y;
}

判定为 Axis.X（撞了左右竖直边）时翻转 dx，为 Axis.Y 时翻转 dy。然后加一个分离推力（separation bias）：把球心沿法线推出 1e-6，否则下一帧 t* 会算成 0，陷入”同一面反复反弹”的死循环。

第三步：一帧内多次碰撞

public final class BallPhysics {
    private static final double EPS = 1e-6;

    /** 推进一帧，可能处理多次碰撞，返回剩余速度 */
    public void step(Board b, double dt) {
        double remain = dt;
        for (int iter = 0; iter < MAX_ITERS && remain > 0; iter++) {
            double dx = vx * remain, dy = vy * remain;

            Hit best = null;                    // 找最早接触的砖块
            for (Brick brick : b.activeBricks()) {
                double t = sweepPointVsAabb(x, y, dx, dy,
                        brick.x, brick.y, brick.w, brick.h, radius);
                if (t >= 0 && (best == null || t < best.t)) {
                    best = new Hit(brick, t);
                }
            }
            // 边界墙也参与扫掠（用四条无限薄矩形）
            Hit wall = sweepWalls(x, y, dx, dy, radius);
            if (wall != null && (best == null || wall.t < best.t)) best = wall;

            if (best == null) {                 // 本帧无碰撞，直接走完
                x += dx; y += dy;
                return;
            }

            double travel = best.t * remain;
            x += vx * travel;
            y += vy * travel;

            Axis axis = resolveAxis(x, y, best.brick.x, best.brick.y,
                                    best.brick.w, best.brick.h, radius);
            if (axis == Axis.X) { vx = -vx; x += Math.signum(vx) * EPS; }
            else                { vy = -vy; y += Math.signum(vy) * EPS; }

            if (best.brick != null) best.brick.hp--;
            remain -= travel;                  // 剩余时间继续推进
        }
    }
}

MAX_ITERS 取 4~8：一帧内最多处理这么多次碰撞，防止极端角度下无限循环。

第四步：反弹角度的几何最优——不只是”撞哪弹哪”

单纯镜像反射会让球陷入水平循环：球在两面墙之间来回弹，永远打不到砖。职业玩家和 AI 都需要主动调节出射角。这里介绍两种可落地的策略。

策略 A：挡板落点决定角度（真实物理）

挡板击球时，出射角由球击中挡板的位置决定：

/** 挡板反弹：入射位置偏移 → 出射角，偏移量线性映射到 ±MAX_ANGLE */
static double[] paddleBounce(double ballX, double paddleX, double paddleW,
                             double ballSpeed, double maxAngleDeg) {
    double center = paddleX + paddleW / 2.0;
    double offset = (ballX - center) / (paddleW / 2.0);   // ∈ [-1, 1]
    offset = Math.max(-1.0, Math.min(1.0, offset));
    double angle = Math.toRadians(maxAngleDeg) * offset;
    // 统一向上（-Y 方向），避免球向下跑
    return new double[]{Math.sin(angle) * ballSpeed,
                        -Math.cos(angle) * ballSpeed};
}

maxAngleDeg 通常取 60°。这样球最多偏离竖直 60°，横向速度上限为 0.866·speed，天然限制了”纯水平”死循环。

策略 B：剩余砖块的最短路径规划

想让 AI 用最少击球清完砖块，可以把问题转成”球从当前位置出发，以哪个角度射出能最快清空剩余砖块”。这本质上是一个几何射线追踪 + 集合覆盖问题：

对候选出射角集合 θ ∈ {1°, 2°, ..., 89°}（左右各一份），做一次完整的轨迹模拟，得到该角度下的”撞击序列”和”清空所需击球数”；
用记忆化：memo[剩余砖块位图][球位置簇] = 最优后续击球数；
每次真正击球时取 argmin 角度。

public final class AnglePlanner {
    private final Map<Long, Integer> memo = new HashMap<>();   // 位图 → 最优剩余击球数
    private final Map<Long, Double> bestAngle = new HashMap<>();

    /** 贪心 + 记忆化：返回当前位图下的最优出射角 */
    public double plan(long brickMask, double ballX, double ballY) {
        Integer cached = memo.get(brickMask);
        if (cached != null) return bestAngle.get(brickMask);

        int best = Integer.MAX_VALUE;
        double bestDeg = 90.0;
        for (int deg = 1; deg <= 89; deg++) {
            for (int sign = -1; sign <= 1; sign += 2) {
                double rad = Math.toRadians(sign * deg);
                long after = simulateAndClear(brickMask, ballX, ballY, rad);
                if (after == 0) { memo.put(brickMask, 1); bestAngle.put(brickMask, sign * deg); return sign * deg; }
                // 估算：清掉的砖块数越多、剩余位图越小越优（用 1 + 深度受限的递归上界）
                int cost = 1 + lowerBound(after);
                if (cost < best) { best = cost; bestDeg = sign * deg; }
            }
        }
        memo.put(brickMask, best);
        bestAngle.put(brickMask, bestDeg);
        return bestDeg;
    }
}

lowerBound 可以用”剩余砖块数 / 单次最大可清砖数”作为下界，配合 1 + LB 就是经典的 IDA*/A* 式剪枝：一旦某个角度的 1 + LB 已经 ≥ 当前最优，直接放弃该角度的完整模拟，省掉大量射线追踪开销。

完整项目结构

breakout-ccd/
├── pom.xml
└── src/main/java/com/daily/algorithm/breakout/
    ├── Vec2.java             // 轻量二维向量
    ├── Brick.java            // 砖块（位置、尺寸、hp、位图索引）
    ├── Board.java            // 砖块布局与位图维护
    ├── Sweep.java            // 扫掠 AABB / slab 求交
    ├── BallPhysics.java      // 一帧多次碰撞的推进
    ├── PaddleLogic.java      // 挡板反弹角度映射
    ├── AnglePlanner.java     // 角度搜索 + 记忆化
    └── Main.java             // 控制台可视化 demo

数值稳定性细节

三处最容易出错的地方，都来自浮点误差：

接触后 t* == 0：球贴着砖块边缘时，tEnter 会是 0 或极小负数。解决方法是反弹后沿法线方向强制偏移 EPS（如上文 x += signum(vx) * EPS）。
角落双轴碰撞：球同时撞到相邻两块砖的接触角时，若只翻一个轴，球会”卡”在缝里。做法是同时检查两轴：若两轴穿透深度差小于 EPS*10，翻转两个分量。
低角度擦边：dx 极小时 slab 求交会算出巨大的 t。上文用 Math.abs(dx) < 1e-9 的平行分支处理，避免 除以近零。

复杂度

单帧碰撞查询：O(B)（B = 活跃砖块数），可用均匀网格分桶降到 O(1) 均摊；
角度规划：O(178 × T)，T 为单次射线模拟的反射次数上限，配合 1 + LB 剪枝后实际只模拟 20% 左右的候选。

小结

打砖块的算法含量不在”反弹”，而在碰撞检测的精度与出射角的选择。扫掠 AABB 用一次 slab 求解把”离散采样漏检”彻底消灭；反弹轴的穿透深度判定解决了角落误反弹；而挡板落点映射 + 位图记忆化角度搜索，则把”物理游戏”变成了一个可优化的搜索问题——这也正是所有弹球类游戏 AI 的共同骨架。

Tagged with: Minkowski和 slab算法反弹角度优化射线追踪打砖块扫掠AABB 连续碰撞检测