普林斯顿算法讲义（四）（1）

6.1 事件驱动模拟

原文：algs4.cs.princeton.edu/61event

译者：飞龙

协议：CC BY-NC-SA 4.0

本章节正在建设中。

根据弹性碰撞的法则使用事件驱动模拟模拟 N 个碰撞粒子的运动。这种模拟在分子动力学（MD）中被广泛应用，以理解和预测粒子级别的物理系统的性质。这包括气体中分子的运动，化学反应的动力学，原子扩散，球体堆积，围绕土星的环的稳定性，铈和铯的相变，一维自引力系统以及前沿传播。相同的技术也适用于其他涉及粒子系统的物理建模领域，包括计算机图形学，计算机游戏和机器人技术。我们将在第七章再次讨��其中一些问题。

一个好的参考资料

硬球模型. 硬球模型（台球模型）是容器中原子或分子运动的理想化模型。我们关注二维版本称为硬盘模型。这个模型的显著特性如下。

• N 个运动中的粒子，限制在单位盒中。
  
• 粒子i具有已知位置(rx[i], ry[i])、速度(vx[i], vy[i])、质量m[i]和半径σ[i]。
  
• 粒子之间以及与反射边界之间通过弹性碰撞相互作用。
  
• 没有其他力的作用。因此，粒子在碰撞之间以恒定速度直线运动。
  

这个简单模型在统计力学中起着核心作用，这个领域将宏观可观测量（例如温度、压力、扩散常数）与微观动力学（单个原子和分子的运动）联系起来。麦克斯韦和玻尔兹曼使用这个模型推导出相互作用分子的速度分布与温度的关系；爱因斯坦用它来解释花粉颗粒在水中的布朗运动。

模拟. 有两种自然方法来模拟粒子系统。

• 时间驱动模拟. 将时间离散化为大小为dt的量子。在每个dt时间单位后更新每个粒子的位置并检查重叠。如果有重叠，将时钟回滚到碰撞时刻，更新碰撞粒子的速度，并继续模拟。这种方法简单，但存在两个重大缺点。首先，我们必须在每个时间量子中执行 N²次重叠检查。其次，如果dt太大，碰撞粒子在我们查看时未发生重叠，我们可能会错过碰撞。为了确保相对准确的模拟，我们必须选择dt非常小，这会减慢模拟速度。
  
• 事件驱动模拟.通过事件驱动模拟，我们只关注发生有趣事件的时间点。在硬盘模型中，所有粒子在碰撞之间以恒定速度直线运动。因此，我们的主要挑战是确定粒子碰撞的有序序列。我们通过维护一个按时间排序的优先队列来解决这个挑战。在任何给定时间，优先队列包含所有未来可能发生的碰撞，假设每个粒子永远沿直线轨迹运动。随着粒子碰撞并改变方向，一些计划在优先队列上的事件变得“过时”或“无效”，不再对应物理碰撞。我们采取一种懒惰策略，将这些无效的碰撞留在优先队列上，等待识别并丢弃它们被删除时。主要的事件驱动模拟循环工作如下：

• 删除即将发生的事件，即具有最小优先级t的事件。
  
• 如果事件对应于无效的碰撞，将其丢弃。如果其中一个粒子自事件插入优先队列以来已经参与了碰撞，则该事件无效。
  
• 如果事件对应于粒子i和j之间的物理碰撞：

• 将所有粒子沿直线轨迹推进到时间t。
  
• 根据弹性碰撞的法则更新两个碰撞粒子i和j的速度。
  
• 确定所有未来可能涉及i或j的碰撞事件，假设所有粒子从时间t开始沿直线轨迹移动。将这些事件插入优先队列。
  

• 如果事件���应于粒子i和墙壁之间的物理碰撞，对粒子i执行类似的操作。
  

• 这种事件驱动的方法比时间驱动的方法产生了更健壮、更准确和更高效的模拟。
  

碰撞预测。 我们回顾了指定粒子是否以及何时与边界或其他粒子碰撞的公式，假设所有粒子都沿直线轨迹移动。

• 粒子与墙壁之间的碰撞. 给定时间t时粒子的位置(rx, ry)、速度(vx, vy)和半径σ，我们希望确定它是否以及何时会与垂直或水平墙壁碰撞。
  由于坐标在 0 和 1 之间，如果ry + Δt vy等于σ或(1 - σ)，则粒子在时间t + Δt 时与水平墙面接触。解出Δt得到：

• 一个类似的方程预测了与垂直墙壁的碰撞时间。
• 两个粒子之间的碰撞. 给定时间t时两个粒子i和j的位置和速度，我们希望确定它们是否以及何时相互碰撞。
  让(rx[i]’ , ry[i]’ )和(rx[j]’ , ry[j]’ )表示粒子i和j在接触时刻，即t + Δt的位置。当粒子碰撞时，它们的中心相距σ = σ[i] + σ[j]的距离。换句话说：

σ² = (rx[i]’ - rx[j]’ )² + (ry[i]’ - ry[j]’ )²

• 在碰撞之前的时间内，粒子沿直线轨迹移动。因此，

rx[i]’ = rx[i] + Δt vx[i], ry [i]’ = ry[i] + Δt vy[i]

rx[j]’ = rx[j] + Δt vx[j], ry [j]’ = ry[j] + Δt vy[j]

• 将这四个方程代入前一个方程，解出得到的二次方程的Δt，选择物理相关的根，并简化，我们得到Δt的表达式，其中包括已知位置、速度和半径。

• 如果Δv ⋅ Δr ≥ 0 或 d < 0，则二次方程对Δt > 0 没有解；否则我们保证Δt ≥ 0。

碰撞解决方案。 在本节中，我们提供了指定粒子在与反射边界或其他粒子发生弹性碰撞后行为的物理公式。为简单起见，我们忽略多粒子碰撞。有三个方程控制着一对硬盘之间的弹性碰撞：(i) 线性动量守恒，(ii) 动能守恒，以及(iii) 碰撞时，法向力作用于碰撞点的表面垂直方向。对物理感兴趣的学生被鼓励从第一原理推导这些方程；其余的可以继续阅读。

• 粒子与墙壁之间。 如果具有速度（vx，vy）的粒子与垂直于x轴的墙壁碰撞，则新速度为（-vx，vy）；如果与垂直于y轴的墙壁碰撞，则新速度为（vx，-vy）。
  
• 两个粒子之间。 当两个硬盘碰撞时，法向力沿着连接它们中心的线作用（假设没有摩擦或旋转）。在接触瞬间，完全弹性碰撞的法向冲量（Jx，Jy）在x和y方向上的作用是：

• 其中m[i]和m[j]分别是粒子i和j的质量，σ、Δx、Δy和Δ v ⋅ Δr如上所定义。一旦我们知道冲量，我们就可以应用牛顿第二定律（以动量形式）来计算碰撞后立即的速度。

vx[i]’ = vx[i] + Jx / m[i], vx[j]’ = vx[j] - Jx / m[j]

vy[i]’ = vy[i] + Jy / m[i], vy[j]’ = vy[j] - Jy / m[j]

Java 中的粒子碰撞模拟。 我们的实现涉及以下数据类型：MinPQ.java、Particle.java 和 CollisionSystem.java。

• 粒子数据类型。 代表在单位盒中移动的粒子。
  
• 事件数据类型。 表示碰撞事件的数据类型。有四种不同类型的事件：与垂直墙壁的碰撞、与水平墙壁的碰撞、两个粒子之间的碰撞和重绘事件。这将是一个很好的机会来尝试面向对象编程和多态性。我们提出以下更简单（但略显不够优雅）的方法。
  为了实现isValid，事件数据类型应该在事件创建时存储相关粒子的碰撞计数。如果粒子的当前碰撞计数与事件创建时的相同，则该事件对应于物理碰撞，即没有干预碰撞。
  

数据文件。 我们使用以下数据格式。第一行包含粒子数量 N。剩下的 N 行中，每行包含 6 个实数（位置、速度、质量和半径），后跟三个整数（颜色的红、绿、蓝值）。您可以假设所有位置坐标在 0 和 1 之间，颜色值在 0 和 255 之间。此外，您可以假设没有粒子相互交叉或与墙壁相交。

N                            
rx ry vx vy radius mass r g b
rx ry vx vy radius mass r g b
rx ry vx vy radius mass r g b
rx ry vx vy radius mass r g b

这里是一些示例数据文件：

| 文件 | 描述 |

| pendulum.txt | 钟摆效应 |

其他潜在的数据文件

• 一个颗粒在运动。
  
• 两个颗粒正面碰撞。
  
• 两个颗粒，一个静止，以角度碰撞。
  
• 一个红色颗粒在运动，N 个蓝色颗粒静止。
  
• N 个粒子在一个具有随机初始方向的晶格上（但速度相同），以使总动能与某个固定温度 T 一致，总线性动量= 0。 对于不同的 T 值，有不同的数据集。
  
• 扩散 I：在容器中心附近分配 N 个非常小的相同大小的粒子，具有随机速度。
  
• 扩散 II：左侧有 N 个蓝色颗粒，右侧有 N 个绿色颗粒，分配速度使它们热化（例如，离开它们之间的隔板并在一段时间后保存位置和速度）。 观察它们混合。 计算平均扩散速率？
  
• N 个大颗粒，所以没有太多空间可以移动而不碰到东西。
  
• 爱因斯坦对布朗运动的解释：中间有一个大红色颗粒，N 个较小的蓝色颗粒。
  

普林斯顿算法讲义（四）（2）https://developer.aliyun.com/article/1484180