从一开始，碰撞检测就像是一个O（n^2）问题。应该使用什么技术来修剪2d碰撞检查？
你有一堆对象，你需要检查每个对象是否与任何其他对象发生碰撞。但是，我知道，检查每个对象与所有其他对象是非常无效的。为什么两个球之间相对昂贵的碰撞检查，如果他们甚至不接近彼此？
这里是我的简单程序的例子我的工作：
如果你有1000个球，然后，如果你与天真的碰撞检测去你将有1000^2集检查（一百万）！这种碰撞检查很快就成为我应用程序的瓶颈。 I 需要来实施一些宽泛的修剪。
在使用2D - 圆形对象时，应使用哪些技术来修剪碰撞检查？我读过关于QuadTrees，BSP，空间散列等的内容，但很难理清哪种方法最适合这种用例。
有没有人有什么可能最适合工作的知识？
我不会使用QuadTrees或其他任何复杂的东西，因为当树球在它们之间移动时，您会不断平衡和重新平衡树木。只有拥有一个网格可能会更有效率 - 每次移动一个球时，只需计算它所在的网格单元格，并在发生变化时将其放入该网格单元中。每次您需要进行碰撞检查时，您都可以检查中心位于网格中的球，或者在距离边缘足够近的情况下检查相邻的球。
您可以尝试使用网格大小来查找最佳值。你可能会发现它取决于你有多少球。
我在下面的评论中说过这一点，但我认为它应该成为答案的一部分： 只有在某物移动时才进行collsion检测，因此您只需检查移动的东西是否与其网格方格中的东西相对如上所述的相邻的）。这样，如果你在底部得到一堆没有移动的东西，那么很快就不会检查这些对象是否发生了碰撞，因为没有任何东西在网格中移动，也没有任何东西移动到网格中或者移出网格。
我第二个网格方法。 QuadTrees（通常用于角色和建筑物等复杂几何体时使用）或BSP（如果物体的分散度/浓度非常不均匀，如高浓度时应该选择）在多人游戏或战略游戏中）
将相关问题添加到我的答案中，并从答案中删除了问题，因为它令人分心。 – mmcdole 2009-01-05 21:46:26
很好，@Simucal。 – 2009-01-06 17:23:34