Collision Basics

Collision detection is really more than just detection. We break down collisions into three areas of interest:

• Deciding what collisions to test. It seems kind of ridiculous to test whether two objects collide if they are on opposite sides of the world. Also, a world with 1,000 moving objects would require you to test each object against every other object, or 999,000 tests in all. So, you should try to limit the number of objects you need to test as much as possible. An easy way to do this is only test objects that are close.
• Detecting a collision. Collision detection really depends on how accurate you want the collisions to be. You could provide perfect collision detection and test every polygon in one object with every polygon in another object, but just imagine the amount of computation involved. Likewise, for the 2D world, you could test every pixel from one sprite to every pixel from another sprite. Usually, games settle with collision-detection techniques that are slightly inaccurate but can be processed quickly.
• Handling a collision. If an object collides with something, the collision will be handled in different ways depending on the type of collision. For example, a projectile colliding with a robot might destroy both the projectile and the robot. An object bumping against a wall might slide against the wall. And so on.

In summary, a game should try for these collision-detection goals:

• Eliminate as many collision tests as possible.
• Quickly decide whether there is a collision.
• Provide collision detection that is accurate enough for the game.
• Handle the collision in a way that doesn't distract the user from the game.

The last goal is basically saying you don't want to restrict the player's movement too much during the course of a game. For example, you don't want to completely stop a player during a wall collision. Instead, let the player slide against the wall or gently bump off it. Also, you don't want your collision detection to be inaccurate to the point that the player can cheat by squeezing through the wall at certain locations in the map, for example. Let's start with a simple collision-detection algorithm. Consider that everything that moves in the game is an object, whether it's a monster, the player, a projectile, or whatever. For each object, follow these steps:

1. Update the object's location.
2. Check for any collisions with other objects or with the environment.
3. If a collision is found, revert the object to its previous location.

Notice that you check for a collision after each object moves. Alternatively, you could just move all the objects first and then check collisions afterward. However, you'd have to store the object's previous location with the object, and problems could occur if three or more objects collide. Also, this basic algorithm just reverts an object to its previous location if a collision occurred. Normally, you want to use other types of collision handling based on the type of collision. With this algorithm in mind, let's get started with object-to-object collisions.