Simple sphere-based collision detection and response

1. Introduction

This tutorial will serve as a guide for implemening a simple sphere-based collision detection and handling routine. There is a lot of information available on these subjects on the internet, but most of this information is fragmented or poorly explained. Additionally, a lot of information is focused on collision detection with polygons, which is not what I am looking for.

The focus of this guide is on sphere-based collision detection in a tile-based 2D world. While the world is tile-based, the objects can move freely in real coordinates, allowing for more realistic movement. However, this obviously creates some new challenges, especially in pathfinding and collision detection. This guide will hopefully explain in a clear manner how to deal with this problem.

Spheres are a convenient way to efficiently do collision detection for large amounts of objects. Collision checks with spheres are extremely fast, and spheres have some very nice properties that make collision response also relatively simple. Additionally, most game objects can actually be approximated with a spherical shape. If this is not the case, they usually can with a number of spherical shapes. This does not change anything about the algorithms in the following guide; just process each sphere individually as if it is a separate object.

Using spheres to represent game objects in collision detection has a number of advantages over boxes. Boxes have very easy collision checks, but are more difficult to deal with in collision response. It is very difficult to compute how to maneuver two boxes around each other without them colliding at any point. When you only need simple collision response such as "destroy one of the two objects" or "bounce back", collision boxes might be a better and simpler choice over spheres. But in cases where you need somewhat realistic collision behaviour, such as in RTS games, spheres are much more suitable.

And yes, I know a sphere is the 3D version of the 2D circle and that this guide is actually about collision detection with circles. But bounding sphere seems to be the general term used for this kind of thing, so I'll stick with it.

2. Collision detection

The best way to approach collision detection and response is by splitting the movement process up into three separate loops over the game objects. In the first loop (the update loop), each game object determines the location it wants to go to. After this, each object \(i\) has a current location \(L_i\) and a movement vector \(M_i\). In the second loop (the collision detection loop), all objects are tested against each other for collisions. If a collision is detected, it is dealt with gracefully by updating the movement vectors \(M_i\). In the final iteration, the location of all the objects is updated: \(L_i = L_i + M_i\).

We will now discuss the structure of the second loop. For each object \(i\), find all the other objects \(j\) that need a collision check. You can limit the number of collision checks by working with a quad tree or another space division structure. This is highly recommended if there are a lot of objects in your world. For more information on quad trees, see http://en.wikipedia.org/wiki/Quadtree.

We assume that each object \(i\) has a sphere associated with it, positioned at the location of the object \(L_i\) with radius \(R_i\). In order to check for a collision between two objects, we substract radii of the spheres from the distance of the two objects:

$$\left\| (L_i+M_i) - (L_j+M_j) \right\| - R_i - R_j$$

If this is negative, there is a collision, and it must be processed. In games, time is usually divided into so-called ticks, or discrete time steps at which the game is updated. This means that each object does not move continually but in large steps as well. That the objects collide at the end of the time step does not mean that they do halfway there. To have clean movement, we need to detect at which point in time the collision occurs.

The following piece of code does exactly that in a very efficient way:

bool hit = checkCollision(O1, M1, O2, M2);
if (!hit) return;
int n = 1;
double t = 1.0;
double tBestSoFar = 0.0;
while (n < 5) {

   // reduce the movement range by a factor 2^n
   double piece = 1.0 / pow(2.0, n);

   // if we had a hit, we move back one piece
   if (hit) t -= piece;

   // if we don't have a hit, we add one piece
   else t += piece;

   // we check for collision at the new location
   hit = checkCollision(O1, M1*t, O2, M2*t);

   // if we don't have a hit, we have found a better match for our t
   if (!hit) tBestSoFar = t;

   // next iteration
   ++n;
}

 // change the movement vector for both objects
 SM1 = M1*tBestSoFar;
 SM2 = M2*tBestSoFar;  

This algorithm will look for the point in time (where as location for t=0 is \(L_i\) and location for t=1 is \(L_i + M_i\)) where the collision occurs. It starts by testing for a collision at t=1, and if there is one, the algorithm proceeds. It will first look at 0.5 for a collision, and if there is one, it will then look at 0.25, otherwise it will look at 0.75. This process is repeated with double the accuracy each time. This results in a pretty accurate estimation of when the collision occurs.

After this computation, \(SM_i\) contains the part of the original move vector \(M_i\) that is safe to carry out for both objects without having a collision. This code will cause no objects to ever collide, but does not handle collisions really well. If an object encounters another object that is not moving, it will just stop forever, because it cannot find a way around the other object. This is dealt with by collision response, and will be discussed in the next section.

3. Collision response

There are a lot of algorithms for dealing with collision response, and they can be roughly divided into three categories:

• projection-based methods, which adjust the location of the object directly to avoid collision;
• impulse-based methods, which change the velocity (first derivative of the location) of the object in order to avoid collision;
• penalty-based methods, which change the acceleration (second derivative of the location) of the object in order to avoid collision.

 We will propose a projection-based method, inspired by the sliding principle proposed in http://www.peroxide.dk/papers/collision/collision.pdf. Assume we have 2 objects \(M_1, M_2\) again, for which, using the algorithm above, the part of the movement is calculated that does not cause a collision, and the part is calculated that does. This part is represented by respectively \(M_1 * tBestSoFar\) and \(M_1 * (1.0 - tBestSoFar)\). It is only the second part we're concerned with here; the first part can be executed without worries.

So for both objects, we now define the illegal (impossible) part of the move vector as follows:

$$v_i = M_i * (1.0 - tBestSoFar)$$

This vector is illustrated in the figure below:

The idea is to have the objects "slide" besodes each other without colliding, so that they can pass each other. This can be compared to when you are walking, and someone is heading your way in the opposite direction. To avoid collision, one of you moves a bit to the left, while the other moves a bit to the right. In order to calculate the improved and safe move vectors \(v_1',v_2'\) from \(v_1, v_2\), we need the tangent of the spheres at the point where they collide. The tangent is always the same when two spheres collide at one point, and is perpendicular to the vector from one center to the other:

$$d = p2 - p1$$

$$tangent = [d.y, -d.x]$$

The tangent should be normalized:

$$tangent = \frac{tangent}{ \left\| tangent \right\|}$$

We now need to compute which direction we want to slide to. If the move vector leans more to the right of \(d\), the new movement should slide to the right around the other object. This is achieved by calculating the projection of \(v_i\) onto the tangent:

\[u_1 = v_1.x * tangent.x + v_1.y * tangent.y\]
\[u_2 = v_2.x * tangent.x + v_2.y * tangent.y\]

If \(u_i\) is positive, this means we are trying to move in the direction of the tangent vector. If it is negative, we are trying to move in the opposite direction. The sign of \(u_1\) can thus be used to determine in which direction to "slide".

Putting this together results in the following code:

// get the remaining part of the move vector that is illegal
// this is V1 and V2 in the figure
BM1 = (M1 * (1.0 - tBestSoFar));
BM2 = (M2 * (1.0 - tBestSoFar));

// get the tangent in normalized form
d = (L1+SM1) - (L2+SM2);
tangent.x = d.y;
tangent.y = -d.x;
tangent.normalize();

// length of the remaining unsafe move vector
double d1 = BM1.length();
double d2 = BM2.length();

// use the projected version to determine the direction in which to slide
double u1 = BM1.x*tangent.x + BM1.y*tangent.y;
double u2 = BM2.x*tangent.x + BM2.y*tangent.y;

// depending on the sign, we move in a given direction
// if our move vector is perpendicular with d, we move in opposite directions for each object
if (u1 < -EPS) SM1 += -tangent * d1;
else SM1 += tangent * d1;
if (u2 < EPS) SM2 += -tangent * d2;
else SM2 += tangent * d2;

Note the EPS in the last lines. This is used to avoid the case where two objects are headed straight at each other, and both turn into the same direction. This is the case when u1=u2=0. To avoid this issue, one object will prefer moving to the left, while the other will prefer moving to the right. To take into account precision roundoff errors, EPS is used. EPS should be a very small number, close to double precision. Something like 1e-8 should do.


4. Wall collision

In a tile-based world, objects often also encounter straight walls defined as lines, for example when a tile is blocked. The code above can easily be adapted to work with lines as well, allowing spheres that collide with walls to gracefully slide along them. In the case of walls, the tangent should be parallel to the wall and the rest of the code remains the same. The collision check is also straight-forward.

The following site explains the collision check between a sphere and a arbitrarily oriented line very well:
http://paulbourke.net/geometry/sphereline/

If you only need straight lines (on the border of tiles), the collision check is much simpler, and just comes down to checking the horizontal/vertical distance between the line and the sphere center, and seeing if it is larger than the radius.


4. Conclusion

The algorithm presented in this article will have spherical objects gracefully slide their way through a tile-based world. When they collide against each other, they will attempt to slide along each other, avoiding collision alltogether. I hope this guide will be useful for anyone who is developing a 2D game and needs a robust collision detection routine!

All feedback is of course welcome.