Collision Detection Math for Games

Broad Phase vs Narrow Phase

Collision detection splits into two phases for performance. The broad phase quickly eliminates pairs of objects that cannot possibly be colliding, reducing the candidate list from potentially thousands of pairs to a handful. The narrow phase performs exact geometric tests on the remaining candidates. Without a broad phase, checking every object against every other object requires N*(N-1)/2 tests, which becomes unacceptably expensive past a few dozen objects.

Spatial hashing divides the game world into a grid of cells. Each object is registered in the cell(s) it occupies. Collision tests only run between objects sharing the same cell. For uniformly distributed objects of similar size, spatial hashing reduces collision checks from O(N^2) to nearly O(N). The cell size should be roughly twice the diameter of the largest common object. Too-small cells cause objects to span many cells; too-large cells reduce the filtering benefit.

Quadtrees (2D) and octrees (3D) recursively subdivide space into four or eight child regions. Objects are stored in the smallest node that fully contains them. Collision candidates are objects sharing any node in the hierarchy. Quadtrees adapt better than fixed grids to uneven object distributions because dense areas subdivide more deeply. The overhead of maintaining the tree (inserting, removing, and rebalancing as objects move) is acceptable for most web games with up to several thousand moving objects.

AABB trees (also called bounding volume hierarchies) organize objects by their axis-aligned bounding boxes in a binary tree. Each internal node's AABB encloses both children's AABBs. Testing a query AABB against the tree prunes entire branches when the query does not overlap a node's AABB. Physics engines like Box2D and Rapier use AABB trees for broad phase because they handle dynamic scenes efficiently with incremental updates as objects move.

AABB (Axis-Aligned Bounding Box)

An AABB is a rectangle (2D) or box (3D) whose edges are parallel to the coordinate axes. Two AABBs overlap if and only if they overlap on every axis independently. In 2D, this requires four comparisons: A's left edge is left of B's right edge, A's right edge is right of B's left edge, A's top is above B's bottom, and A's bottom is below B's top. If all four conditions are true, the boxes overlap. If any one is false, they do not.

Representing an AABB as (minX, minY, maxX, maxY), the overlap test is: A.minX < B.maxX && A.maxX > B.minX && A.minY < B.maxY && A.maxY > B.minY. This test is extremely fast: four comparisons with no multiplication, division, or function calls. For 3D, add two more comparisons for the z-axis. AABB tests are the standard broad-phase filter and the default collision shape for rectangular game objects like platforms, walls, tiles, and UI elements.

The limitation of AABBs is that they do not rotate. A rotated rectangle still has an axis-aligned bounding box, but the AABB is larger than the actual shape, causing false positives (reporting collisions that are not actually occurring). For rotating objects, you can either use oriented bounding boxes (OBBs) with the separating axis theorem, use circular/spherical bounds instead, or accept the AABB false positives and perform a more precise narrow-phase test only on the candidates that pass the AABB check.

Circle and Sphere Collision

Two circles collide when the distance between their centers is less than the sum of their radii. The distance formula is the square root of (dx^2 + dy^2), where dx and dy are the differences in center coordinates. Because square roots are expensive, the standard optimization compares squared values: dx*dx + dy*dy < (r1+r2)*(r1+r2). This eliminates the square root entirely while producing identical results.

Circle-to-circle collision is perfect for objects that are roughly round: characters, projectiles, coins, bombs, asteroids, and particles. It handles rotation naturally (a circle looks the same from every angle) and provides simple collision response: the collision normal is the normalized vector from one center to the other, and the penetration depth is the sum of radii minus the actual distance.

Point-in-circle tests whether a point is inside a circle: dx*dx + dy*dy < radius*radius. This is used for mouse click detection on circular UI elements, range checks (is the player within this ability's radius?), and proximity triggers.

Circle-to-AABB finds the closest point on the AABB to the circle's center by clamping the center coordinates to the AABB's min/max range, then checks if that closest point is within the circle's radius. This test is common in platformers where the player (circular) collides with platforms (rectangular).

Separating Axis Theorem (SAT)

The separating axis theorem states that two convex shapes do not overlap if and only if there exists a line (axis) where their projections onto that line do not overlap. If no such separating axis exists, the shapes are colliding. For convex polygons, you only need to test axes perpendicular to each edge of both polygons. For two rectangles, that is four axes (two per rectangle, though parallel edges share axes, reducing to two unique axes for AABBs).

The algorithm projects all vertices of both polygons onto each candidate axis by computing the dot product of each vertex position with the axis direction. The projection gives a 1D interval (min and max values) for each polygon on that axis. If the intervals overlap on every axis tested, the polygons collide. If any axis shows a gap between the intervals, the polygons are separated and the test terminates early.

SAT also provides collision resolution data. The axis with the smallest overlap between projections is the minimum translation vector (MTV) direction, and the overlap amount is the penetration depth. Moving one polygon by the MTV along that axis by the penetration depth separates the two shapes with the minimum possible displacement. This makes SAT both a detection and a resolution tool.

SAT works only for convex shapes. Concave shapes must be decomposed into convex sub-shapes (convex decomposition) before testing. Most 2D physics engines (Matter.js, Planck.js) handle this decomposition automatically when you provide concave polygon vertices. For simple game objects, using circles or convex hulls avoids the complexity of concave decomposition entirely.

Raycasting

A ray starts at an origin point and extends infinitely in a direction. Raycasting determines what the ray hits first and where the intersection occurs. The ray is parametrized as point = origin + t * direction, where t is a scalar. At t=0, the point is at the origin. As t increases, the point moves along the direction. The first object hit corresponds to the smallest positive t value among all intersections.

Ray-AABB intersection: Calculate the t values where the ray enters and exits the box on each axis. The ray intersects the box if the entry on the last axis entered is before the exit on the first axis exited. This slab-based method requires only a few divisions and comparisons per axis, making it fast enough for hundreds of tests per frame.

Ray-circle intersection: Substitute the ray equation into the circle equation and solve the resulting quadratic. The discriminant tells you whether the ray misses (negative), grazes (zero), or passes through (positive) the circle. The smaller positive root gives the first hit point.

Ray-line segment intersection: Solve for the intersection of the ray with the infinite line containing the segment, then check if the intersection parameter falls within the segment bounds (0 to 1). This test is fundamental for raycasting against polygon edges, walls, and terrain boundaries.

Games use raycasting for line-of-sight checks (can the enemy see the player?), hitscan weapons (instant bullet travel), ground detection (is the character standing on a surface?), mouse picking (what did the player click on?), and sensor beams (laser tripwires, alarm systems). Raycasting against a spatial data structure (quadtree or AABB tree) allows efficient testing against large numbers of objects without checking every one individually.

Collision Response

Detection tells you that two objects are overlapping. Response decides what happens next: do they bounce, stop, slide, or trigger an event? The simplest response is separation: move each object half the penetration depth along the collision normal in opposite directions. This prevents objects from passing through each other but does not simulate bouncing or friction.

Elastic collision (bouncing) reflects the relative velocity across the collision normal. For a ball bouncing off a wall, the reflected velocity is v - 2 * dot(v, n) * n, where n is the normalized collision normal. For two moving objects, the impulse calculation considers both masses and relative velocities. A restitution coefficient between 0 (perfectly inelastic, no bounce) and 1 (perfectly elastic, full bounce) controls how much energy is preserved.

Slide response removes the velocity component along the collision normal while preserving the component along the surface. This is how characters slide along walls instead of sticking to them. The sliding velocity is v - dot(v, n) * n, which projects the velocity onto the plane perpendicular to the normal.