Pool Hall Lessons: Fast, Accurate Collision Detection Between Circles or Spheres

Isn't it wonderful to move through the virtual world in a 3D game? The way you can walk into walls and slide along them as you freely turn -- withoug getting your rail gun stuck between you and the wall? The way you and your opponent can run at each other, swords drawn, actually stop when you reach each other, and can then back away without worrying about your shield getting caught in his chain mail? The way you can circle strafe your opponent over uneven ground without ever having to worry about tripping? In the real world you would have to worry about this kind of stuff…

As developers we can't afford to do collision detection between every polygon of a character and their environment on even the best current hardware; if we did, not only would our games be painfully slow, but we'd also run into problems like those described above. Usually a decent spatial partitioning system and the use of spheres to bound complex, mobile objects let us perform collision detection routines that are very fast and only involve the minimum number of polygons. Not only is it faster, but it helps avoid entangling both player characters and non-player characters in the environment and each other.

Tim Schroeders's article "Collision Detection Using Ray Casting", inthe August 2001 issue of Game Developer magazine focused on detecting collisions between spheres and polygons. This article compliments the information presented there by explaining how to detect collisions between two spheres and determine what they'll do after they collide. This is useful not only for games like pool where accurate collision of spheres is key, but also in games where characters and other mobile objects are bounded by spheres, these can be used to quickly determine if they have bumped into each other.

To make it easier to explain, all the examples will be first in 2D. A later section of this article will explain how to apply the same algorithms to 3D. For the purposes of this article, a circle will be represented by the point at its center and its radius.

Rack 'em! : Proximity Detection between two stationary circles

Are two stationary circles A and B currently touching? The answer, as I'm sure you already know, is very simple. Two circles are in contact with each other if and only if the distance between their centers is less than or equal to the sum of their radii. So, find the distance between the centers of the two circles using the equation:

Then add the radii of the two circles together. If the sum of the radii is greater than or equal to Dist, then the circles are touching. Since multiplications are less computationally expensive than square roots, you should speed up this code by not performing the square root when calculating the distance, and instead square the sum of the radii. The code below shows a sample implementation using this shortcut.

double deltaXSquared = A.x - B.x; // calc. delta X
deltaXSquared *= deltaXSquared; // square delta X

double deltaYSquared = A.y - B.y; // calc. delta Y
deltaYSquared *= deltaYSquared; // square delta Y

// Calculate the sum of the radii, then square it
double sumRadiiSquared = A.radius + B.radius;
sumRadiiSquared *= sumRadiiSquared;

if(deltaXSquared + deltaYSquared <= sumRadiiSquared){
// A and B are touching
}

Your Break: Collision between a moving circle and a stationary circle

For this problem you are given a circle A that is moving through a virtual world. Over a finite period of time, which we'll call t, A moves a certain distance in a certain direction. We'll represent this movement by a vector V. Also in this virtual world is a circle B that is not moving. The problem is to figure out if A comes into contact with B while it is moving along V, and if it does, by what amount do we have to shorten V so that A comes to rest just at the point of contact with B? An illustration of the problem is shown in figure 2.

	Figure 2: Illustration of the Dynamic-Static Collision Problem

Leveraging Stationary Collision

The first, and most obvious solution to this would be to use the stationary collision method described above on the changing destination location of circle A. In other words, move circle A to the end of the movement vector and then test it's new position for collisions. If A is in contact with another circle in its new location, you have two choices. You could do a recursive back off, where you shorten the movement vector and try again until A and B are not touching. Or you could simply not move A. These methods have several problems.

If you went with the recursive back off solution, you could potentially eat up a lot of CPU time trying to make the collision appear accurate. Or, you could set a limit on the number or retries, reducing the computations to an acceptable load but then leaving you potentially with the same problems with the other option…

You could not move the circle at all. It's really cheap to do, but nothing would ever seem to really touch. In the game, circle A would move towards a static circle B over several frames until it's new position intersected with B. Then it would appear to just stop dead some amount before it would have hit B, as if the static circle B had some kind of invisible force field built around it. Assuming you are doing collision detection based on frame rate, the effects would be more noticeable as the frame rate drops.

Finally, if A is moving fast, it is possible that A's final destination is on the other side of B, but not touching it. You would have to perform additional checks to make sure A did not pass through any other object.

Clipping the Movement Vector

A better approach would be to use the movement vector V to represent the circle as it moves through the world. Now all the collision detection is simplified down to a vector tested against a static circle. This approach does one test to see if V touches B. If it does not collide then you are done testing.

This solution has problems as well. Consider the situation shown in figure 3. The movement vector V from the center of A does not come into contact with anything. However, it only checks the path traveled by the center of A for collision, and the bottom or top could still collide with B even if the middle does not.

	Figure 3

A possible solution to this problem is to test against two more vectors coming from the edges of the moving circle parallel to the movement vector V. While this may fix the problem described above, we can see in figure 4 that if we adjust the movement vector V to be the length of the clipped second vector, the circles will still overlap. Also, if the moving circle is larger than the static one, the static one might fit between the top and center vectors, or between the center and bottom vectors, so the collision would not be detected at all. The moving circle would appear to go right over the smaller static one. Obviously this is not the correct answer for collision detection.

	Figure 4