Multiple-Object Collision Detection Strategies

When you have just a couple of objects moving around the screen, its pretty simple to test them against each other. But when you get several objects, or even dozens, you need some kind of strategy for how to test them so that you dont miss any possible collisions. Furthermore, as you have more and more objects being tested , it becomes very important to perform your tests with some kind of efficiency in mind.

Basic multiple-object collision detection

With just two objects, only one collision is possibleA versus B. With three objects, you have three possibilities: A-B, B-C, and C-A. Four objects give you six collisions, and five objects give you ten collisions. When you get up to twenty objects, you need to take into account 190 separate collisions! That means that in every enterFrame handler, you need to run an if statement with a hitTest call or a distance calculation.

Thats enough as it is. You certainly dont need to be adding any unnecessary hit testing to the game plan. But many people who dive into this type of calculation for the first time wind up doing not just a few extra hit tests, but exactly twice as many as necessary! For 20 objects, they do 380 if statements (20 clips each testing 19 others, or 20 — 19 = 380). So, you can see why you should have a solid understanding of this subject.

To see the problem, lets take a look at what needs to be done, and how it is often approached. Say you have six movie clips, named mc0 , mc1 , mc2 , mc3 , mc4 , and mc5 . You have them moving around nicely , bouncing or whatever, and you want to know when any one of the clips hits any other one. The normal thing to do, when youve thought it through a bit, is to make two nested for loops. The outer one loops through each of the six clips, gets a reference to each one in turn , and then loops through again, comparing it to each of the others. Here it is in a sort of pseudocode:

 numClips = 6; for(i=0; i<numClips; i++) {       clipA = this["mc" + i];       for(j=0; j<numClips; j++)       {             clipB = this["mc" + j];             if(clipA.hitTest(clipB))             {                   // do whatever             }       } } 

Thats 36 hit tests for six clips. Seems reasonable, right? Well, this code has two huge problems.

First, take a look what happens the first time through it. The variables i and j will both equal 0. So clipA will hold a reference to mc0 , as will clipB . Hey, youre testing a clip against itself! Thats kind of dumb. Well, you could make sure that clipA != clipB before performing the hitTest , or you could even go simpler and just make sure i != j . Then you get something like this:

 numClips = 6; for(i=0; i<numClips; i++) {       clipA = this["mc" + i];       for(j=0; j<numClips; j++)       {             clipB = this["mc" + j];             if(  i != j &&  clipA.hitTest(clipB))             {                   // do whatever             }       } } 

OK, so youve eliminated six hit tests with that. Now youre down to 30. But this is still way too many. Lets chart out the exact tests youre doing. You are comparing the following:

mc0	with	mc1, mc2, mc3, mc4, mc5
mc1	with	mc0, mc2, mc3, mc4, mc5
mc2	with	mc0, mc1, mc3, mc4, mc5
mc3	with	mc0, mc1, mc2, mc4, mc5
mc4	with	mc0, mc1, mc2, mc3, mc5
mc5	with	mc0, mc1, mc2, mc3, mc4

Look at the very first test: mc0 with mc1 . Now look at the first test on the second row: mc1 with mc0 . Well, thats the same thing, isnt it? If mc0 is not hitting mc1 , then mc1 is surely not hitting mc0 . Or if one is hitting the other, then you can be sure the other is hitting the first. It turns out that you have a whole lot of these double checks in there. If you remove all the duplicate checks, you get a table like this:

 mc0   with   mc1, mc2, mc3, mc4, mc5 mc1   with   mc2, mc3, mc4, mc5 mc2   with   mc3, mc4, mc5 mc3   with   mc4, mc5 mc4   with   mc5 mc5   with   nothing! 

You see that in the first round of tests, youre testing mc0 with every other movie clip. So no other movie clip needs to test against that one again. You drop mc0 off the list. Then mc1 tests against the remaining clips, and you drop it off the list. By the time you get to the last clip, mc5 , every other clip has already tested itself for a collision with it. Theres no need to test it against anything. The result is that youre down to 15 tests. So, you see why I said the initial solution usually ends up being double what is needed.

Now, how do you code this thing? Well, you still have two nested for loops. But now it looks like this:

 numClips for(i=0;  i<numClips-1  ; i++) {       clipA = this["mc" + i];       for(  j=i+1  ; j<numClips; j++)       {             clipB = this["mc" + j];             if(clipA.hitTest(clipB))             {                   // do whatever             }       } } 

Notice that the first, outer for loop now goes to one less than the total number of clips. As you just saw in the final comparison chart, you dont need to test the last clip against anything, as its already been thoroughly tested.

In the inner loop, you always start with one higher than the index of the outer loop. This is because youve already tested everything lower, and you dont want to test the same index, which, as you saw, would be testing a clip against itself. So, this even lets you get rid of that check. The result is just a few characters different from the original code, but gives you a 100% performance increase!

Also, even beyond its performance impact, in many cases, doing double hit testing might have unwanted results. If youre changing the velocity or some other value when you detect a collision, you may wind up changing it twice, resulting in who knows what kind of effect. Of course, the specifics would vary according to the actions youre taking, but in general, you want one collision to result in one action.

Multiple-object springing

Lets make another quick application to see this in action. Again, youll go with the bubble-type reaction, but this time, all bubbles can bounce off of each other. This will require a ball-shaped movie clip in the library with the linkage ball . I even made mine look more like a bubble this time. Figure 9-7 illustrates the effect.

Figure 9-7: Multiple-object collision

Heres the code to put right on frame 1 ( ch09_07.fla ):

 var left:Number = 0; var right:Number = Stage.width; var top:Number = 0; var bottom:Number = Stage.height; var numBalls:Number = 30; var spring:Number = 0.05; var gravity:Number = 0.3; init(); function init() {       for (var i = 0; i<numBalls; i++)       {             var ball:MovieClip = attachMovie("ball", "ball" + i, i);             ball._x = Math.random() * Stage.width;             ball._y = Math.random() * Stage.height;             ball._width = ball._height = Math.random() * 40 + 20;             ball.vx = 0;             ball.vy = 0;       } } function onEnterFrame(Void):Void {       for(var i=0;i<numBalls-1;i++)       {             var ballA:MovieClip = this["ball" + i];             for(var j=i+1;j<numBalls;j++)             {                   var ballB:MovieClip = this["ball" + j];                   var dx:Number = ballB._x - ballA._x;                   var dy:Number = ballB._y - ballA._y;                   var dist:Number = Math.sqrt(dx*dx + dy*dy);                   var minDist:Number = ballA._width / 2 +                                        ballB._width / 2;                   if(dist < minDist)                   {                         var angle:Number = Math.atan2(dy, dx);                         var targetX:Number = ballA._x +                                            Math.cos(angle) * minDist;                         var targetY:Number = ballA._y +                                            Math.sin(angle) * minDist;                         var ax:Number = (targetX - ballB._x) *                                         spring;                         var ay:Number = (targetY - ballB._y) *                                         spring;                         ballA.vx -= ax;                         ballA.vy -= ay;                         ballB.vx += ax;                         ballB.vy += ay;                   }             }       }       for (var i = 0; i<numBalls; i++)       {                 var ball:MovieClip = this["ball" + i];             move(ball);       } } function move(ball:MovieClip) {       ball.vy += gravity;       ball._x += ball.vx;       ball._y += ball.vy;       if (ball._x + ball._width / 2 > right)       {             ball._x = right-ball._width / 2;             ball.vx *= -.9;       }       else if (ball._x - ball._width / 2 < left)       {             ball._x = left+ball._width / 2;             ball.vx *= -.9;       }       if (ball._y + ball._width / 2 > bottom)       {             ball._y = bottom-ball._width / 2;             ball.vy *= -.9;       }       else if (ball._y - ball._width / 2 < top)       {             ball._y = top+ball._width / 2;             ball.vy *= -.9;       } } 

Here, you are simply using the double-nested for loop to perform collision detection. In this case, the reaction might need some additional explanation. Heres the collision reaction code:

 if(dist < minDist) {       var angle:Number = Math.atan2(dy, dx);           var targetX:Number = ballA._x + Math.cos(angle) * minDist;           var targetY:Number = ballA._y + Math.sin(angle) * minDist;           var ax:Number = (targetX - ballB._x) * spring;           var ay:Number = (targetY - ballB._y) * spring;           ballA.vx -= ax;           ballA.vy -= ay;           ballB.vx += ax;           ballB.vy += ay; } 

Remember that this occurs once a collision is found between ballA and ballB . Essentially, it starts out the same as the earlier example with the unmoving center ball. For now, let ballA take the place of that center ball. You find the angle between the two, and get a target x and y. This is the point that you would need to place ballB so that the two balls would not be touching. Based on that, you get the x and y acceleration that would cause ballB to spring to that point. These are ax and ay .

But then you do something a little tricky. In this case, not only does ballB need to spring away from ballA , but ballA must spring away from ballB . The acceleration would be the same force and exactly the opposite direction. So rather than calculate it twice, you just add ax and ay to ballB s velocity, and subtract them from ballA s velocity! You get the same result, and you just saved a bunch of calculation right there. You might be thinking that this doubles the final acceleration, as its being applied twice. Thats true. To compensate, you make the spring variable quite a bit lower than usual.

While were on the subject of optimization tricks, Id like to mention another one here. The preceding code calculates the angle using Math.atan2 , and then uses Math.cos and Math.sin to find the target point:

 var angle:Number = Math.atan2(dy, dx); var targetX:Number = ballA._x + Math.cos(angle) * minDist; var targetY:Number = ballA._y + Math.sin(angle) * minDist; 

But remember that sine is opposite over hypotenuse, and cosine is adjacent over hypotenuse . And realize that the opposite side of the angle is dy , the adjacent side is dx , and the hypotenuse is dist . Thus, you could actually shorten these three lines to just these two:

 var targetX:Number = ballA._x + dx / dist * minDist; var targetY:Number = ballA._y + dy / dist * minDist; 

Voila! Youve just wiped out three calls to trig functions and replaced them with two simple divisions.

Before you move on, take some time to play with the springing bubbles example. You can adjust many variables. Try changing the spring, gravity, number, and size of the balls. You might want to try adding some friction or some mouse interaction.