Module 1 · Arcades and foundations

Collision: AABB and tile-based

Why the cheapest collision primitive — an axis-aligned box — still holds up every 2D engine, and how a tile grid turns a collision check into O(1).

~15 min

The gist in 20 seconds

An AABB (axis-aligned bounding box) is a rectangle whose sides are parallel to the axes. Two of them intersect ⇔ they overlap on both axes at once — that is 4 comparisons, no square roots, no trigonometry. For a static world of tiles it is cheaper still: divide the object's position by the tile size, look at 2–4 neighboring cells, and resolve the collision one axis at a time (X first, then Y) — which removes snagging on corners. The weak spot is tunneling: a fast object jumps over a thin wall in a single step; the cure is a fixed timestep or a swept AABB. The same math is IoU in object detection: box intersection, word for word.

The mechanism

Two AABBs overlapping — the separating axis theorem in miniature

A box is given by its edges [minX,maxX]×[minY,maxY]. Two boxes do not intersect if there is an axis along which their projections come apart. For axis-aligned boxes there are only two candidate axes (X and Y), so intersection is the negation of "they separated on at least one":

overlap \Leftrightarrow (a_{minX} < b_{maxX}) \land (a_{maxX} > b_{minX}) \land (a_{minY} < b_{maxY}) \land (a_{maxY} > b_{minY})

Four comparisons, zero multiplications — which is why this is the basic broad-phase test in every engine. If all four are true, the boxes overlap; the penetration depth on each axis is the smaller of the overlaps, and the cheapest way to push an object out is along the axis of least overlap (the minimum translation vector).

Overlap on both axes = the boxes intersect. Separate on even one and there is no contact.

Tile collision — O(1) instead of "everything against everything"

Checking an object against every wall is O(n). But if the world is laid out in tiles of size T, the object's coordinates directly address the cells: it is enough to look at the 2–4 tiles its box covers.

col = floor(x / T); row = floor(y / T); // the cell under the point // the box covers cells [floor(minX/T)..floor(maxX/T)] × [...Y...]

This reduces "find the nearest wall" to a lookup by index — the same advantage the tilemap gives rendering. The key resolution technique is moving and resolving one axis at a time: move along X → check and push out of walls on X; then move along Y → check and push out on Y. Keeping them separate is critical: resolving both at once makes the object snag on the corner of a tile and get stuck on a flat floor made of tile seams.

Tunneling and sweeping (swept AABB)

A discrete check looks at the position after the step. If the object moved farther than the wall is thick, it was in front of the wall last frame and behind it this frame, and nobody checked the contact in between → it flew through (tunneling). Two cures: a small fixed timestep (which caps the displacement per tick — see the game loop lesson) and a swept AABB — computing not "do they overlap now" but when the first contact happens along the movement segment. For motion along an axis, the entry time per axis is:

t_{entry} = \frac{d_{near}}{v_{axis}}, t_{hit} = \max (t_{entryX}, t_{entryY})

where d_near is the distance to the near face of the obstacle along that axis and v_axis is the velocity along it. The contact is real if t_hit ∈ [0,1] and, at that moment, the projections already overlap on the other axis. Put the object at the position at t_hit, kill the normal component of the velocity and "slide" along the tangent.

A worked example. A bullet flies right at 50 px/tick; a wall 8 px thick sits 30 px ahead of it. Discretely: in one tick the displacement of 50 > (30+8) → the next position is already past the wall, there is no overlap at check time → tunnel. Swept: t_entry = 30/50 = 0.6 ∈ [0,1] → contact at 60% of the step, and the bullet honestly stops in the wall. A smaller fixed step (say 4 substeps of 12.5 px) also catches the wall — but costs more.

🕹 Games to play — and what to notice

From "collision in one line" to the pixel-exact integer physics of platformers. For each case: how it was done and what to provoke to feel the collision model with your hands.

Pong 1972 · collision that is almost 1D

The ball and the paddle are effectively AABBs, but what is interesting is the behavior after contact: the bounce angle often depends on where on the paddle the ball landed (the edge gives a steeper angle) — that is no longer pure physics but a design layer on top of a simple overlap test.

🎮 Play: in Pong, hit the ball with the edge of the paddle versus the center — compare the bounce angles. Check whether the paddle is a segment or a rectangle: catch the ball right at the tip.

Space Invaders 1978 · a grid of AABBs + destructible shields

Bullet against alien is a box overlap; the aliens stand in a grid, so the check goes through addressable cells rather than "every bullet against everyone". The shields are a bitmap chewed away pixel by pixel: a bullet touching a shield erases pixels. Two different collision modes in one game: coarse (grid AABB) and exact (a bitmask on the shield).

🎮 Play: shoot into a shield at an angle — it degrades pixel by pixel, in irregularly shaped holes. That is a pixel mask, not an AABB. Whereas a hit on an alien is an instant "box in box".

Super Mario Bros 1985 · tile collision, per-axis resolution

Mario is an AABB against a tile grid. The genre classic: separate resolution of X and Y (otherwise you snag on tile seams), a "head upward" check for hitting a block and a "feet" one for landing. At high speeds tunneling shows up — speedrunners squeeze through thin walls once they build up momentum.

🎮 Play: in SMB, build up speed on a downhill and fly into the corner of a block — you'll feel the game nudge you one axis at a time. Look up the speedrun tricks that pass through a wall — that is tunneling at high speed.

Celeste / TowerFall pixel-integer physics

Maddy Thorson builds collision on whole pixels: an object is moved one pixel at a time with the fractional remainder banked, and each step is a simple AABB test against the tiles. That is anti-tunneling by brute force (the displacement is capped at a pixel) plus determinism (integer coordinates), which is what frame-perfect tricks and TAS rest on.

🎮 Play: in Celeste, notice the "forgiving" collision at edges (corner correction nudges you past a corner). That sits on top of honest per-pixel AABB — a design layer, like the bounce angle in Pong.

Sonic the Hedgehog a contrast: sensors and height maps

Where AABB isn't enough: slopes and loops. Sonic is not a box: he has sensors (rays pointing down and sideways) that read the tiles' height arrays (a height profile per tile). That is no longer "boxes overlapping" but "probing the surface" — the price for the speed and terrain that a flat AABB cannot give.

🎮 Play: ride a loop or a slope in Sonic — notice how he sticks to the surface at any angle. A box can't do that; those are sensors reading tile height maps.

Deep end · theory: SAT, the Minkowski sum and time of contactskippable

The AABB test is a special case of the separating axis theorem (SAT): two convex bodies do not intersect ⇔ there exists an axis on which their projections do not overlap. For arbitrary convex polygons the candidate axes are the face normals of both bodies; for AABBs the normals degenerate into X and Y, so there are only two axes and the test is that cheap.

The Minkowski sum — why "box against box" = "point against box"

A intersecting B is equivalent to the origin lying inside the Minkowski difference A ⊖ B. For two AABBs that difference is again an AABB (with the half-sizes added). Hence the trick: the problem "a moving box against a wall" collapses into "a moving point (the center) against an inflated wall", and the swept test becomes a ray-AABB intersection — the classic slab method.

The slab method and entry/exit times

A ray p + t·v against an AABB: for each axis you compute the interval [t₁,t₂] during which the ray is inside that axis's slab, and take the intersection of the intervals over all axes:

t_{enter} = \max (t_{1x}, t_{1y}), t_{exit} = \min (t_{2x}, t_{2y})

There is an intersection ⇔ t_enter ≤ t_exit and the interval touches [0,1]. The axis that produced the maximum at entry defines the contact normal — velocity is killed along it and slides along the other. That is continuous collision detection (CCD) for AABBs in its purest form.

Deep end · engineering: broad-phase, spatial indices, determinismskippable

Broad-phase → narrow-phase. First a cheap conservative cull of candidate pairs (AABB overlap), then the expensive exact test only for the survivors. The junior anti-pattern is running the exact test on every pair: that is O(n²).
Spatial hash / uniform grid. You bucket objects into cells and only check within a cell and its neighbors. For objects of similar size this is close to O(n) and simpler than a tree. Tile collision is the degenerate case where the grid already exists.
Sweep and prune. You keep objects sorted by their projection onto an axis; the candidate pairs are those whose intervals overlap. It works well under temporal coherence (little changes from frame to frame).
Hierarchies for mixed sizes. When object sizes differ a lot (and a grid is a poor fit), you take a BVH of AABBs — the same primitive, but in a tree. A direct bridge to rendering (frustum/occlusion culling) and ray tracing.
Determinism. Integer/fixed-point collision + a fixed order of resolving pairs = a reproducible result for lockstep and replays. Float and a non-deterministic order break network sync.

Analogy

An AABB is shipping boxes in a warehouse: to see whether two parcels get in each other's way, you don't unwrap the contents — you check whether the boxes overlap. Crude, but instant. You check the exact shape (the teddy bear inside) only if the boxes already touched. That is broad-phase → narrow-phase: the cheap conservative test culls 99% of pairs, the expensive one finishes off the remaining 1%.

Why it matters

Collision is where "it works" and "it crawls" part ways. Naively checking all pairs kills the frame rate at a hundred objects; AABB plus a spatial grid holds thousands. And the choice of "one axis at a time" versus "both at once" is the difference between a platformer that feels solid and one where the player snags on invisible corners. This is the first lesson about a hierarchy of precision: a cheap conservative filter ahead of an expensive exact one — a pattern that will come back in rendering, in search and in retrieval.

🔁 Beyond games — where this transfers

The lesson gives you two transferable moves: a cheap conservative test before the expensive exact one (broad→narrow) and a spatial index instead of enumerating all pairs.

ML / AI (your domain): AABB overlap is literally IoU (intersection-over-union) in object detection; NMS (non-max suppression) suppresses boxes by the same intersection test. A spatial hash ⇄ ANN / LSH: you bucket vectors and only compare within a bucket. Broad→narrow ⇄ coarse-to-fine retrieval: a cheap ANN candidate generator, then an exact rerank — the same two-phase structure as broad/narrow-phase.

Systems / databases: spatial indices (R-tree, geohash, quadtree) for geo queries; "only check the neighboring cells" = bucketing/sharding by a range key.

Graphics / geometry: BVH and frustum culling in rendering and ray tracing are the same AABBs in a tree; collision and visibility get solved with one structure.

The principle: never run the expensive exact test on every pair. First a cheap conservative filter (one that can only err toward "maybe"), then the exact test on the survivors.

🔧 Run it and poke at it — on your home machine

What to play is above (🕹). Here — see collision live inside an engine:

🔧 Poke at it (debug) ~40 min, Godot

In Godot, put together a platformer from a TileMap + a CharacterBody2D. Turn on Debug → Visible Collision Shapes — you'll see the AABB shapes over the sprites. Split the movement into move_and_slide per axis and watch the resolution. Then break it: crank the object's speed and remove CCD / the small step — you'll catch tunneling through a thin tile. Bring the small fixed step back and the tunnel disappears.

🧪 Test it (QA eyes) ~15 min

Hunt the classic collision bugs: snagging on tile seams (which means the axes are resolved together), jitter at a wall boundary, passing through a wall at speed (tunneling), getting stuck in a corner when touching two walls at once, "sticking" to the ceiling. Every bug is a diagnosis of a specific simplification in the collision code.

Checklist: saw the AABB shapes through debug drawing; provoked tunneling and removed it with a fixed step; caught corner snagging with non-separated axis resolution.

Connections

foundation

Hardware constraints — the sprites and tiles from the previous lesson are exactly the "boxes" and "cells" that collision is computed between.

foundation

The game loop — a fixed step caps the displacement per tick and thereby prevents tunneling; a variable dt during a hitch provokes it.

Arcade AI — ghosts and state machines move on the same tile grid as collision; the topology of cells ties the two lessons together.

Questions worth asking

Why are X and Y resolved separately rather than both at once?

Resolving both at once points the push-out vector "diagonally", and an object moving along a tiled floor snags on the vertical seams between tiles: a micro-overlap on Y at a tile boundary gets read as a wall to the side → stutter and sticking. A separate pass (move on X, push out on X; then Y, push out on Y) makes horizontal movement "blind" to the horizontal seams of the floor. The price is that the axis order slightly affects edge cases (corners), so it is fixed.

AABB overlap and IoU in object detection — really the same formula?

The intersection area of two AABBs is the product of the per-axis overlaps: max(0, minMaxX−maxMinX) · max(0, …Y…). IoU is that intersection divided by the union. So the "did they overlap?" test from collision is IoU's numerator. NMS in detectors discards boxes with a high IoU against an already-accepted one — literally the same geometric primitive as push-out in physics. Different domains, one geometry of axis-aligned boxes.

Is tunneling about collision or about the game loop?

About both, and that is the point. A discrete check only sees the ends of the step; if the displacement per step exceeds the obstacle, the contact in between is lost. It is cured from two sides: from the loop side, a small fixed step (capping the maximum displacement per tick); from the collision side, swept/CCD (finding the moment of contact along the movement segment). During a hitch with a variable dt the step balloons and the tunnel returns — which is why fixed step and collision are one conversation.

Rotate an object by 30° — why does the AABB suddenly lie?

An AABB is by definition axis-aligned: for a rotated object it wraps the overall extent, empty corners included → false positives near the corners and a wrong normal. The options: recompute the AABB as an enclosing box (fast, crude, fine for broad-phase) or move to an OBB / full SAT with face normals (exact, more expensive). The typical scheme: AABB as broad-phase even for rotated bodies, SAT as narrow-phase. That is precisely "cheap filter → exact test".

When is a tile grid worse than a tree (BVH/quadtree)?

When objects differ greatly in size or are distributed unevenly. A uniform grid is good as long as the bodies are roughly one caliber and the density is even: then a cell holds a handful of objects and there are few checks. A giant covering hundreds of cells, or "everything in one corner", kills the grid (either the cell is overloaded or most of them sit empty). Then you take a hierarchy (quadtree/BVH) that adapts resolution to density. Arcade games took the grid because the world was already tiled and uniform.