## Question of the Week

Collision Detection Among Multiple Objects
by kirupa  |  12 August 2005

In the previous page, I briefly provided one way to check for collisions. In this page, I'll try to provide a more efficient method.

More Efficient Method
In our earlier collision detection code, out of the 36 checks made, only 15 are relevant. So, what we need is a method that is about 50% more efficient than what we had used. The following code, though, provides the level of efficiency needed:

totalObjects = target_mc.length;
for (i=0; i<totalObjects; i++) {
circleA = target_mc[i];
for (j=i+1; j<totalObjects; j++) {
circleB = target_mc[j];
circleA = eval(circleA);
circleB = eval(circleB);
if (circleA.hitTest(circleB)) {
}
}
}

Notice that the initial value of our second for loop has been changed. Instead of starting from zero, it starts off with the earlier value of i plus an offset value of 1. Running a trace command inside the second for loop like earlier produces the following output:

circle0 and circle1 are checked for collisions.
circle0 and circle2 are checked for collisions.
circle0 and circle3 are checked for collisions.
circle0 and circle4 are checked for collisions.
circle0 and circle5 are checked for collisions.
circle1 and circle2 are checked for collisions.
circle1 and circle3 are checked for collisions.
circle1 and circle4 are checked for collisions.
circle1 and circle5 are checked for collisions.
circle2 and circle3 are checked for collisions.
circle2 and circle4 are checked for collisions.
circle2 and circle5 are checked for collisions.
circle3 and circle4 are checked for collisions.
circle3 and circle5 are checked for collisions.
circle4 and circle5 are checked for collisions.

The above output is exactly the same as the output from our earlier method, but it does not contain any of the redundant collision checks. Isn't this just great?

Now that you have a brief idea about how our collision detection works, let's take a look at how to get it to work in Flash.

Note
 There may even be better ways than what I presented earlier. One idea that I have not tested in rearranging the items in your array so that the objects nearest to you will be checked for a collision first. Looking at the arrangement of circles, it's easy to see that there is a higher probability of near circles to collide with each other as opposed to a circle far away.

Collision Detection in Flash
First, I have provided a sample FLA file for you to download. It contains six circles like the above image, and it only contains the code for getting the circles to move. You will have to add the code for the collision detection yourself.

Once you have unzipped and opened the above FLA, you should see six circles:

Click on each circle and notice that the circles have instance names such as circle0, circle1, circle2, circle3, circle4, and circle5.

Now, select the first (and only) frame in your timeline and press F9 or go to Window | Development Tools | Actions. Copy and paste the following code above the first line of code already there:

target_mc = ["circle0", "circle1", "circle2", "circle3", "circle4", "circle5"];
//
hitTester = function () {
numCircles = target_mc.length;
for (i=0; i<numCircles; i++) {
circleA = target_mc[i];
for (j=i+1; j<numCircles; j++) {
circleB = target_mc[j];
temp_A = eval(circleA);
temp_B = eval(circleB);
if (temp_A.hitTest(temp_B)) {
dirChanger(temp_A, temp_B);
//
}
}
}
};
this.onEnterFrame = function() {
hitTester();
};

If you test your animation, you will find that all six of your circles move and change directions when any two collide. Let's take a look at the code, for here is where I go into the details of why the code works the way it does on the next page.

Onwards to the next page.

 page 2 of 3