Chapter 10: Collision Detection

Boxes, broad phase, and the bullet that tunnels

Collision detection sounds like it should be the easiest topic in a game programming book. Two rectangles either overlap or they do not; the test is four comparisons and every game engine ships it.

The four comparisons are indeed easy. What is not easy is the assumption hidden underneath them, which almost nobody states out loud: a per-frame overlap test is only correct while things move less than their own size per frame. Break that assumption — with a faster bullet, a thinner target, or one slow frame — and the test silently stops working. The bullet is above the alien on one frame and below it on the next, never overlapping, and the shot simply does nothing.

That is a miserable bug. It is intermittent, it depends on frame rate, it gets worse on the cheap phones your players own and never happens on your development machine, and the symptom — "shots sometimes don't register" — points at input rather than at collision. This chapter builds the test, states the assumption precisely, gives you a formula for the exact speed at which it breaks, and then fixes it.

What you will learn in this chapter

• The axis-aligned bounding box, the four-comparison overlap test, and why the comparisons are strict.
• Why a per-frame overlap test tunnels, and the exact speed at which it starts to.
• How a swept test works, and the cheap approximation that fixes tunnelling for most games.
• The difference between broad phase and narrow phase, and why you want both.
• Why a moving object needs to remember where it was.
• How to choose collision shapes that are not the same as your art.
• The caveats: swept boxes over-report, rotation, and the limits of AABBs.

The code for this chapter

The demonstration is at github.com/nodoid/MonoGameBook/src/Chapter10. It lets you fire shots at a target, raise the shot speed, and turn the swept test off — at which point you can reproduce tunnelling on demand and watch shots pass through a solid object.

The axis-aligned bounding box

An AABB is a rectangle that never rotates. This book stores one as a centre and two half-extents:

public readonly record struct Aabb(Vec2 Centre, float HalfWidth, float HalfHeight)
{
    public float Left   => Centre.X - HalfWidth;
    public float Right  => Centre.X + HalfWidth;
    public float Top    => Centre.Y - HalfHeight;
    public float Bottom => Centre.Y + HalfHeight;

    public Aabb MovedTo(Vec2 centre) => this with { Centre = centre };
}

Centre-and-half-extents rather than min-and-max is a deliberate choice, and it pays off constantly. Moving a box is one assignment. Scaling it is one multiply. The distance between two boxes' centres is the natural quantity for a broad-phase test. And the expansion used later in this chapter is trivial to express. The Left/Right/Top/Bottom properties recover the min-max form for the two places that want it.

The overlap test itself:

public static bool Overlaps(Aabb a, Aabb b) =>
    a.Left < b.Right && a.Right > b.Left &&
    a.Top  < b.Bottom && a.Bottom > b.Top;

This is the separating axis theorem in its simplest possible case. Two convex shapes do not overlap if there exists an axis along which their projections are disjoint; for two axis-aligned boxes there are only two axes to check, and each check is two comparisons.

The comparisons are strict. a.Left < b.Right, not <=. Two boxes that share an edge exactly do not collide. That is the right default: tiles laid edge to edge in a grid should not be reported as overlapping every one of their neighbours, and an object resting exactly on a floor should not be re-colliding every frame. If you want touching to count, use <= deliberately and write down why.

The assumption, stated precisely

Consider a shot travelling straight up at speed v, and an alien whose box is h tall. On each frame the shot is tested where it currently is. Between two tests it moves v × dt.

If v × dt is greater than h, there exists a starting position from which the shot is below the alien on one frame and above it on the next, and never inside it. The test never sees the overlap. The shot passes through.

The book puts that in Core as a function, because a number you can print is worth more than a paragraph you have read:

/// <summary>How far a box may move per frame before a plain overlap test can miss.</summary>
public static float TunnellingSpeed(Aabb target, float secondsPerFrame) =>
    target.HalfHeight * 2f / secondsPerFrame;

Put real numbers in. An alien 14 design units tall, a game running at 60 fps: 14 / 0.0167 = 840 units per second. The design space is 800 units tall, so a shot that crosses the screen in one second is already at the limit.

Now run the same game on a phone that is managing 30 fps: the safe speed halves to 420. And during a single 250 ms stall — the scenario from Chapter 4 — it collapses to 56 units per second, which is slower than almost anything in a game moves. That is why tunnelling reports arrive as "it happens sometimes" rather than as a reproducible bug.

Three of the four ways out are unsatisfying:

• Slow everything down until nothing can outrun its own size. Changes the game to suit the implementation.
• Make everything bigger. Same objection.
• Use a fixed timestep so dt never grows. Chapter 4 gives you this and it genuinely helps — it eliminates the stall case entirely — but it does not help with a shot that is simply fast.
• Test the path, not the point. This is the real answer.

Sweeping

A swept test asks whether the moving box overlapped the target at any point during the frame, not just at the end of it. The exact version solves for the earliest time of impact and is a page of algebra. The approximate version is one line:

/// <summary>The box covering this one's whole journey, used as a cheap sweep test.</summary>
public Aabb Expanded(Vec2 travel) => new(
    Centre + travel * 0.5f,
    HalfWidth  + MathF.Abs(travel.X) * 0.5f,
    HalfHeight + MathF.Abs(travel.Y) * 0.5f);

Grow the box to cover the whole journey: the centre moves to the midpoint of the path, and each half-extent grows by half the distance travelled on that axis. The result is the smallest AABB containing both the start and end boxes.

/// <summary>Overlap test against every position the box passed through this frame.</summary>
public static bool SweptOverlaps(Aabb moving, Vec2 travel, Aabb target) =>
    Overlaps(moving.Expanded(travel), target);

That is the entire fix. Two multiplies, two absolute values, and the same four comparisons as before. A shot moving 900 units in one frame now presents a 900-unit-tall box to the test, and cannot skip anything.

What the approximation gets wrong

The expanded box is the bounding box of the swept path, not the swept path itself. For motion along a single axis — which is what a vertical shot does — the two are identical, and the test is exact.

For diagonal motion they differ. A shot moving diagonally sweeps a slanted capsule; its bounding box is a rectangle containing that capsule, including two corner regions the shot never visited. So a diagonal sweep can report a hit that did not physically occur, in the corners.

Whether that matters depends on your game. For bullets it essentially never does — a false positive in a corner region is indistinguishable from a graze, and players read it as generous rather than wrong. For a platformer character resolving against level geometry it matters a great deal, and you want a real swept AABB test that returns the time of impact so you can move the character exactly to the contact point.

Remembering where you were

A swept test needs the start of the journey as well as the end, which means moving objects have to remember their previous position:

public sealed class Shot
{
    public Vec2 Position { get; private set; }
    public Vec2 PreviousPosition { get; private set; }

    public Aabb Box => new(Position, 2f, 7f);
    public Vec2 Travel => Position - PreviousPosition;

    public void Update(float seconds)
    {
        PreviousPosition = Position;
        Position = Position with { Y = Position.Y - Speed * seconds };

        if (Position.Y < -20f)
            IsAlive = false;
    }
}

Three points worth copying.

`PreviousPosition` is set first in `Update`, before the move. Setting it afterwards — or in a separate pass — leaves a window in which the two disagree, and the resulting bug is a shot whose swept box is empty on the frame it should have hit.

`Travel` is derived, not stored. Same principle as Chapter 9: two stored values that must agree are two values that can disagree.

The box is derived too, and it is (2, 7) — a shot four units wide and fourteen tall. Not a square, because a bullet is not a square, and the height is what makes the vertical tunnelling case less severe than it would otherwise be.

This extra field is also exactly what render interpolation needs, from Chapter 4. Objects that remember where they were are useful twice.

Broad phase and narrow phase

Everything above is a narrow phase test: given two specific objects, do they collide? The other half of the problem is deciding which pairs to test at all.

With n moving objects and m targets, testing everything against everything is n × m tests per frame. For a shot against forty aliens that is forty tests — free. For two hundred particles against two hundred obstacles it is forty thousand, per frame, and it is no longer free.

The broad phase is a cheap filter that eliminates most pairs before the real test runs. In increasing order of complexity:

Test the obvious first. A shot travelling up cannot hit anything below it. One comparison eliminates most of the world, and it costs nothing.

Uniform grid. Divide the playfield into cells, put each object in the cell(s) it covers, and only test objects sharing a cell. Ideal when objects are roughly the same size and evenly spread — which describes almost every 2D arcade game.

Sort and sweep. Keep objects sorted by their left edge; walk the list and only test overlapping spans. Very effective for objects that mostly move along one axis.

Quadtree or spatial hash. Necessary when the distribution is wildly uneven or the object count is in the thousands. Rarely necessary for a mobile 2D game, and a great deal of machinery to maintain.

The advice for a book at this level is blunt: start with the n × m loop, and add the "test the obvious first" filter, which is a single if. Move to a uniform grid when a profiler — Chapter 22 — tells you collision is costing real milliseconds. A quadtree you added before you needed one is a source of bugs, not of speed.

Layers: the other cheap filter

Before the broad phase, there is an even cheaper one: most pairs of objects have no business colliding at all. Player shots should not hit the player; alien bombs should not hit aliens; particles should hit nothing.

The standard implementation is a pair of bitmasks per object — what layer am I on, and what layers do I collide with — and a single & to decide whether to test:

[Flags]
public enum Layer
{
    None        = 0,
    Player      = 1 << 0,
    PlayerShot  = 1 << 1,
    Alien       = 1 << 2,
    AlienBomb   = 1 << 3,
}

public static bool ShouldTest(Layer aMask, Layer bLayer) =>
    (aMask & bLayer) != 0;

One bitwise AND per pair, before any arithmetic. In a game with four layers this typically removes three-quarters of the candidate pairs, and it removes them for a reason a reader can understand, which the spatial structures do not.

Caveats

The swept box over-reports on diagonals

Covered above, and worth repeating because it is the one thing about this technique that will surprise you. If you need geometric truth on diagonals, use the exact slab test.

Very fast objects still need care

Sweeping fixes detection. It does not fix ordering: if a shot's swept box overlaps two aliens, which did it hit? The expanded-box test cannot tell you, because it has discarded the time information. Either take the nearest target along the direction of travel — cheap and almost always right — or use the exact test and take the smallest time of impact.

AABBs cannot rotate

Rotate an AABB and it is no longer axis-aligned; the usual response is to grow the box to contain the rotated shape, which makes it noticeably too big at 45 degrees. If your game has rotating rectangles, you need oriented boxes and a full separating-axis test, which is a different chapter. Circles, on the other hand, are rotation-invariant and cheaper than boxes — distanceSquared < (r1 + r2)², with no square root — so for round things use circles.

Do not compare distances with a square root

Vec2.Length calls MathF.Sqrt. In a hot loop comparing distances, compare squared distances instead and never call it. Chapter 9's KillNearest uses Length because forty comparisons per shot is nothing; a particle system doing ten thousand should not.

Detection is not resolution

This chapter answers "did they touch?". It does not answer "where should they be now?". Resolution — pushing objects apart, sliding along walls, stacking — needs the contact normal and the time of impact, and is a substantially harder problem. For an arcade game where collision means "destroy both objects", detection is all you need, which is why this book stops here.

The exact test, for when you need it

The expanded-box sweep detects. When you need to respond — stop a character at a wall, slide along it, or decide which of two overlapping targets was hit first — you need the fraction of the frame at which contact occurred. That is the slab test, and it is short enough to be worth having in full:

/// <summary>
/// Time of impact of a moving box against a static one, as a fraction of the
/// frame, or null when they never meet. Axis-aligned motion only.
/// </summary>
public static float? SweepTime(Aabb moving, Vec2 travel, Aabb target)
{
    float entry = 0f;
    float exit = 1f;

    if (!Slab(moving.Left, moving.Right, target.Left, target.Right,
              travel.X, ref entry, ref exit))
        return null;

    if (!Slab(moving.Top, moving.Bottom, target.Top, target.Bottom,
              travel.Y, ref entry, ref exit))
        return null;

    return entry;
}

private static bool Slab(
    float min, float max, float targetMin, float targetMax,
    float travel, ref float entry, ref float exit)
{
    if (MathF.Abs(travel) < 0.0001f)
        return min < targetMax && max > targetMin;   // no motion on this axis

    float near = (targetMin - max) / travel;
    float far  = (targetMax - min) / travel;

    if (near > far)
        (near, far) = (far, near);

    entry = MathF.Max(entry, near);
    exit  = MathF.Min(exit, far);

    return entry <= exit;
}

The idea is that each axis defines a slab — a band the moving box must be inside for a collision to be possible on that axis — and the box is inside both slabs only during the overlap of their two time intervals. Take the latest entry and the earliest exit; if the entry is after the exit, the intervals do not overlap and there is no collision.

Two details are easy to get wrong. The near > far swap handles motion in the negative direction, where the two boundary crossings arrive in the opposite order. And the near-zero travel case has to be handled separately, because dividing by it gives infinities that propagate; the correct answer when there is no motion on an axis is simply whether the boxes already overlap on it.

With a time of impact in hand, resolution is straightforward: move the object to position + travel * entry, zero the velocity component on the axis that produced the entry time, and — if you want sliding — re-run the remaining 1 - entry of the frame with the other component intact.

Circles, which are cheaper

If the thing you are testing is roughly round, do not use a box at all:

public static bool CirclesOverlap(Vec2 a, float ra, Vec2 b, float rb)
{
    Vec2 delta = b - a;
    float radii = ra + rb;
    return delta.X * delta.X + delta.Y * delta.Y < radii * radii;
}

Two subtractions, three multiplies, two additions and a comparison — cheaper than the four comparisons of an AABB once you account for computing the edges, and with no square root because the radii are compared squared. Circles are also rotation-invariant, which means a spinning asteroid needs no special handling at all.

The general rule for a 2D game is: circles for things that are round or that rotate, AABBs for things that are rectangular and do not, and a circle-versus-AABB test for the pairs that mix. That last one is the nearest-point test — clamp the circle centre to the box, then compare the distance to the radius — and it is another six lines.

Building and running this chapter

The solution is src/Chapter10/Chapter10.sln in the book's repository at github.com/nodoid/MonoGameBook/src/Chapter10. It builds and runs entirely on its own; nothing in it depends on any other chapter having been read or built.

Build either head from the chapter folder:

cd src/Chapter10
dotnet build Android/Chapter.Android.csproj
dotnet build iOS/Chapter.iOS.csproj

To deploy to a connected Android device or a running emulator:

dotnet build Android/Chapter.Android.csproj -t:Run

To run on the iOS Simulator without opening an IDE, build for the simulator runtime and install the bundle by hand:

dotnet build iOS/Chapter.iOS.csproj -p:RuntimeIdentifier=iossimulator-arm64
xcrun simctl install booted \
  iOS/bin/Debug/net10.0-ios/iossimulator-arm64/Chapter10.iOS.app
xcrun simctl launch booted com.monogamebook.chapter10

Everything the chapter demonstrates is reachable by touch on the first screen; there are no menus to navigate and nothing to load.

Try it yourself

1. Turn the swept test off and raise the shot speed until shots start passing through the target. Compare the speed at which it starts with the TunnellingSpeed figure on screen.
2. With sweeping off, halve the target's height and note that the tunnelling speed halves with it.
3. Turn sweeping on and raise the speed as high as it will go. No shot is ever missed.
4. Change Overlaps to use <= and place two boxes exactly edge to edge. Watch them collide continuously.
5. Add a Layer mask to Shot and to the target, and confirm that a shot on the PlayerShot layer refuses to test against another PlayerShot.

Summary

An axis-aligned box test is four strict comparisons, and storing boxes as a centre plus half-extents makes everything else in the chapter easy to write. That test is correct — and only correct — while objects move less than their own size per frame. TunnellingSpeed puts a number on it: for a 14-unit target at 60 fps, 840 units per second, halving on a 30 fps device and collapsing to almost nothing during a stall.

Sweeping fixes it for a line of code. Expand the moving box to cover its journey — centre at the midpoint, half-extents grown by half the travel — and test that. Exact for axis-aligned motion, slightly generous on diagonals, and cheap enough that there is no reason not to use it for anything fast.

Doing that requires moving objects to remember where they were, which is a field you want anyway for render interpolation. Set it at the top of Update, before the move, and derive travel rather than storing it.

Around the narrow-phase test sit two filters. Layer masks remove pairs that should never interact, with one bitwise AND. A broad phase removes pairs that are nowhere near each other; start with a single directional if, move to a uniform grid when a profiler says so, and do not build a quadtree you have not measured a need for.

Chapter 11 steps back from the playfield to the structure around it: waves, lives, game over and restart — and why a transition table is a better answer than the pile of booleans that every game grows if you let it.