Collision Detection

In games programming, collision detection is an important topic, as it is a key factor to most games. By collision detection, we mean checking whether two "objects" in your game are intersecting (overlapping each other). It would, in fact, be possible to write an entire book on collision detection, and if you search for this topic on the Internet, you will find hundreds of articles and a variety of techniques that can be used.

In the following sections, however, we are going to focus on two simple methods of performing collision detection in a game—bounding circle and bounding box collision detection—which give us good approximations of whether two objects have collided, regardless of the actual form of the object (i.e., the object (game character, etc.) does not necessarily need to be square or round; we just approximate to either a box or a circle for the collision testing). So let's start by looking at how we can do bounding circle collision detection.

Bounding Circle

The more common name for this method of collision detection is actually "bounding sphere," but since we are in 2D, circle is more appropriate, as a sphere is a 3D object. This form of collision detection is relatively simple. All we need to do is get the distance between the two center points of the circles that we are testing and then compare this to the sum of the two circles' radii (half the diameter).

Figure 12-9: Radius of a circle

If the distance between the center points is less than the sum of the two radii, the circles will be intersecting; otherwise, they will not be overlapping each other.

To work out the distance between the two circles, we can use the Pythagorean theorem (urg, I know we all hate math, but don't worry, this is simple). Let's first look at the following diagram of a right-angled triangle (one corner at a 90 degree angle) with its three sides denoted as A, B, and C.

Figure 12-10: A triangle

Using the Pythagorean theorem, we can work out the length of side C by squaring the lengths of sides A and B and taking the square root of the sum. This can be seen in the following formula:

So that's fine for a triangle, but it still doesn't give us the distance between two circles… or does it?

Take a look at the following diagram:

Figure 12-11: The magic of Pythagoras

As you can see, if you think about the distance between the two center points as being the C line of the triangle, we can construct a right-angled triangle from this to create our A and B lines. We can also work out the length of the lines A and B by finding the absolute (positive) values of:

Length A = x2 – x1

Length B = y2 – y1

...where (x1, y1) and (x2, y2) are the two center points of the circles. Then we can simply apply the length of A and B to the formula that we saw before to obtain the length of C, which is the distance between the circles.

Now that we have looked at the basic theory behind bounding circle collision detection, let's look at a working applet example where we have two circles, one of which we can move with the arrow keys and change the radius with the Page Up and Page Down keys. When the circles intersect, their colors will change to red. Here is the complete source code listing for this example.

Listing 12-4: Bounding circle example

Circle.java

import java.awt.*; import java.awt.geom.*;     public class Circle {     public Circle(int x, int y, int radius)     {         this.x = x;         this.y = y;         this.radius = radius;     }         public void render(Graphics g)     {         int diameter = radius*2;         g.fillOval(x-radius, y-radius, diameter, diameter);     }         public boolean intersects(Circle otherCircle)     {         int xDiff = (x-otherCircle.x);         int yDiff = (y-otherCircle.y);         int distance = xDiff*xDiff + yDiff*yDiff;           int totalRadius = (radius + otherCircle.radius);           return (distance < (totalRadius*totalRadius));     }       public int x, y, radius; }

BoundingCircleIntersection.java

import java.awt.*; import java.awt.image.*; import java.awt.event.*; import javax.swing.*;         public class BoundingCircleIntersection extends JApplet      implements Runnable, KeyListener {      public void init()     {         getContentPane().setLayout(null);         setSize(DISPLAY_WIDTH, DISPLAY_HEIGHT);         setIgnoreRepaint(true);         addKeyListener(this);             backBuffer = new BufferedImage(DISPLAY_WIDTH, DISPLAY_HEIGHT,             BufferedImage.TYPE_INT_RGB);         bbGraphics = (Graphics2D) backBuffer.getGraphics();           // create two circles...         circle1 = new Circle(DISPLAY_WIDTH/2, DISPLAY_HEIGHT/2, 30);         circle2 = new Circle(100, 100, 15);     }       public void start()     {         loop = new Thread(this);         loop.start();     }       public void stop()     {         loop = null;     }       public void run()     {         long startTime, waitTime, elapsedTime;         // 1000/25 Frames Per Second = 40 millisecond delay         int delayTime = 1000/25;           Thread thisThread = Thread.currentThread();         while(loop==thisThread)         {             startTime = System.currentTimeMillis();               // render to back buffer now             render(bbGraphics);               // render back buffer image to screen             Graphics g = getGraphics();             g.drawImage(backBuffer, 0, 0, null);             g.dispose();               //  handle frame rate             elapsedTime = System.currentTimeMillis() - startTime;             waitTime = Math.max(delayTime - elapsedTime, 5);               try             {                  Thread.sleep(waitTime);              }             catch(InterruptedException e) {}         }     }         public void render(Graphics g)     {         g.clearRect(0, 0, DISPLAY_WIDTH, DISPLAY_HEIGHT);           if(circle1.intersects(circle2)) // change the color to red...             g.setColor(Color.red);         else             g.setColor(Color.green);           circle1.render(g);         circle2.render(g);     }         public void keyTyped(KeyEvent e) { }     public void keyReleased(KeyEvent e) { }       public void keyPressed(KeyEvent e)     {         switch(e.getKeyCode())         {             case KeyEvent.VK_LEFT:                 circle2.x--;                 break;               case KeyEvent.VK_RIGHT:                 circle2.x++;                 break;               case KeyEvent.VK_UP:                 circle2.y--;                 break;               case KeyEvent.VK_DOWN:                 circle2.y++;                 break;               case KeyEvent.VK_PAGE_UP:                 if(circle2.radius < 50)                     circle2.radius++;                 break;               case KeyEvent.VK_PAGE_DOWN:                 if(circle2.radius > 2)                     circle2.radius--;                 break;         }     }       private Thread loop;     private BufferedImage backBuffer;     private Graphics2D bbGraphics;       private static final int DISPLAY_WIDTH = 400;     private static final int DISPLAY_HEIGHT = 400;       private Circle circle1, circle2;   }

Here is a screen shot of the applet in action:

Figure 12-12: Before and after intersection

Remember that you may need to click on the applet to gain the key focus. Also note that we have just implemented a KeyListener to get the input, rather than using our main loop synchronized EventProcessor to keep the example code to a minimum.

Let's first look at the Circle class, as this is where the actual intersection code is. First, however, declare the constructor to take in three parameters: the x, y positions and the radius. The constructor then simply sets the member variables to be equal to these values. Nothing complicated there.

Next, we have the render method, which will be called from the main loop to render this circle to the screen. All this method actually does is call the fillOval method of the Graphics object g. Notice how we first deduct the radius of the circle from the x, y coordinates before we pass them into the method; this is simply so that our coordinates represent the center and not the top left. The render method can be seen here:

public void render(Graphics g) {     int diameter = radius*2;     g.fillOval(x-radius, y-radius, diameter, diameter); }

Now comes the good bit—the intersects method. This method will take another Circle object as a parameter, so we can easily compare "this" circle to another one and return either true or false, depending on whether it intersects.

In the intersects method, we first need to get the lengths of the A and B lines that we spoke of before (the horizontal and vertical sides of the triangle). So we do this simply by taking away the circle's x and y positions from the other circle's x, y positions. This can be seen here:

int xDiff = (x-otherCircle.x); int yDiff = (y-otherCircle.y);

Note that we do not have to worry about these values being absolute (positive), as in the next step we will be squaring the values that will always make them positive.

int distance = xDiff*xDiff + yDiff*yDiff;

Here we are using a slightly modified version of the Pythagorean theorem, in that we have omitted the square root altogether, as we don't really require it (we'll see why in a minute). So now we have the distance between the two center points of the two circles that we are testing; we can proceed by getting the value of the sum of the two radii. This can be seen in the next line of code:

int totalRadius = (radius + otherCircle.radius);

Then we perform the actual test by returning the result of testing, whether the distance was less than the totalRadius squared. We square the total radius to simply balance the two sides of the if statement—if you remember before, we omitted the square root from where we found the distance, so the distance we have is actually the distance squared. To compensate for this, we simply square the total radius. Note that although finding the square root is very easy, as there is a static method called Math.sqrt(double), it is very expensive to execute. For this situation, we don't actually require it. The line of code that performs the test can be seen here:

return (distance < (totalRadius*totalRadius));

The Circle class and our intersection test are now covered. Let's have a quick look at the key points in the main class BoundingCircleIntersection. Note that we have used the ActiveRenderingApplet example from Chapter 9 as a base for this example.

First we declare two Circle objects, circle1 and circle2, as members to the main class. Then we initialize them in the constructor with the following two lines of code:

circle1 = new Circle(DISPLAY_WIDTH/2, DISPLAY_HEIGHT/2, 30); circle2 = new Circle(100, 100, 15);

Then, in the render method, we call the intersects method of circle1, passing the circle2 object in as a parameter. This will then return true or false (i.e., whether they intersect or not). If they do intersect, we set the color to red so both circles will be drawn in red; otherwise, we set it to green. This can be seen here:

if(circle1.intersects(circle2)) // change the color to red...     g.setColor(Color.red); else     g.setColor(Color.green);

After this, we can simply render the circles to the screen by calling their render methods, as can be seen in the following two lines of code:

circle1.render(g); circle2.render(g);

The final relevant part of the main class is the keyPressed method where we handle adjusting the position of the circle2 object using the arrow keys and also allow the user to adjust the radius of circle2, making it larger and smaller, by means of the Page Up and Page Down keys.

Bounding Box

As we mentioned before, the second collision detection technique that we are going to look at is bounding box collisions, where we test if the rectangular bounds of our object intersect with another object's rectangular bounds.

The best and easiest way to implement this is to actually test if the bounding boxes do not intersect, as we will see in the code to follow.

Let's first look at an example applet, which shows bounding box collisions in action. Then we will look at the underlying theory. Here is the complete code listing for the bounding box example:

Listing 12-5: Bounding box example

Box.java

import java.awt.*;     public class Box {     public Box(int x, int y, int w, int h)     {         this.x = x;         this.y = y;         this.w = w;         this.h = h;      }         public void render(Graphics g)     {         g.fillRect(x, y, w, h);     }         public boolean intersects(Box otherBox)     {         return !(otherBox.x >= x+w || otherBox.x+otherBox.w <= x ||             otherBox.y >= y+h || otherBox.y+otherBox.h <= y);     }       public int x, y, w, h;  }

BoundingBoxIntersection.java

import java.awt.*; import java.awt.image.*; import java.awt.event.*; import javax.swing.*;         public class BoundingBoxIntersection extends JApplet implements     Runnable, KeyListener {      public void init()     {         getContentPane().setLayout(null);         setSize(DISPLAY_WIDTH, DISPLAY_HEIGHT);         setIgnoreRepaint(true);         addKeyListener(this);             backBuffer = new BufferedImage(DISPLAY_WIDTH, DISPLAY_HEIGHT,             BufferedImage.TYPE_INT_RGB);         bbGraphics = (Graphics2D) backBuffer.getGraphics();           // create two boxes...         box1 = new Box(DISPLAY_WIDTH/2 - 50, DISPLAY_HEIGHT/2 - 25,             100, 50);         box2 = new Box(100, 100, 50, 50);     }       public void start()     {         loop = new Thread(this);         loop.start();     }       public void stop()     {         loop = null;     }       public void run()     {         long startTime, waitTime, elapsedTime;         // 1000/25 Frames Per Second = 40 millisecond delay         int delayTime = 1000/25;           Thread thisThread = Thread.currentThread();         while(loop==thisThread)         {             startTime = System.currentTimeMillis();               // render to back buffer now             render(bbGraphics);               // render back buffer image to screen             Graphics g = getGraphics();             g.drawImage(backBuffer, 0, 0, null);             g.dispose();               //  handle frame rate             elapsedTime = System.currentTimeMillis() - startTime;             waitTime = Math.max(delayTime - elapsedTime, 5);               try             {                  Thread.sleep(waitTime);              }             catch(InterruptedException e) {}         }     }             public void render(Graphics g)     {         g.clearRect(0, 0, DISPLAY_WIDTH, DISPLAY_HEIGHT);           if(box1.intersects(box2)) // change the color to red...             g.setColor(Color.red);         else             g.setColor(Color.green);           box1.render(g);         box2.render(g);     }         public void keyTyped(KeyEvent e) { }     public void keyReleased(KeyEvent e) { }         public void keyPressed(KeyEvent e)     {         switch(e.getKeyCode())         {             case KeyEvent.VK_LEFT:                 box2.x--;                 break;               case KeyEvent.VK_RIGHT:                 box2.x++;                 break;               case KeyEvent.VK_UP:                 box2.y--;                 break;               case KeyEvent.VK_DOWN:                 box2.y++;                 break;          }     }       private Thread loop;     private BufferedImage backBuffer;     private Graphics2D bbGraphics;       private static final int DISPLAY_WIDTH = 400;     private static final int DISPLAY_HEIGHT = 400;       private Box box1, box2;   }

The following figure is a screen shot of this example in action:

Figure 12-13: Before and after intersection

So let's look at the Box class. First, we have the constructor that takes in four parameters—the x, y locations, the width, and the height of the box. It then assigns the parameters to an instance member of the class, in the same way as we did with the Circle class in the previous example.

Next, we have defined a render method that draws the rectangle to the Graphics object g which is passed into the render method, using the fillRect method of the Graphics object. The render method can be seen here.

public void render(Graphics g) {     g.fillRect(x, y, w, h); }

Finally, we have our intersects method, which takes a Box object as a parameter so we can compare this Box object to the Box object that was passed in. The check for the intersection is accomplished in a single line of code that can be seen inside the intersects method here:

public boolean intersects(Box otherBox) {     return !(otherBox.x >= x+w || otherBox.x+otherBox.w <= x ||         otherBox.y >= y+h || otherBox.y+otherBox.h <= y); } 

Here we are actually checking if the box passed in does not intersect with this box, and then we swap the result (i.e., false to true and true to false) so that true will represent the boxes intersecting.

The first check here is if the box passed in, otherBox's x position, is to the right of this box's x position plus this box's width. We are checking if the leftmost side of the otherBox is to the right of the rightmost side of this box. If it is, it will not be intersecting and true is generated (which will then be returned as false due to the ! part of the code).

This process is then repeated for the other three sides of the boxes. If you are still not sure, study the line of code and try to figure out what is happening—it does make sense!

Let's now look at the key parts of the main class BoundingBoxIntersection that we use to display the boxes. We define two boxes in the class called box1 and box2. In the constructor we initialize them with the following two lines of code:

box1 = new Box(DISPLAY_WIDTH/2 - 50, DISPLAY_HEIGHT/2 - 25, 100, 50); box2 = new Box(100, 100, 50, 50);

In the render method, we do the same move as in the previous bounding circle example—we call the intersects method of box1, passing in box2 as an argument (as we want to test if box2 intersects box1). If it does intersect, we color both boxes red; otherwise, we set the color to green. The code for this can be seen here:

if(box1.intersects(box2)) // change the color to red...     g.setColor(Color.red); else     g.setColor(Color.green);

Once we have set the color appropriately, we can call the render methods of both the boxes, passing in the Graphics object g, which will be used to render them. This can be seen here:

box1.render(g); box2.render(g);

Finally we have the keyPressed method, as with the bounding circle example, to move box2 around the screen with the cursor keys so we can test the intersections.

Note that the java.awt.Rectangle class contains an intersects method built in, which takes another Rectangle if you choose to define your box regions as instances of this class.