Hour 21. Collision Detection

Collision detection makes a game look and feel realistic by allowing objects to hit each other and react to those collision events. This hour explores the two most common and efficient techniques for detecting collisions between game objects, with a theoretical discussion of the algorithms and an applied example.

Collision Detection Techniques

The two collision techniques we will study get their names from the techniques they employ: bounding rectangles and bounding circles. We’ll study each in detail and then create an example to test collisions.

Bounding Rectangles (Box Collision)

The most common technique used in video games to test for collisions is the bounding rectangle technique, also known as box collision. The name comes from the use of a rectangle that surrounds the entire shape of the object and is often derived from the frame size (with animation) or actual dimensions of the image loaded from a bitmap file (in cases where no animation is involved).

To determine whether two game objects have collided, we can create a bounding box around each one and then compare the boxes to see if they overlap. The box may be a Rect stored in the game object, or it may be generated on-the-fly. The latter approach is the norm because it recalculates the boundary as the object is moving, taking into account the X,Y position and width/height properties. Figure 21.1 shows an illustration of five objects with their bounding boxes.

Figure 21.1. Five game objects with bounding boxes.

This illustration shows some of the flaws in the bounding box collision detection technique. As you can see, none of the objects are actually colliding, but their bounding boxes are! This is a legitimate problem. How do we solve it?

The short answer is: We don’t. The bounding boxes in this illustration have been slightly exaggerated, but they are often large, as shown, to take into account the differences in animation frames (where some frames take up more room than others). Because animation frames must all be the same size, the bounding box is defined by the largest frame. If an object is actively rotating, the bounding box around the object while it is in a diagonal orientation will be quite large. This poses a problem for us.

One solution is to adjust the bounding rectangle so that it represents the bulk of the shape rather than just the outer perimeter of the image. A good average reduction that produces consistent results is 25%, with up to 50% if the shape is dense (with few or no convex parts).

Figure 21.2 is another illustration, this time showing actual physical contact between the two game objects. If you note how far in the second object intersects the first, you may notice that it’s about halfway into the spaceship bounding box. This trend is fairly common, which is why the 25 to 50% figure comes up quite often.

Figure 21.2. A collision is more apparent between larger game objects.

Bounding Circles (Radial Collision)

The second common technique for collision detection uses bounding circles around two objects. This technique is quite a bit different from bounding rectangles. For a comparison, see Figure 21.3. The bounding circle seems huge in comparison. There is a simplicity to the algorithm, based on distance, and this technique works extremely well in some situations.

Figure 21.3. Comparison of two bounding shapes: rectangle and circle.

Very simply, take the center point of each shape and use a radius value to simulate a circle around the shape. To test for collision, compare the distance between two objects in relation to the radius of each: If the distance is less than the sum of the radii, a collision has occurred. See Figure 21.4, which shows four asteroids again, close to a spaceship. The most surprising example is the asteroid in the lower-right corner: Although it is fully within the bounding circle of the space ship, this clearly shows that no physical collision has occurred! Figure 21.5 demonstrates a problem when objects actually collide.

Figure 21.4. Bounding circles produce similar results in collision testing.

Figure 21.5. Physical collision between the two shapes shows the problem with this technique.

There really is no rule that you must use one technique or the other when dealing with certain game genres; it’s normal to use a mix of the two. In some cases, where a game object has an odd shape (such as the spaceship here), it is helpful to use two bounding shapes to accommodate the object. For instance, a pair of smaller boxes or circles around the fore and aft parts of the ship would work well and produce very good results. For a simpler game with one collision test per object, a single bounding rectangle will suffice.

Demonstrating Collisions

To demonstrate collision detection, we will build a project called Collision Demo. It is somewhat similar to the project in the previous hour but is considerably enhanced to effectively illustrate this subject with flair. First, we’ll make some required enhancements to the engine, including work on the Engine class, the Sprite class, and then we’ll write the code for the program.

Engine Enhancements

The Engine class must be modified to handle collision detection internally to properly demonstrate engine-level functionality. We could implement a collision method in the main game and be done with it, but this approach is far more useful long term. These enhancements will presume to use new features not yet added to the Sprite class; rest assured, we will modify Sprite soon enough.

Remember the abstract methods? We have taken them for granted for several hours now, but now it’s time to add a new one! The new collision() method notifies the game when a collision occurs. Only a single Sprite parameter is needed, thanks to new properties in the Sprite class that support collision processing (noted in bold). All these changes will be made to the Engine.java file.

/**
 * Abstract methods that must be implemented in the subclass!
 */
public abstract void init();
public abstract void load();
public abstract void draw();
public abstract void update();
public abstract void collision(Sprite sprite);

Further along in the Engine.java source code file, we need to make additional changes so that the engine automatically tests for collisions when a Sprite object in the entity manager is flagged for it. So, look for the run() method. The required changes are also noted next in the run() method. Note also that import android.graphics.Paint.* is required (and Eclipse will notify you if it isn’t already in your engine source listing).

@Override
public void run() {
    Log.d("Engine","Engine.run start");

    ListIterator<Sprite> iter=null, iterA=null, iterB=null;

    Timer frameTimer = new Timer();
    int frameCount=0;
    int frameRate=0;
    long startTime=0;
    long timeDiff=0;

    while (p_running) {
        // Process frame only if not paused
        if (p_paused) continue;

        // Calculate frame rate
        frameCount++;
        startTime = frameTimer.getElapsed();
        if (frameTimer.stopwatch(1000)) {
            frameRate = frameCount;
            frameCount = 0;

            //reset touch input count
            p_numPoints = 0;
        }

        // Call abstract update method in sub-class
        update();

        /**
         * Test for collisions in the sprite group
         * Note that this takes place outside of rendering
         */
        iterA = p_group.listIterator();
        while (iterA.hasNext()) {
            Sprite sprA = (Sprite)iterA.next();
            if (!sprA.getCollidable()) continue;

            /*
             * Improvement to prevent double collision testing
             */
            if (sprA.getCollided())
                continue; //skip to next iterator

            //iterate the list again
            //ListIterator<Sprite>
            iterB = p_group.listIterator();
            while (iterB.hasNext()) {
                Sprite sprB = (Sprite)iterB.next();
                if (!sprB.getCollidable()) continue;

                /*
                 * Improvement to prevent double collision testing
                 */
                if (sprB.getCollided())
                    continue; //skip to next iterator

                //do not collide with itself
                if (sprA == sprB) continue;

                /*
                 * Ignore sprites with the same ID? This is an important
                 * consideration. Decide if your game requires it or not.
                 */
                if (sprA.getIdentifier() == sprB.getIdentifier())
                    continue;

                if (collisionCheck(sprA, sprB)) {
                    sprA.setCollided(true);
                    sprA.setOffender(sprB);
                    sprB.setCollided(true);
                    sprB.setOffender(sprA);
                    break; //exit while
                }
            }
        }//while

        // Rendering section, lock the canvas
        // Only proceed if the SurfaceView is valid
            if (beginDrawing()) {

                /**
                 * Note: In a future hour this will be moved to
                 * the draw() method call so the user can define
                 * the color of the background.
                 */
                p_canvas.drawColor(Color.BLACK);

             /**
             * Draw the group entities with transforms
             */
            iter = p_group.listIterator();
            while (iter.hasNext()) {
                Sprite spr = (Sprite)iter.next();
                spr.animate();
                spr.draw();

                /**
                 * For collision testing purposes, draw boundary
                 * around each sprite (temporary).
                 */
                if (spr.getCollidable()) {
                    if (spr.getCollided()) {
                        p_paintDraw.setStyle(Style.STROKE);
                        p_paintDraw.setColor(Color.RED);
                        p_canvas.drawRect(spr.getBoundsScaled(),
                        p_paintDraw);
                    }
                }
            }

            // Call abstract draw method in sub-class
            draw();

           /**
            * Print engine debug information (temporary).
            */
            int x = p_canvas.getWidth()-150;
            p_canvas.drawText("ENGINE", x, 20, p_paintFont);
            p_canvas.drawText(toString(frameRate) + " FPS", x, 40,
                p_paintFont);
            p_canvas.drawText("Pauses: " + toString(p_pauseCount),
                x, 60, p_paintFont);

            /**
             *  Complete the rendering process by unlocking the canvas
             */
            endDrawing();
        }

        /**
         * Notify game of any sprites that have collided
         */
        iter = p_group.listIterator();
        while (iter.hasNext()) {
            Sprite spr = (Sprite)iter.next();
            collision(spr); //notify game
            spr.setCollided(false);
        }

        // Calculate frame update time and sleep if necessary
        timeDiff = frameTimer.getElapsed() - startTime;
        long updatePeriod = p_sleepTime - timeDiff;
        if (updatePeriod > 0) {
            try {
                Thread.sleep( updatePeriod );
            }
            catch(InterruptedException e) {}
        }

    }//while
    Log.d("Engine","Engine.run end");
    System.exit(RESULT_OK);
}

The enhancements to run() called on one support method: the collisionCheck() method, which has not been written yet. Add this new collision method to the Engine.java file as well.

/**
 * Collision detection
 */
public boolean collisionCheck(Sprite A, Sprite B) {
    boolean test = Rect.intersects(A.getBoundsScaled(),
        B.getBoundsScaled());
    return test;
}

Sprite Enhancements

Quite a few modifications must be made to the Sprite class to support collision handling! First, add the following new private properties to the class:

private boolean p_collidable, p_collided;
private Sprite p_offender;
private String p_name;
private int p_identifier;

Next, initialize these new properties in the constructor method:

p_collidable = p_collided = false;
p_offender = null;
p_name = "";
p_identifier = 0;

No changes are made to existing methods, but we do need all these new helper and get/set methods to make collision handling possible!

public boolean getCollidable() {
    return p_collidable;
}

public void setCollidable(boolean value) {
    p_collidable = value;
}

public boolean getCollided() {
    return p_collided;
}

public void setCollided(boolean value) {
    p_collided = value;
}

public Sprite getOffender() {
    return p_offender;
}

public void setOffender(Sprite value) {
    p_offender = value;
}

public String getName() {
    return p_name;
}

public void setName(String value) {
    p_name = value;
}

public int getIdentifier() {
    return p_identifier;
}

public void setIdentifier(int value) {
    p_identifier = value;
}

public Rect getBounds() {
    Rect r = new Rect(position.x, position.y,
            position.x + p_width, position.y + p_height);
    return r;
}

public Rect getBoundsScaled() {
    Rect r = getBounds();
    r.right = (int) (r.left + r.width() * p_scale.x);
    r.bottom = (int) (r.top + r.height() * p_scale.y);
    return r;
}

Collision Demo Source

The Collision Demo program is a project that uses the engine library again, as usual. The goal of this program is to demonstrate sprite collisions in real-time by highlighting collisions as they occur. This is done by drawing a red box around sprites that are in a collision state. Figure 21.6 shows the program in action.

Figure 21.6. The Collision Demo highlights sprite collisions in real-time.

Here is the source code for the Collision Demo program. As expected, it is again on the short side, thanks to the engine.

/**
 * H21 Collision Demo
* Requires game.engine.Engine to build.
 */
package android.program;
import java.util.Random;
import android.graphics.*;
import android.renderscript.*;
import game.engine.*;

public class Game extends game.engine.Engine {
    Canvas canvas;
    Paint paint;
    game.engine.Timer timer;
    Random rand;
    Texture asteroid_image;
    Sprite ship;
    Texture ship_image;
    boolean collision;

    public Game() {
        canvas = null;
        paint = new Paint();
        timer = new Timer();
        rand = new Random();
        asteroid_image = null;
        ship = null;
        ship_image = null;
        collision = false;
    }

    public void init() {
        setScreenOrientation(Engine.ScreenModes.LANDSCAPE);
    }

    public void load() {
        asteroid_image = new Texture(this);
        if (!asteroid_image.loadFromAsset("asteroid_sheet.png")) {
            fatalError("Error loading asteroid_sheet");
        }

        int w = getScreenWidth();
        int h = getScreenHeight();
        Rect boundary = new Rect(-60,-60,w,h);

        /**
         * Add very fast warping background sprites
         */
        for (int n=0; n<10; n++) {
            Sprite ast = new Sprite(this, 60, 60, 8);
            ast.setTexture(asteroid_image);
            ast.position = new Point(100+w+rand.nextInt(w), rand.nextInt(h-60));
            ast.addAnimation(new FrameAnimation(0, 63, 1));
            Float2 vel = new Float2(rand.nextFloat()*-100.0f, 0); //fast
            ast.addAnimation(new WarpBehavior(boundary, 60, 60, vel));
            ast.setFrame(rand.nextInt(63));
            ast.setScale(0.1f + rand.nextFloat()); //small

            ast.setCollidable(false);
            ast.setName("scenery");
            ast.setIdentifier(10); //arbitrary # (your choice)

            addToGroup(ast);
        }

        /**
         * Add slower collidable warping sprites
         */
        for (int n=0; n<10; n++) {
            Sprite ast = new Sprite(this, 60, 60, 8);
            ast.setTexture(asteroid_image);
            ast.position = new Point(100+w+rand.nextInt(w), rand.nextInt(h-60));
            ast.addAnimation(new FrameAnimation(0, 63, 1));
            Float2 vel = new Float2(rand.nextFloat()*-10.0f, 0); //slow
            ast.addAnimation(new WarpBehavior(boundary, 60, 60, vel));
            ast.setFrame(rand.nextInt(63));
            ast.setScale(1.5f + rand.nextFloat()); //large

            ast.setCollidable(true);
            ast.setName("asteroid");
            ast.setIdentifier(100); //arbitrary # (your choice)

            addToGroup(ast);
        }

        ship = new Sprite(this);
        ship_image = new Texture(this);
        if (!ship_image.loadFromAsset("ship3.png")) {
            fatalError("Error loading ship3");
        }
        ship.setTexture(ship_image);
        ship.position = new Point(100, h/2);
        ship.addAnimation(new ThrobAnimation(0.8f, 1.2f, 0.001f, true));
        ship.addAnimation(new FenceBehavior(new Rect(0,0,200,h-64)));

        ship.setName("ship");
        ship.setIdentifier(200); //arbitrary #
        ship.setCollidable(true);
        addToGroup(ship);
    }

    public void draw() {
        canvas = getCanvas();
        drawText("Collision Demo", 10, 20);
        //ship.draw();

        if (collision) {
            drawText("*** COLLISION ***", 10, 80);
            collision = false;
        }
    }

    public void update() {
        Point touch=null;
        int inputs = getTouchInputs();

        if (timer.stopwatch(20)) {
            if (inputs > 0) {
                touch = getTouchPoint(0);
                if (touch.x < 200) {
                    if (touch.y < ship.position.y) {
                        ship.position.y -= 5.0f;
                    }
                    else {
                        ship.position.y += 5.0f;
                    }
                }
            }

            ship.animate();

        }
    }

    /**
     * New abstract collision() method called by engine
     */
    public void collision(Sprite sprite) {
        Sprite other = sprite.getOffender();
        if (other == null) return;
        if (sprite.getName() == "ship") {
            if (other.getName() == "asteroid") {
                collision = true;
            }
        }
    }
}

Summary

This hour introduced the important subject of collision detection. While studying the concepts behind bounding rectangle and bounding circle detection, we made some impressive new enhancements to the engine that enable, via Sprite properties, automatic collision detection with in-game notifications!

Q&A

Q. Discuss the pros and cons of automatically detecting collisions in a game. In some cases, will it ever be used at all? In other cases, will it be used extensively?

A. Answers will vary.

Q. This hour’s example is a good test of the performance of the code on various Android devices. If you have an Android device, try the game on your device and note the difference in frame rate compared with the emulator. What do you think the result will be?

A. Results will vary. Discuss before and after running the tests.

Workshop

Quiz

1. What type of collision detection uses a rectangle around each object?

2. What type of collision detection uses the radius of a circle around each object?

3. Which Java method is called to test for collisions in the engine code?

Answers

1. Box collision (or bounding rectangle)

2. Radial collision (or bounding circles)

3. Rect.intersects()

Activities

The Collision Demo does a pretty good job of automatically detecting collisions, but it is also a bit slow. Be sure to selectively turn collision on and off for sprites that don’t require it. See what kinds of results you can get by changing the collision method to radial for the asteroids in this project.