实时计算碰撞——处理时间延迟

Question

假设：

• 您正在编写一个程序，其中 3 个（或更多）圆（或其他几何图形）在屏幕上实时移动，所有圆都具有不同的速度，由于物理原因，速度可能会在某些时间发生变化-计算。

• 只能对每一帧进行计算

• 每一帧上进行计算，您必须确保彼此“碰撞”/“在本帧与上一帧之间的时间内发生碰撞”的圆圈将通过使用“反弹”物理计算

• 假设在这段时间之间第 x 帧和第 x+1 帧，三个圆会相互碰撞。然而，在 x 帧期间，没有一个圆接触另一个圆。在 x+1 帧中，同样的情况适用（无碰撞） 我将尝试用图像更好地说明这一点：

问题：

什么是跟踪这样的碰撞的好方法，这样碰撞就不会由于两帧之间的一些（意外的）大的时间延迟而被跳过？

这个问题在我脑海中萦绕了太久了......

编辑：

对于所有认为这篇文章过时的人：请参阅此，然后再投票决定关闭。

Answer 1

要正确执行此操作：

• 计算圆的精确碰撞时间，而不是四舍五入到下一帧：
  • 如果您的对象在一维以上移动，则需要寻根。
• 按顺序解决冲突，如下：
  • 在上述确切的碰撞时间停止模拟。
  • 解决第一次碰撞中圆的物理问题。
  • 重新计算以确定新轨迹导致的任何碰撞。
  • 重新启动模拟。
  • 重复此操作，直到到达帧末尾且没有发生碰撞。
• 任何其他计划外的物理变化也将需要更新即将发生的碰撞。

您可能会注意到这可能会进行大量计算。当你的球失去动能并最终相互静止时，这可能会特别令人讨厌——如果你的物理学使这种情况成为可能，你将需要为“静止接触”添加某种阈值（不幸的是，这可能会使情况变得复杂）你的物理学非常重要）。

---

更新，回应评论：我想澄清的是，我的答案忽略了你的假设之一——如果你假装帧边界之间没有任何时间，你就无法准确地处理冲突。碰撞不会发生在帧边界处；一般来说，碰撞将发生在帧边界之间，因此您的计算需要反映这一点。

如果您假设帧之间的所有运动都是线性的（即，您的模拟在帧边界上进行所有加速），那么确定是否、何处以及何时发生碰撞实际上非常简单。它将您的帧间“模拟”减少到几乎没有 - 您可以以封闭形式求解方程，即使您的模拟是 2D 或 3D：

posAB = posA - posB                [relative vector between circles A and B]
velAB = velA - velB                [relative velocity between circles A and B]
posAB(t) = posAB(0) + t * velAB    [relative vector as a function of time]
rAB = rA + rB                      [sum of radii of the two circles]
collision happens when distance(t) = abs(posAB(t)) == rAB
-> rAB^2 = | posAB(t) |^2 = | posAB(0) + t * velAB |^2
-> t^2 * |velAB|^2 + t * 2*posAB(0).velAB + |posAB(0)|^2 - rAB^2 == 0
solve quadratic equation for t:
   - if discriminant is negative, there is no collision.
   - if collision times are outside current timestep, there is no current collision.
   - otherwise, smallest t should be the correct collision time.
   - watch out for cases like 2 circles coming *out* of collision...

最后，听起来您正在尝试进行过早的优化。最好先让事情顺利进行，然后再让事情快速进行；在运行代码之前，您不会知道实际的瓶颈。我还认为您实际上低估了现代计算机的能力。当然，您总是可以添加足够的对象来使您的计算机陷入困境，但我认为您会惊讶地发现它需要多少......

Answer 2

仅在“框架”中评估事物的想法可能是不正确的。

最古老的 OO 模式之一是“模型-视图-控制器” - 它鼓励正在查看的内容（模型）与如何查看（视图）之间的解耦。

物理引擎对模型对象进行操作，因此会始终跟踪它们之间的交互 ​​- 因此，当视图出现并询问“帧 x+1”中每个圆的位置和方向时， ”场景，它可以根据自上次查看请求以来已经过去的实际时间轻松回答。

Answer 3

我知道你的问题表明物理只能在每一帧进行评估，但我不明白什么时候会出现这种情况。以足够小的步骤逐步增量更新物理以避免对象完全绕过彼此（每一步更新一次）是很简单的。

然而，坚持显式更新方案（速度乘以时间步长）仅适用于低速度。正如在许多基于物理的游戏中所见，提高速度通常会导致穿透物体。
大多数简单的物理引擎选择只允许这些错误，因为强大的碰撞检测是非常困难和昂贵的。

如果将适用性限制为仅圆形，则可以采取一些措施。 则将对象的距离写为时间函数（在时间步长内）

x_a = x0_a + v_a*t
x_b = x0_b + v_b*t
d_ab = norm(x_a-x_b) = norm(x0_b-x0_a + (v_b-v_a)*t) = norm(dx + dv*t)

如果距离函数 d_ab 等于任意 r_a+r_b 半径之和， >t 在时间步内，就会发生碰撞。因此，首先检查哪些对象发生碰撞（如果有），然后从该点继续并重做分析，直到到达时间步的末尾。相当复杂，并且仍然只适用于圆/球体。

Answer 4

这里碰撞检测的关键词是“连续”或“不连续”。

就像其他一些答案所写的那样，大多数现代碰撞库都采用非连续版本，因为分析许多碰撞形状的确切碰撞时间的成本很高。这意味着您让对象相互渗透，检测到这一点，然后调整它们的速度以抵消相互渗透。正如已经指出的那样，这允许快速移动的物体相互经过。这是通过增加运行物理的频率来解决的，本质上您需要将其与渲染分离（使用更快的计时器运行它）。您解决相互渗透等问题的实际方法属于另一个问题的范围。

然而，对于圆，您可以分析求解任何一对具有恒定（或加速）速度的圆的精确碰撞时间，这一事实使您可以在这种特殊情况下进行连续碰撞检测。这将是一个不错的项目，但我不确定这是否是正确的方法，因为您可能突然想要包含其他形状，然后您就陷入困境。您必须解决的公式已作为答案发布。

除了总结这两种方法之外，我想在这里补充一点，因为你似乎非常关心“现代计算系统”的处理速度，现在的计算机即使以简单的方式检查所有这些计算，也能以极快的速度执行任何这些计算。成对的圆圈，如果你稍微优化一下内部代码。与渲染相比，为了解决高速的非连续情况，提高物理速度可能没有任何问题。

非连续引擎为避免对所有对象进行配对检查而添加的内容是使用某种数据结构来跟踪对象及其在空间中的一般位置和占用情况，以检测潜在重叠，而无需检查每个物体对每个物体。这在行话中被称为“广泛阶段”。如果你开始增加对象的数量，你最终肯定需要实现这样的东西。您没有说明“大量”圆圈是什么或您的目标CPU，因此希望您可以跳过这一点并以简单的方式作为开始，但很难说，除非您发布您的用例。

底线：我会选择经过尝试和测试的非连续引擎类型，具有足够的物理频率以避免高速跳跃情况，并且不用担心性能。如果您确实有兴趣为游戏编写代码，并且不想关心细节，您可以简单地使用一些现有的 2D 物理库，例如 花栗鼠 或 Box2D。我不熟悉它们的实现，但我确信如果您研究代码，它们也是学习该主题的好方法。