It’s been a while since I wanted to revisit our game’s collision-detection system to give it a little boost, but I dragged my feet before rolling up my sleeves—anything to do with collisions always fries my brain.

What we had before was fairly simple, and in itself worked pretty well, without any major glitches. But the constraints on player movement were becoming too severe, so something had to be done.

In our engine, every object in the game is wrapped inside a new, simpler shape than the original. This wrapper shape is computed at the time we load the model into the game, forming a cuboid that encapsulates the entire object. As for our player, we simply placed an invisible cube at their feet.

By now you can probably imagine all the limitations we faced in-game:

• Collisions only occurred at the player’s feet, so if an object was positioned at head or even torso height, there was no collision.

• Because the player’s collision shape is just a cuboid rather than something round, it’s hard for them to climb anything resembling stairs. We had workarounds—like placing an invisible collider over the stairs to simulate a smooth ramp—but it’s far from ideal and adds extra work for the artists.

• More recently, I added a tool to easily edit the maze’s walls. Those walls are long, winding meshes, and bounding boxes handle that kind of shape very poorly—so we need a way to collide against other primitives, like triangles. In fact, any obstacle can be broken down into triangles, since that’s 3D’s fundamental building block.

Those were the three issues I saw as most important to resolve.

Approaches I considerated

There are basically two schools of thought for detecting collisions:

• Predictive system: It works by casting a ray from the player’s current position to where he’ll be at the end of the frame, then checking exactly when it will hit an obstacle.

• Reactive system: We simply check at each frame whether the player is already colliding. If they are, we snap them back out of the collision.

The predictive approach is more forward-looking, since you know in advance if a collision is coming—but the trade-off is that it really is more complicated to implement. The reactive approach, by contrast, is much simpler to code—but it has its own drawback: if the player moves really fast, you can miss a collision between checks.

Originally we used the predictive system, but it was relatively straightforward because it was just cuboid vs. cuboid. Now we want something like sphere/capsule vs. triangle—and that is truly hell; after you rearrange the equation with Minkowski sums and differences, the triangle turns into a collection of 2 triangles, 3 parallelograms, 9 cylinders, and 6 spheres for the corners. No, thanks.

So I chose the reactive system, because it really is simpler to implement (and that’s crucial), and because this isn’t a game where the player will be sprinting around. Here we advance slowly, we observe, we look around—so we’re unlikely to miss a collision during a frame. And honestly, there are simple tricks you can deploy to mitigate any misses. In this world, every problem has its solution.

Collision system overview

1. Broad phase: We iterate through all game objects to see which are roughly near the player, then add those to our checklist. Also, because we now want to collide only with triangles, we turn each obstacle into a collection of triangles—for example, an OBB or AABB is really just twelve triangles. It’s trivial to generate.

2. Narrow phase: This is the heart of it, we take the player’s collider (a sphere at its position) and check whether it collides with any of the triangles on our checklist.

3. Collision response: Once we’ve detected a collision with a triangle, we decide what to do—e.g. re-position the player outside the collision and make them slide gently along the obstacle.

From here on out, we’ll focus on the second phase: collision detection. And my wild explanations—which have given me countless headaches can start.

The Narrow Phase: Sphere vs Triangle

During this phase, we go through our list of triangles (the checklist) and check if the player intersects with any of them. It’s also possible that we'll collide with multiple obstacles within the same frame; if that happens, we only handle the closest one—the one with the greatest penetration depth.

So we have a sphere (at the player’s feet) and a triangle representing a patch of surface. The sphere has a center (the player’s position) and a radius—which determines whether our player is a big eater or not. Finally, the triangle is defined by three points in world space.

At a given time, the player’s sphere projected center can be in one of three states:

• Entirely outside the triangle.
• Entirely inside the triangle (i.e., the sphere’s center lies within the triangle’s three points).
• Partly outside and partly inside—i.e., the center lies outside, but a portion of the sphere’s volume overlaps the triangle.

Knowing those, we can check whether the sphere intersects the triangle’s plane (extended infinitely). We define an infinite plane by a point on it, plus a normal. Since the plane extends the triangle’s surface, we pick one of the triangle points as the plane's point, and compute the plane's normal with the rest of the triangle's points: normal := normalize(cross(v1 − v0, v2 − v0));. Then we project the sphere’s center onto this plane’s normal and measure the distance. If that distance exceeds the sphere’s radius, there’s no collision.

If the distance is less than the radius, it means we intersect the infinite plane—but not necessarily the triangle itself. To test the triangle, we project the sphere’s center onto the plane (giving us a point on it) and then check if that point is inside the triangle; If so, the player collides with the triangle, otherwise, there's still one more case to check.

Now the last one, the trickier case: if the projected point lies outside the triangle, part of the sphere can still hit one of the triangle’s edges. To catch that, we find the closest point on the triangle’s edges to the sphere’s center—and if that distance is less than the radius, we have a collision.

Here’s the check for the last case in code:

min_dist := FLOAT32_MAX;

ab := v1 - v0;
ab_closest_point := closest_point_on_segment(v0, v1, sphere_center);
ab_dist := distance(ab_closest_point, sphere_center);
if  ab_dist <= min_dist {
    closest_edge = ab_closest_point;
    min_dist = ab_dist;
}

bc := v2 - v1;
bc_closest_point := closest_point_on_segment(v1, v2, sphere_center);
bc_dist := distance(bc_closest_point, sphere_center);
if  bc_dist <= min_dist {
    closest_edge = bc_closest_point;
    min_dist = bc_dist;
}

ac := v2 - v0;
ac_closest_point := closest_point_on_segment(v2, v0, sphere_center);
ac_dist := distance(ac_closest_point, sphere_center);
if  ac_dist <= min_dist {
    closest_edge = ac_closest_point;
    min_dist = ac_dist;
}

if distance(closest_edge, sphere_center) < sphere_radius {
    intersect_edges = true;
};

Collision response

Now that we know there’s a collision, we gather the information needed for the last phase—resolution. Generally, the obvious next step is to push our sphere (i.e., the player) out of the obstacle. We place the sphere at the point of impact, then nudge it away along the opposite direction (the surface normal) by the impact depth:

snap_to_surface := velocity;
snap_to_surface += (impact_depth + SKIN_WIDTH) * normal;

Here, impact_depth is simply sphere_radius − distance_from_impact_point. As for the normal, instead of using the surface normal, we use the direction from the sphere’s center to the impact point—that’s actually what lets us climb stairs smoothly.

Here's a little preview of the result, the green sphere shows the collision resolution against the surface: it glides gently over it, with the sphere’s radius giving us a natural margin of error:

From Sphere to Capsule

Until now, the player was represented by a sphere placed at their feet. But, as I mentioned earlier, we want collisions with obstacles that could be on the full height of the player.

Conceptually, a capsule and a sphere are very similar shapes; a capsule is just a stack of spheres placed along a line segment—let's say, roughly the player's height.

For our collision story, we simply need to find the sphere that's closest to the triangle, which means finding the point on this line segment closest to the triangle.

Once that's done and we've identified the closest sphere, we just perform the "Sphere vs. Triangle" check described above—and voilà, we're done.

So right now, the three points from earlier have been addressed, and that was the main goal, but there's still some work left. For instance, I still have a glitch when the player ends up in corners, but that shouldn't be too complicated to fix—I'll keep you posted.

Another feature I’d like to add is the possibility of constraining the player’s movement to a specific surface, preventing them from falling off. This would further reduce the number of colliders we have to manually place in certain parts of the game. But that's a good topic for another article!