From O(n²) to 60 FPS: spatial hashing in a survivor game

The bug report was my own framerate: wave 25 of Endless Onslaught, 400 entities on screen, twelve weapons firing — and the game dropping to 22 FPS on a machine that renders 4K video without blinking.

The culprit was the most innocent-looking code in the project:

for (const bullet of bullets) {
  for (const enemy of enemies) {
    if (distanceSquared(bullet, enemy) < hitRadius) {
      // handle hit...
    }
  }
}

500 bullets × 400 enemies = 200,000 distance checks per frame, at 60 frames per second. Twelve million checks a second to discover that almost everything is far away from everything else.

The fix: stop asking the wrong question#

The insight isn't "make the collision check faster" — a squared-distance check is already four arithmetic ops. The insight is that most of those checks don't need to happen at all. Spatial hashing makes that structural.

class SpatialHash<T extends { x: number; y: number }> {
  private cells = new Map<string, T[]>();
 
  constructor(private cellSize = 64) {}
 
  clear() {
    this.cells.clear();
  }
 
  insert(entity: T) {
    const key = this.keyFor(entity.x, entity.y);
    const bucket = this.cells.get(key);
    if (bucket) bucket.push(entity);
    else this.cells.set(key, [entity]);
  }
 
  /** All entities in cells overlapping the given area. */
  query(x: number, y: number, radius: number): T[] {
    const found: T[] = [];
    const minX = Math.floor((x - radius) / this.cellSize);
    const maxX = Math.floor((x + radius) / this.cellSize);
    const minY = Math.floor((y - radius) / this.cellSize);
    const maxY = Math.floor((y + radius) / this.cellSize);
    for (let cx = minX; cx <= maxX; cx++) {
      for (let cy = minY; cy <= maxY; cy++) {
        const bucket = this.cells.get(`${cx}:${cy}`);
        if (bucket) found.push(...bucket);
      }
    }
    return found;
  }
 
  private keyFor(x: number, y: number) {
    return `${Math.floor(x / this.cellSize)}:${Math.floor(y / this.cellSize)}`;
  }
}

Each frame the grid is rebuilt from scratch — cheap, because insertion is O(1) per entity. Collision, weapon targeting and enemy separation all became query() calls:

for (const bullet of bullets) {
  const candidates = grid.query(bullet.x, bullet.y, HIT_RADIUS);
  for (const enemy of candidates) {
    if (distanceSquared(bullet, enemy) < hitRadius) {
      // handle hit...
    }
  }
}

A bullet at any moment checks 3–15 candidates instead of 400.

Results, measured not guessed#

Two subtleties made the numbers stick:

• Cell size is a tuned constant. At 64px, query areas typically overlap 4–9 cells. Smaller cells meant more grid overhead per query; larger cells meant bigger candidate lists. I profiled four values and 64 won — for my weapon radius distribution, not universally.
• Rebuild > maintenance. Dirty-tracking moved entities between cells was faster on paper and buggier in practice. A full rebuild each frame is a known cost with no edge cases.

Profiling lessons that transferred#

I "optimised" the particle renderer before touching this, expecting it to be the bottleneck. It was 3% of frame time. The collisions were 70%. The browser's performance panel told me this in ten minutes; my intuition would have taken another week to be wrong.

After the fix I went hunting the next tiers:

• Object pooling for bullets and damage numbers — garbage collection pauses were masking as "random stutter".
• Fixed-timestep simulation with interpolated rendering, so physics stayed deterministic and frame-time spikes stopped causing tunnelling.
• Separate canvas layers — the HUD redraws only when values change, not every frame.

The idea that keeps coming back#

A spatial hash grid and a search inverted index are the same idea wearing different clothes: stop scanning everything and ask a structure for the right subset. Bucketing entities by position, terms by document, vectors by region — it's all a bet that locality is worth exploiting.

That bet paid for itself in a game at 60 FPS. It also happens to be the entire thesis of good retrieval systems. Play the game, learn the lesson.