从一开始，碰撞检测就好像是一个 O(n^2) 问题。
您有一堆对象，您需要检查每个对象是否与任何其他对象发生碰撞。但是，我知道将每个对象与所有其他对象进行检查是非常低效的。如果两个球甚至彼此不靠近，为什么要在两个球之间进行相对昂贵的碰撞检查？
这是我正在处理的简单程序的示例：
如果您有 1000 个球，那么如果您使用简单的碰撞检测，您将有 1000^2 次收集检查（一百万）！这种碰撞检查很快成为我的应用程序的瓶颈。我需要实施一些广泛的阶段修剪。
使用 2d 圆形对象时，应该使用哪些技术来修剪碰撞检查？我读过关于 QuadTrees、BSP、空间散列等的信息，但很难找出最适合这个用例的方法。
有没有人知道什么可能最有效？
空间散列。请参阅Hugo Elias 的相关页面。
我不会使用 QuadTrees 或任何复杂的东西，因为当球在它们之间移动时，你会不断地平衡和重新平衡树。仅仅拥有一个网格可能会更有效 - 每次移动球时，您都可以计算它所在的网格单元，如果它发生变化则将其扔到那里。每次您需要进行碰撞检查时，您只需检查中心在您的网格中的球，或者如果您足够靠近边缘，则在相邻的球中。
您可以尝试使用网格大小来找到最佳值。你可能会发现这取决于你有多少球。
我在下面的评论中说过这一点，但我认为它应该成为答案的一部分：仅在某物移动时进行碰撞检测，因此您只需检查移动的物体与其网格正方形中的物体（以及上面提到的相邻物体） ）。这样，如果底部有一堆没有移动的东西，很快就不会检查这些对象是否发生碰撞，因为它们的网格内没有任何东西移动，也没有任何东西移入或移出它们的网格。
我支持 Grid 方法。球的 2D 模拟不会受益于 QuadTree（通常在您具有复杂的几何形状，如角色和建筑物时使用）或 BSP（如果您的物体分散/集中度非常不均匀，则应该选择它，例如高浓度区域和低浓度区域，在多人游戏或策略游戏中）