6.1 Event-Driven Simulation：碰撞预测、失效事件与弹性证书

6.1 · Event-Driven Simulation覆盖 6 个作者站正式主题，以章专属状态模型、逐步轨迹、反例恢复和独立预言机验收。

学习目标

能解释“6.1 · Event-Driven Simulation”如何用未来事件优先队列、碰撞预测和失效检测推进硬盘粒子系统
能逐项核对事件驱动模拟、硬盘粒子模型、碰撞预测、碰撞响应、未来事件优先队列、失效事件，并区分作者站内容与本页独立补充
能按“每次有效碰撞更新 O(1) 粒子并安排 O(N) 新预测；队列操作为 O(log Q)”手算一个最小输入，逐步检查“模拟时钟单调前进；只有参与粒子的碰撞计数仍与预测时一致的事件才有效”
能注入“粒子发生一次碰撞后仍执行队列中基于旧速度预测的后续事件”，保存基线、首个分叉、恢复和同输入重放证据

来源、版次与独立重写边界

“6·1 · Event-Driven Simulation”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“6·1 · Event-Driven Simulation”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“6·1 · Event-Driven Simulation”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：6.1 · Event-Driven Simulation

1. 事件驱动模拟：在本页通过“预测未来碰撞”连接解释、交互状态和练习验收。
2. 硬盘粒子模型：在本页通过“插入最早事件”连接解释、交互状态和练习验收。
3. 碰撞预测：在本页通过“移动全部粒子”连接解释、交互状态和练习验收。
4. 碰撞响应：在本页通过“验证并响应碰撞”连接解释、交互状态和练习验收。
5. 未来事件优先队列：在本页通过“作废旧事件并重预测”连接解释、交互状态和练习验收。
6. 失效事件：在本页通过“预测未来碰撞”连接解释、交互状态和练习验收。

从“没有事件发生时，模拟器不必醒来”开始

事件驱动模拟（event-driven simulation）把计算集中到状态真正改变的时刻。对于没有外力的hard discs，粒子在两次碰撞之间保持constant velocity，因此可以直接从当前clock跳到下一次collision。

先预测：如果time-driven simulator每0.1秒检查一次，而两个small discs在0.04秒相撞、0.08秒已经彼此穿过，0.1秒snapshot还能发现碰撞吗？不能。减小dt可降低漏检，却让每个empty interval也执行 $N^2$ overlap checks。

Event-driven版本维护未来事件优先队列（priority queue of future events），每次delete-min、验证、推进、响应、局部重预测。

6.1.1 Hard-disc model：碰撞之间是解析直线

硬盘粒子模型（hard-disc model）中，particle i具有：

\mathbf r_i=(r_{x,i},r_{y,i}),\quad \mathbf v_i=(v_{x,i},v_{y,i}),\quad \sigma_i,\quad m_i

其中position在unit box内，radius与mass为positive。两次events之间不存在force，所以对任意 $\Delta t\ge0$ ：

\mathbf r_i(t+\Delta t)=\mathbf r_i(t)+\Delta t\,\mathbf v_i(t)

Model assumptions必须写进contract：

Initial discs不重叠，也不穿墙。
Pair collision是binary、instantaneous、frictionless、perfectly elastic。
Wall是stationary、reflecting boundary。
Ignore simultaneous multi-particle contacts与spin。
Floating-point computation需要tolerance policy，不能把negative tiny time重新排进queue。

这不是任意rigid-body engine。它故意选择能解析预测next event的物理模型，以展示priority queue、lazy invalidation和data abstraction怎样结合。

6.1.2 Wall collision prediction

碰撞预测（collision prediction）先处理wall。

Particle center x必须位于 $[\sigma,1-\sigma]$ 。若 $v_x\gt0$ ，到right vertical wall的time：

\Delta t_x=\frac{1-r_x-\sigma}{v_x}

若 $v_x\lt0$ ，到left wall：

\Delta t_x=\frac{\sigma-r_x}{v_x}

分子与分母都negative，因此result positive。 $v_x=0$ 时vertical wall time是infinity。Horizontal wall对y完全类似。

double timeToHitVerticalWall() {
    if (vx > 0) return (1.0 - rx - radius) / vx;
    if (vx < 0) return (radius - rx) / vx;
    return Double.POSITIVE_INFINITY;
}

只把finite event且 $clock+\Delta t\le limit$ 插入MinPQ。Absolute time而非delta作为key，保证来自不同prediction moments的events可直接排序。

6.1.3 Pair collision prediction：relative motion的quadratic

对particles i与j，定义relative quantities：

\Delta\mathbf r=\mathbf r_j-\mathbf r_i,\qquad \Delta\mathbf v=\mathbf v_j-\mathbf v_i,\qquad \sigma=\sigma_i+\sigma_j

接触时centers distance等于sigma：

\left\|\Delta\mathbf r+\Delta t\,\Delta\mathbf v\right\|^2=\sigma^2

展开得到quadratic。令：

\begin{aligned} dvdr &= \Delta\mathbf v\cdot\Delta\mathbf r,\\ dvdv &= \Delta\mathbf v\cdot\Delta\mathbf v,\\ drdr &= \Delta\mathbf r\cdot\Delta\mathbf r,\\ D &= dvdr^2-dvdv(drdr-\sigma^2). \end{aligned}

若 $dvdr\ge0$ ，particles在separating或切向不靠近；若dvdv=0，相对位置不变；若 $D\lt0$ ，trajectory lines不会在radius sum处相交。否则earliest physical root：

\Delta t=-\frac{dvdr+\sqrt D}{dvdv}

必须positive，否则返回infinity。

double dvdr = dx * dvx + dy * dvy;
if (dvdr >= 0) return INFINITY;
double dvdv = dvx * dvx + dvy * dvy;
if (dvdv == 0) return INFINITY;
double d = dvdr * dvdr - dvdv * (drdr - sigma * sigma);
if (d < 0) return INFINITY;
double dt = -(dvdr + Math.sqrt(d)) / dvdv;
return dt > 0 ? dt : INFINITY;

Floating-point near-tangent cases可能让理论zero的D变成tiny negative。Tolerance若使用，应scale-aware且测试记录；盲目clamp所有negative D会制造不存在的collision。

6.1.4 Future-event queue：预测的是“如果什么都不先发生”

初始化时，对每个particle a：

与all particles计算pair hit time。
计算vertical与horizontal wall hit times。
插入limit以内的future events。
插入time 0的redraw event。

每个event包含absolute time、possibly-null particles a/b，以及creation时的collision counts。Null组合编码四种event：

a与b都存在：pair collision。
只有a：vertical-wall collision。
只有b：horizontal-wall collision。
都null：redraw。

Queue中的collision不是promise，只是基于当前straight-line assumptions的candidate。若A原预计在t=4撞B，但A在t=2先撞墙改变velocity，t=4的A/B event就不再代表physical collision。

6.1.5 Invalidated events：collision count作为version stamp

失效事件（invalidated events）不必在heap内部主动查找删除。Event creation保存：

countA = a == null ? -1 : a.count();
countB = b == null ? -1 : b.count();
 
boolean isValid() {
    if (a != null && a.count() != countA) return false;
    if (b != null && b.count() != countB) return false;
    return true;
}

每次真实collision后，参与particles的count增加。旧event出heap时比较snapshot，mismatch就discard；这就是lazy invalidation。

Why counts suffice：在该model中，particle trajectory只会因collision改变。Count未变意味着position可由same start state与velocity外推，prediction assumptions仍成立；count改变则无论new velocity碰巧相同与否，都保守invalid。

6.1.6 Collision resolution：impulse更新velocity

碰撞响应（collision resolution）发生在所有particles都已推进到event time以后。

Wall response

Vertical wall反转x component：

(v_x,v_y)\longrightarrow(-v_x,v_y)

Horizontal wall反转y component。Speed不变，因此particle kinetic energy不变；particle momentum会改变，因为container接收opposite impulse。

Pair response

At contact，normal沿 $\Delta\mathbf r$ 。官方公式令：

J=\frac{2m_i m_j(\Delta\mathbf v\cdot\Delta\mathbf r)} {(m_i+m_j)\sigma}, \qquad (J_x,J_y)=J\frac{\Delta\mathbf r}{\sigma}

然后：

\begin{aligned} \mathbf v_i'&=\mathbf v_i+\frac{\mathbf J}{m_i},\\ \mathbf v_j'&=\mathbf v_j-\frac{\mathbf J}{m_j}. \end{aligned}

Impulse只作用在normal direction；frictionless tangential components保持。Correct implementation同时守恒pair linear momentum与kinetic energy：

m_i\mathbf v_i+m_j\mathbf v_j =m_i\mathbf v_i'+m_j\mathbf v_j'

\frac12m_i\|\mathbf v_i\|^2+\frac12m_j\|\mathbf v_j\|^2 =\frac12m_i\|\mathbf v_i'\|^2+\frac12m_j\|\mathbf v_j'\|^2

6.1.7 Main loop：验证后推进，再局部修复future

Official event loop：

while (!pq.isEmpty()) {
    Event e = pq.delMin();
    if (!e.isValid()) continue;
 
    for (Particle p : particles) p.move(e.time - t);
    t = e.time;
 
    if      (e.a != null && e.b != null) e.a.bounceOff(e.b);
    else if (e.a != null)                e.a.bounceOffVerticalWall();
    else if (e.b != null)                e.b.bounceOffHorizontalWall();
    else                                 redraw(limit);
 
    predict(e.a, limit);
    predict(e.b, limit);
}

Main-loop invariant：

Clock t never decreases。
每个particle position代表exact time t。
Queue含在current trajectories下预测的future candidates；stale ones可存在但会被snapshot拒绝。
处理physical event后，只有a/b trajectories改变，所以只需重新预测涉及a或b的events。

Redraw也放入same queue，使visualization遵守simulation clock，而不是用separate timer篡改physics。Official HZ=0.5，在每个redraw后安排 $t+1/HZ$ 的next redraw。

6.1.8 Work model与扩展边界

Baseline predict(a)扫描N particles，花O(N) pair predictions；initialization对all particles约O(N²)，每个pair collision后重算a与b各O(N)，heap insertion/deletion另有logarithmic cost。实际queue含duplicates与invalidated events，memory和work取决于collision density。

Time-driven baseline在T/dt个ticks上做O(N²) overlap checks，还可能因dt过大miss events。Event-driven更accurate，但不是自动subquadratic。

Large N可用cell method：unit box划分cells，只预测nearby particles，并安排cross-cell events。它减少candidate pairs，却增加spatial index与cell-boundary maintenance。Simultaneous multi-particle collision也超出当前binary-event assumptions，需要batch same-time contacts或constraint solver。

6.1.9 Independent certificate：不要只看动画“像在碰”

Physics animation可能视觉合理但数值错误。Independent trace certificate至少检查：

Clock：processed valid event times nondecreasing，delta nonnegative。
Geometry：pair event时center distance约等于radius sum；wall event时center coordinate约等于radius或1-radius。
Validity：event snapshots等于current collision counts。
Conservation：pair momentum与kinetic energy在scale-aware tolerance内不变；wall speed不变。
Bounds：每次event后particles仍在box内且不重叠。
Reprediction：velocity改变后，所有涉及changed particles的新finite events都被安排。

for (const event of processedEvents) {
  assert(event.time >= previousTime);
  assert(event.snapshotMatchesCurrentCounts());
  assertContactGeometry(event);
  const before = invariants(event);
  resolve(event);
  assertConservation(before, invariants(event));
  assertAllParticlesInsideBox();
}

Testing还应含one particle wall bounce、two equal masses head-on、unequal masses、glancing collision、parallel trajectories、near tangent、event invalidation chain与time-reversal experiment。Roundoff drift要报告，不应用large epsilon掩盖systematic energy leak。

6.1.10 逐步运行路线

先预测，再操作三个本节实验

分步1 / 3

1. 对象、操作与成本模型

先在“6.1 · Event-Driven Simulation”的两个最小情境间切换，再逐项选择正式概念。预测“每次有效碰撞更新 O(1) 粒子并安排 O(N) 新预测；队列操作为 O(log Q)”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

6.1 · Event-Driven Simulation：对象、操作与不变量

用未来事件优先队列、碰撞预测和失效检测推进硬盘粒子系统

选择最小情境

切换正式概念

失效事件: 粒子 A 先与 B 碰撞，队列里仍有旧预测 A-C
当前观察: event-driven simulation：A 的碰撞计数变化使旧 A-C 事件失效

每次有效碰撞更新 O(1) 粒子并安排 O(N) 新预测；队列操作为 O(log Q)

本节易错边界与可重放合同

练习与答案

练习

问题 1：目录与状态映射。 对下列正式概念逐项指出正文解释、交互状态和练习证据：

事件驱动模拟：在实验 1 中指出对应状态，并写出一个通过条件。
硬盘粒子模型：在实验 2 中指出对应状态，并写出一个通过条件。
碰撞预测：在实验 3 中指出对应状态，并写出一个通过条件。
碰撞响应：在实验 1 中指出对应状态，并写出一个通过条件。
未来事件优先队列：在实验 2 中指出对应状态，并写出一个通过条件。
失效事件：在实验 3 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“每次有效碰撞更新 O(1) 粒子并安排 O(N) 新预测；队列操作为 O(log Q)”不是孤立结论？

问题 3：故障恢复。 怎样证明“粒子发生一次碰撞后仍执行队列中基于旧速度预测的后续事件”已经修复？

保存粒子位置/速度、模拟时钟、事件时间、碰撞计数、有效标记、能量动量与重放轨迹作为正常基线；注入该故障并标记第一个违反“模拟时钟单调前进；只有参与粒子的碰撞计数仍与预测时一致的事件才有效”的状态；撤销后用完全相同的输入、版本和随机种子重放。只有全部状态与独立预言机重新一致，才可发布修复结论。

小结

Event-driven simulation只在interesting event times改变state，避免fixed dt的空扫描与漏碰撞。
Hard-disc model在events之间作constant-velocity linear motion，pair与wall contacts是perfectly elastic。
Collision prediction由wall linear equation或relative-motion quadratic求earliest positive time。
Priority queue of future events按absolute time排序；queued candidates依赖创建时的trajectory assumptions。
Invalidated events通过collision-count version snapshots惰性拒绝，无需从heap中主动定位删除。
Collision resolution先把all particles推进到event time，再更新normal velocity components与counts。
Pair response守恒linear momentum与kinetic energy；这些数值证书比动画更可靠。
处理有效event后只需repredict涉及changed particles的future collisions。
Baseline initialization O(N²)、每次响应O(N) reprediction；cell methods可缩小candidate neighborhood。