Collision Detection

in reviewThis lesson is complete and being validated before release - details may still change.

Collision Detection

Loading interactive demo…

Discs and axis-aligned boxes scattered on a field, and the detector a physics engine runs over them: every pair is judged first by the boxes around the two shapes (the broad phase, four comparisons that throw most pairs out) and, only when those overlap, by the test its shapes deserve (the narrow phase). A hit carries the contact normal and the depth a response would push along. Touching does not count.Take the tour, or press and explore. Legend:

The panel beside the stage is the real CollisionDetector class from the published library executing in your browser, with the current line highlighted.

The first body of the pair under test.
The second body of the pair under test, and the line between their centres with the narrow phase's gap.
A body in a hit found so far, and the hit's normal and depth.
A body not yet in any hit.
The box around each body, dashed, when the bounds chips show them.

pairs counts the pairs judged so far, rejected those the boxes threw out, narrowed those that reached the shape test, and hits the overlapping pairs found.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

Every pair, twice. With $n$ bodies there are $\binom{n}{2} = \frac{n(n-1)}{2}$ pairs, and the detector judges each one in two phases. The broad phase compares the axis-aligned boxes around the two shapes: boxes $A$ and $B$ overlap only when $A_{\text{left}} < B_{\text{right}}$ , $B_{\text{left}} < A_{\text{right}}$ , $A_{\text{bottom}} < B_{\text{top}}$ , and $B_{\text{bottom}} < A_{\text{top}}$ all hold. Four comparisons, no square root, the same test whatever the shapes inside. If any fails the boxes are apart on that axis, nothing inside them can touch, and the pair is out. Only a pair whose boxes overlap reaches the narrow phase, the test its two shapes need.

The narrow tests. Two discs with centres $c_1, c_2$ and radii $r_1, r_2$ have gap $|c_2 - c_1| - (r_1 + r_2)$ . Two boxes have a gap on each axis, $g_x = \max(A_{\text{left}} - B_{\text{right}},\ B_{\text{left}} - A_{\text{right}})$ and $g_y$ likewise, and their gap is the larger of the two: the boxes overlap only when both are negative, and then the shallower overlap is the way out. A disc and a box clamp the disc's centre to the box, $p = \operatorname{clamp}(c, \text{box})$ , and the gap is $|p - c| - r$ ; a centre inside the box leaves by its nearest face. In every case a gap below zero is a hit, and touching, a gap of exactly zero, is not.

What a hit carries. The depth is $-\text{gap}$ , and the normal is the unit direction from the first body to the second along which they are closest, or overlap least. A response that moves the second body by the depth along the normal, or splits the move between the two, leaves them just separated; the next lesson's forces act along that same direction. The normal is what makes the answer useful: a yes without a direction cannot be acted on.

Why the broad phase pays. The box test is cheaper than any shape test and throws out most pairs, because most bodies are far from each other. On the stage's defaults it rejects about four pairs in five. But it is only a filter: a disc's bounding square has corners the disc does not, so two squares can overlap while the discs stay clear, and the narrow phase is what notices. Two boxes are the degenerate case, a box being its own bounding box, so with boxes alone the broad phase is the whole answer and the narrow phase only measures the depth.

The cost that remains. Every pair is still formed, so the work is $O(n^2)$ however cheap each test. Ten bodies make 45 pairs, sixteen make 120, a thousand make half a million. The way out is never to form the far pairs at all: bin the bodies into cells so a body is only paired with the bodies of the cells around it. That is the spatial hash, and the quadtree after it.

Tunnelling. All of this judges where the bodies are at one tick. A body moving further than its own size in a tick can pass clean through a thin wall between two checks. Engines that care sweep the shape along its motion, which is a continuous test, or cap how far a body may move per tick.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

The boxes are computed once, before the pair loop, since every body's box is compared against every other's; bounds is a static so the stage draws the same box the code compares.
overlaps is strict, inherited from the navigation lessons' Rectangle: boxes that share an edge do not overlap, and the narrow tests agree by treating a gap of exactly zero as clear.
reject reports which axis the boxes are apart on and by how much, found by apart only for the narration; the test itself needed only the four comparisons.
contact is one static for every pair of kinds, choosing among discs, boxes, and discAndBox, and flipping the normal when the box comes first so the normal always runs from the first body to the second.
A centre inside a box has no nearest point to measure from, so discAndBox takes the nearest face as the way out and the depth is the radius plus the distance to that face.
Only the traced path is in detect; the three narrow tests are untraced statics the stage also calls, so the picture and the code agree about every gap.

The first video games had to answer the question: Spacewar! in 1962 checked whether a torpedo had reached a ship, and Pong a decade later decided ball against paddle in logic chips alone. Those were one pair at a time. The problem grew teeth when scenes held hundreds of bodies and every frame had to ask which of the thousands of pairs touched. Physics engines split the job in two: a cheap broad phase that throws out the pairs whose bounding boxes are apart, and a narrow phase that runs the exact test on what is left and hands its contact normal and depth to the response.

1962Steve Russell and the Tech Model Railroad Club - Spacewar! runs on the PDP-1 at MIT: two ships, a star, and torpedoes that have to know when they have hit something.source
1972Allan Alcorn, Atari - Pong decides ball against paddle in discrete logic chips, with no microprocessor, the collision test built from counters and comparators.source
1988Elmer Gilbert, Daniel Johnson, and S. Sathiya Keerthi - Publish the GJK algorithm, which computes the distance between two convex shapes from their support points, the narrow phase most 3D engines run today.source
1995Jonathan Cohen, Ming Lin, Dinesh Manocha, and Madhav Ponamgi - I-COLLIDE brings sweep and prune to large environments: sort the bounding boxes' ends along each axis and only pairs whose intervals overlap on every axis go on to the exact test.source
2007Erin Catto - Releases Box2D, an open-source 2D physics engine whose broad phase, narrow phase, and contact solver became the model for a generation of game engines.source

Used today

Physics engines - Box2D, Bullet, PhysX, and Havok all run a broad phase over bounding volumes and a narrow phase per shape pair, then solve the contacts the narrow phase reports.
Games - Bullets against walls, feet against floors, pickups against players: every game loop asks which bodies overlap this frame.
Robotics - A motion planner tests a candidate pose of the robot against the obstacles with the same shape tests before it commits to a path.
User interfaces - Hit testing a pointer against windows, buttons, and canvas objects is the point-against-box case of the same question.

bodies10

shapes

bounds

pairs: 45
rejected: 36
narrowed: 9
hits: 8

collision-detector.ts

import { Rectangle } from "../navigation/geometry";import type { Tracer } from "../trace";/** A disc: its centre and radius. */export interface CollisionCircle {  kind: "circle";  x: number;  y: number;  r: number;}/** An axis-aligned box: its lower-left corner and its size. */export interface CollisionBox {  kind: "box";  x: number;  y: number;  w: number;  h: number;}export type CollisionBody = CollisionCircle | CollisionBox;/** Which narrow test a pair of bodies takes. */export type CollisionTest = "circle-circle" | "box-box" | "circle-box";/** * The narrow phase's answer for a pair: the signed gap between the two * shapes (negative is how deep they overlap) and the unit direction * from the first body to the second along which they are closest, or * overlap least. */export interface CollisionContact {  gap: number;  nx: number;  ny: number;}/** An overlapping pair, with the normal and depth a response would push along. */export interface CollisionHit {  a: number;  b: number;  depth: number;  nx: number;  ny: number;}/** The axis the bounding boxes are apart on when they are. */export type CollisionAxis = "x" | "y";/** * Collision detection between discs and axis-aligned boxes in a plane, * the way a physics engine does it: every pair is first judged by the * boxes around the two shapes (the broad phase, one cheap test that * throws most pairs out), and only a pair whose boxes overlap takes * the test its shapes deserve (the narrow phase): centre distance * against the radii for two discs, face gaps for two boxes, the * nearest point of the box against the radius for a disc and a box. * Touching does not count: a gap of exactly zero is clear, as the * rectangle's `overlaps` already says. A hit carries the contact * normal and the depth, which is what a response needs to push the * bodies apart. * * Time: O(n^2) pairs, each O(1). The spatial hashing lesson is what * brings the pair count down. */export class CollisionDetector {  constructor(private readonly tracer?: Tracer) {}  /** How many pairs n bodies make. */  static pairsOf(n: number): number {    return Math.max(0, (n * (n - 1)) / 2);  }  /** The box around a body: the body itself for a box, the square around a disc. */  static bounds(body: CollisionBody): Rectangle {    if (body.kind === "circle") {      if (!(body.r > 0)) throw new RangeError(`a circle needs a positive radius, got ${body.r}`);      return new Rectangle(body.x - body.r, body.y - body.r, 2 * body.r, 2 * body.r);    }    return new Rectangle(body.x, body.y, body.w, body.h);  }  /** Which narrow test two bodies take. */  static testOf(a: CollisionBody, b: CollisionBody): CollisionTest {    if (a.kind === "circle" && b.kind === "circle") return "circle-circle";    if (a.kind === "box" && b.kind === "box") return "box-box";    return "circle-box";  }  /** The narrow phase for one pair, untraced: the signed gap and the direction from a to b. */  static contact(a: CollisionBody, b: CollisionBody): CollisionContact {    if (a.kind === "circle" && b.kind === "circle") return CollisionDetector.discs(a, b);    if (a.kind === "box" && b.kind === "box") return CollisionDetector.boxes(CollisionDetector.bounds(a), CollisionDetector.bounds(b));    if (a.kind === "circle" && b.kind === "box") return CollisionDetector.discAndBox(a, CollisionDetector.bounds(b));    const c = CollisionDetector.discAndBox(b as CollisionCircle, CollisionDetector.bounds(a));    return { gap: c.gap, nx: 0 - c.nx, ny: 0 - c.ny };  }  /** Every overlapping pair among the bodies, in pair order. */  detect(bodies: readonly CollisionBody[]): CollisionHit[] {    const boxes = bodies.map((body) => CollisionDetector.bounds(body));    const hits: CollisionHit[] = [];    for (let a = 0; a < bodies.length; a++) {      for (let b = a + 1; b < bodies.length; b++) {        const ba = boxes[a]!;        const boundsOfA = boxes[a]!;        const bb = boxes[b]!;        const boundsOfB = boxes[b]!;        // ▸ take the next pair of bodies        this.tracer?.emit("pair", { a, b, test: CollisionDetector.testOf(bodies[a]!, bodies[b]!) });        const overlap = ba.overlaps(bb);        const overlap = boundsOfA.overlaps(boundsOfB);        // ▸ do the boxes around them overlap?        this.tracer?.emit("bounds", { a, b, overlap });        if (!overlap) {          const apart = CollisionDetector.apart(ba, bb);          const apart = CollisionDetector.apart(boundsOfA, boundsOfB);          // ▸ the boxes are apart: the pair is out, no shape test needed          this.tracer?.emit("reject", { a, b, axis: apart.axis, gap: apart.gap });          continue;        }        const contact = CollisionDetector.contact(bodies[a]!, bodies[b]!);        // ▸ the shapes' own test: the signed gap between them        this.tracer?.emit("narrow", { a, b, gap: contact.gap, overlap: contact.gap < 0 });        if (contact.gap < 0) {          const hit = { a, b, depth: -contact.gap, nx: contact.nx, ny: contact.ny };          // ▸ they overlap: record the pair with its normal and depth          this.tracer?.emit("hit", { ...hit });          hits.push(hit);        }      }    }    return hits;  }  /** The axis two boxes that do not overlap are apart on, and by how much: the wider gap when both axes have one. */  private static apart(a: Rectangle, b: Rectangle): { axis: CollisionAxis; gap: number } {    const gx = Math.max(a.x - b.right, b.x - a.right);    const gapAlongX = Math.max(a.x - b.right, b.x - a.right);    const gy = Math.max(a.y - b.top, b.y - a.top);    const gapAlongY = Math.max(a.y - b.top, b.y - a.top);    return gx >= gy ? { axis: "x", gap: gx } : { axis: "y", gap: gy };    return gapAlongX >= gapAlongY ? { axis: "x", gap: gapAlongX } : { axis: "y", gap: gapAlongY };  }  /** Two discs: the centre distance against the radii. */  private static discs(a: CollisionCircle, b: CollisionCircle): CollisionContact {    const dx = b.x - a.x;    const dy = b.y - a.y;    const d = Math.hypot(dx, dy);    const centreDistance = Math.hypot(dx, dy);    const n = d > 0 ? { nx: dx / d, ny: dy / d } : { nx: 1, ny: 0 };    const n = centreDistance > 0 ? { nx: dx / centreDistance, ny: dy / centreDistance } : { nx: 1, ny: 0 };    return { gap: d - (a.r + b.r), ...n };    return { gap: centreDistance - (a.r + b.r), ...n };  }  /** Two boxes: the gap on each axis; the larger is the gap, and the overlap, when both are negative, is least along it. */  private static boxes(a: Rectangle, b: Rectangle): CollisionContact {    const gx = Math.max(a.x - b.right, b.x - a.right);    const gapAlongX = Math.max(a.x - b.right, b.x - a.right);    const gy = Math.max(a.y - b.top, b.y - a.top);    const gapAlongY = Math.max(a.y - b.top, b.y - a.top);    const ca = a.centroid;    const cb = b.centroid;    if (gx >= gy) return { gap: gx, nx: cb.x >= ca.x ? 1 : -1, ny: 0 };    if (gapAlongX >= gapAlongY) return { gap: gapAlongX, nx: cb.x >= ca.x ? 1 : -1, ny: 0 };    return { gap: gy, nx: 0, ny: cb.y >= ca.y ? 1 : -1 };    return { gap: gapAlongY, nx: 0, ny: cb.y >= ca.y ? 1 : -1 };  }  /** A disc and a box: the box's nearest point to the centre against the radius; a centre inside the box leaves by its nearest face. */  private static discAndBox(c: CollisionCircle, box: Rectangle): CollisionContact {    const p = box.clamp(c);    const nearestPoint = box.clamp(c);    const dx = p.x - c.x;    const dx = nearestPoint.x - c.x;    const dy = p.y - c.y;    const dy = nearestPoint.y - c.y;    const d = Math.hypot(dx, dy);    const centreDistance = Math.hypot(dx, dy);    if (d > 0) return { gap: d - c.r, nx: dx / d, ny: dy / d };    if (centreDistance > 0) return { gap: centreDistance - c.r, nx: dx / centreDistance, ny: dy / centreDistance };    // The centre is inside: the nearest face is the way out, the depth is the radius plus the way to it,    // and the normal still runs from the disc toward the box, so it points away from that face.    const faces = [      { gap: -(c.x - box.x) - c.r, nx: 1, ny: 0 },      { gap: -(box.right - c.x) - c.r, nx: -1, ny: 0 },      { gap: -(c.y - box.y) - c.r, nx: 0, ny: 1 },      { gap: -(box.top - c.y) - c.r, nx: 0, ny: -1 },    ];    return faces.reduce((best, face) => (face.gap > best.gap ? face : best));  }}

pairs =: 45
rejected =: 36
narrowed =: 9
hits =: 8

45 pairs judged: 36 thrown out by their boxes, 9 given the shape test, 8 hits.

import { Rectangle } from "../navigation/geometry";import type { Tracer } from "../trace";/** A disc: its centre and radius. */export interface CollisionCircle { kind: "circle"; x: number; y: number; r: number;}/** An axis-aligned box: its lower-left corner and its size. */export interface CollisionBox { kind: "box"; x: number; y: number; w: number; h: number;}export type CollisionBody = CollisionCircle | CollisionBox;/** Which narrow test a pair of bodies takes. */export type CollisionTest = "circle-circle" | "box-box" | "circle-box";/** * The narrow phase's answer for a pair: the signed gap between the two * shapes (negative is how deep they overlap) and the unit direction * from the first body to the second along which they are closest, or * overlap least. */export interface CollisionContact { gap: number; nx: number; ny: number;}/** An overlapping pair, with the normal and depth a response would push along. */export interface CollisionHit { a: number; b: number; depth: number; nx: number; ny: number;}/** The axis the bounding boxes are apart on when they are. */export type CollisionAxis = "x" | "y";/** * Collision detection between discs and axis-aligned boxes in a plane, * the way a physics engine does it: every pair is first judged by the * boxes around the two shapes (the broad phase, one cheap test that * throws most pairs out), and only a pair whose boxes overlap takes * the test its shapes deserve (the narrow phase): centre distance * against the radii for two discs, face gaps for two boxes, the * nearest point of the box against the radius for a disc and a box. * Touching does not count: a gap of exactly zero is clear, as the * rectangle's `overlaps` already says. A hit carries the contact * normal and the depth, which is what a response needs to push the * bodies apart. * * Time: O(n^2) pairs, each O(1). The spatial hashing lesson is what * brings the pair count down. */export class CollisionDetector { constructor(private readonly tracer?: Tracer) {} /** How many pairs n bodies make. */ static pairsOf(n: number): number { return Math.max(0, (n * (n - 1)) / 2); } /** The box around a body: the body itself for a box, the square around a disc. */ static bounds(body: CollisionBody): Rectangle { if (body.kind === "circle") { if (!(body.r > 0)) throw new RangeError(`a circle needs a positive radius, got ${body.r}`); return new Rectangle(body.x - body.r, body.y - body.r, 2 * body.r, 2 * body.r); } return new Rectangle(body.x, body.y, body.w, body.h); } /** Which narrow test two bodies take. */ static testOf(a: CollisionBody, b: CollisionBody): CollisionTest { if (a.kind === "circle" && b.kind === "circle") return "circle-circle"; if (a.kind === "box" && b.kind === "box") return "box-box"; return "circle-box"; } /** The narrow phase for one pair, untraced: the signed gap and the direction from a to b. */ static contact(a: CollisionBody, b: CollisionBody): CollisionContact { if (a.kind === "circle" && b.kind === "circle") return CollisionDetector.discs(a, b); if (a.kind === "box" && b.kind === "box") return CollisionDetector.boxes(CollisionDetector.bounds(a), CollisionDetector.bounds(b)); if (a.kind === "circle" && b.kind === "box") return CollisionDetector.discAndBox(a, CollisionDetector.bounds(b)); const c = CollisionDetector.discAndBox(b as CollisionCircle, CollisionDetector.bounds(a)); return { gap: c.gap, nx: 0 - c.nx, ny: 0 - c.ny }; } /** Every overlapping pair among the bodies, in pair order. */ detect(bodies: readonly CollisionBody[]): CollisionHit[] { const boxes = bodies.map((body) => CollisionDetector.bounds(body)); const hits: CollisionHit[] = []; for (let a = 0; a < bodies.length; a++) { for (let b = a + 1; b < bodies.length; b++) { const ba = boxes[a]!; const boundsOfA = boxes[a]!; const bb = boxes[b]!; const boundsOfB = boxes[b]!; // ▸ take the next pair of bodies this.tracer?.emit("pair", { a, b, test: CollisionDetector.testOf(bodies[a]!, bodies[b]!) }); const overlap = ba.overlaps(bb); const overlap = boundsOfA.overlaps(boundsOfB); // ▸ do the boxes around them overlap? this.tracer?.emit("bounds", { a, b, overlap }); if (!overlap) { const apart = CollisionDetector.apart(ba, bb); const apart = CollisionDetector.apart(boundsOfA, boundsOfB); // ▸ the boxes are apart: the pair is out, no shape test needed this.tracer?.emit("reject", { a, b, axis: apart.axis, gap: apart.gap }); continue; } const contact = CollisionDetector.contact(bodies[a]!, bodies[b]!); // ▸ the shapes' own test: the signed gap between them this.tracer?.emit("narrow", { a, b, gap: contact.gap, overlap: contact.gap < 0 }); if (contact.gap < 0) { const hit = { a, b, depth: -contact.gap, nx: contact.nx, ny: contact.ny }; // ▸ they overlap: record the pair with its normal and depth this.tracer?.emit("hit", { ...hit }); hits.push(hit); } } } return hits; } /** The axis two boxes that do not overlap are apart on, and by how much: the wider gap when both axes have one. */ private static apart(a: Rectangle, b: Rectangle): { axis: CollisionAxis; gap: number } { const gx = Math.max(a.x - b.right, b.x - a.right); const gapAlongX = Math.max(a.x - b.right, b.x - a.right); const gy = Math.max(a.y - b.top, b.y - a.top); const gapAlongY = Math.max(a.y - b.top, b.y - a.top); return gx >= gy ? { axis: "x", gap: gx } : { axis: "y", gap: gy }; return gapAlongX >= gapAlongY ? { axis: "x", gap: gapAlongX } : { axis: "y", gap: gapAlongY }; } /** Two discs: the centre distance against the radii. */ private static discs(a: CollisionCircle, b: CollisionCircle): CollisionContact { const dx = b.x - a.x; const dy = b.y - a.y; const d = Math.hypot(dx, dy); const centreDistance = Math.hypot(dx, dy); const n = d > 0 ? { nx: dx / d, ny: dy / d } : { nx: 1, ny: 0 }; const n = centreDistance > 0 ? { nx: dx / centreDistance, ny: dy / centreDistance } : { nx: 1, ny: 0 }; return { gap: d - (a.r + b.r), ...n }; return { gap: centreDistance - (a.r + b.r), ...n }; } /** Two boxes: the gap on each axis; the larger is the gap, and the overlap, when both are negative, is least along it. */ private static boxes(a: Rectangle, b: Rectangle): CollisionContact { const gx = Math.max(a.x - b.right, b.x - a.right); const gapAlongX = Math.max(a.x - b.right, b.x - a.right); const gy = Math.max(a.y - b.top, b.y - a.top); const gapAlongY = Math.max(a.y - b.top, b.y - a.top); const ca = a.centroid; const cb = b.centroid; if (gx >= gy) return { gap: gx, nx: cb.x >= ca.x ? 1 : -1, ny: 0 }; if (gapAlongX >= gapAlongY) return { gap: gapAlongX, nx: cb.x >= ca.x ? 1 : -1, ny: 0 }; return { gap: gy, nx: 0, ny: cb.y >= ca.y ? 1 : -1 }; return { gap: gapAlongY, nx: 0, ny: cb.y >= ca.y ? 1 : -1 }; } /** A disc and a box: the box's nearest point to the centre against the radius; a centre inside the box leaves by its nearest face. */ private static discAndBox(c: CollisionCircle, box: Rectangle): CollisionContact { const p = box.clamp(c); const nearestPoint = box.clamp(c); const dx = p.x - c.x; const dx = nearestPoint.x - c.x; const dy = p.y - c.y; const dy = nearestPoint.y - c.y; const d = Math.hypot(dx, dy); const centreDistance = Math.hypot(dx, dy); if (d > 0) return { gap: d - c.r, nx: dx / d, ny: dy / d }; if (centreDistance > 0) return { gap: centreDistance - c.r, nx: dx / centreDistance, ny: dy / centreDistance }; // The centre is inside: the nearest face is the way out, the depth is the radius plus the way to it, // and the normal still runs from the disc toward the box, so it points away from that face. const faces = [ { gap: -(c.x - box.x) - c.r, nx: 1, ny: 0 }, { gap: -(box.right - c.x) - c.r, nx: -1, ny: 0 }, { gap: -(c.y - box.y) - c.r, nx: 0, ny: 1 }, { gap: -(box.top - c.y) - c.r, nx: 0, ny: -1 }, ]; return faces.reduce((best, face) => (face.gap > best.gap ? face : best)); }}