Collision Detection Among Multiple Objects

Collision detection is an important feature in various applications ranging from games to particle modeling. The basic idea behind collision detection is to determine when objects collide and to react appropriately. There are already several tutorials on this site that address various portions of collision detection, and this tutorial extends the earlier tutorials with information on how to detect collisions among multiple objects.

	Note
While the tutorial is intended for Macromedia Flash, the first half of the tutorial discusses general topics that can be applied to any language.

In prior tutorials, you had a good idea about which objects would collide with each other. The Flash code was often tailored to simply detecting when those particular objects would collide, and that was great for most cases. What about situations where you have multiple objects to check for collisions against? The answer to that requires a new tutorial - this one!

The following animation is an example of the collision detection code in action:

[ check out the collision detection ]

Notice that when a pair of circles in the above animation collide, they change directions. I have no prior knowledge of which pair of circles would collide or when/where they would collide. That uncertainty better resembles a situation you would face in real life, and our code should take into account such vagueness.

Less Efficient Method
Normally, I would first provide the directions for recreating the above animation in Flash. I am going to take the road less traveled and start by explaining how to approach this problem. I am certain you would encounter similar situations in your future Flashing endeavors.

Let's say our environment is represented by the following graphic with 5 circles that each have the ability to move around:

Our goal is to detect when any of the circles collide with each other. In order to detect a collision, we could check Circle 1, Circle 2, Circle 3, Circle 4, Circle 5, and Circle 6 with each other to check for a collision. In order to do so many repetitive tasks, you would use a loop. I will use a for loop, because it provides me with greater control over the starting and end conditions of the loop.

Our code for checking each circle with each other can be written as:

totalObjects = target_mc.length;

for (i=0; i<totalObjects; i++) {

circleA = target_mc[i];

for (j=0; j<totalObjects; j++) {

circleB = target_mc[j];

circleA = eval(circleA);

circleB = eval(circleB);

if (circleA.hitTest(circleB)) {

// your code here

}

}

}

For the purposes of this tutorial, the names of our circle movie clips are stored in an array called target_mc. Notice that I am using two for loops in the above code. Remember that in order to check for one collision, you need  two objects. Since each object is stored as an array, by using two for loops, I am able to quickly scan through each circle and check for a collision against all other circles on the stage.

Adding a simple trace statement to check for which circles are accessed during just ONE run of our collision detection function produces 36 lines. I have provided a copy of the trace command, and I also went ahead and highlighted those tests that I feel are unnecessary:

circle0 and circle0 are checked for collisions.
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 circle0 are checked for collisions.
circle1 and circle1 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 circle0 are checked for collisions.
circle2 and circle1 are checked for collisions.
circle2 and circle2 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 circle0 are checked for collisions.
circle3 and circle1 are checked for collisions.
circle3 and circle2 are checked for collisions.
circle3 and circle3 are checked for collisions.
circle3 and circle4 are checked for collisions.
circle3 and circle5 are checked for collisions.
circle4 and circle0 are checked for collisions.
circle4 and circle1 are checked for collisions.
circle4 and circle2 are checked for collisions.
circle4 and circle3 are checked for collisions.
circle4 and circle4 are checked for collisions.
circle4 and circle5 are checked for collisions.
circle5 and circle0 are checked for collisions.
circle5 and circle1 are checked for collisions.
circle5 and circle2 are checked for collisions.
circle5 and circle3 are checked for collisions.
circle5 and circle4 are checked for collisions.
circle5 and circle5 are checked for collisions.

The items highlighted in Blue are unnecessary because you are checking if an object is colliding with itself. The items in Yellow are also unnecessary. For every yellow colored line, you will see its equivalent collision check a few lines earlier. In fact, a check between circles 4 and 0 is the same as a check between circles 0 and 4. The ordering of the circles being checked isn't important in our case.

Remember, your collision detection function will itself be called numerous times in a second. Your for loop doesn't need to re-run itself automatically. In other words, it is in our best interests to keep the list of circles checked for a collision in our for loop as short and complete at the same time as possible.

Also, beyond being repetitive, another issue with the above code lies in the complexity. Since each object checks for a collision with every other object, you are basically exponentially (n^2) increasing the number of checks required to test for a collision for each object you add.

page 1 of 3