AABB, circles and SAT: picking a hitbox

The ball in Brick Buster is a square with a half-width of eight pixels. Every brick it can break is tested as a rectangle two pixels smaller than the one drawn on screen, and the ball may never travel more than six pixels before the game resolves a collision. None of those numbers is about how the game looks.

Three tests cover nearly all of 2D: an axis-aligned box against another box, a circle against a circle, and the separating axis theorem for everything that rotates. Each is exact for one family of shapes and a polite fiction everywhere else, and the fiction is where a player ends up convinced the game cheated.

The costs below are measured, not estimated: each test in a flat loop of thirty million calls in Node 24.18 on one laptop, best of two runs. The absolutes are worth what one machine and one JIT are worth; the ratios survive the trip.

Three collision tests, each in a flat loop of 30 million calls

Test	What the code does	Nanoseconds per call
Box against box	Four comparisons and no arithmetic at all	1.5
Circle against circle	Two squares and a comparison, with no square root	1.5
Circle against box	Clamp the centre, then one squared distance	2.6
SAT, two rotated boxes	Four axes, eight vertex projections each	91

Ten thousand box tests cost about fifteen microseconds, a thousandth of a 16.6 ms frame. Ten thousand SAT tests cost nine tenths of a millisecond, five percent of that same frame. The gap between them is why the box test is the default.

Four comparisons will do for anything that stays on its axis

Two axis-aligned boxes overlap when neither is entirely left, right, above or below the other. Written out, that is four comparisons between stored edge coordinates and no multiplication anywhere, which is why it measures about the same as an empty loop with a branch in it.

What matters more than the price is that the answer is exactly right. For two rectangles there is no approximation to argue about: if the boxes overlap, the shapes overlap, and no player can find a case where the test and the picture disagree. Bricks, paddles, platforms and tetromino cells are all rectangles, which is most of what a 2D game draws.

The catch is in the name. Rotate one rectangle by twenty degrees and the test still runs, still returns a boolean, and now answers a question about the rotated shape's bounding box. A long thin shape turned diagonally reports hits against things it is nowhere near. Any game with a spinning object either re-fits a box every frame, or moves up to SAT.

A circle is a squared distance, and it lies about corners

Circle against circle is the cheapest test with any arithmetic in it: subtract the centres, square both differences, add them, and compare against the squared sum of the radii. The square root is the part everyone adds by mistake, and it costs more than the rest of the test together while changing nothing, because comparing squared distances orders them the same way. Vector Storm runs this test for every bullet against every enemy and never calls a square root to do it.

For round things the test is exact, and bullets, bombs, coins and explosions are circles by design.

For everything else the circle is a claim the player can check by eye. The runner in Neon Dash is thirty pixels wide and forty-six tall, so a circle drawn around it needs a radius of about 27.5 pixels, the half diagonal, from the square root of fifteen squared plus twenty-three squared. That circle reaches 12.5 pixels out to each side of a body fifteen pixels wide, and every obstacle in that ghost margin kills a player who can see they were clear.

Clamping the centre is the whole circle-against-box test

Circle against box needs one idea: find the point on the box closest to the circle's centre, and measure from there. Clamping each coordinate of the centre into the box's range finds that point, in two comparisons per axis.

With the centre outside the box the clamp lands on the nearest edge or corner and the distance is honest. With the centre inside, the clamp returns the centre itself, so the distance comes out as zero and the test reports a hit, which is the right answer for a boolean; only a direction needs the inside case handled separately, because a normal of zero length points nowhere.

It measured 2.6 nanoseconds against 1.5 for the box test it replaces. Reach for it when exactly one of the two things colliding is round.

SAT tests the edge normals, and a box only has two

The separating axis theorem says two convex shapes are not touching when some line exists onto which their shadows do not overlap. The axes worth checking are the edge normals, because if any axis can separate them, one of those can. A rectangle's four edges are two pairs of parallel lines, so its axes collapse to two and two boxes mean four axes in total.

Each axis projects every corner of both shapes onto it, keeps the minimum and maximum, and asks whether the two ranges overlap. One gap ends the test early. If every axis overlaps the shapes touch, and the axis with the smallest overlap gives the direction and depth to push them apart — the minimum translation vector, which a physics response needs and the box test cannot supply.

Convexity is not optional: the theorem fails if either shape is concave, and a concave shape has to be cut into convex pieces and tested piece by piece. Curves are worse again, having infinitely many candidate normals, which is why circles stay out of the polygon path. That leaves SAT doing what it is good at: two rotating convex polygons, at 91 nanoseconds the pair.

A wrong hitbox and a tunnelled collision look identical

Two separate bugs produce the same complaint. One is a hitbox that does not match the picture. The other is a fast object that crosses a wall between two frames without ever overlapping it, so no test fires however correct the box is.

Brick Buster answers the second with sub-steps. The ball moves at most six pixels per resolution step, with a cap of twenty-four steps a frame, and each step is resolved before the next begins. A brick is twenty-six pixels tall and about seventy-five wide, so a six pixel step is nowhere near long enough to cross one unnoticed. Swept tests solve for the exact time of impact along the path and cost more code than frame time; both approaches turn a limit on speed into a limit on distance per step.

The box you inset by four pixels is the one players believe

Once the test is chosen the shape still has to be decided, and the honest shape is almost never the sprite. Neon Dash pulls the runner's hitbox in four pixels on every side, so a body drawn thirty pixels wide and forty-six tall is tested as twenty-two by thirty-eight.

Nobody reads a character as the outer pixel of an outstretched arm; they read the mass in the middle. Limbs move with the animation while the hitbox does not, so a box matching the drawing on one frame is wrong on the next four. The inset is a lie told in the player's favour, and its only cost is a little space where an overlap is visible but not fatal.

The size of the lie matters as much as the direction. Take eight pixels off each side of a thirty pixel runner and fourteen are left, at which point bullets pass through the middle of the character. Four pixels is about the largest inset that survives the second complaint.

Pros and cons

Sources

• dyn4j: The Separating Axis Theorem — the statement of the theorem, the rule that the axes to test are the edge normals, the note that a rectangle reduces to two axes, and the minimum translation vector built from the smallest overlap.
• Hyperplane separation theorem — the formal version for two closed convex objects, and the warning that the theorem does not apply when either shape is concave.
• Real-Time Collision Detection — the companion site for Christer Ericson's 2005 book that these primitive tests are sourced back to, which also lists his talk on the separating axis test.