现在的位置: 首页 > 综合 > 正文

多物体碰撞检测方法

2014年09月05日 ⁄ 综合 ⁄ 共 2227字 ⁄ 字号 评论关闭

多物体碰撞检测方法 在屏幕上有只有两个物体时, 判断它们之间的碰撞是非常简单的。但是如果物体很多时,我们就需要了解一些碰撞检测的策略,以便不遗漏任何可能发生的碰撞。当要检测的物体越来越多时,如果进行有效的判断就显得至关重要。 基本的多物体碰撞检测 当只有两个物体时,碰撞只可能在 A - B 物体间发生。如果有三个物体,就有三种可能:A – B, B – C, C – A。如果是四个物体就有六种可能,五个物体就有十种可能。 如果物体多达 20 个,就需要分别进行判断 190 次。这就意味着在我们的 enterFrame
函数中,需要调用 190 次 hitTest 方法或距离计算。 如果使用这种方法,那么就会多用出必要判断的两倍!比如说 20 个物体就执行了 380 次 if 语句(20 个影片每个判断 19 次,20 * 19 = 380)。大家现在知道学习本节内容的重要性了吧。 看一下问题,审视一下平常的做法。假设我们有六个影片,分别为 sprite0, sprite1, sprite2, sprite3, sprite4, sprite5。让它们运动并执行反弹,我们想要知道它们之间何时会发生碰撞。思考一下,依次获得每个影片的引用,然后再执行循环,再去和其它的影片进行比较。下面是一段伪代码:
numSprites = 6; for (i = 0; i < numSprites; i++) { spriteA = sprites[i]; for (j = 0; j < numSprites; j++) { spriteB = sprites[j]; if (spriteA.hitTestObject(spriteB)) { // 执行代码 } } } 六个影片执行了 36 次判断。看上去很合理,对吗?其实,这段代码存在着两大问题。首先,来看第一次循环,变量 i 和 j 都等于 0。因此 spriteA
所持的引用是 sprite0,而 spriteB 的引用也是一样。嗨,我们原来是在判断这个影片是否和自己发生碰撞!无语了。所以要在 hitTest 之前确认一下 spriteA != sprieB,或者可以简单地写成 i != j。代码就应该是这样: numSprites = 6; for (i = 0; i < numSprites; i++) { spriteA = sprites[i]; for (j = 0; j < numSprites; j++) { spriteB = sprites[j];
if (i != j && spriteA.hitTestObject(spriteB)) { // do whatever } } } OK,现在已经排除了六次判断,判断次数降到了 30 次,但还是太多。下面列出每次比较的过程: sprite0 与 sprite1, sprite2, sprite3, sprite4, sprite5 进行比较 sprite1 与 sprite0, sprite2, sprite3, sprite4, sprite5 进行比较 sprite2 与 sprite0, sprite1,
sprite3, sprite4, sprite5 进行比较 sprite3 与 sprite0, sprite1, sprite2, sprite4, sprite5 进行比较 sprite4 与 sprite0, sprite1, sprite2, sprite3, sprite5 进行比较 sprite5 与 sprite0, sprite1, sprite2, sprite3, sprite4 进行比较 请看第一次判断: 用 sprite0 与 sprite1 进行比较。再看第二行: sprite1
与 sprite0 进行比较。它俩是一回事,对吧?如果 sprite0 没有与 sprite1 碰撞,那么 sprite1 也肯定不会与 sprite0 碰撞。或者说,如果一个物体与另一个碰撞,那么另一个也肯定与这个物体发生碰撞。所以可以排除两次重复判断。如果删掉重复判断,列表内容应该是这样的: sprite0 与 sprite1, sprite2, sprite3, sprite4, sprite5 进行比较 sprite1 与 sprite2, sprite3, sprite4, sprite5 进行比较
sprite2 与 sprite3, sprite4, sprite5 进行比较 sprite3 与 sprite4, sprite5 进行比较 sprite4 与 sprite5 进行比较 sprite5 没有可比较的对象! 我们看到第一轮判断,用 sprite0 与每个影片进行比较。随后,再没有其它影片与 sprite0 进行比较。把 sprite0 放下不管,再用 sprite1 与剩下的影片进行比较。当执行到最后一个影片 sprite5 时,所有的影片都已经和它进行过比较了,因此 sprite5 不需要再与任何影片进行比较了。结果,比较次数降到了
15 次,现在大家明白我为什么说初始方案通常执行了实际需要的两倍了吧。 那么接下来如果写代码呢?仍然需要双重嵌套循环,代码如下: numSprites = 6; for (i = 0; i < numSprites - 1; i++) { spriteA = sprites[i]; for (j = i + 1; j < numSprites; j++) { spriteB = sprites[j]; if (spriteA.hitTestObject(spriteB)) { // do whatever
} } } 请注意,外层循环执次数比影片总数少一次。就像我们在最后的列表中看到的,不需要让最后一个影片与其它影片比较,因为它已经被所有影片比较过了。 内层循环的索引以外循环索引加一作为起始。这是因为上一层的内容已经比较过了,而且不需要和相同的索引进行比较。这样一来执行的效率达到了 100%。

抱歉!评论已关闭.