This series of tutorials presents a robust method for collision detection and response. The concepts demonstrated apply equally well to both 2D and 3D simulations, and can be generalized for a wide variety of situations. Examples are in C-like pseudocode; basic familiarity C language syntax is assumed. A working example application is provided at the end to demonstrate the collision system in action.
Before we start, a few terms I'll be using:
Enough preamble, let's look at some code! The objects we'll be using in this example look like this:
Our moving objects are rectangular, and store their current position, previous position, and velocity. Static objects only need position and size. Each framestep of the simulation will look something like this (simplified a bit for clarity):
When movingObject is updated, its previous position (presumed to be non-penetrating) is saved in lastPosition. Its position is a hypothetical future state; resolveCollisions may interpolate position back toward lastPosition to some extent in order resolve new penetrations. Note that the example in this tutorial assumes a single moving object; multiple moving objects will be covered in part 2.
Now, the resolveCollisions function itself:
Conceptually, it's fairly simple. It starts with the assumption that the entire framestep is being processed as a single timeslice. An intersection test with the moving object is performed against every* static object, returning a collision struct if penetration has occurred.
*This could be made more efficient with space partitioning, which would allow you to test against only the static objects that are closest to the moving object and may be penetrated by it.
The collision struct contains all of the information necessary to resolve penetration. However, it is not processed until all objects have been intersection tested; if there are multiple collisions, they must be processed in order based on when they occur in the current timeslice. Otherwise, collisions are order-dependent, and the simulation will behave inconsistently. Don't pay attention to the surfaceArea test just yet; we'll come back to it in a moment.
After all objects have been intersection tested, if there were no collisions, we're finished. If there was at least one collision, we've saved the one which occurred earliest within the timeslice in bestCollision. This collision can now be resolved, moving the penetrating object back in time to a point when there's no penetration.
At this point, the timeslice is subdivided. Since we've already tested all of the objects in the simulation and processed the earliest collision, we know that everything up to the time when that collision occurred has been fully resolved. However, if the collision occurred at an earlier time than the very end of the framestep, the moving object may still have some distance to move, and could collide with other objects. Since the simulation has been changed by resolving a collision, we need to start over and test everything again for the remaining timeslice within the framestep.
This continues until either all collisions have been processed, or we hit an arbitrary limit on the number of subdivisions. This limit is imposed so that resolveCollisions cannot get into an infinite loop in a degenerate case where collisions fail to be resolved. The printed warning is so that you'll know you may need to debug your intersection tests or collision response.
There's one niggling problem with this approach for the sort of rectangular objects we're using in this example. If two static objects are flush against each other forming a solid wall, and the moving object is moving diagonally against that wall, a collision may be detected with the inside edge, causing the moving object to get hung up on the crack where the two static objects meet. This is why the surfaceArea field exists in the collision struct. If two collisions occur at the same time, a secondary check is performed to give the one with greater surface area priority over the other. A collision with the inside edge of a crack will produce a surface area of zero or close to zero, while the collision against the solid edge of the wall will have a much larger surface area, so it will take priority and prevent crack snags.
Generally speaking, there are two distinct ways to test for collisions: Discrete, and swept. Discrete collision tests involve checking for penetration at a single point in time. This is problematic in some cases; it allows very small or very fast-moving objects to pass directly through each other. This problem can be exacerbated if you don't use a fixed timestep. In contrast, a swept collision test extrudes the object's path through time and considers the entire span of movement, allowing collisions in between the start and end positions to be detected.
The above resolveCollisions code calls two functions we haven't defined yet: intersectionTest and resolveCollision. Here's a possible intersectionTest implementation:
This may look complex, but it's mostly just tedious. The rectangular bounds of the static object and the moving object in its previous and current positions are saved to temporary variables to help readability. Intersections are tested first on the X axis, then on the Y axis. At the end, whichever axis had the earlier collision (if any) writes the necessary information to outCollision.
For each axis, intersectionTest first checks one-dimensionally to see if the moving object is within the span of the static object on the opposite axis as the one being tested. It then checks one-dimensionlly on the other axis to see if either side of the moving object will penetrate the boundary of the static object. If so, a collision has been detected, and the time at which it occurs within the timeslice is calculated. If objects are already penetrating or moving away from each other, no collision will be registered.
The test that follows may seem a bit strange, but it's necessary to compensate for the fact that this implementation of intersectionTest doesn't truly implement swept collision detection; it simply uses the union rect of the moving object's last and current positions in a discrete test against the static object. If an object is moving diagonally, it's possible to get a false positive if a corner of the union rect passes through a static object, but the actual path of the object does not. By rechecking to make sure the moving object is within range of the static object at the computed collision time, this problem is averted.
The last step in the process is to resolve collisions once the best one has been found. A resolveCollisions implementation might look like this:
The moving object's position is interpolated back toward its lastPosition. In essence, it travels back in time to the latest non-penetrating moment. Velocity is set to zero on the collision axis. (For elastic collisions, you could also negate and dampen velocity on that axis.) Finally, a new lastPosition is saved, and position is updated based on the new velocity for the remaining timeslice. When the next iteration of collision detection is run, the updated velocity ensures that the moving object will not subsequently penetrate the static object that caused this collision again, and the updated lastPosition and position allow it to collide with objects in its newly-altered path of travel.
This technique is not limited to rigid 2D collisions with axis aligned rectangular objects. The intersection test and collision response presented here are only examples. You can replace them with something that detects differently shaped objects, or responds to collisions with different dynamics, or works in the third dimension, and resolveCollisions is still just as applicable. The timeslice subdivision and in-order collision processing is a skeleton on top of which you can implement a wide variety of collision detection behaviors. In part 2 (coming soon), we'll add the capability to resolve collisions between multiple moving objects.