游戏中的数学 13：连续碰撞与首次接触时间

2026-07-23 · 4 分钟阅读 · 1671 字

离散漏判

离散碰撞只检查 Tick 结束位置。物体若在一个 1/60s Tick 内从墙前移动到墙后，终点不重叠，却已经穿过墙。实验把问题限定为一维移动圆与墙，先让失败能被穷举。

// $WORK_DIR/.tmp/game-math-lab/Program.cs
// GameMathLab.SweptCircleWall
static bool SweptCircleWall(
    double start, double speed, double dt,
    double radius, double wallMin, double wallMax,
    out double toi)
{
    toi = 0;
    if (!double.IsFinite(start) ||
        !double.IsFinite(speed) ||
        !double.IsFinite(dt) ||
        !double.IsFinite(radius) ||
        !double.IsFinite(wallMin) ||
        !double.IsFinite(wallMax) ||
        dt < 0 || radius < 0 || wallMin > wallMax)
        return false;
    var expandedMin = wallMin - radius;
    var expandedMax = wallMax + radius;
    if (start >= expandedMin && start <= expandedMax)
        return true;
    if (Math.Abs(speed) < 1e-12)
        return false;

    var t0 = (expandedMin - start) / speed;
    var t1 = (expandedMax - start) / speed;
    if (t0 > t1) (t0, t1) = (t1, t0);

    var enter = Math.Max(0, t0);
    var exit = Math.Min(dt, t1);
    if (enter > exit || exit < 0)
        return false;
    toi = enter;
    return true;
}

状态由固定 Tick 拥有：start 是 Tick 开始位置，speed 单位为 m/s，dt 单位为秒，TOI 也用秒。渲染插值只能读取结果，不能改写这组权威输入。

连续检测不等于把 Tick 改成连续时间模拟。它只在一个固定 Tick 内解析最早接触事件，随后仍由离散状态机提交位置。回放只需保存相同输入和 Tick 序号，不必同步平台墙钟，也不会让渲染帧率决定碰撞次数。

Minkowski 扩张

移动圆撞墙可以转化为“圆心射线撞扩张后的墙”：墙区间两侧各扩张一个半径，圆心退化为点。首次进入扩张区间的时间是 t0，离开时间是 t1；只有时间区间与 [0,dt] 相交才算本 Tick 命中。

速度符号只决定先遇到扩张区间的哪一侧。交换 t0/t1 后，同一段 slab 计算同时覆盖从左向右和从右向左；静止且未重叠才返回无命中。初始重叠单独定义为 toi=0，移动提交层会停止本 Tick，绝不把圆心强行传送到某一侧边界。

// Program.cs · Chapter13 单 Tick 判定
const double dt = 1.0 / 60;
const double radius = .25;
var start = -1.0;
var end = start + speed * dt;

var overlapEnd =
    end + radius >= 0 &&
    end - radius <= thickness;

var crosses =
    start + radius < 0 &&
    end - radius > thickness;

var discreteHit = overlapEnd;
var continuousHit = SweptCircleWall(
    start, speed, dt, radius,
    0, thickness, out _);

Minkowski 扩张、首次接触与切向余量

漏判区域扫描

固定实验组合 20 档速度与 20 档墙厚，共 400 例。速度为 5..100m/s，墙厚为 0.05..1.0m。该实验用于覆盖输入空间，不用于性能评估；热力图中每个格子都可由终点重叠和扫掠区间两个布尔值复算。

// Program.cs · Chapter13 参数扫描
var rows = new List<(double X, double Y, double V)>();
int discreteMiss = 0, continuousMiss = 0;

foreach (var speed in Enumerable.Range(1, 20)
                                 .Select(i => i * 5.0))
foreach (var thickness in Enumerable.Range(1, 20)
                                     .Select(i => i * .05))
{
    // overlapEnd、crosses、continuousHit 由上一段计算
    var missed = crosses && !discreteHit ? 1 : 0;
    if (missed == 1) discreteMiss++;
    if (crosses && !continuousHit) continuousMiss++;
    rows.Add((speed, thickness, missed));
}

Check(discreteMiss > 0 && continuousMiss == 0,
    "continuous sweep catches tunnelling cases");

速度与墙厚对应的离散漏判热力图及二值图例

接触提交

固定 Tick 提供起点和速度，求解器扩张墙体并计算进入、离开时间，只提交 [0,dt] 内最早的 TOI。物体先移动到接触点，再用切向速度消耗剩余时间。只检查 Tick 终点会在高速物体越过整段墙体后误报安全。

// Program.cs · Chapter13 接触与切向余量
var movement = MoveCircleAgainstWall(
    new Vector2(-1, 0),
    new Vector2(100, 20),
    1.0 / 60, .25, 0, .1);
var penetration = Math.Max(0,
    movement.Position.X + .25);

Check(movement.Hit
    && Math.Abs(movement.Position.X + .25) < 1e-6,
    "mover stops at contact boundary");
Check(Math.Abs(movement.Position.Y - 20.0 / 60) < 1e-6,
    "remainder moves along tangent");
Check(penetration < 1e-9,
    "mover does not penetrate wall");

WriteData(13, new {
    cases = rows.Count,
    discrete_misses = discreteMiss,
    continuous_misses = continuousMiss,
    sample_toi_s = movement.Toi,
    final_position = V(movement.Position),
    remainder_s = movement.RemainingSeconds,
    penetration_m = penetration
});

固定样本的 TOI 为 0.0075s：圆心从 -1m 前进到扩张墙边界 -0.25m，路程 0.75m / 100m/s。剩余 0.0091667s 只保留切向速度 20m/s，因此最终位置为 (-0.25,0.333333)m，穿透深度为零。

接触后不能把整个 Tick 的速度再次积分，否则虽检测到 TOI，物体仍会穿透。正确顺序是先消耗 toi，再把剩余 dt-toi 投影到接触切线；若一帧出现多个接触，循环应设最大迭代数，并把预算耗尽记录为可观察失败。

反向运动与初始重叠需要进入回归集合。右侧圆以 -100m/s 撞墙时停在 wallMax+radius=0.35m；圆心一开始就在扩张区间内时保持原位，返回 toi=0 且不再消费剩余时间。

var reverse = MoveCircleAgainstWall(
    new Vector2(1.1f, 0), new Vector2(-100, 20),
    1.0 / 60, .25, 0, .1);
Check(reverse.Hit &&
      Math.Abs(reverse.Position.X - .35) < 1e-6,
    "signed sweep stops at the right boundary");

var overlap = MoveCircleAgainstWall(
    new Vector2(.05f, 7), new Vector2(100, 20),
    1.0 / 60, .25, 0, .1);
Check(overlap.Hit && overlap.Toi == 0 &&
      overlap.RemainingSeconds == 0 &&
      overlap.Position == new Vector2(.05f, 7),
    "initial overlap stops without teleporting");

漏判边界

400 组正速度扫描中，终点检测漏掉 22 组，连续扫掠漏判为 0；额外的反向速度和初始重叠回归也通过。这个结果只覆盖一维轴对齐墙，不能外推到旋转凸体。

22 个漏判格集中在“单 Tick 位移大于墙厚与直径组合”的区域，是离散端点测试的结构性盲区。把频率从 60Hz 提高只能缩小该区域，不能消除它；速度上限或墙厚一旦变化，穿墙会再次出现。

cd "$WORK_DIR"
/usr/bin/time -p dotnet run \
  --project .tmp/game-math-lab/GameMathLab.csproj \
  -- --out .tmp/game-math-lab/out

CH13 PASS cases=400 discrete_misses=22 continuous_misses=0 sample_toi=0.007500s final=(-0.250,0.333)m reverse=pass overlap=stopped remainder=0.009167s penetration=0.000E+000m
TOTAL pass=15 fail=0 skip=0 chapters=15 elapsed_ms=148.7
exit_code=0

{
  "cases": 400,
  "discrete_misses": 22,
  "continuous_misses": 0,
  "sample_toi_s": 0.0075,
  "final_position": { "x": -0.25, "y": 0.3333333 },
  "remainder_s": 0.009166666666666667,
  "penetration_m": 0,
  "reverse": {
    "toi_s": 0.00750000023841858,
    "final_position": {"x": 0.35, "y": 0.3333333}
  },
  "initial_overlap": {
    "toi_s": 0,
    "final_position": {"x": 0.05, "y": 7},
    "remainder_s": 0
  }
}

移动体约束

连续检测增加了分支与形状扩张成本，却把穿墙从步长依赖的概率事件变成可证明的时间区间。当前能力限定在一维轴对齐墙：支持双向速度，初始重叠选择停止而不是推测推出方向；旋转与任意凸体等需求出现时再升级。

逻辑层消费 TOI，先提交接触点，再在剩余时间内沿接触切线滑动；这就是当前一维墙合同内的固定步长移动体。第 14 章只读取这个权威世界位置，将它投影到屏幕并从屏幕射线回代，显示层无权修正物理状态。