DEV Community

mustafa morbel
mustafa morbel

Posted on Originally published at Medium

Shaking Hands with Everyone: Broad-Phase Collision and Spatial Hashing from 200 to 20,000 Bodies

Originally published on Medium. Read on Medium for free via Friend Link.

🎮 Try the Live Interactive Demo · 📦 GitHub Repo & Vitest Suite · ⚡ Get the TS 2D Canvas Physics Starter Kit

Illustration of a broad-phase bouncer at a neon narrow-phase nightclub entrance, letting 14,323 candidate pairs inside while turning away rejected circle pairs.

Broad-phase acts as a bouncer in front of narrow-phase: out of 199.99M pairs at 20,000 bodies, only 14,323 candidates make it inside.

Quick takeaways

  • Checking every pair produces n(n - 1) / 2 tests: 199,990,000 checks at 20,000 bodies, dropping the browser demo to 1 FPS at 2,500 bodies.
  • A cheap spatial hash grid filters impossible pairs first, leaving collideBodies (narrow-phase) completely untouched.
  • On 20,000 uniformly distributed bodies, candidate pairs drop from 199,990,000 to 14,323 (nearly 14,000× fewer checks), lifting 2,500-body FPS from 1 to 46.
  • A deterministic Vitest parity suite verifies zero missed collisions against brute-force O(n²) overlap checks, alongside a benchmark against a QuadTree.

The physics engine was done, the game ran smoothly, and I was happily pulling back the slingshot to smash blocks. Then curiosity hit: “What if this scene had two hundred bodies instead of twenty?”

I dumped two hundred balls onto the canvas. The frame rate noticeably dipped.

I added a thousand. The page froze, the cooling fan kicked in, and my laptop started humming like a jet preparing for takeoff. Rendering was relaxed because drawing a thousand circles is trivial for a browser; the bottleneck was that nested loop running every frame.

When we previously built a 2D physics engine from scratch in Canvas, we solved collisions the brute-force way: comparing every body against every other body. Back then, I admitted it didn’t scale and punted broad-phase optimization to Matter.js. Today, we pay off that debt by building our own broad-phase from scratch and scaling the engine from 200 bodies to 20,000 without touching Matter.js.

Think of it like a wedding reception. Right now, our engine insists that every guest walk across the hall and shake hands with every other guest one by one. Charming at a table of twenty; a disaster in a hall of two thousand. Instead of letting guests roam the whole hall, we seat them at tables and have everyone shake hands only with their tablemates.

The O(n²) wall

Measuring the loop puts a number on why it slows down. Our engine’s step() function ended with these three lines:

// BEFORE — legacy version of the physics engine; NOT in this repo, replaced by broad-phase
// 3. Body-body collisions (every pair once)
for (let i = 0; i < this.bodies.length; i++) {
  for (let j = i + 1; j < this.bodies.length; j++) {
    this.collideBodies(this.bodies[i], this.bodies[j]);
  }
}
Enter fullscreen mode Exit fullscreen mode

It looks harmless. Yet for n bodies, this nested loop generates n × (n - 1) / 2 pairs. That is our handshake count: everyone in the room shakes everyone else's hand once.

The math is merciless. At 200 bodies, that is 19,900 checks, which is manageable. At 2,000 bodies, 1,999,000 checks. At 20,000 bodies, 199,990,000 checks. Multiplying the object count by 100 multiplies the workload by 10,000×. Broad-phase exists to avoid that quadratic growth.

Vintage train-station split-flap board displaying O(n²) pair counts using n(n-1)/2: 200 to 19,900, 2,000 to 1,999,000, and 20,000 to 199,990,000 handshakes.

Quadratic pair growth under n(n - 1) / 2: scaling 10× in bodies multiplies naive collision checks by 100×.

We don’t need a heavy profiler to plot this curve. We can count the exact number of checks directly, giving us a deterministic metric that never varies from machine to machine:

// src/benchmark.ts
export function countNaiveChecks(n: number): number {
  let checks = 0;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      checks++; // real collideBodies would run here
    }
  }
  return checks;
}
Enter fullscreen mode Exit fullscreen mode

To feel the drop live in the browser, a lightweight frame counter is enough, with no HUD library required:

// src/demo.ts
let frames = 0;
let fpsSince = performance.now();
let fps = 0;

function sampleFps(now: number) {
  frames++;
  if (now - fpsSince >= 500) {
    fps = Math.round((frames * 1000) / (now - fpsSince));
    frames = 0;
    fpsSince = now;
  }
}
Enter fullscreen mode Exit fullscreen mode

Putting a “+500 bodies” button on screen and watching FPS melt with every click is the most convincing moment in this whole exercise. The chart doesn’t slope gently downward; past a threshold, O(n²) makes it fall off a cliff.

Industrial control panel showing a finger pressing a red +500 button while an analog FPS gauge drops through 60, 22, to FREEZE under an O(n²) warning light.

Every +500 bodies click compounds O(n²) checks until frame rate drops off a cliff.

Broad-phase vs. narrow-phase

Take another look at collideBodies from our engine:

// src/world.ts — EXCERPT: see file for full body
private collideBodies(a: Body, b: Body) {
  const totalInvMass = a.invMass + b.invMass;
  if (totalInvMass === 0) return; // two static bodies cannot collide

  const delta = sub(b.pos, a.pos);
  const dist = length(delta);
  const minDist = a.radius + b.radius;
  if (dist >= minDist || dist === 0) return; // no contact
  // ... normal, impulse, overlap correction ...
}
Enter fullscreen mode Exit fullscreen mode

This function determines with exact precision whether two bodies actually collide, then resolves the impact with impulses. It is accurate and expensive because it runs square roots, vector subtractions, and dot products.

This stage is called narrow-phase, because it zooms in on a single candidate pair and decides its fate with full geometric precision. Every physics engine splits its collision pipeline into two stages:

  • Broad-phase is cheap and coarse. It answers “could these two bodies possibly be colliding?” using a handful of additions and comparisons, eliminating millions of impossible pairs in one sweep and leaving a small list of candidate pairs. It never claims two bodies definitely collided, only that they are worth checking.
  • Narrow-phase is expensive and exact. It runs only on the candidate pairs produced by broad-phase, tests true geometry, and resolves impulses. Our collideBodies is already the narrow-phase.

Our engine’s only crime was skipping broad-phase altogether. That naive nested loop shoved every pair straight into the expensive narrow-phase. We were forcing the entire reception hall to shake hands.

The target pipeline is simple:

every frame:
  1. integration (gravity → velocity → position)  ← unchanged
  2. wall collisions                              ← unchanged
  3. BROAD-PHASE  → generate candidate pairs      ← NEW
  4. NARROW-PHASE → collideBodies(a, b)           ← fewer calls
Enter fullscreen mode Exit fullscreen mode

Notice what didn’t change: we don’t touch a single line inside narrow-phase. collideBodies stays exactly as it is. All we do is place a bouncer in front of it: a spatial hash grid.

A uniform spatial hash grid

The bouncer’s job is straightforward: divide the world into equal square cells, place each body into the cell(s) it occupies, and suggest candidate pairs only from bodies sharing the same cell. We split the hall into tables; now you only shake hands with your tablemates.

This data structure is called a spatial hash grid. The “hash” comes from mapping a body’s world coordinates (x, y) to a cell key that points into a Map holding the list of bodies in that cell.

First, we define the minimal shape the grid needs to see. The grid doesn’t care about a body’s mass, velocity, or restitution, only where it is and how wide it is:

// src/grid.ts
import type { Vec2 } from "./vec";

// Anything insertable into the grid: just a position and a radius.
export interface HasBounds {
  pos: Vec2;
  radius: number;
}
Enter fullscreen mode Exit fullscreen mode

Our Body type already satisfies this (pos and radius), so the grid plugs directly into our engine. Now the class skeleton:

// src/grid.ts — class skeleton; insert/queryPairs follow below
export class SpatialHashGrid<T extends HasBounds> {
  private cells = new Map<string, number[]>(); // cell key → body indices in that cell
  private items: T[] = [];                      // index → body

  constructor(public readonly cellSize: number) {}

  // Start each frame fresh by clearing previous cells.
  clear(): void {
    this.cells.clear();
    this.items.length = 0;
  }

  // Convert a cell coordinate pair into a Map key.
  private hash(cx: number, cy: number): string {
    return cx + "," + cy;
  }

  // Snap a world coordinate down to its cell coordinate.
  private cellOf(v: number): number {
    return Math.floor(v / this.cellSize);
  }
}
Enter fullscreen mode Exit fullscreen mode

I used a string key like "3,-2". Yes, string keys in a performance article look slightly ironic, and there is a reason for it: first make it right, then make it fast.

The hash function must map two cell coordinates to a collision-free key. Many spatial hash tutorials use an XOR hash like cx * prime1 ^ cy * prime2. That approach has a subtle flaw: two distinct cells can collide onto the same hash bucket, silently merging two separate tables into one and spawning phantom candidate pairs. A string key eliminates hash collisions completely and handles negative coordinates without extra math. It raises the constant factor slightly, which is a grain of sand next to the quadratic wall.

Vintage hotel key rack with brass tags labeled 3,-2, 3,-1, 4,-2, and 4,-1 alongside a crossed-out XOR symbol, illustrating collision-free string cell keys in a spatial hash grid.

Using "${cx},${cy}" string keys in a Map avoids XOR hash collisions—collision-free, slightly ironic.

Insertion, querying, and cell size

Next come insertion and querying. Insertion has one subtlety: if we insert a body only into the cell containing its center, two circles straddling a cell boundary will overlap in world space while sitting at different tables, never seeing each other. Missed collisions are the sneakiest bugs in physics; you rarely notice them until a body tunnels straight through a corner.

The fix is clean: insert the body into every cell touched by its AABB (axis-aligned bounding box). A small circle usually lands in one cell; a circle straddling a boundary gets written to two or four cells and reliably meets its neighbor:

// src/grid.ts — SpatialHashGrid body
insert(item: T): void {
  const id = this.items.length;
  this.items.push(item);

  const minCx = this.cellOf(item.pos.x - item.radius);
  const maxCx = this.cellOf(item.pos.x + item.radius);
  const minCy = this.cellOf(item.pos.y - item.radius);
  const maxCy = this.cellOf(item.pos.y + item.radius);

  for (let cx = minCx; cx <= maxCx; cx++) {
    for (let cy = minCy; cy <= maxCy; cy++) {
      const key = this.hash(cx, cy);
      let cell = this.cells.get(key);
      if (!cell) {
        cell = [];
        this.cells.set(key, cell);
      }
      cell.push(id);
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

On the query side, we pair up every body inside each cell. However, inserting via AABB introduces a cost: if two bodies share two cells, they will be emitted twice. That is double counting, and it wastes narrow-phase work. The fix is deduplicating with a single integer key ordered by ID:

// src/grid.ts — SpatialHashGrid body
queryPairs(): Array<[T, T]> {
  const pairs: Array<[T, T]> = [];
  const seen = new Set<number>();
  const n = this.items.length;

  for (const cell of this.cells.values()) {
    for (let i = 0; i < cell.length; i++) {
      for (let j = i + 1; j < cell.length; j++) {
        const a = cell[i];
        const b = cell[j];
        // low id * N + high id → unique, collision-free key per pair.
        const lo = a < b ? a : b;
        const hi = a < b ? b : a;
        const key = lo * n + hi;
        if (seen.has(key)) continue;
        seen.add(key);
        pairs.push([this.items[lo], this.items[hi]]);
      }
    }
  }
  return pairs;
}
Enter fullscreen mode Exit fullscreen mode

The lo * n + hi trick packs two IDs into a single integer. Because n is the total number of bodies, this key is guaranteed collision-free: every ordered pair maps to a unique number, and the seen set skips any pair it has already encountered.

The single parameter that decides how well the grid performs is cell size. The first time I wrote a spatial grid, I made the cells huge, basically one giant cell covering the whole world. I wired up the grid, hit run, and FPS didn’t budge a single frame. I stared at the screen for half an hour wondering why it wasn’t faster. The reason was embarrassingly simple: one giant cell puts everyone back at a single table. Too large, and the grid becomes an expensive imitation of the naive loop. Too small, and every body spills into dozens of cells, blowing up insertion cost.

The sweet spot usually sits around a cell size of 1 to 2× the largest body’s diameter. At that ratio, each body lands in a handful of cells, and each cell holds a handful of bodies. Instead of guessing, we can run a small sweep over cell sizes and count the generated candidate pairs:

// src/benchmark.ts
export function sweepCellSize(items: HasBounds[], sizes: number[]) {
  return sizes.map((cellSize) => {
    const grid = new SpatialHashGrid<HasBounds>(cellSize);
    for (const it of items) grid.insert(it);
    const candidates = grid.queryPairs().length;
    return { cellSize, candidates };
  });
}
Enter fullscreen mode Exit fullscreen mode

Candidate count moves in one direction: larger cells produce more candidates. In a scene with n = 2,000 and seed = 1, cell size 8 yields 638 candidates, 24 yields 1,418, 48 yields 3,162, and a world-sized cell yields 1,999,000 (the exact naive count). Smaller cells shrink candidate count, yet each body gets written into more cells, increasing insertion overhead. Total time spent across insertion, query, and narrow-phase traces a U-curve, and the bottom of that U-curve is the right cell size for your scene. Measure to find it rather than relying on a formula.

Science-fair tri-fold board titled Measure Cell Size, Don’t Guess, showing a U-shaped performance curve against cellSize and a wire grid holding spheres.

Benchmarking cellSize reveals the sweet spot: too small bloats insertion, too large bloats narrow-phase—measure, don't guess.

Large and fast bodies

Uniform grids have one famous weakness: a single giant body. Picture a guest in the hall whose arms span three tables at once. Because we insert by AABB, that giant gets written into every cell it overlaps. It won’t miss anyone, but if it touches half the cells in the world, comparison counts climb right back up. A uniform grid shines when bodies are roughly similar in size; if an ant and an elephant share the same scene, no single cell size fits both.

At small scales you can ignore this. When density spikes in one corner of the hall and drops to zero everywhere else, a one-size-fits-all cell stops working, and a QuadTree handles it better.

Museum display case showing a large elephant spanning multiple grid cells next to a tiny ant inside a single cell, illustrating the limits of a uniform grid with fixed cellSize = 48.

When an ant and an elephant share a uniform grid, no single cellSize fits both—the classic case for a QuadTree.

Then there is the fast-body problem. If your bullet travels half the screen in a single frame, insert only places it in the cells of its current position, completely blind to bodies along the corridor it just crossed. Broad-phase alone cannot solve tunneling, but it can at least surface the right candidates: insert the body using the swept AABB covering both its current position and its next-frame position:

// src/grid.ts — SpatialHashGrid body
insertSwept(item: T & { vel: Vec2 }, dt: number): void {
  const nx = item.pos.x + item.vel.x * dt; // next-frame position
  const ny = item.pos.y + item.vel.y * dt;

  const minX = Math.min(item.pos.x, nx) - item.radius;
  const maxX = Math.max(item.pos.x, nx) + item.radius;
  const minY = Math.min(item.pos.y, ny) - item.radius;
  const maxY = Math.max(item.pos.y, ny) + item.radius;

  const id = this.items.length;
  this.items.push(item);
  for (let cx = this.cellOf(minX); cx <= this.cellOf(maxX); cx++) {
    for (let cy = this.cellOf(minY); cy <= this.cellOf(maxY); cy++) {
      const key = this.hash(cx, cy);
      let cell = this.cells.get(key);
      if (!cell) {
        cell = [];
        this.cells.set(key, cell);
      }
      cell.push(id);
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

Our Body already carries vel, so this works out of the box. Keep in mind that this introduces the bullet to the right candidates without resolving the collision itself. Stopping a bullet from teleporting through a wall belongs to narrow-phase (continuous collision detection and swept intersection tests). Broad-phase only proposes candidates; it doesn't make final decisions.

Wiring it into the engine: broad to narrow

Now we can rip that naive nested loop out of step() and drop in the two-stage pipeline. We add a grid field to World and replace the final block (running inside a fixed-timestep game loop for deterministic physics):

// src/world.ts — relevant excerpt (gravity, constructor, and collideWalls are in the file)
export class World {
  bodies: Body[] = [];
  grid = new SpatialHashGrid<Body>(48); // cell ≈ 1–2× largest diameter

  step(dt: number) {
    // 1. Integration (unchanged)
    for (const b of this.bodies) {
      if (b.invMass === 0) continue;
      b.vel = add(b.vel, scale(this.gravity, dt));
      b.pos = add(b.pos, scale(b.vel, dt));
    }

    // 2. Wall collisions (unchanged)
    for (const b of this.bodies) this.collideWalls(b);

    // 3. BROAD-PHASE: clear and populate the grid each frame
    this.grid.clear();
    for (const b of this.bodies) this.grid.insert(b);

    // 4. NARROW-PHASE: run existing solver only on candidate pairs
    for (const [a, b] of this.grid.queryPairs()) {
      this.collideBodies(a, b);
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

Look at what we did to narrow-phase: nothing. collideBodies sits untouched, identical line for line to the original physics engine. All we did was shrink the stream of pairs reaching it from millions down to thousands. Broad-phase works simply by calling the expensive function less often.

One detail worth noting: we clear() and rebuild the grid from scratch every frame. Updating bodies incrementally as they move between cells sounds faster, but for most 2D games, rebuilding from scratch is both simpler and fast enough because insertion is already cheap. Measure before optimizing prematurely; you may never need incremental updates.

Benchmark: grid vs. QuadTree vs. naive

To weigh all three approaches on the same scale, we need a deterministic scene generator: a seeded PRNG so every run on every machine produces the exact same layout:

// src/benchmark.ts
// mulberry32: small, fast, deterministic PRNG
function makeRng(seed: number): () => number {
  return () => {
    seed |= 0;
    seed = (seed + 0x6d2b79f5) | 0;
    let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

// Constant DENSITY: world area scales with body count (no clustering).
export function makeScene(n: number, seed = 1): HasBounds[] {
  const rng = makeRng(seed);
  const world = Math.sqrt(n) * 40; // keep density constant
  const items: HasBounds[] = [];
  for (let i = 0; i < n; i++) {
    items.push({
      pos: { x: rng() * world, y: rng() * world },
      radius: 6,
    });
  }
  return items;
}
Enter fullscreen mode Exit fullscreen mode

Scaling world with sqrt(n) is intentional: it keeps spatial density constant. That matters because a spatial grid's "near-linear" promise holds under this exact condition. Pile all 20,000 bodies onto a single point, and the grid degrades right back to O(n²), which is just a tax levied by physics. Under heavy clustering, a QuadTree fights back better.

The harness counts how many candidate pairs each method emits, giving us a deterministic, hardware-independent metric showing exactly how many times narrow-phase gets called:

// src/benchmark.ts
export function benchmark(n: number) {
  const scene = makeScene(n);

  // Naive: every pair once — closed form n(n-1)/2 (no need to loop 200M times when n is large).
  const naive = (n * (n - 1)) / 2;

  // Spatial Hash Grid
  const grid = new SpatialHashGrid<HasBounds>(24);
  for (const it of scene) grid.insert(it);
  const gridPairs = grid.queryPairs().length;

  // QuadTree
  const qt = new QuadTree<HasBounds>({ x: 0, y: 0, w: Math.sqrt(n) * 40, h: Math.sqrt(n) * 40 });
  for (const it of scene) qt.insert(it);
  const qtPairs = qt.queryPairs().length;

  return { n, naive, gridPairs, qtPairs };
}
Enter fullscreen mode Exit fullscreen mode

Here are the candidate pair counts from a run (cellSize = 24, constant-density scene, seed = 1; numbers are deterministic and reproducible via npm run bench):

Bodies (n) | Naive Pairs | Grid Candidates | QuadTree Candidates
-----------+-------------+-----------------+--------------------
200        | 19,900      | 160             | 4,451
2,000      | 1,999,000   | 1,418           | 163,493
20,000     | 199,990,000 | 14,323          | 4,818,747
Enter fullscreen mode Exit fullscreen mode

The naive column climbs quadratically. The grid stays nearly linear: at 20,000 bodies, naive runs 199,990,000 checks while the grid emits just 14,323 candidates, nearly 14,000× less work. The QuadTree also bridges the cliff compared to naive: 4,818,747 instead of 199,990,000, roughly 40× fewer checks. Yet on this uniformly distributed scene, it trails far behind the grid because bodies straddling node boundaries get stuck in upper nodes and pair against everything below them. On uniform, spread-out scenes, the grid wins, turning the FPS cliff into a flat plateau. The browser demo shows the same story: at 2,500 bodies, naive mode collapses to 1 FPS while grid mode holds 46 FPS.

So what is a QuadTree? Instead of slicing the world into fixed cells, it subdivides by occupancy. A region splits into four quadrants when crowded and stays whole when empty. That adaptability directly answers the uniform grid’s “one-size cell” limitation, shining when ants and elephants share the canvas or density varies wildly. Our benchmark runs a real QuadTree; here is its skeleton:

// src/quadtree.ts — skeleton: see file for full subdivide/childFor/collect bodies
interface QuadBounds { x: number; y: number; w: number; h: number; }

export class QuadTree<T extends HasBounds> {
  private items: T[] = [];
  private children: QuadTree<T>[] | null = null;

  constructor(
    private bounds: QuadBounds,
    private capacity = 8,
    private maxDepth = 8,
    private depth = 0,
  ) {}

  insert(item: T): void {
    if (this.children) {
      const c = this.childFor(item);
      if (c) {
        c.insert(item);
        return;
      } // fits completely inside one child
    }
    this.items.push(item);
    if (
      !this.children &&
      this.items.length > this.capacity &&
      this.depth < this.maxDepth
    ) {
      this.subdivide();
    }
  }

  // Candidate pairs: each node's own items + pairs with ancestor items.
  queryPairs(): Array<[T, T]> {
    const out: Array<[T, T]> = [];
    this.collect([], out);
    return out;
  }
}
Enter fullscreen mode Exit fullscreen mode

I won’t unpack every detail here, since QuadTrees deserve their own article (coming up next in this series). For now, the main trade-off is clear: a uniform grid is both faster and simpler when bodies are similarly sized and spread out; a QuadTree pulls ahead on clustered scenes with widely varying object sizes. Neither wins everywhere because the shape of your scene decides. Writing both and measuring on your own workload beats any blog debate.

Author’s note: While writing that follow-up, I spotted an omission in this QuadTree: *`*collect()* passes the ancestor list down to child nodes *without pruning*. As a result, large bodies stuck in upper nodes get paired against the entire subtree below them, making the QuadTree column above look worse than it needs to be. Filtering out ancestors whose AABB doesn't touch the child's bounds (a one-line *aabbHitsBounds* check) drops candidates on the exact same scene from 4,818,747 to 155,240, completely losslessly, since *childFor`* already requires full containment. I'm keeping the table above as-is because it reflects the honest measurement of this code, so don't write off QuadTrees based on it. The full fix and head-to-head re-benchmark across both scene types are Up Next.*

Tests: does the grid ever lie?

Broad-phase has only one unforgivable sin: missing a real collision. Emitting extra false candidates is forgivable; narrow-phase filters them out, costing only a bit of CPU. If the grid fails to pair two overlapping bodies, however, that collision vanishes silently, a body ghosts through a wall, and players scream “bug.”

So the real invariant to test is simple: the grid’s candidates must cover every truly overlapping pair. The cleanest way to prove this is comparing the grid’s filtered output against brute-force O(n²). First, a pure, deterministic overlap check for two circles:

// src/overlap.ts
export function circlesOverlap(a: HasBounds, b: HasBounds): boolean {
  const dx = a.pos.x - b.pos.x;
  const dy = a.pos.y - b.pos.y;
  const r = a.radius + b.radius;
  return dx * dx + dy * dy < r * r; // no sqrt — squared distance is enough
}
Enter fullscreen mode Exit fullscreen mode

We tag test bodies with an id, filter the grid's candidate pairs by actual overlap, and assert an exact match against brute-force:

// test/grid.test.ts — SpatialHashGrid suite
// (the file also includes a QuadTree parity test: 4 tests total)
import { describe, it, expect } from "vitest";
import { SpatialHashGrid, type HasBounds } from "../src/grid";
import { circlesOverlap } from "../src/overlap";

interface TestItem extends HasBounds { id: number; }

function scene(n: number, seed: number): TestItem[] {
  let s = seed;
  const rand = () => {
    s = (s * 1103515245 + 12345) & 0x7fffffff;
    return s / 0x7fffffff;
  };
  return Array.from({ length: n }, (_, id) => ({
    id,
    pos: { x: rand() * 400, y: rand() * 400 },
    radius: 6 + rand() * 10, // varying radii: stress multi-cell AABB insertion
  }));
}

// Brute-force: all truly overlapping pairs (ground truth)
function bruteForceOverlaps(items: TestItem[]): Set<string> {
  const set = new Set<string>();
  for (let i = 0; i < items.length; i++) {
    for (let j = i + 1; j < items.length; j++) {
      if (circlesOverlap(items[i], items[j])) set.add(`${i}-${j}`);
    }
  }
  return set;
}

describe("SpatialHashGrid.queryPairs", () => {
  it("never misses a truly overlapping pair (matches brute-force)", () => {
    const items = scene(500, 42);
    const grid = new SpatialHashGrid<TestItem>(24);
    for (const it of items) grid.insert(it);

    const fromGrid = new Set<string>();
    for (const [a, b] of grid.queryPairs()) {
      if (circlesOverlap(a, b)) {
        const [lo, hi] = a.id < b.id ? [a.id, b.id] : [b.id, a.id];
        fromGrid.add(`${lo}-${hi}`);
      }
    }

    expect(fromGrid).toEqual(bruteForceOverlaps(items));
  });

  it("never emits the same pair twice (no double counting)", () => {
    const items = scene(300, 7);
    const grid = new SpatialHashGrid<TestItem>(20);
    for (const it of items) grid.insert(it);

    const pairs = grid.queryPairs();
    const keys = pairs.map(([a, b]) =>
      a.id < b.id ? `${a.id}-${b.id}` : `${b.id}-${a.id}`,
    );
    expect(new Set(keys).size).toBe(keys.length); // all unique
  });

  it("pairs a large body spanning many cells with all its neighbors", () => {
    const big: TestItem = { id: 0, pos: { x: 100, y: 100 }, radius: 60 };
    const small: TestItem[] = [
      { id: 1, pos: { x: 60, y: 100 }, radius: 5 },
      { id: 2, pos: { x: 140, y: 100 }, radius: 5 },
      { id: 3, pos: { x: 100, y: 55 }, radius: 5 },
    ];
    const grid = new SpatialHashGrid<TestItem>(24); // cell << large diameter
    for (const it of [big, ...small]) grid.insert(it);

    const hits = new Set<number>();
    for (const [a, b] of grid.queryPairs()) {
      if (circlesOverlap(a, b)) {
        if (a.id === 0) hits.add(b.id);
        if (b.id === 0) hits.add(a.id);
      }
    }
    expect(hits).toEqual(new Set([1, 2, 3])); // caught all three
  });
});
Enter fullscreen mode Exit fullscreen mode

The first test is the heart of the suite: 500 bodies of varying sizes, seeded so every run is identical. The grid’s filtered candidates must match the brute-force overlap set exactly. Missing even a single pair turns the test red. I deliberately varied radius so bodies span multiple cells via their AABB, putting both deduplication and boundary coverage under real pressure.

When this test is green, your broad-phase is trustworthy. You have proven that the bouncer filtering out millions of pairs never turned away a single pair that actually collided. Few green checks in a physics engine feel more reassuring than that.

Summary

  1. Naive pair-by-pair collision testing is O(n²): multiplying bodies by 100 multiplies work by 10,000, directly from n(n - 1) / 2.
  2. Collision pipelines have two stages: a cheap, coarse broad-phase filters candidates, and an exact, expensive narrow-phase resolves them. collideBodies was narrow-phase from day one.
  3. A spatial hash grid divides the world into equal cells, hashes bodies to cell keys, and pairs only bodies sharing a cell. Split the hall into tables; shake hands only at your table.
  4. Insert each body into every cell touched by its AABB (so boundary collisions are never missed), and deduplicate candidate pairs with an ID-ordered integer key (so pairs are never checked twice).
  5. Set cell size to about 1 to 2× the largest body’s diameter; too large collapses back toward naive, too small explodes insertion cost. Sweep and measure instead of guessing.
  6. Uniform grids excel on spread-out, similarly sized bodies; QuadTrees pull ahead on clustered scenes with widely varying sizes. Let your scene shape pick the winner.
  7. Broad-phase has one unforgivable sin: missing a real collision. Your main test is that filtered candidates must equal the brute-force overlap set.

The grid, QuadTree, benchmark harness, live FPS demo, and Vitest suite are all in the GitHub repository. Run npm test to verify pair parity and npm run dev to watch the FPS cliff disappear, or open the interactive live demo right in your browser.

When we first built our physics engine, we brushed broad-phase aside as “production work Matter.js handles.” Saying that out loud made it sound like a massive engineering undertaking; sitting down to write it produced eighty lines around a Map and an integer deduplication trick. Estimating the size of a problem from across the room almost always inflates it.

We split the hall into tables, so twenty thousand guests can dance at once without shaking hands with the wrong person.

How are you handling broad-phase collision culling in your own 2D engine or Canvas projects? I’d love to hear your thoughts.

Canvas 2D and game architecture series

About the author

I’m Mustafa Morbel, a software engineer with over 17 years of experience building modern web applications, game engines, WebGL/Canvas graphics, and AI-driven workflows.

  • Grab the source code, Vitest suite, and benchmark harness on GitHub, or try the interactive live demo directly in your browser.
  • Follow along on LinkedIn and X / Twitter (@mustafamorbel) for upcoming articles on Canvas architecture and TypeScript performance.
  • Grab the complete Canvas 2D & Game Physics Starter Kit on Buy Me a Coffee.
  • If you found this useful, leave a clap and share how you’ve tuned broad-phase in your own projects! 🧠💬

Top comments (0)