data-structures - 应该使用什么技术来修剪 2d 碰撞检查？

Question

从一开始，碰撞检测感觉就像是一个 O(n^2) 问题。

您有一堆对象，您需要检查每个对象是否与任何其他对象发生碰撞。但是，我知道根据所有其他对象检查每个对象是非常低效的。如果两个球彼此不靠近，为什么要在两个球之间进行相对昂贵的碰撞检查？

这是我正在处理的简单程序的示例:



如果您有 1000 个球，那么如果您使用天真的碰撞检测，您将有 1000^2 个集合检查(一百万)!这种碰撞检查很快成为我应用程序中的瓶颈。我需要实现一些广泛的阶段修剪。

在处理二维圆形对象时，应该使用哪些技术来修剪碰撞检查？我已经阅读了有关 QuadTrees、BSP、空间散列等的内容，但很难找出最适合此用例的方法。

有没有人知道什么可能最有效？

Answer 1

我不会使用 QuadTrees 或任何复杂的东西，因为当球在它们之间移动时，你会不断地平衡和重新平衡树。仅仅有一个网格可能会更有效 - 每次移动球时，您只需计算它所在的网格单元，如果它发生变化，就将其扔到那里。每次您需要进行碰撞检查时，您只需检查中心位于您的网格中的球，或者如果您足够靠近边缘，则可以检查相邻的球。

您可以试验网格大小以找到最佳值。你可能会发现这取决于你有多少球。

我在下面的评论中说过这一点，但我认为它应该成为答案的一部分:
仅当某物移动时才进行碰撞检测，因此您只需根据其网格方块(以及上面提到的相邻网格)中的物体检查移动的物体。这样，如果你在底部找到一堆不动的东西，很快这些物体就不会被检查是否发生碰撞，因为它们的网格内没有任何东西在移动，也没有任何东西进出它们的网格。