低帧率的碰撞检测

Question

我不了解碰撞检测算法，但出于教育目的，我正尝试在 Python 中尝试处理粒子系统中的碰撞。

我现在检测碰撞的方式似乎很低效。可能是目前最慢的算法：

• 遍历我的粒子列表中的所有粒子（由半径定义的圆）（通过for循环），调用当前粒子p
• 在每次迭代中，将 p 与每个其他粒子（另一​​个 for 循环）进行比较
• 检测碰撞

使用上述方法，当粒子计数高且 FPS 低时，我的一些粒子甚至没有检测到碰撞。有没有办法在我当前的方法中防止这种情况，或者我是否必须实施另一种更有效的方法（这可能是可行的方法）？

Answer 1

提高效率的常用技术是将所有对象放入某种 space 分区数据结构中，以便将对数限制为接近 O(n) 而不是 O(n^2) )，这就是你现在所拥有的。四叉树和 k-d 树是两个候选者。这些树中的节点代表 space 的区域。只需要检查包含在同一区域中或与同一区域相交的对象对。

为了避免遗漏碰撞，仅仅比较点是不够的。相反，检查每个粒子从先前位置到当前位置的线段的交点。因此，您需要 "edge" quadtree or kd-tree.

要考虑的另一件事是是构建一个 space 分区并在帧之间更新它，还是为每个帧从头开始重建分区。前者要复杂得多，可能不会产生更好的速度。先试试后者。