2D Spatial Hashing for 60 FPS Canvas Collisions

If you have ever tried building a horde survival game or a bullet hell shooter on an HTML5 canvas, you know the exact moment your browser decides to pack its bags. Everything runs swimmingly with fifty swarming sprites. You bump the count to two thousand, and suddenly your silky 60 FPS display stutters like an old slide projector, turning your fan into a tiny jet engine.

The culprit is almost always naive collision detection. Testing every single entity against every other entity means running an $O(n^2)$ loop. At 2,000 entities, that is roughly two million checks every single frame. The browser engine does not stand a chance.

The fix? 2D spatial hashing. It is the weapon of choice across indie game dev circles and web performance breakdowns for tackling broad-phase collisions without breaking a sweat.

---

Direct Answer: What is 2D Spatial Hashing?

2D Spatial Hashing is a broad-phase collision detection optimisation technique that divides a 2D game world into a uniform grid of cells. Entities register their presence only into the cells they overlap. Instead of checking an entity against the entire game world ($O(n^2)$), the engine only checks against neighbours occupying the exact same cells ($O(1)$ to $O(n)$ average lookup), instantly preserving a 60 FPS frame rate.

---

The Broad-Phase vs. Narrow-Phase Split

Before writing a single line of maths, you must divide your collision system into two distinct steps:

1. Broad Phase: Quickly discard 99% of objects that are nowhere near each other. (Fast, approximate, cheap).

2. Narrow Phase: Run precise mathematical intersection tests—like Circle-to-Circle or Separating Axis Theorem (SAT)—on the few entities that actually share physical space. (Accurate, expensive).

Spatial hashing handles the broad phase. It acts like sorting your post by postal codes: the postie does not check every house in Yorkshire to deliver a letter addressed to Leeds.

+-------------------+-------------------+
|  Cell (0,0)       |  Cell (1,0)       |
|    [Zombie A]     |    [Bullet 1]     |
|    [Zombie B]     |                   |
+-------------------+-------------------+
|  Cell (0,1)       |  Cell (1,1)       |
|                   |    [Player]       |
+-------------------+-------------------+

In the diagram above, Zombie A only checks Zombie B. It never wastes CPU cycles evaluating Bullet 1 or the Player.

---

Building a Lightweight 2D Spatial Hash in JavaScript

Here is a lean, garbage-collector-friendly implementation tailored for HTML5 canvas loops.

class SpatialHash {
  constructor(cellSize) {
    this.cellSize = cellSize;
    this.grid = new Map();
  }

  // Convert world coordinates to a single string/integer key
  _key(x, y) {
    const gx = Math.floor(x / this.cellSize);
    const gy = Math.floor(y / this.cellSize);
    return `${gx}:${gy}`;
  }

  clear() {
    this.grid.clear();
  }

  // Insert an entity with an axis-aligned bounding box (AABB)
  insert(entity) {
    const startX = Math.floor(entity.x / this.cellSize);
    const endX = Math.floor((entity.x + entity.width) / this.cellSize);
    const startY = Math.floor(entity.y / this.cellSize);
    const endY = Math.floor((entity.y + entity.height) / this.cellSize);

    for (let x = startX; x <= endX; x++) {
      for (let y = startY; y <= endY; y++) {
        const key = `${x}:${y}`;
        if (!this.grid.has(key)) {
          this.grid.set(key, []);
        }
        this.grid.get(key).push(entity);
      }
    }
  }

  // Retrieve candidate colliders for a given entity
  query(entity) {
    const candidates = new Set();
    const startX = Math.floor(entity.x / this.cellSize);
    const endX = Math.floor((entity.x + entity.width) / this.cellSize);
    const startY = Math.floor(entity.y / this.cellSize);
    const endY = Math.floor((entity.y + entity.height) / this.cellSize);

    for (let x = startX; x <= endX; x++) {
      for (let y = startY; y <= endY; y++) {
        const key = `${x}:${y}`;
        const bucket = this.grid.get(key);
        if (bucket) {
          for (let i = 0; i < bucket.length; i++) {
            if (bucket[i] !== entity) {
              candidates.add(bucket[i]);
            }
          }
        }
      }
    }
    return candidates;
  }
}

---

Architecture Comparison: Spatial Hash vs. Quadtree

When developers debate broad-phase techniques on Reddit and YouTube code audits, the discussion almost always pits Spatial Hashing against Quadtrees. Here is how they stack up for casual browser game architectures:

Feature	Naive Array Loop	Quadtree	2D Spatial Hash
Time Complexity	$O(n^2)$	$O(n \log n)$	$O(n)$ average
Setup Cost per Frame	Zero	Moderate (recursive tree builds)	Low (direct bucket insertions)
Dynamic Entity Handling	Painless	Clunky (requires constant node pruning)	Trivial (clear and repopulate)
Implementation Complexity	Dead simple	High	Moderate
Ideal Use Case	Under 100 entities	Static level geometry	Dense, mobile swarms (bullet hells)

A Quadtree shines when entity distribution is wildly uneven across vast distances, like a space exploration game. But for compact browser arenas packed with swarming enemies, a flat spatial hash wipes the floor with dynamic trees because it avoids deep recursive allocations.

---

Avoiding the Garbage Collection Trap

In browser game development, the hidden villain of framerate drops is rarely math calculation—it is the JavaScript Garbage Collector (GC).

If you instantiate hundreds of temporary arrays and composite string keys ("${gx}:${gy}") every frame at 60 FPS, the browser will periodically halt execution to reclaim that memory. That results in jarring micro-stutters.

To harden your spatial hash against GC spikes:

• Use Packed Numerical Keys: Instead of creating a string key with template literals, pack 16-bit integer grid coordinates into a single 32-bit integer: (gx << 16) | (gy & 0xFFFF).
• Object Pooling: Rather than throwing away array buckets every tick, retain empty arrays and reset their length (bucket.length = 0).
• Calibrate Your Cell Size: Set the cell dimensions to roughly double the size of your average dynamic entity. If cells are too small, entities straddle multiple boundaries, spiking insertion overhead. If cells are too large, you drift back toward $O(n^2)$ inside individual buckets.

By routing your dynamic canvas entities through a spatial grid, you trade a few kilobytes of transient memory for an unshakeable 16.6-millisecond frame budget. Your horde survival prototype will happily juggle thousands of simultaneous projectiles while your players enjoy silky smooth input response.