Introduction

Since the last post, a few of the placeholder graphics have been replaced with real sprites, and there are some new weapons. While testing them, I noticed that something was off with the collision detection. It turned out that both the broad phase and the narrow phase had a flaw, so let’s take a look.

Bullets That Pass Through Enemies

Every now and then, a bullet would visibly fly straight through an enemy without hitting it. My first guess was that the hitbox was a few pixels too small, but it wasn’t.

What was going on is this: a fast bullet can move further in one frame than a small enemy is wide. So in one frame it’s in front of the enemy, and in the next it’s already behind it. Since the collision check only looks at where things are at the end of each frame, 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, so a bullet that ended the frame in a different grid cell than its target was never checked against it. 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, and the grid uses that 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 price: 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 takes care of 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. But 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. Either way, though, the game’s update loop would have to change, because it moves everything once and checks collisions once per frame. That’s a lot of rework for one bug.

So, let’s leave the existing check 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, because two objects moving side by side at the same speed can’t pass through each other, however fast they are.

What about a speed threshold? I don’t use one. 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 wouldn’t save any work either: 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.

I ruled out two other options. 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. And making small hitboxes bigger doesn’t fix the bug either, it just changes the difficulty.

Two Moving Shapes

The sweep has to deal with two moving shapes of different sizes. Luckily, there’s a standard trick that 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 some care, though. 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 r2r\sqrt{2} along the diagonal, about 41% further, which means a circle that only passes near a corner would count as a hit.

So what does the code do? It 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);
}

Here, 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 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 us the time of impact, because time is the same for both objects. It doesn’t give us the position, though. For that, we 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.

So how do we fix that? By making “first” mean first in time. The sweep already computes when the two shapes touched, so every hit gets its own time of impact. The collision pass now 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.

But what time does a simple hit have? The simple check only sees that the bullet overlaps B at the end of the frame, while 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. If we treated B’s hit as “end of frame”, we’d 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

So what does all this 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:

ObjectsSweeps per passSweep offSweep onΔPer sweepAllocated (off / on)
1031.96 ± 0.05 μs2.10 ± 0.05 μs+6.8%49 ns412 / 434 B
20114.66 ± 0.09 μs5.27 ± 0.21 μs+13.2%55 ns1442 / 1384 B
30288.54 ± 0.22 μs9.67 ± 0.18 μs+13.3%40 ns3092 / 3019 B
404914.27 ± 0.50 μs16.04 ± 0.63 μs+12.4%36 ns4940 / 5065 B
506421.63 ± 0.73 μs24.61 ± 0.74 μs+13.8%47 ns8081 / 8243 B
609832.38 ± 1.39 μs37.23 ± 1.47 μs+15.0%50 ns11117 / 11768 B
7012146.78 ± 2.32 μs53.88 ± 2.94 μs+15.2%59 ns15988 / 14974 B
8016967.77 ± 4.05 μs74.68 ± 4.00 μs+10.2%41 ns20755 / 19698 B
9020395.71 ± 7.81 μs104.60 ± 5.16 μs+9.3%44 ns24924 / 24855 B
100248131.13 ± 9.41 μs144.56 ± 9.58 μs+10.2%54 ns30079 / 31912 B
The sweep adds about 7 to 15% to a frame's collision work, roughly 50 ns per sweep

The sweep adds about 7 to 15% to a frame’s collision work, roughly 50 ns per sweep

The sweep adds about 7 to 15% to the frame’s collision work, roughly 35 to 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, and 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. I got that wrong: the 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. So in the next post, we’ll replace those with convex hulls that follow each sprite’s outline.

Resources