Collisions, Part Deux

When Bullets Tunnel

Since the last post, some placeholder graphics have been replaced with actual sprites, and a few new weapon types have been added. I also stumbled upon the collision detection again, which turns out to have been too simplistic after all: Both the broad phase and the narrow phase had a flaw, which we’ll now take a closer look at.

The Innocent-Looking Bug

Every now and then, while testing the game, I’ve noticed the following: Sometimes a bullet visibly flies right through an enemy without hitting it. At first glance, it looks like the hitbox is a few pixels too small. But that’s not the case. With a calculator in hand, the problem becomes clear: Fast projectiles travel a distance in a single frame that might exceed the width of a small enemy hitbox. This means a projectile can be clearly in front of an enemy in one frame, but clearly behind it in the next. There’s never an overlap that could be detected. The collision check always considers only two snapshots: before and after the frame. If the enemy fits completely into the gap between them, it’s essentially invisible - Too bad! This has a name: tunneling. Here’s a quick illustration of the problem:

The Spatial Hash Grid Had the Same Blind Spot

The previous post also touched on the broad phase of collision detection. Using a spatial hash grid, it is possible to quickly rule out pairs that cannot possibly touch before performing more complex calculations. It turned out that this grid had exactly the same problem, just one level higher. It indexed each object solely based on its bounding box at the end of the frame. As a result, a bullet that ended the frame just across a grid cell boundary from its target was never even offered up as a candidate pair. The blind spot was not only in the narrow phase, but already one step earlier: In the decision of which pairs should be checked at all.

To fix this, an additional bounding box is added to the object. For a moving object, this box is the union of the boxes from the current and previous frames, built from before-and-after snapshots. The grid indexes against this wider box instead of the plain end-of-frame box. As a result, a fast bullet now appears in every cell along its path, not just the one in which it lands. Anything in one of those cells becomes a candidate pair.

The tradeoff is that a fast object now costs more grid memberships and produces more candidate pairs than a slow one at the same size, because it’s touching more cells.

Just Take Smaller Steps, Then!

Now that the broad phase is fixed, how can we fix the narrow phase? The seemingly simple solution is “sub-stepping”: You break down the movement of a fast object within the same frame into several smaller segments and perform the usual before-and-after check for each segment. Done globally, these extra steps would be performed for every object, not just the few that are truly fast. The entire collision check would be repeated multiple times per frame for the slow majority of objects, which never had a tunneling problem to begin with. Adaptive sub-stepping, which only splits up the fast objects, avoids that cost and is a common approach. But either way, a sub-stepping movement loop would have to be woven into the code, which currently assumes “move once, check for collisions once per frame”. That’s more rework than a missed-hit bug seems to justify.

Instead, the existing before-and-after check is kept the same. It is performed the same way it was before. If this check does not detect a collision, a second, more detailed check follows: a sweep that checks whether the two shapes touched at any point during the frame. It only has to run for pairs that moved relative to each other. Two objects traveling side by side at the same speed can’t have passed through each other, no matter how fast they are.

The first version only swept when the relative motion was large compared with the smaller of the two shapes, on the theory that slow pairs can’t tunnel. That’s almost true, but not quite: A shot that grazes a corner can only cross a tiny part of the shape, and that small part can be shorter than any threshold. And the threshold didn’t even save any work: In the example below, every pair that reached this point was a fast bullet that cleared it anyway. So it was dropped. If the simple check misses a pair of candidates, and they move relative to each other, they are swept.

Two other options were quickly ruled out. Adding an opt-in flag to certain fast projectile types might appear as a reasonable quick fix until you consider the situation a year from now: Every time a new fast weapon is added in the future, someone will have to remember to set that flag, and the day someone forgets, the bug will be back unnoticed. Yikes. Deriving the condition from how the pair actually moved relative to each other means you don’t have to remember anything. Just making the minimum hitbox size bigger isn’t a bug fix. It’s more like changing the difficulty, which only looks like a bug fix.

Two Moving Shapes

The next step is to examine two moving shapes with different sizes. The standard trick collapses both difficulties in sequence:

1. Motion: Instead of reasoning about two things moving, subtract one object’s movement from the other’s. What’s left is a single relative displacement. Only one thing is moving, the other thing is now holding still.
2. Size: A Minkowski sum lets you “grow” one shape by the outline of the other. Once that’s done, the second shape shrinks to a single point.

Here’s an illustration of how this works:

After doing these two steps, the original question turns into a ray cast. Does a straight line, representing the point’s path, ever enter this one grown region?

Here’s an example:

The corners are important. If you enlarge a box the “lazy” way, by the radius of a circle, all the edges are simply shifted outward by that radius, and the corners stay square. Along the edges, that’s exactly right. At the corners, it isn’t: A circle rolling around a box’s corner stays exactly one radius away from it, so the real grown shape has rounded corners. The squared-off corner sticks out to $r\sqrt{2}$ along the diagonal, about 41% farther. A circle that would have touched a corner is counted as a hit even though it didn’t make contact.

The fix casts against the simple squared-off version first. Only when the impact point lands in one of the diagonal zones next to a corner does it solve that corner again as what it really is: a circle with the same radius. In code, that’s a slab test against the grown box followed by a corner check:

static bool TryCircleVsAabbTime(Vector2 center, float radius, Rectangle box, Vector2 displacement, out float t)
{
    t = 0f;

    if (displacement.LengthSquared() < EpsilonSquared) {
        return false;
    }

    // Cast the circle's center as a ray against the box grown by the radius (squared corners).
    if (!TryRayVsBox(center, displacement,
            box.Left - radius, box.Top - radius, box.Right + radius, box.Bottom + radius,
            out var boxTime)) {
        return false;
    }

    var centerAtImpact = center + displacement * boxTime;
    var isPastVerticalEdge = centerAtImpact.X < box.Left || centerAtImpact.X > box.Right;
    var isPastHorizontalEdge = centerAtImpact.Y < box.Top || centerAtImpact.Y > box.Bottom;

    // Hit a flat edge: the squared version was exact.
    if (!isPastVerticalEdge || !isPastHorizontalEdge) {
        t = boxTime;
        return true;
    }

    // Hit a squared-off corner: re-solve against the real rounded corner, a circle of the same radius.
    var corner = new Vector2(
        centerAtImpact.X < box.Left ? box.Left : box.Right,
        centerAtImpact.Y < box.Top ? box.Top : box.Bottom);

    return TryCircleSweep(center, corner, radius, displacement, out t);
}

center is the circle’s center at the start of the frame, and displacement is how far it moves relative to the box during the frame. TryRayVsBox is the classic slab test, which clips the ray’s entry and exit times one axis at a time. TryCircleSweep solves the quadratic for when a moving point first comes within radius of the corner. The result t is the time of impact, as a fraction of the frame between 0 and 1. The method returns false if the circle never touches the box during the frame.

The other two shape pairs are simpler. Two boxes grow into a bigger box with square corners that are actually correct, so that’s the plain slab test on its own. Two circles become one circle whose radius is the sum of both radii, so that’s TryCircleSweep on its own.

The next important point is this: Two objects touching each other is one thing. Where they touched is another thing. The subtraction trick (subtracting one motion from the other) is used to determine the time of impact because it involves a fact of relative motion. However, it can’t be used to determine the position of impact. To do that, you have to take that point in time and put it back into the actual path of each object to find a point of contact that’s meaningful.

Which Hit Comes First?

For a single pair of shapes, the sweep only looks for a hit after the simple check has missed, so it can only add a hit, never change or remove one. With three shapes involved, it gets less tidy.

Picture a bullet that tunnels right through enemy A and ends the frame overlapping enemy B, right behind it. That’s two hits in one frame: A swept hit on A and a simple end-of-frame hit on B. The collision pass used to act on each hit as soon as its pair came up. Pairs come up in whatever order the spatial hash grid happens to store them. Since a bullet destroys itself on impact, which also switches off its collider. So, whichever pair came up first won. Sometimes that was B, the enemy behind the one the bullet actually reached first. At least the bullet can’t damage both enemies, but picking the wrong one is bad enough. When A happened to come first, the sweep’s hit on A replaced the simple hit on B. So an existing hit did change after all.

The fix makes “first” mean first in time. The sweep already computes when in the frame the two shapes touched; that number just wasn’t passed along. Every hit has its own time of impact. The collision pass collects all hits first, organizes them based on their time, and then acts on them in order. Before acting on each one, it checks again whether both objects can still collide. If an earlier hit already used up the bullet, the later one is dropped.

That raises the question of what time a simple hit has. The simple check only sees that the bullet overlaps B at the end of the frame. That means contact began at some point up to the end of the frame, not necessarily at the end. Enemies in a shmup overlap all the time: The bullet might have entered B at t = 0.2 and still be inside it at the end, while its swept hit on A is at t = 0.36. Treating B’s hit as “end of the frame” would pick A, even though the bullet reached B first. So simple hits run the same sweep, just to find out when contact began. Where they touched still comes from the simple check, as before. Pairs that were already touching when the frame started get t = 0.

What This Actually Costs

To measure what the sweep costs, the collision benchmark runs the same build twice: once as it ships, and once with the sweep switched off. The scene is modelled on the game: a 640×360 playfield (the design resolution), where half the objects are player bullets (small circles moving 7.5 units per frame, the game’s fastest) and the other half are enemies (32×32 boxes drifting 1.5 units per frame).

Times are the mean ± standard deviation for one simulated frame: moving every object, rebuilding the spatial hash grid and running the collision pass. Allocations are bytes per frame. “Sweeps per pass” counts how often the sweep actually ran, and “per sweep” is the extra time divided by that count:

The obligatory diagram:

The sweep isn’t free. It adds about 7–15% to the frame’s collision work, roughly 35–60 ns per sweep. At 100 objects, that’s about 13 μs per frame, less than 0.1% of the frame budget at 60 fps. Every pair that reaches the narrow phase runs exactly one sweep: either to find a hit the simple check missed, or to find out when a hit it found began. Allocations are the same with and without it. Running the two variants in the opposite order gives the same picture, so run order isn’t skewing the numbers.

Two things are active in both columns, so their cost isn’t part of the difference: the wider broad-phase boxes from earlier in this post, and the step that collects and sorts all hits before acting on them.

An earlier version of this post claimed the sweep cost nothing measurable. That benchmark spread its objects over a 2000×2000 field, so they almost never shared a grid cell. At 10 objects, the narrow phase ran about once every five frames. It could hardly have measured the sweep at all.

Closing the Gap

Tunneling was fixed with a sweep test that runs for every candidate pair the simple check misses, as long as the two moved relative to each other. For any single pair, the new code only adds a hit that the old code missed, and never changes or removes a hit that it already got right. That’s why it could ship without redoing any of the existing collision unit tests. Across several pairs in one frame, hits are now ordered by when they actually happened, instead of by whatever order the grid happens to store things in.

Next up, every hitbox in the game so far has been either a circle or an AABB. This works well for many enemies, but can be inaccurate for long, thin, or maybe L-shaped ones. The next post will look at replacing those with convex hulls fitted to each sprite’s actual outline.

Resources

• https://en.wikipedia.org/wiki/Minkowski_addition