9.4 多物体碰撞检测策略
在屏幕上有只有两个物体时，判断它们之间的碰撞是非常简单的。但是如果物体很多时，我们就需要了解一些碰撞检测的策略，以便不遗漏任何可能发生的碰撞。当要检测的物体越来越多时，如果进行有效的判断就显得至关重要。
9.4.1 基本的多物体碰撞检测
当只有两个物体时，碰撞只可能在 A - B 物体间发生。如果有三个物体，就有三种可能：A – B，B – C，C – A。如果是四个物体就有六种可能，五个物体就有十种可能。
如果物体多达 20 个，就需要分别进行判断 190 次。这就意味着在我们的 enterFrame 函数中，需要调用 190 次 hitTest 方法或距离计算。
如果使用这种方法，那么就会多用出必要判断的两倍！比如说 20 个物体就执行了 380次 if 语句（20 个影片每个判断 19 次，20 * 19 = 380）。大家现在知道学习本节内容的重要性了吧。
看一下问题，审视一下平常的做法。假设我们有六个Sprite，分别为 sprite0，sprite1，sprite2，sprite3，sprite4，sprite5。让它们运动并执行反弹，我们想要知道它们之间何时会发生碰撞。思考一下，依次获得每个Sprite的引用，然后再执行循环，再去和其它的Sprite进行比较。下面是一段伪代码：
numSprites = 6;
for (i = 0; i < numSprites; i++)
{
spriteA = sprites[i];
for (j = 0; j < numSprites; j++)
{
spriteB = sprites[j];
if (spriteA.hitTestObject(spriteB))
{
// 执行代码
}
}
}
六个Sprite执行了 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 时，所有的Sprite都已经和它进行过比较了，因此 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
}
}
}
请注意，外层循环执次数比Sprite总数少一次。就像我们在最后的列表中看到的，不需要让最后一个Sprite与其它Sprite比较，因为它已经被所有Sprite比较过了。内层循环的索引以外循环索引加一作为起始。这是因为上一层的内容已经比较过了，而且不需要和相同的索引进行比较。这样一来执行的效率达到了 100％。
9.4.2 多物体弹性
我们再来看一个小程序。同样也是气泡效果的交互运动，不过这次所有的气泡彼此间都可以相互反弹。效果如图 9-7 所示。
图9-7 多物体弹性
以下代码见文档类 Bubbles2.as：
package
{
import flash.display.Sprite;
import flash.events.Event;
public class Bubbles2 extends Sprite
{
private var balls:Array;
private var numBalls:Number = 30;
private var bounce:Number = -0.5;
private var spring:Number = 0.05;
private var gravity:Number = 0.1;
public function Bubbles2()
{
init();
}
private function init():void
{
balls = new Array();
for(var i:uint = 0; i < numBalls; i++)
{
var ball:Ball = new Ball(Math.random() * 30 + 20, Math.random() * 0xffffff);
ball.x = Math.random() * stage.stageWidth;
ball.y = Math.random() * stage.stageHeight;
ball.vx = Math.random() * 6 - 3;
ball.vy = Math.random() * 6 - 3;
addChild(ball);
balls.push(ball);
}
addEventListener(Event.ENTER_FRAME, onEnterFrame);
}
private function onEnterFrame(event:Event):void
{
for(var i:uint = 0; i < numBalls - 1; i++)
{
var ball0:Ball = balls[i];
for(var j:uint = i + 1; j < numBalls; j++)
{
var ball1:Ball = balls[j];
var dx:Number = ball1.x - ball0.x;
var dy:Number = ball1.y - ball0.y;
var dist:Number = Math.sqrt(dx * dx + dy * dy);
var minDist:Number = ball0.radius + ball1.radius;
if(dist < minDist)
{
var angle:Number = Math.atan2(dy, dx);
var tx:Number = ball0.x + dx / dist * minDist;
var ty:Number = ball0.y + dy / dist * minDist;
var ax:Number = (tx - ball1.x) * spring;
var ay:Number = (ty - ball1.y) * spring;
ball0.vx -= ax;
ball0.vy -= ay;
ball1.vx += ax;
ball1.vy += ay;
}
}
}
for(i = 0; i < numBalls; i++)
{
var ball:Ball = balls[i];
move(ball);
}
}
private function move(ball:Ball):void
{
ball.vy += gravity;
ball.x += ball.vx;
ball.y += ball.vy;
if(ball.x + ball.radius > stage.stageWidth)
{
ball.x = stage.stageWidth - ball.radius;
ball.vx *= bounce;
}
else if(ball.x - ball.radius < 0)
{
ball.x = ball.radius;
ball.vx *= bounce;
}
if(ball.y + ball.radius > stage.stageHeight)
{
ball.y = stage.stageHeight - ball.radius;
ball.vy *= bounce;
}
else if(ball.y - ball.radius < 0)
{
ball.y = ball.radius;
ball.vy *= bounce;
}
}
}
}
本例中的交互动画还需要两点补充说明。这是碰撞后的运动代码：
if(dist < minDist)
{
var angle:Number = Math.atan2(dy, dx);
var tx:Number = ball0.x + Math.cos(angle) * minDist;
var ty:Number = ball0.y + Math.sin(angle) * minDist;
var ax:Number = (tx - ball1.x) * spring;
var ay:Number = (ty - ball1.y) * spring;
ball0.vx -= ax;
ball0.vy -= ay;
ball1.vx += ax;
ball1.vy += ay;
}
只要 ball0 与 ball1 发生了碰撞就会执行这段代码。基本上与前面例子中的centerBall 意思相近，只不是用 ball0 代替 centerBall。求出需要它俩的夹角，然后计算目标点的 x,y 坐标，这就是 ball1 要到达的点，这样做才不会让两个小球碰撞到一起。接下来，计算出 x,y 轴的加速度 ax,ay。下面要注意了，本例中，不仅 ball1 要向 ball0 弹性运动，而且 ball0 还必需离开 ball1，加速度的方向相反。只需要将 ax 和 ay 加到 ball1 的速度向量中，再从 ball0 的速度向量中将它们减去即可！这样就免去了计算两次的麻烦。大家也许认为这样做，就相当于把最终的加速度扩大了两倍。是的，您说得没错。为了弥补这一点，我们将 spring 的值设置得比平时小一些。 下面说说另一个问题。代码中使用 Math.atan2 计算夹角，然后再用 Math.cos 和 Math.sin 求出目标点：
var angle:Number = Math.atan2(dy, dx); var tx:Number = ball0.x + Math.cos(angle) * minDist; var ty:Number = ball0.y + Math.sin(angle) * minDist;
但是大家不要忘记，正弦是对边与斜边之比，而余弦是邻边与斜边之比。请注意，该角的对边就是 dy，邻边就是 dx，而斜边就是 dist。所以，我们实际上可以将这三行代码缩短为两行：
var tx:Number = ball0.x + dx / dist * minDist; var ty:Number = ball0.y + dy / dist * minDist;
瞧！只用了两个简单的除法就取代了调用三次三角函数。下面请实验一下这个泡泡球的例子，试调整 spring,gravity,number 和 ball 的大小，观察运行结果。大家还可以添加摩擦力或鼠标交互的动作。
9.5碰撞检测的其它方法
ActionScript 内置的 hitTest 方法与距离碰撞检测方法并不是实现碰撞检测仅有的方法，但使用它们可以完成大部分的碰撞检测。如果要进行更深入的研究， 我们会发现聪明的开发者们已经提出了一些非常精巧的碰撞检测方法。比如，Grant Skinner 提出了一种通过操作多个位图对象，来确定什么时候，哪些物体之间的像素发生了重叠。大家可以在 www.gskinner.com找到相关内容。
文件下载（已下载 2430 次）发布时间：2011/6/27 下午8:18:59 阅读次数：9149
