算法（24）：event-driven simulation

Page 42-43目标与物理模型内容目标是用弹性碰撞定律模拟N个运动粒子的行为。物理模型是“硬球模型”粒子是圆盘有位置、速度、质量和半径。只存在弹性碰撞粒子之间、粒子与墙壁。没有其他外力重力、摩擦力忽略。科学意义这个模型可以推导出宏观性质温度、压力与微观运动的关系麦克斯韦-玻尔兹曼分布、布朗运动。你的关注点这是一个动态系统你需要在时间轴上处理粒子状态的变化。Page 44-47时间驱动模拟——为什么它不行第44-45页展示了一个简单的Ball类每次移动固定时间步长dt遇到墙壁就反弹。但缺少粒子间的碰撞检测。第46页时间驱动模拟的流程离散时间步长dt每一步都检查所有粒子对是否重叠如果重叠则回退到碰撞时刻更新速度继续。第47页关键缺陷问题1每一步需要检查~N²/2对粒子如果dt很小计算量爆炸。问题2如果dt太大两个粒子可能在两次检查之间穿过彼此而没有重叠导致完全错过碰撞。结论时间驱动模拟在粒子数量大或需要高精度时不可行。Page 48事件驱动模拟——核心思想物理策略只在“有事情发生”时前进时间两次碰撞之间所有粒子做匀速直线运动。维护一个按时间排序的优先队列里面存放所有未来的潜在碰撞事件。每次从队列中取出时间最小的事件即下一次碰撞处理它然后预测这次碰撞可能引发的新事件重新插入队列。你的关注点这正是在 DFT/逻辑仿真中处理“信号翻转事件”的经典模式。优先队列在这里扮演“时间调度器”的角色。Page 49粒子-墙壁碰撞预测物理公式计算粒子到墙壁的距离除以速度在垂直方向的分量得到碰撞时间。PPT上给出了公式但物理细节不重要你只需要知道timeToHitWall()返回一个double值表示“从现在开始多少时间后会撞墙”。Page 50-52粒子-粒子碰撞预测与解析PPT 给出了完整的向量公式相对速度、相对位置、判别式d用于计算两个圆盘何时相撞以及碰撞后的速度变化。但是PPT 在第51页用大字标注了Important note: This is high-school physics, so we wont be testing you on it!这是高中物理不会考你。所以这些公式你完全不需要记忆。你只需要知道timeToHit(Particle that)返回两个粒子碰撞的时间如果它们正在远离则返回无穷大bounceOff(Particle that)更新两个粒子的速度向量。Page 53-54Particle 数据类型的骨架展示了timeToHit和bounceOff的实现代码。代码较长但核心逻辑已经被上面的公式覆盖。物理细节同样不需要深究。Page 55事件驱动模拟的初始化和主循环——这一页是算法的核心初始化把所有粒子与墙壁的潜在碰撞加入优先队列。把所有粒子与粒子的潜在碰撞加入优先队列。这些事件都是“潜在”的——因为如果某个碰撞先发生了后续的事件可能就无效了。主循环从优先队列中取出最小时间的事件t。检查事件是否已失效如果该事件涉及的粒子自事件创建以来已经发生过其他碰撞则这个事件就是无效的直接丢弃。将所有粒子按直线轨迹移动到时间t。更新碰撞粒子的速度调用bounceOff。只针对刚碰撞的粒子重新预测它们未来可能的新碰撞粒子-墙壁、粒子-粒子并插入优先队列。关键物理事实为什么只预测“刚碰撞的粒子”因为其他粒子的轨迹没有改变它们未来的碰撞时间依然有效。只有速度发生了变化的粒子才会改变未来事件的时钟。这正是“事件驱动”高效的原因——你只更新受影响的那一小部分。Page 56Event 数据类型约定两个粒子都不为空 → 粒子-粒子碰撞。一个粒子不为空 → 粒子-墙壁碰撞。两个都为空 →重绘事件用来刷新屏幕动画。Event类还存储了事件创建时两个粒子的碰撞计数器countA和countB。用来检测事件是否失效如果当前粒子计数器与存储的值不同说明粒子在事件被处理前已经撞过了。Page 57-58CollisionSystem 框架代码predict(a)方法为给定粒子a计算它与所有其他粒子的碰撞时间以及与墙壁的碰撞时间将它们作为新事件插入优先队列。simulate()方法就是 Page 55 描述的主循环。Page 59-62模拟可视化示例展示了几种不同的粒子碰撞模拟动画截图随机粒子台球布局billiards.txt大质量粒子撞击小粒子群这些只是运行结果展示没有新的算法内容。这一节你需要记住的唯一算法机制“当事件发生时只重新计算受影响的粒子的未来事件其他事件保持不变。用碰撞计数器标记事件的有效性避免在事件触发前从堆中删除它们。”一、运动公式推导Q我想看看这页的“高中物理”都是怎么来的A1. 物理建模把两个粒子简化为“一个粒子”的运动你把粒子i和j的速度、位置相减得到相对速度Δv和相对位置Δr。物理含义你可以想象粒子i静止不动粒子j以Δv运动。它们能否相撞取决于Δv是否指向Δr即二者是否在接近。2. 碰撞条件它们中心距离等于σ3. 展开成标准二次方程4. PPT 中的判别式d就是二次方程的判别式b² - 4ac5. 为什么条件Δv · Δr 0直接返回∞如果Δv · Δr 0Δv · Δr是相对速度在相对位置方向上的投影。如果 0说明两个粒子正在远离或相对静止。它们当前的距离不会减小因此无论判据d如何t只能是负值过去的时间或无解。所以直接返回无限大未来不会发生碰撞。6. 最终取根公式二、关于PQ的用法初始化Q好吧让我们来探讨一下这里的PQ是怎么使用的。首先我具有如此之多的粒子并且他们中有一些是静止的有一些是具有初始速度的被放置在一个单位面积的空间中。那么这个时候pq里面会有什么呢你之前说pq里装的是可能的碰撞但是在这个初始化场景下我们并不知道哪些是可能的碰撞呀简要讲一讲。A在初始化时PQ 里会被填入“所有理论上可能发生的碰撞”即使我们不知道它们是否真的会发生。这个“强行计算并插入后续通过失效检测过滤掉无效事件”的设计是这个算法能够避免复杂事件管理的关键。1. 初始化阶段强制计算所有潜在的“第一次碰撞”在模拟开始的那一刻t0所有粒子的位置和速度都是已知的。虽然我们不知道谁会先撞上谁但我们可以假设没有其他粒子干扰计算每个粒子与所有其他粒子的“理论首次碰撞时间”。具体操作粒子-粒子对于每一对粒子(i, j)调用timeToHit(particles[j])计算出它们在假设直线运动下首次碰撞的时间dt。如果dt是有限值不是无穷大就将这个事件(tdt, ai, bj)插入优先队列。粒子-墙壁对于每个粒子i调用timeToHitVerticalWall()和timeToHitHorizontalWall()分别计算它撞到四面墙的时间如果有限也插入优先队列。物理后果初始化阶段的计算量是O(N²)因为要检查所有粒子对。对于粒子数量庞大的模拟这确实是一次性开销但也正是这个模型能正确运行的代价。2. 为什么可以“盲目地”把所有可能的碰撞都塞进去因为你不知道哪些碰撞会被“截胡”。比如粒子 A 和 B 预计在t5时相撞但粒子 A 在t2时先撞了墙速度改变了那么 A 和 B 在t5的碰撞就永远不会发生。这个算法的处理方式是它不会在t2时去堆里删除那个失效的(A,B, t5)事件。它只是在t2处理完墙碰撞后重新计算 A 和 B 的新碰撞时间并把新事件插入堆中。当时间推进到t5时从堆顶弹出(A,B, t5)然后检查它是否失效检查 A 的碰撞计数器countA是否自该事件创建以来增加过。如果增加了意味着 A 在t2撞过墙则(A,B)事件失效直接丢弃不处理。如果没有增加则事件有效处理真正的碰撞。结论PQ 在初始化阶段装载的是“在没有干扰情况下所有可能发生的碰撞候选事件”。这种“预测所有可能忽略失效事件”的策略是事件驱动模拟能够用堆高效处理的核心原因——你永远不需要在堆中删除任意元素只需要靠计数器自然淘汰它们。这正是你之前看到的“惰性删除Lazy Deletion”或“幽灵事件”模式在粒子碰撞模拟中的具体体现。