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 sounds 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 Map 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 sphere whose point of impact lay directly beyond a grid cell boundary of its target was not even suggested as a candidate pair in the first place. 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. However, 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. Furthermore, a sub-stepping movement loop would have to be woven into the code, which currently assumes that “once moved, checked for collisions once per frame”, requiring more extensive reprogramming than a “missed-hit” error seems to justify.

Instead, the existing before-and-after check is retained in its entirety. It is performed unchanged, as before. If this check does not detect a collision, but the geometry suggests that a collision could indeed occur - namely, when the distance that an object has moved in this frame is large enough relative to the smaller of the two shapes involved - then a second, more detailed check is performed. For the vast majority of pairs, only the simple check is performed, so there are no additional costs here. Only the rare, fast pair that fails the simple check is examined more closely and is allocated a few additional CPU cycles.

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 the actual distance traveled means you don’t have to remember anything. And simply increasing the minimum hitbox size isn’t a bug fix - it’s more of a difficulty adjustment masquerading as a bug fix. It would make every enemy easier to hit at any speed, rather than just fixing the cases where shots actually missed.

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 using the radius of a circle - all the edges are simply shifted outward by that radius, and the corners are flattened. However, this is incorrect, because a circle that runs along the corners of a box cuts them off exactly at a distance equal to the radius. In the flattened version, the wall is shifted outward. A sphere that would have cleanly grazed a corner is incorrectly counted as a hit.

The next important point is this: Whether two objects have touched and where they touched are two different matters. The trick of subtraction (subtracting one motion from the other) applies to determining the time of impact, since this involves a fact of relative motion. However, it does not apply to determining the position of impact. For that, you have to take that point in time and reinsert it into the actual trajectory of each object to obtain a point of contact that is meaningful.

What this actually costs

Let’s run the collision benchmark using both the code from shortly before this change and the code after the change, with each object taking a limited step per frame just beyond the threshold that triggers the tunneling problem. This ensures that each pair appears to be moving quickly and triggers the complex path without moving so far in a single frame that it would have been unrealistic for anything in the actual game.

The obligatory diagram:

The extra cost is about 10% more, and it goes up a little bit with the number of objects, but it never goes below the “Before” baseline. Allocation actually decreases on the “After” side, but this is not due to the sweep. The test whether a tunneling-problem might have occurred only runs after the discrete test. A more likely explanation: These two points in the code are ten weeks apart. In between, there were a few dozen changes to spawning and scene object management. Any one of these changes could easily change a small value like this. So it seems reasonable to say that the decline isn’t because of the sweep collision test.

Closing the Gap

Tunneling was fixed with a sweep test that only kicks in when a pair can move in a way that makes a miss possible. Most pairs are free, and the rest cost about 10%. The new code only adds a hit that the old code missed. It never changes or removes a hit that it already got right. That’s why it could be shipped without redoing every existing collision test. Also, “pay for it only when the geometry demands it” is a safe default rather than a performance hack added to a correctness fix.

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.