什么技术应该用于修剪2D碰撞检查？

Question

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

你有一堆对象，需要检查每个对象是否与其他对象发生碰撞。然而，我知道对每个对象进行所有其他对象的相对位置检查非常低效。如果两个球根本不接近，为什么要执行一个相对昂贵的碰撞检查呢？

这是我正在开发的简单程序的示例：

如果你有1000个球，那么如果使用朴素的碰撞检测，你将需要进行1000^2次集合检查（100万次）！这种碰撞检测很快成为我的应用程序的瓶颈。我需要实现一些广域剪枝技术。

在处理二维圆形对象时，应使用什么技术来剪枝碰撞检查？我已经阅读了关于QuadTrees、BSP、空间哈希等技术，但很难弄清楚哪种方法最适合这种情况。

有人知道什么方法能够最好地解决这个问题吗？

- Simucal

Answer 1

空间哈希。请参见Hugo Elias关于此的页面。

- Breton

Answer 2

我不建议使用四叉树或其他复杂的数据结构，因为球在移动时需要不断平衡和重构树结构。相比之下，使用网格会更有效率。每次移动一个球时，只需计算它所在的网格单元格，并将其放入其中。每次进行碰撞检查时，只需检查球的中心是否位于你的网格内，或者在边缘附近的相邻网格内。

你可以尝试调整网格大小以找到最佳值，这可能取决于你有多少个球。

我在下面的评论中提到过这一点，但我认为它应该作为答案的一部分： 只有当物体移动时才进行碰撞检测，这样你只需要检查移动物体与其网格方格（以及上述提到的相邻方格）中的物体是否发生碰撞。这样，如果底部堆积了一些静止的物体，很快这些物体就不会被检查碰撞，因为它们的网格内没有任何东西在移动，也没有任何东西在它们的网格内进出。

- Paul Tomblin

---

我在我的回答中添加了相关问题并从你的回答中删除了问题，因为它会分散注意力。 - mmcdole

Answer 3

我赞同使用网格方法。对于球体的2D模拟，不需要使用四叉树（通常用于具有复杂几何形状的角色和建筑物）或BSP（如果您在多人游戏或策略游戏中具有非常不均匀的物体分布/浓度，例如高浓度区域和低浓度区域，则应选择BSP）。

- Robert Gould

---

看一下上面的图片，你认为这构成了足够不均匀的浓度吗？通常窗口会更大，球会沉在底部。您仍然建议使用网格而不是BSP吗？ - mmcdole

BSP是一种不规则网格，我建议使用类似棋盘的规则网格。不同之处在于，与BSP相比，类似棋盘的网格易于实现和调试，并且即使用于专业游戏也足够适用。如果性能成为问题，或者作为个人挑战，您可以将网格升级到BSP。 - Robert Gould

在您的情况下，浓度实际上是不均匀的。在下面，您有很多球，而在顶部则较少。因此，您可以向底部使用更细的网格大小，这是专业知识的应用，因为您知道会发生什么，而且这不像台球桌那样是一个非常普遍的情况。 - Robert Gould

通常，对象被分为静态和动态。动态对象会检查与动态和静态对象的碰撞，但静态对象根本不会检查碰撞，因为它们不会移动。在许多模拟中，具有低动量的动态对象将被放置在静态容器中，以优化性能。 - Robert Gould

@Robert Gould，你说得对，他们受到了压力，然后重新排列成更紧密的配置。我正在考虑实现一个网格，并编辑我的帖子以展示结果。 - mmcdole