Collisions

Whenever objects move in a scene, there is a chance that they will collide. Unless the objects are ghosts that can pass through each other, the program must detect their collision and take appropriate action. For example, most games will not allow a player to move through a wall. Many games also need to detect circumstances where the player touches an object such as a piece of treasure (a good thing) or where a bullet touches the player (a bad thing).

In this article, you will learn how to do the following:

• Determine when two objects collide

• Use multiple levels of refinement to make collision detection efficient

XNA provides two classes that make collision detection fairly easy: BoundingSphere and BoundingBox. Both of these classes represent a volume that surrounds an object such as a player, tank, bullet, or wall.

The BoundingSphere class represents a three-dimensional sphere surrounding an object. It has a center and a radius. One of the advantages of a bounding sphere is that it looks the same no matter how you rotate it. In other words, if the program rotates an object around its center, its bounding sphere remains the same.

The BoundingBox class represents a three-dimensional box surrounding an object. For performance reasons, the sides of the box are always perpendicular to the X, Y, and Z axes. In other words, they are parallel with the X-Y, X-Z, and Y-Z coordinate planes.

The BoundingSphere and BoundingBox classes provide an Intersect method that returns true if the object intersects another BoundingSphere or BoundingBox object. The following code snippet shows how a program might determine whether the player’s BoundingSphere object has intersected a jewel’s BoundingBox object. If the player touches the jewel, the game might award points and remove the jewel from the scene.

if (playerSphere.Intersects(jewelBox))
{
    // The player touched the jewel. Award points and remove the jewel.
    ...
}

A more complicated program that contains many prizes, obstacles, and other objects that can interact with the player might store those objects in lists or arrays so that it can loop through them to see whether any are touching the player.

For example, the Collisions program shown in Figure 1 lets you press on the arrow buttons to move the player’s avatar around. (An avatar is a graphical representation of the player on the screen.)

If the player is pressing a movement button when the Update method executes, the code calculates the player’s new position and then calls the NewPositionOk method shown in the following code to see whether the new position would make the player bump into an obstacle.

// Return false if the new position makes the avatar collide with something.
private bool NewPositionOk(Vector3 newAvatarPosition)
{
    // Get the avatar's new bounding sphere.
    BoundingSphere avatarSphere = new BoundingSphere(
        new Vector3(newAvatarPosition.X, 0, newAvatarPosition.Z),
        AvatarRadius);

    // Check each bounding box for a collision.
    foreach (BoundingBox box in obstacleBoxes)
    {
        if (box.Intersects(avatarSphere)) return false;
    }

    // There was no collision.
    return true;
}

This code creates a BoundingSphere object at the avatar’s proposed new position. All of the obstacles’ bounding boxes extend down to Y = 0 so the program gives the avatar’s bounding sphere the Y coordinate 0 so it can intersect with the objects’ bounding boxes.

After creating the bounding sphere, the code loops through the obstacleBoxes list. If any of the BoundingBox objects in the list intersect the avatar’s sphere, the method returns false to indicate that the player should not be allowed to move to this new position.

Because a BoundingBox object’s sides must be parallel to the coordinate planes, a BoundingBox object is ideal for representing roughly rectangular objects that are stationary and that have sides parallel to the coordinate planes. If the object is rotated so that its sides are not parallel to the coordinate planes, however, its bounding box will not fit as well.

For example, Figure 2 shows two cars. The car on the left is aligned with the coordinate axes so its green bounding box fits it fairly well. The car on the right is rotated so that its sides are not parallel to the coordinate planes, and its yellow bounding box does not fit as well. Although the two boxes bound cars of the same size, the box on the right is considerably bigger.

If a bounding box or sphere does not fit an object well and the program uses it for collision detection, it might think the object has collided with another object when it has not. For example, a small object could intersect the lower-left front corner of the yellow bounding box shown in Figure 2 without touching the car itself. The green bonding box fits its car much more closely, so there is less room for an object to make a “false collision.”

You can face similar problems if you use a BoundingSphere object to represent an object that does not have a very spherical shape. For example, a long skinny object such as a telephone pole will occupy only a small part of a BoundingSphere object, so the sphere will contain lots of space where false collisions might occur.

You can solve these problems by covering tricky objects with more than one bounding box or sphere. For example, you could use a collection of small bounding spheres to cover the edges of the car in Figure 2. Then if the car is rotated, the spheres will move with their edges and they will fit better than a larger bounding box would.

The tradeoff here is that using lots of small bounding boxes or spheres means you need to perform a lot more calculations. If you have 100 obstacles in a scene and use one BoundingBox object to represent a car, then you need to check for 100 possible intersections between the car and the obstacle. However, if you use 10 small BoundingSphere objects to represent the car, you need to check each of those spheres with every obstacle’s bounding box for a total of 10 * 100 = 1,000 comparisons.

You can solve this problem by using a multi-level strategy. First use the larger BoundingBox object to determine whether any of the obstacles intersect that larger volume. Then if one or more collisions occur, see whether any of the smaller BoundingSphere objects intersect with any of the obstacles that intersected the large BoundingBox object. For example, if two obstacles intersected with the large BoundingBox object, the program would need to perform 100 checks for collision with the large BoundingBox object plus 2 * 10 = 20 checks for collision with the smaller BoundingSphere objects, giving a total of 120 comparisons not 1,000.

If you keep track of the player’s and obstacles’ positions, you might be able to reduce the number of comparisons even further. For example, if the player is inside a room in a house, there is no need to check for collisions with obstacles that are outside of the room.

The BoundingBox and BoundingSphere classes make collision detection relatively easy. Use the classes to represent the obstacles, touchable items such as treasures, and moving objects in the scene. When an object moves, compare its bounding object to those of the other objects in the scene.

To represent an object that does not naturally fit well in a sphere or a box aligned with the coordinate planes, you can use several smaller BoundingBox or BoundingSphere objects. To make checking for collisions more efficient, use a larger bounding box or sphere to see whether it is worth checking the smaller bounding objects for intersections. That technique, together with some program logic such as not comparing objects that you know are in different rooms, can make collision detection efficient.

The Collisions program described in this article detects collisions when the player moves an avatar around a scene. In many programs, objects move by themselves. For example, a thrown ball (or hand grenade) flies through the air without any player interaction until it hits the ground (or explodes).

The next article in this series discusses game physics. It explains how a program can model objects such as balls moving in ballistic paths and how you can use position, velocity, and acceleration to model movement more generally.