Object-to-Object Collisions

Ideally, no matter how accurate you want the collision detection to be, it's a good idea to both eliminate as many object-to-object tests as possible and do a few other tests first to ensure that two objects have a good chance of colliding.

Eliminating Tests

Obviously, if an object doesn't move from one frame to the next, you don't need to do any collision tests for that object. For example, a crate that just sits there will never collide with anything. Other objects will collide with the crate, but those collisions are handled by the other objects. To help eliminate collision tests further, you really should test only objects that are in the same proximity. One way to do this is to arrange objects on a grid, like in Screenshot. Each object exists in one cell on the grid. Even though an object's bounds could extend to other cells, the object exists in only one cell. This way, an object needs to test for collisions only with objects in its own cell and its surrounding cells.

Other ways to isolate objects include 1D or 3D versions of the grid concept. For example, in a side-scrolling game, objects could be in a list sorted by their x location, so only neighboring objects in the list test for collisions. For a 3D game, objects could be isolated in a 3D grid instead of a 2D grid, so each cell would be a cube instead of a square. In this chapter, for collision with the 3D engine, we use the 2D version. Isolating objects on a gird also has the benefit of easily applying object culling. For example, with a top-down engine, you would draw only the objects in visible cells. For a BSP tree, you would draw only the objects in cells that have visible leaves. The code for arranging objects in a grid is trivial and is implemented for this chapter in the GridGameObjectManager class. When an object is updated, the checkObjectCollision() method is called (see Listing 11.1). This method checks for a collision with any objects in the object's surrounding cells.

Listing 11.1 Checking Surrounding Cells (GridGameObjectManager.java)

/**
 The Cell class represents a cell in the grid. It contains
 a list of game objects and a visible flag.
*/
private static class Cell {
 List objects;
 boolean visible;
 Cell() {
 objects = new ArrayList();
 visible = false;
 }
}
...
/**
 Checks to see if the specified object collides with any
 other object.
*/
public boolean checkObjectCollision(GameObject object,
 Vector3D oldLocation)
{
 boolean collision = false;
 // use the object's (x,z) position (ground plane)
 int x = convertMapXtoGridX((int)object.getX());
 int y = convertMapYtoGridY((int)object.getZ());
 // check the object's surrounding 9 cells
 for (int i=x-1; i<=x+1; i++) {
 for (int j=y-1; j<=y+1; j++) {
 Cell cell = getCell(i, j);
 if (cell != null) {
 collision |= collisionDetection.checkObject(
 object, cell.objects, oldLocation);
 }
 }
 }
 return collision;
}

This code calls the chectObject() method of the CollisionDetection class, which detects a collision between an object and a list of objects. You'll implement this class next.

Bounding Spheres

An inaccurate but fast technique for performing collision detection is the use of bounding spheres, such as the one in Screenshot.

This idea is that if two objects' spheres collide, the collision is treated as if the two objects collide. A first try at testing whether two objects' spheres collide works something like this:

dx = objectA.x - objectB.x;
dy = objectA.y - objectB.y;
dz = objectA.z - objectB.z;
minDistance = objectA.radius + objectB.radius if (Math.sqrt(dx*dx + dy*dy + dz*dz) < minDistance) {
 // collision found
}

However, that Math.sqrt() function call involves a lot of computation. Instead, you could square both sides of the equation to get something a bit simpler:

if (dx*dx + dy*dy + dz*dz < minDistance*minDistance) {
 // collision found
}

If your game is in a 2D world instead of 3D, you can test for circles instead of spheres, taking the z coordinate out of the equation. Testing bounding spheres is easy, but it's not very accurate. For example, in Screenshot, the bounding sphere of the player collides with the bounding sphere of the robot, even though the player and the robot don't actually collide.

Of course, having this amount of inaccuracy is fine for many games. For example, for a fast-moving action game in which you're running around picking up food or ammo, you probably won't care whether you pick up the item a little before you actually touch the item. But for other situations, the inaccuracy can be annoying, such as when you get wounded by a creature that you know didn't touch you. After an initial bounding sphere collision tests positive, you could go a step further and perform a second set of more comprehensive tests, such as checking every polygon of the object against every polygon of the other object. Another method is to use a second set of spheres as a more accurate set of tests, as in Screenshot. In this figure, the robot has three bounding spheres that more accurately describe the robot's shape. After the bounding spheres of two objects test positive for a collision, their second set of spheres could be tested. If any of the player's secondary spheres collide with any of the robot's secondary spheres, then a collision occurs.

So, you effectively have two levels of spheres for each object. Of course, you don't have to stop at just two levels of sphere testing. You could have many more, with each level having more spheres, therefore getting more accurate. This is commonly called a sphere tree or sphere subdivision. This way, you can quickly reject noncolliding objects and have more accurate tests for potential collisions. This also lets you know which part of your object was hit, allowing you to act accordingly. For example, you could have just your robot's lower leg fall off if a missile strikes it. Note that sphere trees need to rotate with the object as the object rotates. For example, the spheres need to follow a robot's arm as it moves around. In the code from , "3D Objects," we defined 3D objects as nested polygon groups. Because this is already a tree structure, to implement sphere trees you could give each polygon group its own set of spheres and ensure that the group's transform is applied to the spheres. You won't actually implement sphere trees in this chapter, but it's food for thought. To sum it up, for a typical frame, most of the objects require no collision test, some objects require a simple collision test, and a few objects require the more complex, computationally expensive collision tests.

Bounding Cylinders

An alternative to bounding spheres is upright bounding cylinders, shown in Screenshot. This reduces collision tests to a 2D circle test and a 1D vertical test.

Upright bounding cylinders tend to describe tall, thin objects (such as players or monsters) more accurately than just one sphere. In this chapter, for the 3D engine, you'll implement upright bounding cylinders for object-to-object collision detection. All the basic collision-detection code in this chapter goes in the CollisionDetection class. The methods for handling object-to-object collision in this class are shown in Listing 11.2.

Listing 11.2 Checking Objects (CollisionDetection.java)

/**
 Checks if the specified object collisions with any other
 object in the specified list.
*/
public boolean checkObject(GameObject objectA, List objects,
 Vector3D oldLocation)
{
 boolean collision = false;
 for (int i=0; i<objects.size(); i++) {
 GameObject objectB = (GameObject)objects.get(i);
 collision |= checkObject(objectA, objectB,
 oldLocation);
 }
 return collision;
}
/**
 Returns true if the two specified objects collide.
 Object A is the moving object, and Object B is the object
 to check. Uses bounding upright cylinders (circular base
 and top) to determine collisions.
*/
public boolean checkObject(GameObject objectA,
 GameObject objectB, Vector3D oldLocation)
{
 // don't collide with self
 if (objectA == objectB) {
 return false;
 }
 PolygonGroupBounds boundsA = objectA.getBounds();
 PolygonGroupBounds boundsB = objectB.getBounds();
 // first, check y axis collision (assume height is pos)
 float Ay1 = objectA.getY() + boundsA.getBottomHeight();
 float Ay2 = objectA.getY() + boundsA.getTopHeight();
 float By1 = objectB.getY() + boundsB.getBottomHeight();
 float By2 = objectB.getY() + boundsB.getTopHeight();
 if (By2 < Ay1 || By1 > Ay2) {
 return false;
 }
 // next, check 2D, x/z plane collision (circular base)
 float dx = objectA.getX() - objectB.getX();
 float dz = objectA.getZ() - objectB.getZ();
 float minDist = boundsA.getRadius() + boundsB.getRadius();
 float distSq = dx*dx + dz*dz;
 float minDistSq = minDist * minDist;
 if (distSq < minDistSq) {
 return handleObjectCollision(objectA, objectB, distSq,
 minDistSq, oldLocation);
 }
 return false;
}
/**
 Handles an object collision. Object A is the moving
 object, and Object B is the object that Object A collided
 with. For now, just notifies Object A of the collision.
*/
protected boolean handleObjectCollision(GameObject objectA,
 GameObject objectB, float distSq, float minDistSq,
 Vector3D oldLocation)
{
 objectA.notifyObjectCollision(objectB);
 return true;
}

In this code, game objects have a PolygonGroupBounds object that bounds a polygon group as a cylinder. The bounds consist of the cylinder's radius, bottom height (often 0), and top height. The checkObject() method just checks whether two bounding cylinders collide; if they do, the handleObjectCollision() method is called. The handleObjectCollision() method just notifies the moving object that a collision occurred through the notifyObjectCollision() method. This and other notify methods exist in the GameObject class, but they don't do anything by default-subclasses of GameObject can override notify methods if they want. For example, in the Blast class, the notifyObjectCollision() method is used to destroy a bot if it collides with one:

public void notifyObjectCollision(GameObject object) {
 // destroy bots and itself
 if (object instanceof Bot) {
 setState(object, STATE_DESTROYED);
 setState(STATE_DESTROYED);
 }
}

Also, for now, in the GridGameObjectManager, if an object collides with another, its location is restored to its previous location. Later, you'll work to create a more realistic response to an object-to-object collision by sliding to the side of the object.

The Discrete Time Issue

A typical game updates the state of the game in discrete time slices, such as how you update each object based on the amount of time passed since the last update. For example, in Screenshot, this bird's-eye view shows an object's discrete time movement. The moving object collides with the larger object in frame 3.

Unfortunately, this discrete time movement can cause a problem with collision detection. Imagine that the object is moving faster or the frame rate is slower. In this scenario, the moving object could "skip over" the object it collides with. For example, in Screenshot the moving object collides with the larger object between frames 2 and 3.

A couple solutions to this problem exist. The more accurate but computationally expensive solution is to treat a moving object's bounds as a solid shape from the start location to the end location, as shown in Screenshot.

Alternatively, if an object moves a certain distance, you could check various points between the start and end locations for collisions. In Screenshot, you could put an extra check halfway between each frame.