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

data-structures collision-detection spatial

7839 观看

3回复

50185 作者的声誉

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

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

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

替代文字

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

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

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

作者: mmcdole 的来源 发布者: 2009 年 1 月 5 日

回应 (3)


6

12842 作者的声誉

空间散列。请参阅Hugo Elias关于它的页面

作者: Breton 发布者: 05.01.2009 09:31

6

142692 作者的声誉

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

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

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

作者: Paul Tomblin 发布者: 05.01.2009 09:32

2

41962 作者的声誉

我是第二个Grid方法。2D球模拟不会受益于QuadTrees(通常在人物和建筑物等复杂几何体时使用)或BSP(如果你的物体的分散/浓度非常不均匀,你应该选择,如高浓度区域和低浓度区域,在多人游戏或战略游戏中)

作者: Robert Gould 发布者: 06.01.2009 06:52
32x32