luminance

Initially I implemented collision detection and motion in this platformer prototype the same way I had done it previously in Fury², my game creation system project from a while back. Entities have a position and velocity, which are both pairs of floats (x, y). Every frame, I compute the new position of the entity - pos+vel - in a given axis (x or y), and then do a check to see if it’s obstructed. If it’s obstructed, I halve the velocity and try again, and I repeat that iteratively a few times until I give up. After doing that for both axes, I have a relatively good approximation of how far the entity can move in its desired direction.

It was good enough for me, and the performance wasn’t *terrible*, so I didn’t worry about it much. But I always had this nagging doubt in my mind - this solution is obviously a hack. Isn’t there a way to do this with pure math?

Well, I’m not very good at math, but it turns out there is a way to do it with pure math. So today I threw out all the motion and collision code I had written for the platformer and decided to try a pure math approach, and see if I could resolve collisions non-iteratively. Suprisingly enough, it wasn’t actually that hard.

Here’s a summary of how it works:

I already do my collision detection using the separating axis theorem (SAT). To check for collision between a pair of convex polygons, I compute a set of axes based on the polygons (a vector perpendicular to every edge of each polygon) and then for each axis in the set, I project both polygons onto that axis and see if they overlap. As soon as I find an axis in which the polygons are not overlapping, I know that they are not intersecting - no need to check all of them.

Pretty simple, and actually quite easy to code - Around 20 lines of C# for a relatively efficient implementation of the check itself, and another 20 lines to compute the list of axes without any duplicates, since there’s no point in checking the same axis twice.

With the algorithm described above, it’s actually quite simple to build motion on top of it. Once I’ve projected both polygons onto a given axis, and confirmed that they don’t intersect, I can do another projection - I can project the velocity of the moving polygon onto that same axis, and add that to the original projection of the moving polygon to get the projection of its new, desired location. At that point, I know whether the polygon will intersect on this axis as a result of moving, and not only that, I can compute the amount of intersection by determining how much the two intervals overlap. Once I have that value, I can use it to compute a vector that will separate the two polygons.

Once I iterate over all the axes and compute separating vectors, I can pick the smallest separating vector and add it to the original velocity of the polygon. At this point I can do some checks to see if the new velocity is acceptable - for example, did the separating vector cause the polygon to change directions entirely? In that case, it’s probably not acceptable, and we can just flat-out reject movement and say that the polygon cannot move in this direction at all. Likewise, if the separating vector is enormous, that means the polygon moved all the way through the obstruction to avoid collision, which we obviously don’t want either, so we can reject it.

The end result was essentially this:

• For every axis, project movingPolygon and stationaryPolygon onto that axis. This produces two intervals - movingInterval and stationaryInterval.
• Check to see if movingInterval and stationaryInterval overlap. This tells us whether or not the polygons were already colliding.
• Project the velocity of movingPolygon onto the axis, and add that projected value to movingInterval. This gives us the new interval of the moving polygon - newInterval.
• Check to see if newInterval and stationaryInterval overlap. If they overlap, determine how much they overlap by - overlapAmount. At this point we know whether or not the two objects would have collided.
• If the newInterval is overlapping, we can now compute a vector that will separate the two polygons, by multiplying the current axis by the amount of overlap (the axis is a unit vector, and the amount of overlap is a distance).
• Add the separating vector to the original velocity of the polygon, to compute the new candidate velocity - newVector.
• Check to see if Magnitude(newVector) <= Magnitude(movingPolygonVelocity). If not, reject the new vector.
• Check to see if Normalize(newVector) ·dot· Normalize(movingPolygonVelocity) >= 0. If not, reject the new vector. (This ensures that we don’t push the object in the opposite direction to resolve the potential collision - in this case, the magnitude would have still passed the previous check)
• If the new vector was not rejected, we know that the two objects will not be colliding.
• Once you’ve iterated over all the axes, select the largest non-colliding vector (if any). That’s your resultVector.

At the end of this algorithm, you have four outputs:

• areColliding (right now, before applying the velocity)
• wouldHaveCollided (if we applied the original velocity)
• willCollide (if you apply the result velocity)
• resultVelocity

In the case where the collision could not be resolved, the resultVelocity will be 0. In the case where there was no collision, the resultVelocity will be the input velocity. In every other case, the resultVelocity is a vector that safely moves the polygon in the desired direction, without producing a collision.

One detail to note is that the quality of the result velocity depends on the axes that you check. If you only check axes generated from the shapes of the colliding objects, you can get strange (though valid) results - for example, two boxes will not produce any axes except X and Y to check, so if the object is moving at an angle, the algorithm will miss the ideal axis to compute the resultVelocity from. There are a few ways to solve this - you can pre-compute a set of ‘basic axes’ to check in every case, or you can derive a set of axes from the velocity of the object. Either way, though, the algorithm seems to work quite well - it works as well as the old one did in the platformer, and passes all my unit tests.

It’s always nice to go from 100 lines of code to 10 lines of code. Unfortunately, I’m not done yet. My previous implementation supported walking up and down slopes in a natural manner, and it also supported moving platforms. The new implementation supports neither, so I have some more work to do. Hopefully I can solve both of those problems using pure math, too - I’m working on sloped surfaces right now, and it looks like I can make it work with pure math by improving on my existing algorithm.

You can see the source code for my implementation here. Note that there’s some commented out bits in there from my work on sloped surfaces.

Gruedorf Code, collision, csharp, Fury², Gruedorf, motion, platformer, polygon, xna