2D collision detection: boxes, circles, SAT and tunnelling

Collision detection is one of those systems that looks finished after an afternoon and then keeps sending you bug reports for months. The player sinks a pixel into the floor. A bullet passes through a thin wall. Two crates jitter forever because they keep pushing each other in turns. None of this is mysterious once you split the problem into its parts: finding out whether two shapes overlap, finding out by how much and in which direction, moving them apart, and making sure fast objects cannot skip the test entirely. This piece builds those parts in order, with small std Rust code you can drop into any engine, and a couple of numbers to show where the limits are.

Step 1: decide what "collision" means in your game

Before writing a test, write down what you need the answer for. There are three common questions, and they want different code.

1. Is anything touching this? A pickup, a trigger zone, a hurtbox. You only need a yes or no.
2. How far do I need to move to stop overlapping? Solid characters and walls. You need a direction and a depth.
3. When during this frame did the first contact happen? Fast bullets, dashes, anything that moves more than its own size per step. You need a time.

Most small games need all three, but for different pairs of objects. Treating every pair as a full physics contact is how a jam game ends up spending half its frame on coins. Keep the cheap question cheap.

It also helps to decide early whether your collision runs on a fixed step. If movement is integrated with a variable delta time, the same jump can land in the floor on one machine and on top of it on another. A fixed timestep loop makes every test below behave identically from run to run, which matters a lot when you are trying to reproduce a bug.

Step 2: axis-aligned boxes

The axis-aligned bounding box, or AABB, is the workhorse of 2D games. Its sides line up with the x and y axes, so two boxes overlap when their ranges overlap on both axes at once. I store boxes as a centre and half extents rather than min and max corners, because the overlap depth then falls out of the same subtraction.

#[derive(Clone, Copy, Debug)]
struct Aabb { cx: f32, cy: f32, hw: f32, hh: f32 }

/// Returns the push to apply to `a` so it no longer overlaps `b`.
fn aabb_push(a: Aabb, b: Aabb) -> Option<(f32, f32)> {
    let dx = b.cx - a.cx;
    let px = (a.hw + b.hw) - dx.abs();
    if px <= 0.0 { return None; }
    let dy = b.cy - a.cy;
    let py = (a.hh + b.hh) - dy.abs();
    if py <= 0.0 { return None; }
    // Push out along the axis of least penetration.
    if px < py {
        Some((-px * dx.signum(), 0.0))
    } else {
        Some((0.0, -py * dy.signum()))
    }
}

The function does two things in one pass. If either axis has no overlap, it returns early with None, which is the cheap yes or no answer. If both overlap, it picks the axis where the overlap is smallest and returns a push along that axis, pointing away from b. That "minimum translation" rule is what makes a character standing on a floor get pushed up rather than sideways.

One small trap: signum of zero is one in Rust for positive zero, so two boxes with identical centres get pushed in a consistent direction rather than not at all. That is usually what you want, but it is worth knowing when you see a crate spawned inside a wall shoot out to the left every time.

Step 3: circles

Circles are even cheaper, and they are friendlier for characters that should slide around corners instead of catching on them. Two circles overlap when the distance between their centres is less than the sum of their radii. Compare squared distances so you only take a square root when there is an actual hit.

fn circle_push(ax: f32, ay: f32, ar: f32, bx: f32, by: f32, br: f32) -> Option<(f32, f32)> {
    let (dx, dy) = (ax - bx, ay - by);
    let r = ar + br;
    let d2 = dx * dx + dy * dy;
    if d2 >= r * r { return None; }
    let d = d2.sqrt();
    if d == 0.0 { return Some((r, 0.0)); } // same centre, pick an axis
    let depth = r - d;
    Some((dx / d * depth, dy / d * depth))
}

The push here points from b towards a, scaled by the overlap depth. The zero distance case needs its own branch because the normal is undefined; any fixed direction works as long as it is deterministic.

Circle against box is the mixed case you will meet constantly, a round player against square tiles. The trick is to clamp the circle's centre into the box to get the closest point on the box, then run the circle test against that single point with a radius of zero. It is four lines and it handles corners correctly, which a pure box player never does.

Step 4: the separating axis theorem

Boxes and circles cover a surprising share of games. When you need rotated rectangles, slopes or arbitrary convex polygons, the separating axis theorem (SAT) is the standard tool. The idea is simple to state: two convex shapes do not overlap if and only if there is some line you can project them both onto where their shadows do not overlap. For polygons, you only need to try the normals of each polygon's edges.

for each edge normal n of shape A, then of shape B:
    project every vertex of A onto n, keep min and max
    project every vertex of B onto n, keep min and max
    overlap = min(maxA, maxB) - max(minA, minB)
    if overlap <= 0: shapes are separate, stop
    if overlap < best: best = overlap, best_axis = n
push A by best along best_axis, flipped to point away from B

That pseudocode is the whole algorithm. The AABB test in step 2 is SAT with only two axes, x and y, which is why it is so fast. A rotated rectangle adds two more axes. A triangle against a rectangle has five distinct normals at most.

Two details catch people. First, normals do not need to be normalised to answer the yes or no question, but they must be normalised if you want the overlap to be a real distance. Second, the direction of the final push must be checked against the vector between the shape centres and flipped if it points the wrong way, otherwise objects get pulled through each other.

Step 5: resolve overlaps without jitter

Detection tells you about one pair. A level has many. The naive loop, test every pair and push immediately, works for two objects and falls apart with a stack of five crates, because each push creates a new overlap somewhere else.

A few rules keep this calm:

• Move one axis at a time for characters. Apply horizontal velocity, resolve against the world, then apply vertical velocity and resolve again. This alone removes most "stuck on the seam between two tiles" bugs, because the character never sees a diagonal overlap with a tile edge.
• Static geometry never moves. When a dynamic object hits a wall, the dynamic object takes the whole push. When two dynamic objects meet, split it, half each, or weight it by mass if you have one.
• Zero the velocity component along the push. If the floor pushes you up, your downward velocity should go to zero. Otherwise gravity keeps rebuilding the overlap every frame and you get a slow, visible sink.
• Iterate a fixed small number of times. Two to four passes over the overlapping pairs settle most stacks. If they do not, the design probably wants fewer stacked physics objects rather than more passes.

Step 6: stop tunnelling

Tunnelling is when an object moves so far in one step that it is on one side of a wall before the step and on the other side after, and the overlap test never sees them touching. Let us put numbers on it.

Take a fixed step of 60 updates per second, so each step is about 16.7 milliseconds. A wall is 8 pixels thick. A bullet is 4 pixels wide. For the bullet to be guaranteed to overlap the wall in at least one step, it must not move more than the combined thickness, 12 pixels, per step.

So anything faster than about 720 pixels per second (12 pixels times 60) can pass through that wall. That is not fast for a bullet. A player dash of a few hundred pixels per second is fine; a projectile almost never is.

There are three fixes, in order of effort.

Substep. Split the movement of fast objects into smaller pieces and test each one. If the bullet moves 30 pixels, move it in three steps of 10. Simple, and the cost is only paid by the few objects that need it.

Sweep with a ray. Treat the bullet as a point moving along a line segment, and test that segment against the wall box expanded by the bullet's half size. This gives you a time of impact between 0 and 1 within the step, so the hit happens at the right place even at enormous speeds. The slab method for segment against box is a dozen lines and well documented in any graphics textbook.

Thicken the world. Sometimes the honest answer is to make the walls thicker in the collision data than they look in the art, or to cap projectile speed. Level designers rarely notice a wall that is solid 4 pixels deeper than its sprite.

Step 7: do fewer tests

Testing every object against every other object is n squared. With 50 objects that is 1,225 pairs, which is nothing. With 2,000 particles that might hit enemies, it is close to two million, which is a lot.

A uniform grid is the usual answer for 2D. Pick a cell size roughly the size of your typical object, put each object into the cells its box touches, and only test pairs that share a cell. For tile maps you already have this grid for free: a character can only touch the handful of tiles under its box, so compute those tile coordinates and test only them. If you have structured your game with components, as described in the piece on ECS for 2D games, the broad phase is a natural system of its own that writes candidate pairs for the narrow phase to read.

Quadtrees and bounding volume hierarchies exist and are good, but for a small 2D game a grid is easier to debug and usually fast enough. Measure before you reach for anything clever.

A quick debugging routine

When a collision bug arrives, I go through the same short list:

1. Draw every collider as an outline. Half of all collision bugs are a box that is offset from its sprite.
2. Log the push vector for the involved pair for a few frames. A push that flips sign every frame means two resolutions are fighting.
3. Check the order: movement, then resolution, then rendering. Resolving after drawing shows the overlap for one frame and looks like jitter.
4. Freeze the game and step one update at a time. Tunnelling and seams are obvious at that speed.

Where to go next: take the AABB function above, add the circle against box case from step 3, and build a tiny test level with an 8 pixel wall and a 4 pixel bullet you can speed up with a key. Watch it start to pass through at the speed the table predicts, then add substepping and watch it stop. Once the numbers match what you see, the rest of the collision code tends to make sense. If you want to see where collision sits among the other systems, the overview of game engine architecture shows how it fits between input, simulation and rendering.