Hack 40 Detect Multiple Collisions

Collision detection is used in games and simulations. Optimize Flash collision detection to allow advanced motion graphics.

Flash allows you to perform collision detections between two movie clips with the MovieClip.hitTest( ) method. The method will return true if a collision is detected and false if no collision is detected.

The definition of what constitutes a collision can also be varied. You can detect a collision between a point and a movie clip edge or between the bounding boxes of the two movie clips (i.e., the rectangles that you see around movie clips when you select them in the authoring environment). We look at both situations next.

Assuming you have two movie clips, clipA and clipB, on the Stage, the following code makes clipA draggable and displays the value true for every frame in which the bounding boxes of clipA and clipB overlap. Otherwise, it displays false.

clipA.onEnterFrame = function( ) {

  hit = clipA.hitTest(clipB);

  trace(hit);

};

clipA.startDrag(true);

The trouble with this type of collision detection is that it indicates a collision when the bounding boxes overlap, even if the pixels within the movie clips do not overlap. In Figure 5-13, the two circular movie clips do not overlap but the hitTest( ) method in the preceding listing returns true because the bounding boxes overlap.

Figure 5-13. The hitTest( ) method returns true if the bounding boxes overlap

One solution is to perform manual collision detection. For circles, this happens to be easy. If the centers of the circles are closer than the sum of their radii, the circles overlap. Using the Pythagorean Theorem to calculate the distance between two points, the code to check for contact between two circles is:

function circleHitTest (circle1, circle2) {

  var a = circle1._x - circle2._x;

  var b = circle1._y - circle2._y;

  dist = Math.sqrt( Math.pow(a, 2) + Math.pow(b, 2));

  return dist < Math.abs(circle1._width/2 - circle2._width/2);

}

Another solution is to use near-rectangular graphics that fill or nearly fill the movie clip's bounding box. This idea is not as silly as it might seem, and this approach was routinely used in early video games (which is why the space invaders tended to be fairly rectangular).

You can also perform collision detection between a point and a movie clip. The following code checks for collisions between the mouse position and a movie clip named clipA:

this.onEnterFrame = function( ) {

  hit = clipA.hitTest(_xmouse, _ymouse, true);

  trace(hit);

};

That code returns true if the tip of the mouse pointer is over any occupied pixels within clipA (including pixels with zero alpha or even if the clip is hidden by setting clipA._visible = false).

ActionScript doesn't provide a native way of checking for collisions between individual pixels in two movie clips. You can test for collisions only between two clips' bounding boxes or between a point and the pixels within a clip.

Although in theory you can detect collisions between any two clips, in practice, the number of clips you can use is limited by Flash's ability to perform the calculations fast enough. The processor can't exhaustively check the thousands of possible combinations when numerous clips interact. Because there is no built-in event that notifies you of collisions, you have to test for collisions explicitly whenever you want to see if they occurred (known as polling). This can lead to very slow operation for any sizable number of clips.

However, there is a saving grace (it wouldn't be a hack without one, now would it?). Most developers don't realize that MovieClip.hitTest( ) recognizes embedded movie clips when performing the collision test.

As long as you arrange your timelines in an appropriate "collision hierarchy" of embedded movie clips, you can test for a collision between a movie clip and a hundred others with a single hit test. Or you can create an optimized collision engine that runs only when certain collisions have already occurred (rather than having to poll for detailed collisions every frame). Let's see how.

A Collision Hierarchy

In most cases, you want to detect a collision between one thing and another group of objects. These other objects might be gas molecules in a physics simulation, a swarm of marauding aliens, or the walls in a maze. Let's assume you are checking collisions against a single graphic representing the player (the character controlled by the user).

The slow way of checking for collisions is to treat each movie clip as a separate entity. So if you have 20 aliens onscreen, you need to check for collisions between the player and each of the aliens.

The better way to do it is to place all the aliens inside a single movie clip, such as one named alienSwarm, so that you have a hierarchy, as shown in Figure 5-14.

Figure 5-14. A hierarchy with aliens inside an alienSwarm clip

You can then detect collisions between the aliens and the player's ship by checking for collisions between alienSwarm and the ship clip, regardless of the number of aliens in the swarm. Better still, the detection process doesn't slow down significantly even if there are numerous aliens in the swarm!

To try this technique yourself, create a movie clip named ship, making sure its registration point is near the tip of the graphic, as shown in Figure 5-15. This represents the ubiquitous player's spaceship sprite.

Figure 5-15. The player's ship with registration point near the tip

Create a second movie clip symbol named asteroid, as shown in Figure 5-16, and give it a linkage identifier of asteroid. The position of this movie clip's registration point is not important.

Figure 5-16. The asteroid movie clip symbol

Place the ship movie clip near the bottom of the Stage as per the typical Space Invaders player ship position.

Add the following code to the first (and only) frame in the timeline (like all timeline code, it is best placed in a layer named actions set aside for this purpose):

function shipMove( ) {

  // Detect keypresses and move ship accordingly

  if (Key.isDown(left)) {

    ship._x -= playerSpeed;

  }

  if (Key.isDown(right)) {

    ship._x += playerSpeed;

  }

  // Check for collisions

  if (asteroidBelt.hitTest(ship._x, ship._y, true)) {

    trace("collision");

  }

  updateAfterEvent( );

}



function asteroidMove( ) {

  // Move this asteroid

  this._y += this.asteroidSpeed;

  if (this._y > 400) {

    this._x = Math.random( ) * 550;

    this._y = 0;

  }

}



function createAsteroids( ) {

  // Create a movie clip named asteroidBelt. Inside it, 

  // create 20 asteroids: asteroid0 to asteroid19.

  this.createEmptyMovieClip("asteroidBelt", 0);

  initAsteroid = new Object( );

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

    initAsteroid._x = Math.random( ) * 550;

    initAsteroid._y = Math.random( ) * 400;

    initAsteroid.asteroidSpeed = Math.round((Math.random( ) * 3) + 2);

    initAsteroid.onEnterFrame = asteroidMove;

    asteroidBelt.attachMovie("asteroid", "asteroid" + i, i, initAsteroid);

  }

}

// Setup

left = Key.LEFT;

right = Key.RIGHT;

playerSpeed = 10;

asteroidSpeed = 3;

shipInterval = setInterval(shipMove, 10);

createAsteroids( );

The createAsteroids( ) function creates a movie clip named asteroidBelt and creates 20 asteroids (asteroid0 through asteroid19) within it. The asteroids travel down the screen over time.

The ship movie clip is controlled via the left and right arrow keys, and the goal is to dodge the asteroids.

The ship animation is given a much higher part of the Flash Player's performance budget [Hack #71] by controlling it via a setInterval( ) event, whereas the asteroids are given onEnterFrame( ) event handlers, which perform animation at a slower rate (the frame rate).

If the player collides with one or more asteroids, the Output panel displays the word "collision" for every frame in which the collision occurs. The key to maintaining performance is the single collision test used for the entire asteroid belt:

if (asteroidBelt.hitTest(ship._x, ship._y, true)) {

  trace("collision");

}

Collisions in the Reverse Hierarchy

Using a collision hierarchy offers a big performance enhancement, but it works in only one direction. We can detect collisions between the asteroid belt and the player, but we can't (for example) detect a collision between the ship's laser and individual asteroids, which we would need to do if we're going to make them explode when hit (as all well-behaved asteroids should).

Even in this reverse situation, a collision hierarchy still helps immensely by telling you when a collision has occurred. Using this information, you can optimize collision detection code because you know to run your laser-to-individual-asteroid collision detection routine only after a collision with the asteroid belt has already occurred.

Here is one possible scenario.

Test for a collision between the asteroid belt and the player's laser. If you detect a collision, you know the laser has hit an asteroid, you just don't know which one.

Look at either the _x or _y property of individual asteroids against the laser's position, and eliminate all asteroids that are too far away for a collision. This eliminates almost all the asteroids from the collision test.

Of those that are close enough, check using individual hit tests (i.e., using MovieClip.hitTest( )).

Your secondary collision detection routine (testing against individual asteroids) runs much less often than the primary hitTest( ) (testing against the entire asteroid belt). When it does run, you know at least one collision has occurred, and you can optimize the code with this fact in mind.

Final Thoughts

Collision detection need not be a barrier to high-performance Flash simulations or motion graphics. By building your graphics in a hierarchy, you can substantially reduce the time needed to detect collisions.

In a typical shooting game, you have to make two frequent collision detections and one infrequent collision detection. The two frequent hit tests are between the alien swarm and the player, and between the player's laser and the alien swarm. If the second hit test gives a positive result, you have to make a less frequent (but more detailed) collision search between the laser and each alien instance within the swarm.