Collision Detection

Most action games have many objects flying around on the screen. Whether it's a spear heading toward a mammoth, a car flying along a track, or in the case of Star Assault, bullets hurtling toward doomed enemies, you need to determine when any of the objects collide.

Basic Intersection

In Chapter 7, the RoadRun game had a basic form of collision detection. Every cycle you would check whether the bounding rectangle of your main actor (the wombat) was intersecting with any of the vehicles. If this was the case, then splattime for another wombat!

This type of collision detection works by checking whether any of the four corner points of one rectangle lie within another. You can see this illustrated in Figure 10.12.

The code for this is the same as our collision detection from the Actor class in Chapter 7, for example:

/**
* Simple collision detection checks if a given point is in the Actor's
* bounding rectangle.
* @param px The x position of the point to check against.
* @param py The y position of the point to check against.
* @return true if the point px, py is within this Actor's bounding rectangle
*/
public boolean isCollidingWith(int px, int py)
{
  if (px >= getX() && px <= (getX() + getActorWidth()) &&
       py >= getY() && py <= (getY() + getActorHeight()) )
       return true;
  return false;
} 
/**
* Determines if another Actor has collided with this one. We do this by
* checking if any of the four points in the passed in Actor's bounding
* rectangle are within the bounds of this Actor's (using the isCollidingWith
* point method above)
* @param another The other Actor we're checking against.
* @return true if the other Actor's bounding box collides with this one.
*/
public boolean isCollidingWith(Actor another)
{
  // check if any of our corners lie inside the other actor's
  // bounding rectangle
  if (isCollidingWith(another.getX(), another.getY()) ||
        isCollidingWith(another.getX() + another.getActorWidth(), another.getY()) ||
        isCollidingWith(another.getX(), another.getY() + another.getActorHeight()) ||
        isCollidingWith(another.getX() + another.getActorWidth(),
                                  another.getY()+ another.getActorHeight()))
        return true;
  else
        return false;
}

Nothing too complicated there, right? Although this works quite well, it's also extremely slow. Since you'll be doing a great deal of collision detection in your game, it's pretty important to do it as quickly as possible, so take a look at an alternative rectangle intersection test known as plane exclusion.

Intersection through Exclusion

To understand how this works, you need to think the opposite of how you normally would to determine whether two things collide. Instead of trying to determine whether the rectangle intersects another, ask if it doesn't. For example, suppose the left edge of one rectangle is beyond the right edge of another. In that case there's no possible way the rectangles can intersect, right? One of them is beyond the opposite side of the other, so it just can't happen. You can see what I mean in Figure 10.13. None of the A rectangles could ever be in a collision state with B if the left side is beyond the right edge of B.

You can use this test to exclude one plane. If you are able to exclude all four planes (top, bottom, left, and right), then it's not possible that the rectangles intersect. If you can't exclude them all, then logically there has to be an intersection somewhere. As you can see, Figure 10.14 covers all the possible places one rectangle can be in relation to another.

The following code does this by comparing two rectangles: a and b. The first rectangle is made up of the coordinates ax, ay, aw and ah, where ax and ay are the top-left point of a rectangle with a width of aw and a height of ah. The second rectangle is the same except you use the b set of variables. Here's the code:

/**
* Test for a collision between two rectangles using plane exclusion.
* @return True if the rectangle from the b coordinates intersects those
* of a.
*/
public static final boolean isIntersectingRect(int ax, int ay,
                                                   int aw, int ah,
                                                   int bx, int by,
                                                   int bw, int bh)
{
   if (by + bh < ay || // is the bottom of b above the top of a?
       by > ay + ah || // is the top of b below bottom of a?
       bx + bw < ax || // is the right of b to the left of a?
       bx > ax + aw)   // is the left of b to the right of a?
      return false;

   return true;
}

Nice and simple, isn't it? You'll find this method is also extremely fast because of the low number of comparisons. Since it's used in many places, you should place it in a general Tools class.

Reacting to a Collision

Once you've determined that two objects have collided, you need to do something about it. The easiest thing to do would be to ignore it, but then what was the point of detecting the collision in the first place? The next easiest thing would be to remove one or both of the objects from your world. This is common in the case of a rocket hitting a ship. You have the ship show some type of "ouch" graphic (such as an explosion or shield impact), and then you remove the bullet from the game world. The more complicated case is to have both objects remain in the game world but react in some way to the collision. To do this, you need to manage things better.

Imagine you've just arrived at the scene of an accident where two cars (Porsches) have collided. Your job is to rectify the situationfix the cars, deal with all the consequences of the crash, and then send everybody on their merry wayin about 10 milliseconds.

The first problem you have to deal with is that the cars are still in a collision state (their rectangles are intersecting), so you need to back them out of this position before you can do anything else. If you fail to do this, you would detect the collision state again the next time around (endlessly). The easiest method to reverse the state of a collision is to simply go back in time a little. You can do this by placing the objects where they were before they collided. For example you add the following code to the cycle method that moves your Actors:

// remember our position
int lastXFP = xFP;
int lastYFP = yFP;

// move
xFP = MathFP.add(xFP, xVelFP);
yFP = MathFP.add(yFP, yVelFP);

// test for collision
if (checkCollision(this))
{
   // if we hit something move back to where we were
   xFP = lastXFP;
   yFP = lastYFP;
}

Unfortunately, you still have a problem. When the game resumes, your Porsches, which are still heading in the same direction, will just smash into each other again! Backing the cars out of the collision state is an important step, but if you want both cars to continue you need to adjust their directions so they don't just slam into each other again. Say, here's an idea: Why don't you use that great bounce code you just figured out? When the Porsches impact, you could make them rebound off each other.

In the previous section, you saw that to bounce something off a surface, you need to invert either the horizontal or vertical velocity components based on the edge of the surface you hit. This was pretty easy in the previous example because you knew exactly which side of the screen the ship had hit. In this case, however, your collision code only determines whether or not they collidednot the edge upon which they collided. You need to determine this edge before you know which way to bounce.

You can determine the edge by comparing the position of the intersecting corner relative to the collision point. However, the code to do this is typically complex, quite slow, and not entirely accurate. The easier, more accurate method is to test for collisions separately on each component of your velocity as you move. Essentially, you move on the x-axis, and then test for a collision. If the collision occurs at that point, you know you've hit a vertical edge. Then you move on the y-axis and repeat the test, except this time a collision means you hit a horizontal edge. You can see this illustrated in Figure 10.15.

If this all sounds familiar, that's because it is. The advanced movement example earlier in the chapter used this method to detect collisions on the edge of the screen and bounce off (without getting stuck). Here it is again so you don't have to flick back:

// Save the original position (so if it collided we can back out of
// this movement).
int origXFP = shipXFP;
int origYFP = shipYFP;

// Move the ship.
shipXFP = MathFP.add(shipXFP, xVelFP);
shipYFP = MathFP.add(shipYFP, yVelFP);

// Check our position and if we're hitting an edge reverse a velocity
// component.
if (MathFP.toInt(shipXFP) < 1 ||
    MathFP.toInt(shipXFP)+SHIP_FRAME_WIDTH >= myCanvas.getWidth())
{
   // back out of the collision position
   shipXFP = origXFP;
   xVelFP = MathFP.mul(xVelFP, MathFP.toFP("-1.0"));
}
if (MathFP.toInt(shipYFP) < 1 ||
    MathFP.toInt(shipYFP)+SHIP_FRAME_HEIGHT >= myCanvas.getHeight())
{
   // back out of the collision position
   shipYFP = origYFP;
   yVelFP = MathFP.mul(yVelFP, MathFP.toFP("-1.0"));
}

Advanced Collision Detection

The methods you've reviewed so far are very simple collision detection techniques. They certainly won't cover very complex collision cases. For example, if an object is moving fast enough, it's possible that a single step (cycle) could take the object completely beyond an object with which it should have collided. You can see this illustrated in Figure 10.16.

For many J2ME games you won't have to worry (or care) about this case. If you do, however, you will need to detect collisions based on the path of the object, not just where it ends up. One technique for doing this is to do an intersection test for the line from the center of the object's starting position to the center of its end position, against all four sides of the other object. Figure 10.17 illustrates this.

Line intersection tests are complex processes, so doing this test four times for every object comparison is slow going. Doing this type of collision test for all the objects flying around in the game is rarely worth it.

Another method for detecting collisions between two objects is to test whether their bounding circles overlap. You can do this quickly by comparing the sum of the radii of both objects squared against the sum of the distance between the objects squared. If the radius result is greater than the distance, then the circles collide.

To figure out the radius you simply use half the value of the height or width, whichever is greater. Here's the original collision method modified to use a bounding circle test. If you're going to use this, I recommend pre-calculating and storing the radius values for speed.

/**
 * Returns true if b intersects a (uses bounding circle comparison)
 */
public static final boolean isIntersectingRect(int ax, int ay, int aw, int ah,
                                                   int bx, int by, int bw, int bh)
{ 
   int radius = (Math.max(aw, ah)/2) + 1;
   int anotherRadius = (Math.max(bw, bh)/2)+1;

   int radiusSquared = radius * radius;
   int anotherRadiusSquared = anotherRadius * anotherRadius;

   // if the distance squared < the square of the two radii then
   // the circles overlap
   int distanceX = ax - bx;
   int distanceY = ay - by;

   if (((distanceX * distanceX) + (distanceY * distanceY)) <
        (radiusSquared + anotherRadiusSquared))
      return true;
   else
      return false;
}

A Collision Example

In the following example, you will bring together all the components of collision detection. You'll create five ships and have them fly around in random directions. When they collide, they'll bounce off each other before they continue. To accomplish this, I've separated the ship and game screen components into their own classes. To bring all this together I've also created a simple MIDlet class called CollisionTest and expanded out the Tools class with a few extras (like a random number generator). Also because it's getting a little sophisticated, I've split out all the code relating to the little ships into a new Ship class.

First up is the MIDlet class to handle everything, CollisionTest:

import javax.microedition.midlet.*;
import javax.microedition.lcdui.*;

/**
 * An example that creates some ships and flies them around bouncing off each
 * other.
 * @author Martin J. Wells
 */
public class CollisionTest extends MIDlet implements CommandListener, Runnable
{
   private GameScreen gameScreen;
   private Command quit;
   private boolean running; 
/**
 * Constructor for the MIDlet creates the GameScreen object, adds a quit
 * command and then creates a thread to do our cycling and painting.
 */
public CollisionTest()
{
   // Construct a canvas
   gameScreen = new GameScreen();

   // And a way to quit
   quit = new Command("Quit", Command.EXIT, 2);
   gameScreen.addCommand(quit);
   gameScreen.setCommandListener(this);

   // Create the game thread.
   running = true;
   Thread t = new Thread(this);
   t.start();
}

/**
 * Runnable interface run method that cycles the ship and requests a repaint
 * of the Canvas.
 */
public void run()
{
   while (running)
   {
      gameScreen.repaint();
      gameScreen.cycle();

      try
      {
         // Simple timing - sleep for 100 milliseconds.
         Thread.sleep(100);
      }
      catch (InterruptedException e)
      {
      }

   }
} 
/**
 * Handles Application Manager notification the MIDlet is starting (or
 * resuming from a pause). In this case we set the canvas as the current
 * display screen.
 * @throws MIDletStateChangeException
 */
protected void startApp() throws MIDletStateChangeException
{
   Display.getDisplay(this).setCurrent(gameScreen);
}

/**
 * Handles Application Manager notification the MIDlet is about to be paused.
 * We don't bother doing anything for this case.
 */
protected void pauseApp()
{
}

/**
 * Handles Application Manager notification the MIDlet is about to be
 * destroyed. We don't bother doing anything for this case.
 */
protected void destroyApp(boolean unconditional)
         throws MIDletStateChangeException
{
}

/**
 * The CommandListener interface method called when the user executes
 * a Command, in this case it can only be the quit command we created in the
 * constructor and added to the Canvas.
 * @param command The command that was executed.
 * @param displayable The displayable that command was embedded within.
 */
public void commandAction(Command command, Displayable displayable)
{
   try
   {
      if (command == quit)
      {
         running = false; 
            destroyApp(true);
            notifyDestroyed();
         }
      }

      catch (MIDletStateChangeException me)
      {
         System.out.println(me + " caught.");
      }
   }

}

Next is a modified version of the GameScreen class that creates five Ship objects (you'll see the Ship class in just a moment) and places them in a vertical row down the screen. It then gives each Ship a random direction and a velocity so they'll all fly off in different directions. When collision is detected, the Ships will bounce off each other before continuing.

import javax.microedition.lcdui.Canvas;
import javax.microedition.lcdui.Graphics;

/**
 * A GameScreen (Canvas with game logic) that creates five Ships then flies them
 * off in random directions. If a collision occurs the Ship will bounce off
 * before continuing.
 * @author Martin J. Wells
 */
public class GameScreen extends Canvas
{
   private Ship[] ships;

   /**
    * Constructor for the GameScreen that creates the five Ships.
    */
   public GameScreen()
   {

This is where the five Ships are constructed and positioned in a vertical down the center of the screen. In this example we set them all off in different directions so they collide (the random directions are set in the Ship constructor).

      // Create 5 ships positioning them in a vertical line down the center of
      // the screen.
      ships = new Ship[5]; 
      for (int i = 0; i < ships.length; i++)
         ships[i] = new Ship(getWidth()/2, 20*i, this);
   }

In the render method the main addition is to loop through the array of Ships and call their render methods to draw them on the screen. It's the same thing with the cycle method, which again just loops through calling the cycle method for all the Ships.

   /**
    * Canvas paint implementation which clears the screen and then draws
    * the ships at their current positions.
    * @param graphics The graphics context on which to draw.
    */
   protected void paint(Graphics graphics)
   {
      graphics.setColor(0);
      graphics.fillRect(0, 0, getWidth(), getHeight());
      // Cycles through the array of Ships and draws them all on the canvas.
      for (int i = 0; i < ships.length; i++)
         ships[i].render(graphics);
   }

   /**
    * Calls the cycle method on all the Ships in the array.
    */
   public void cycle()
   {
      for (int i = 0; i < ships.length; i++)
      {
         Ship s = ships[i];
         s.cycle();
      }
   }

For the collision test we need to deal with detecting if a collision occurs between one Ship and the other four.

   /**
    * Called by the Ship class to test whether a collision has occured between
    * one ship (the s paramater) and any other Ship in the array.
    * @param s The Ship to test against.
    * @return True if the Ship s is colliding with another.
    */ 
   public boolean checkCollision(Ship s)
   {
      // did this ship hit another?
      for (int j = 0; j < ships.length; j++)
      {
         Ship another = ships[j];
         // First we test that Ship s is not the element of the array being
         // tested.
         if (another != s &&
             Tools.isIntersectingRect(s.getX(), s.getY(), 16, 16,
                                        another.getX(), another.getY(), 16, 16))
            return true;
      }
      return false;
   }

}

Since our little spaceships are getting a bit complicated I've placed all the logic in a new class called Ship. This class handles the movement and drawing of the Ships.

import net.jscience.math.kvm.MathFP;
import javax.microedition.lcdui.*;
import java.io.IOException;

/**
 * Class to handle the drawing and movement of a little spaceship. Image is
 * loaded in a Sprite from the ship.png file.
 * @author Martin J. Wells
 */
public class Ship
{
   private static int SHIP_FRAME_WIDTH = 16; // size of the ship in pixels
   private static int SHIP_FRAME_HEIGHT = 16;

   // Some pre-calculated values to speed things up.
   public static final int FP_PI2 = MathFP.mul(MathFP.PI, MathFP.toFP(2));
   public static final int FP_DEGREES_PER_RAD = MathFP.div(MathFP.toFP(360),
                                                                FP_PI2);
   public static final int FP_22P5 = MathFP.toFP("22.5");

   private static ImageSet shipImageSet;  // the one and only imageset 
   private int xFP;                        // x position (as a MathFP)
   private int yFP;                        // y position (as a MathFP)
   private int direction;                  // current direction in degrees

   private int xVelFP;                     // x velocity (as a MathFP)
   private int yVelFP;                     // y velocity (as a MathFP)

   private int maxVelFP = MathFP.toFP("2");
   private int thrustFP = MathFP.toFP("0.2");

   private Sprite shipSprite;
   private int worldWidth;                 // size of the world (so we can wrap)
   private int worldHeight;
   private GameScreen gameScreen;

   /**
    * Constructs a ship starting at a given location.
    * @param x The starting x position.
    * @param y The starting y position.
    * @param gs The GameScreen this Ship belongs to (used to call back for
    * collision detection)
    */
   public Ship(int x, int y, GameScreen gs)
   {
      gameScreen = gs;

      // Load up the images for the Ship. Note that shipImageSet is a static
      // so this code will only be run once (after that shipImageSet will not
      // be null).
      if (shipImageSet == null)
      {
         // Set the width and height of the world (we only do this once as
         // well).
         worldWidth = gs.getWidth();
         worldHeight = gs.getHeight();

         try
         {
            Image[] frames = ImageSet.extractFrames(Image.createImage("/ship.png"),
                                                        0, 0, 4, 4,
                                                        SHIP_FRAME_WIDTH,
                                                        SHIP_FRAME_HEIGHT); 
            shipImageSet = new ImageSet(1);
            shipImageSet.addState(frames, 0);
         }
         catch (IOException ioe)
         {
            System.out.println("unable to load image");
         }
      }

      // Create a Sprite for this instance of the Ship.
      shipSprite = new Sprite(shipImageSet, 0, 0);

      // Set the starting position.
      xFP = MathFP.toFP(x);
      yFP = MathFP.toFP(y);

      // Set a random direction.
      direction = Tools.getRand(0, 359) / 23 * 23;
   }

   /**
    * Calculates the correct frame based on the Ship's direction and then draws
    * that frame in on the screen at the Ship's current position.
    * @param graphics The graphics context upon which to draw.
    */
   public void render(Graphics graphics)
   {
      // Calculate the frame by dividing the direction by 22.5 degrees (360
      // degrees divided by 16 frames equals 22.5).
      int frame = MathFP.toInt(MathFP.div(MathFP.toFP(direction), FP_22P5));
      shipSprite.setFrame(frame);
      shipSprite.draw(graphics, MathFP.toInt(xFP), MathFP.toInt(yFP));
   }

   /**
    * Movement for the Ship. Collision detection is done by asking the
    * GameScreen class through the checkCollision method. This is done because
    * the GameScreen is the one with the array of Ships.
    */
   public void cycle()
   { 
      // move the ship according to its current direction (in radians)
      int dirRadians = MathFP.div(MathFP.toFP(direction), FP_DEGREES_PER_RAD);

      int xAccFP = MathFP.mul(thrustFP, MathFP.cos(dirRadians));
      int yAccFP = MathFP.mul(thrustFP, MathFP.sin(dirRadians));

      xVelFP = MathFP.add(xVelFP, xAccFP);
      yVelFP = MathFP.add(yVelFP, yAccFP);

      // Cap the velocity to a controllable level
      if (xVelFP > maxVelFP)
         xVelFP = maxVelFP;
      else if (xVelFP < -maxVelFP) xVelFP = -maxVelFP;
      if (yVelFP > maxVelFP)
         yVelFP = maxVelFP;
      else if (yVelFP < -maxVelFP) yVelFP = -maxVelFP;

      int lastXFP = xFP;
      xFP = MathFP.add(xFP, xVelFP);

      // Test for collisions, after x movement.
      if (gameScreen.checkCollision(this))
      {
         xVelFP = MathFP.mul(xVelFP, MathFP.toFP("-1"));
         xFP = MathFP.add(lastXFP, xVelFP);
      }

      int lastYFP = yFP;
      yFP = MathFP.add(yFP, yVelFP);

      // Test for collisions, after y movement.
      if (gameScreen.checkCollision(this))
      {
         yVelFP = MathFP.mul(yVelFP, MathFP.toFP("-1"));
         yFP = MathFP.add(lastYFP, yVelFP);
      }

      // Check the position and wrap around if we have to.
      if (MathFP.toInt(xFP) < 0) xFP = MathFP.toFP(worldWidth - 1);
      if (MathFP.toInt(xFP) > worldWidth) xFP = MathFP.toFP(0);
      if (MathFP.toInt(yFP) < 0) yFP = MathFP.toFP(worldHeight - 1);
      if (MathFP.toInt(yFP) > worldHeight) yFP = MathFP.toFP(0); 
   }

   /**
    * @return The x position of the Ship.
    */
   public int getX()
   {
      return MathFP.toInt(xFP);
   }

   /**
    * @return The y position of the Ship.
    */
   public int getY()
   {
      return MathFP.toInt(yFP);
   }

}

As I mentioned earlier you will also need to add a random number generator to the Tools class to set the random directions on the Ships.

public final class Tools
{
   private static final Random randomizer = new Random();

   /**
    * A method to obtain a random number between a miniumum and maximum
    * range.
    * @param min The minimum number of the range
    * @param max The maximum number of the range
    * @return
    */
   public static final int getRand(int min, int max)
   {
      int r = Math.abs(randomizer.nextInt());
      return (r % ((max - min + 1))) + min;
   }

   ...