At how many objects does naive collision detection break?

At 5,700 moving objects. That is the exact point where an all-pairs nested loop stops fitting inside a 16.67 ms frame: 5,700 objects cost 16.60 ms, 5,800 cost 17.16 ms. Below that the naive loop is genuinely fine and the broadphase you were told to write is a waste of your afternoon. Above it, the cliff is vertical — 10,000 objects cost 52.4 ms and 50,000 cost 1,251 ms, a frame rate of 0.8.

Hardware: Apple M3, 16 GB, macOS 26.4.1, Node v23.5.0, single-threaded, no engine, no GPU, no network. This is JavaScript on a laptop, not a C++ engine. A tight SIMD-friendly C++ inner loop will move every absolute number here by roughly an order of magnitude. What transfers is the relative scaling and the pair counts, which are properties of the algorithms and not of the language — the pair counts below are exact and reproduce from the seed.

The short answer

• A naive all-pairs loop exceeds a 16.67 ms frame budget at 5,700 objects (16.60 ms), and is 3.1x over budget by 10,000.
• A uniform grid held 60 fps to 158,400 objects — 27.8x further than naive. A hashed variant held to 123,200, sweep-and-prune to 62,400, and 80,000 when the sort was replaced with an insertion sort over the previous frame's order.
• A quadtree broke at 21,200 objects — 7.5x worse than a flat grid, because it does 71x the pair checks (901,609 vs 12,678 at n=10,000) and chases pointers to do them.
• Updating a quadtree incrementally instead of rebuilding it made it worse. It started at 9.3 ms/frame and reached 86.6 ms by frame 600. Rebuilding from scratch every frame stayed flat at 6.3 ms. Rebuilding is not the problem people say it is; it is the fix.
• Garbage collection was not the source of frame spikes. The allocation-heavy quadtree triggered 102 GCs over 600 frames costing 29.7 ms in total — 0.05 ms per frame against a 6.3 ms broadphase, longest pause 0.83 ms. Its p99/p50 ratio was 1.17.

How the world is generated and stepped

Every number below comes from the same simulation. n axis-aligned boxes of side 8 units live in a square world of side L = 20 * sqrt(n), so each object owns 400 square units regardless of n — density is held constant and only the count changes. That isolates algorithmic scaling. Positions and headings come from a seeded mulberry32(12345); speeds are 20–80 units/second. Each frame integrates dt = 1/60 and reflects off the walls. At n = 10,000 the world is 2000x2000 and there are about 3,100 genuine overlapping pairs per frame.

Timing covers the broadphase only — build plus query — and excludes integration. All seven implementations were cross-checked frame by frame and report identical overlap counts at both uniform and 16x-clustered density, so the pair-check numbers are comparing like with like. Reported figures are p50 over 20–60 frames after two warm-up frames.

When does the nested loop actually stop working?

p50 milliseconds per frame. Grid and hash use a cell of 16 units, 2x object size.

The pair checks explain it. At n = 10,000 naive performs 49,995,000 AABB tests to find 3,238 real overlaps — one useful answer per 15,440 tests. The grid performs 12,678, a 3,944x reduction. Sweep-and-prune performs 400,559, which is 125x better than naive but still 32x worse than the grid, because projecting onto one axis leaves every object in a tall thin column of false candidates.

Note the top-left of that table. At 100 objects the quadtree is 3.3x slower than the naive loop it is meant to replace, and at 500 it is still slower. Below about 1,000 objects every acceleration structure is overhead. If your game has 200 entities, write the nested loop and go build the game.

What cell size should a spatial hash use?

Sweeping cell size at n = 10,000, object side 8, mean centre-to-centre spacing 20:

The rule: make the cell 2–4x the typical object size. The basin is wide and flat — anything from 1x to 8x lands within 20% of optimum — so this is not a parameter worth agonising over. What matters is not being outside it. At 32x object size the grid is 4x slower than optimum; at 64x it has already blown the frame budget on its own.

The last row is the folklore made concrete. A one-cell grid performs exactly naive's 49,995,000 pair checks — and takes 2.5x longer to do them (129.3 ms vs 52.4 ms), because every check now costs a bucket lookup, an index indirection and a dedup stamp. A degenerate spatial hash is not as bad as naive. It is considerably worse.

One trap specific to hashed grids, as opposed to a dense array of cells: at a cell size of 4 the hash performed 133,833 checks against the dense grid's 4,952, a 27x penalty, and ran 3.4 ms instead of 1.4 ms. The world had 250,000 occupied cells and the hash table had 32,768 slots, so unrelated regions of the map collided into the same bucket. Size the table against the number of occupied cells, not the number of objects.

Does clustering break a spatial hash?

Partly — and less than everyone claims. Same 10,000 objects, same object size, same cell of 32, but squeezed into a progressively smaller region:

The grid got 17.5x slower while naive got only 1.5x slower, which looks like the predicted collapse. It is not. Divide the grid's checks by the real overlaps and the ratio is 9.2, 8.7, 8.9, 8.5 — flat across a 64x change in density. The grid is not becoming less efficient; the problem is becoming bigger. At 64x density there genuinely are 188,419 overlapping pairs, and any correct broadphase must enumerate them.

The part that is a real defect is the fixed cell size. Scaling the cell down with the cluster cut the checks from 1,598,392 to 292,748 and the frame from 15.08 ms to 7.86 ms — 1.9x, for one number changed. That is the actionable finding: clustering does not require a different data structure, it requires the cell to track local density. If your game has a stampede mechanic, derive cell size from the current bounding box of the entities each frame rather than hard-coding it at build time.

Does a quadtree handle mixed object sizes better?

This is the one case where the quadtree earns its reputation. Adding 20 world-spanning 1,600-unit objects to 9,980 normal ones, at n = 10,000:

The quadtree degraded 1.3x where the grid degraded 8.2x — it stores a huge object once at a shallow node, where a uniform grid stamps it into every one of the 10,000 cells it covers. The theory is correct. The practice is that the grid was 6.5x faster to begin with, so after both degrade the grid is still 2.8x faster in absolute terms — and retuning the cell from 16 to 64 recovered most of the loss for free. A milder mix, 5% of objects at 200px, cost the grid only 3.1x and it stayed the fastest structure at 2.67 ms.

Is rebuilding a quadtree every frame the problem?

No, and this measurement reversed my expectation completely. The received wisdom is that rebuilding the tree each frame is the naive mistake and incremental updates are the fix. Over 600 frames at n = 10,000:

The incrementally updated quadtree got 9.3x slower over ten seconds of simulated play, and passed the naive loop's cost by frame 200. Its pair checks went from 28,172 to 100,622 at n = 1,000 and from 901,609 to 1,961,205 at n = 10,000. The mechanism: an object that moves out of its node is reinserted from the root, and if it now straddles a boundary it lodges in an ancestor node where every query must test it. Nodes that empty out are never merged. The tree slowly turns into a list. Benchmark it for 20 frames — as most published comparisons do — and it looks like a 20% win. It is a 9x loss.

Sweep-and-prune is the counter-example, and it is the structure where incrementality genuinely pays: replacing the full sort with an insertion sort over the previous frame's order, which is nearly sorted because objects move a fraction of their width per frame, took n = 10,000 from 1.479 ms to 0.874 ms and moved its breaking point from 62,400 objects to 80,000. Same pair count, 41% less time, and it stayed flat over 600 frames.

Is garbage collection what causes the frame spikes?

Not at this scale, which also surprised me. Measured with a PerformanceObserver on gc entries over 600 frames at n = 10,000:

The quadtree allocates a fresh node graph every frame and triggered a GC roughly every sixth frame — and it cost 29.7 ms spread over 600 frames, with no single pause longer than 0.83 ms. Against a 6.3 ms broadphase that is 0.8% of the budget. The quadtree's problem is that it does 71x the pair checks, not that it allocates. V8's young-generation collector is very good at exactly this allocation pattern.

The three structures built on preallocated Int32Array buckets triggered zero collections across 600 frames and have a p99/p50 ratio under 1.10 — which is the real argument for typed arrays here. Not raw speed, but a frame time you can budget against. The same preallocation discipline is what made the difference in parsing a multi-gigabyte JSON file.

What to actually build

Write the nested loop until it hurts; at under 1,000 objects it beats every structure here. When it hurts, write a uniform grid with a cell 2–4x your typical object size, backed by a counting sort into two preallocated Int32Arrays. That is roughly 40 lines, it held 60 fps to 158,400 objects, it allocates nothing, and it degrades gracefully. Reach for a quadtree only when your object sizes span two orders of magnitude, and if you do, rebuild it every frame.

We use these numbers when sizing the entity budgets in our Unity templates, the same way the sprite atlas measurements set the texture budgets. If you are building 2D game content and want the animation side handled, CST Animator is where that work went.

Check it yourself

Save as broadphase.mjs and run node broadphase.mjs. No dependencies. It reproduces the headline threshold by bisection in well under a minute.

// node broadphase.mjs   — finds the n at which each approach exceeds 16.67 ms
const rng = a => () => { a|=0; a=(a+0x6D2B79F5)|0; let t=Math.imul(a^(a>>>15),1|a);
  t=(t+Math.imul(t^(t>>>7),61|t))^t; return ((t^(t>>>14))>>>0)/4294967296; };

function world(n) {                       // side-8 boxes, constant density
  const r = rng(12345), L = 20 * Math.sqrt(n);
  const x = new Float64Array(n), y = new Float64Array(n);
  const vx = new Float64Array(n), vy = new Float64Array(n);
  for (let i = 0; i < n; i++) {
    x[i] = r() * L; y[i] = r() * L;
    const a = r() * 6.283, s = 20 + r() * 60;
    vx[i] = Math.cos(a) * s; vy[i] = Math.sin(a) * s;
  }
  return { n, L, x, y, vx, vy, h: 4 };
}
function step(w) {
  const { n, L, x, y, vx, vy, h } = w;
  for (let i = 0; i < n; i++) {
    x[i] += vx[i] / 60; y[i] += vy[i] / 60;
    if (x[i] < h || x[i] > L - h) vx[i] = -vx[i];
    if (y[i] < h || y[i] > L - h) vy[i] = -vy[i];
  }
}
function naive(w) {
  const { n, x, y, h } = w; let c = 0, hit = 0;
  for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) {
    c++; if (Math.abs(x[j]-x[i]) < 2*h && Math.abs(y[j]-y[i]) < 2*h) hit++;
  }
  return { c, hit };
}
function makeGrid(n) { return { it: new Int32Array(n*4), st: new Int32Array(n).fill(-1), cnt: null }; }
function grid(w, g, cell = 16) {          // cell = 2x object size
  const { n, L, x, y, h } = w, gw = Math.ceil(L/cell), cells = gw*gw;
  if (!g.cnt || g.cnt.length !== cells+1) { g.cnt = new Int32Array(cells+1); g.sp = new Int32Array(cells+1); }
  else g.cnt.fill(0);
  const cl = i => Math.min(gw-1, Math.max(0, i));
  const box = i => [cl((x[i]-h)/cell|0), cl((x[i]+h)/cell|0), cl((y[i]-h)/cell|0), cl((y[i]+h)/cell|0)];
  for (let i = 0; i < n; i++) { const [a,b,c,d] = box(i);
    for (let cy = c; cy <= d; cy++) for (let cx = a; cx <= b; cx++) g.cnt[cy*gw+cx]++; }
  let acc = 0; for (let k = 0; k < cells; k++) { g.sp[k] = acc; acc += g.cnt[k]; } g.sp[cells] = acc;
  if (g.it.length < acc) g.it = new Int32Array(acc*2);
  for (let k = 0; k < cells; k++) g.cnt[k] = g.sp[k];
  for (let i = 0; i < n; i++) { const [a,b,c,d] = box(i);
    for (let cy = c; cy <= d; cy++) for (let cx = a; cx <= b; cx++) g.it[g.cnt[cy*gw+cx]++] = i; }
  g.st.fill(-1); let ch = 0, hit = 0;
  for (let i = 0; i < n; i++) { const [a,b,c,d] = box(i);
    for (let cy = c; cy <= d; cy++) for (let cx = a; cx <= b; cx++) {
      const k = cy*gw+cx, e = g.sp[k+1];
      for (let p = g.sp[k]; p < e; p++) { const j = g.it[p];
        if (j <= i || g.st[j] === i) continue; g.st[j] = i; ch++;
        if (Math.abs(x[j]-x[i]) < 2*h && Math.abs(y[j]-y[i]) < 2*h) hit++; } } }
  return { c: ch, hit };
}
const RUN = { naive: w => naive(w), grid: (w, s) => grid(w, s) };
const MAKE = { naive: () => null, grid: makeGrid };

function p50(name, n) {
  const w = world(n), s = MAKE[name](n), t = [];
  for (let i = 0; i < 2; i++) { step(w); RUN[name](w, s); }
  const t0 = performance.now();
  while (t.length < 12 && (t.length < 3 || performance.now() - t0 < 700)) {
    step(w); const a = performance.now(); RUN[name](w, s); t.push(performance.now() - a);
  }
  return t.sort((a, b) => a - b)[t.length >> 1];
}

const BUDGET = 16.666;
for (const name of ['naive', 'grid']) {
  let lo = 100, hi = 100;
  while (hi < 400000 && p50(name, hi) < BUDGET) { lo = hi; hi *= 2; }
  while (hi - lo > Math.max(50, lo * 0.02)) {
    const mid = (lo + hi) >> 1;
    if (p50(name, mid) < BUDGET) lo = mid; else hi = mid;
  }
  console.log(`${name}: 60 fps up to n=${lo} (${p50(name,lo).toFixed(2)} ms), ` +
              `over budget at n=${hi} (${p50(name,hi).toFixed(2)} ms)`);
}

On the machine above it prints, in 4.6 seconds total:

naive: 60 fps up to n=6100 (16.59 ms), over budget at n=6200 (17.11 ms)
grid: 60 fps up to n=126400 (16.57 ms), over budget at n=128000 (16.86 ms)

Those are not quite the 5,700 and 158,400 from the table, and the gap is worth explaining rather than hiding. This script uses one constant half-extent where the harness stores per-object half-extents in Float64Arrays — four extra typed-array loads per pair, worth about 7% to naive. In the other direction its box() helper allocates a small array per call, costing the grid about 20%. Both effects are the kind of detail that decides these benchmarks, and neither changes the conclusion: the grid buys between 21x and 28x the object count.

Run it on your own hardware before trusting any absolute number above. The ratio between the two lines is the finding; the milliseconds belong to this laptop.