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

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

你有一堆对象,你需要检查每个对象是否与任何其他对象发生碰撞.但是,我知道将每个对象与所有其他对象进行对比检查是非常无效的.为什么两个球之间的相对昂贵的碰撞检查,如果它们彼此不相近？

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

如果你有1000个球,那么如果你进行了天真的碰撞检测,你将获得1000 ^ 2次收集检查(一百万)!这种冲突检查很快成为我的应用程序的瓶颈.我需要实施一些广泛的阶段修剪.

在处理2d - 圆形物体时,应该使用哪些技术来修剪碰撞检查？我已经阅读过关于QuadTrees,BSP,空间散列等的内容,但很难理解哪种方法最适合这个用例.

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

空间哈希. http://freespace.virgin.net/hugo.elias/models/m_colide.htm

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

您可以尝试使用网格大小来查找最佳值.你可能会发现这取决于你有多少球.

我在下面的评论中说过这个,但我认为它应该成为答案的一部分:只有当某些东西移动时才进行collsion检测,所以你只需要检查移动的东西是否反对它的网格中的东西(和上面提到的相邻的东西) ).这样,如果你在底部得到一堆没有移动的东西,很快就会检查这些对象的碰撞,因为没有任何东西在他们的网格中移动,也没有任何东西移入或移出他们的网格.