Collisions, Part Deux

Introduction

Since the last post, some placeholder graphics have been replaced with real sprites, and there are a few new weapons. The collision detection also needed another look: both the broad phase and the narrow phase had a flaw.

Bullets That Pass Through Enemies

Sometimes a bullet visibly flew through an enemy without hitting it. It looked like the hitbox was a few pixels too small, but it wasn’t. A fast bullet can move further in one frame than a small enemy is wide. So it can be in front of the enemy in one frame and behind it in the next. The collision check only looks at where things are at the end of each frame, so it never sees an overlap. If the enemy fits into the gap between two positions, the bullet misses it. This is called tunneling:

The Same Problem in the Broad Phase

The previous post introduced the broad phase: a spatial hash grid that quickly rules out pairs that can’t touch, before the more expensive checks run. The grid had the same problem. It stored each object by its bounding box at the end of the frame. A bullet that ended the frame in a different grid cell than its target was never checked against it. So the problem started one step earlier than the narrow phase: in choosing which pairs to check at all.

The fix is a second bounding box per object. For a moving object, it covers both its position in the previous frame and its position in this frame. The grid uses this wider box. A fast bullet is now in every cell along its path, not just the one it ends in, and everything in those cells becomes a candidate pair.

The cost: a fast object is in more cells than a slow one of the same size, so it produces more candidate pairs.

Fixing the Narrow Phase

That fixes the broad phase. For the narrow phase, the obvious fix is sub-stepping: split each frame’s movement into smaller steps and run the check after each one. Doing that for every object repeats the whole collision check several times per frame, mostly for slow objects that never tunnel. Adaptive sub-stepping only splits the fast objects, which avoids that cost. But either way, the game’s update loop would need to change, because it moves everything once and checks collisions once per frame. That’s a lot of rework for one bug.

Instead, the existing check stays as it is. If it finds no collision, a second check runs: a sweep, which tests whether the two shapes touched at any point during the frame. It only runs for pairs that moved relative to each other. Two objects moving side by side at the same speed can’t pass through each other, however fast they are.

There is no speed threshold. A shot that grazes a corner only crosses a tiny part of the shape, and that part can be shorter than any threshold. A threshold also wouldn’t save work: in the benchmark below, every pair that reaches this point is a fast bullet that would pass it anyway. So if the simple check misses a pair and the two moved relative to each other, the pair is swept.

Two other options were ruled out. An opt-in flag on fast projectile types would work until someone adds a new fast weapon and forgets to set it. Deciding from how the pair actually moved needs no flag. Making small hitboxes bigger doesn’t fix the bug either. It changes the difficulty.

Two Moving Shapes

The sweep has to handle two moving shapes of different sizes. The standard trick removes both problems, one after the other:

1. Motion: Subtract one object’s movement from the other’s. Now only one object moves, and the other stands still.
2. Size: A Minkowski sum grows one shape by the outline of the other. The other shape then shrinks to a single point.

After these two steps, the question becomes a ray cast: does the point’s straight path enter the grown shape?

The corners need care. The simple way to grow a box by a circle’s radius is to move every edge outward by the radius and keep the corners square. That is exact along the edges, but not at the corners. A circle rolling around a corner stays one radius away from it, so the real grown shape has rounded corners. The square corner sticks out to $r\sqrt{2}$ along the diagonal, about 41% further. A circle that only passes near a corner would count as a hit.

So the code casts against the square version first. If the impact point lands in a corner zone, it solves 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. displacement is how far it moves relative to the box during the frame. TryRayVsBox is the standard slab test: it clips the ray’s entry and exit times one axis at a time. TryCircleSweep solves a quadratic equation 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, from 0 to 1. The method returns false if the circle never touches the box during the frame.

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

One more detail: when two objects touch and where they touch are separate questions. Subtracting one motion from the other gives the time of impact, because time is the same for both objects. It doesn’t give the position. For that, put the time of impact back into each object’s real path.

Which Hit Comes First?

For one pair of shapes, the sweep only runs after the simple check has missed, so it can only add a hit. With three shapes, it gets more complicated.

Take a bullet that tunnels 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 hit on B. The collision pass used to act on each hit as soon as its pair came up, in whatever order the grid stores the pairs. A bullet destroys itself on impact, which also turns off its collider, so whichever pair came up first won. Sometimes that was B, the enemy behind the one the bullet reached first. And when A came first, its swept hit replaced the simple hit on B, so the sweep did change an existing hit after all.

The fix: “first” now means first in time. The sweep already computes when the two shapes touched, so every hit gets its own time of impact. The collision pass collects all hits, sorts them by time, and acts on them in that order. Before each one, it checks that both objects can still collide. If an earlier hit already used up the bullet, the later hit is dropped.

What time does a simple hit have? The simple check only sees that the bullet overlaps B at the end of the frame. Contact may have started earlier. Enemies in a shmup overlap all the time: the bullet might have entered B at t = 0.2, while its swept hit on A is at t = 0.36. Treating B’s hit as “end of frame” would pick A, although the bullet reached B first. So simple hits also run the sweep, only to find out when contact began. Where they touched still comes from the simple check. Pairs that already touched at the start of the frame get t = 0.

Cost

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

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

The sweep 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 a frame 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 found hit began. Allocations are the same with and without it. Running the two variants in the opposite order gives the same result.

Both columns include the wider broad-phase boxes and the sorting of hits, so their cost is not part of the difference.

An earlier version of this post said the sweep cost nothing measurable. That benchmark spread its objects over a 2000×2000 field, so they almost never shared a grid cell, and the sweep hardly ran.

Summary

A sweep now runs for every candidate pair the simple check misses, if the two moved relative to each other. For a single pair, it only adds hits the old code missed and never removes one, so the existing collision tests stayed as they were. When several pairs hit in one frame, the hits are handled in the order they happened.

Next up: every hitbox in the game so far is a circle or an AABB. That works for many enemies, but not for long, thin or L-shaped ones. The next post replaces those with convex hulls that follow each sprite’s outline.

Resources

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