Game Dev Mechanics: Spatial Hashing — How It Works

The Problem with Naive Collision Detection

Imagine you are building a top-down space shooter with 400 bullets and 150 enemies on screen at once. Every frame, you need to know whether any bullet has hit any enemy. The naive approach is simple: loop over every bullet and test it against every enemy. That is 400 × 150 = 60,000 pair checks per frame. Now add asteroid debris, pickup items, and enemy projectiles. The numbers explode.

This is the classic O(n²) collision detection problem. As the number of dynamic objects grows, the work grows quadratically. Double the objects and you quadruple the checks. At 60 fps with thousands of objects, the naive approach will melt your frame budget long before you run out of design ideas.

Spatial hashing is one of the most practical solutions to this problem. It reduces broad-phase collision detection to roughly O(n) per frame, scales well with object count, and can be implemented from scratch in an afternoon. It is used throughout the game industry for bullet-hell shooters, RTS unit management, fluid simulations, and procedural placement systems.

What Is Spatial Hashing?

Spatial hashing divides the game world into a uniform grid of rectangular cells. Each cell is a bucket in a hash map, storing references to every object that overlaps it. When you need to find potential collisions for an object, you compute which cells it occupies and look up only those buckets, rather than scanning every other object in the world.

The result: objects only ever collide with their neighbors, and finding those neighbors costs O(1) on average. If a typical cell contains three or four objects, you reduce 10,000 pair checks down to a handful. The more objects you add, the more dramatic the savings.

The term "spatial hashing" distinguishes this from a naive uniform grid. A true uniform grid requires allocating a 2D array large enough to span the world, which is expensive for large worlds. Spatial hashing uses a hash map (dictionary) instead, so only occupied cells consume memory, and the world can be effectively infinite.

The Math: Cells, Keys, and Hash Functions

Step 1: Choose a Cell Size

The most important parameter is the cell size $s$. The ideal value is roughly equal to the diameter of your most common dynamic object. This way, any single object overlaps at most a 2×2 block of cells (four cells in 2D), keeping insertion cost constant per object.

Given a circular object at position $(x, y)$ with radius $r$, the range of cells it overlaps is:

$$c_{x,\min} = \left\lfloor \frac{x - r}{s} \right\rfloor, \quad c_{x,\max} = \left\lfloor \frac{x + r}{s} \right\rfloor$$

$$c_{y,\min} = \left\lfloor \frac{y - r}{s} \right\rfloor, \quad c_{y,\max} = \left\lfloor \frac{y + r}{s} \right\rfloor$$

The object is inserted into every cell in the rectangle $[c_{x,\min}, c_{x,\max}] \times [c_{y,\min}, c_{y,\max}]$. For a circle with $r \leq s$, this is at most four cells.

Step 2: The Hash Function

We need to map a 2D integer cell coordinate $(c_x, c_y)$ to a single hash key. The simplest approach concatenates the coordinates as a string: "cx,cy". This is readable and easy to debug, but string allocation in a hot loop causes garbage collection pressure in JavaScript.

A faster approach uses large prime multipliers and XOR:

$$\text{key} = (c_x \cdot p_1) \oplus (c_y \cdot p_2)$$

where $p_1 = 73856093$ and $p_2 = 19349663$ are commonly used primes. The XOR distributes keys uniformly, minimizing hash collisions. For 3D, add a third prime $p_3 = 83492791$ for $c_z$:

$$\text{key} = (c_x \cdot p_1) \oplus (c_y \cdot p_2) \oplus (c_z \cdot p_3)$$

// Fast integer spatial hash key for 2D
function hashCell(cx, cy) {
  return (cx * 73856093) ^ (cy * 19349663);
}

// Insert one object into the spatial hash
function insert(hashMap, obj, cellSize) {
  const r = obj.radius;
  const x0 = Math.floor((obj.x - r) / cellSize);
  const x1 = Math.floor((obj.x + r) / cellSize);
  const y0 = Math.floor((obj.y - r) / cellSize);
  const y1 = Math.floor((obj.y + r) / cellSize);

  for (let cx = x0; cx <= x1; cx++) {
    for (let cy = y0; cy <= y1; cy++) {
      const key = hashCell(cx, cy);
      if (!hashMap.has(key)) hashMap.set(key, []);
      hashMap.get(key).push(obj);
    }
  }
}

Step 3: Querying for Candidate Pairs

After inserting all objects, every bucket (cell) that contains more than one object represents a group of potential colliders. Iterate over all buckets and test pairs within each bucket using your narrow-phase check (circle overlap, AABB test, SAT, etc.):

function getCandidatePairs(hashMap) {
  const pairs = [];
  const seen = new Set();

  for (const bucket of hashMap.values()) {
    for (let i = 0; i < bucket.length; i++) {
      for (let j = i + 1; j < bucket.length; j++) {
        const a = bucket[i], b = bucket[j];
        // Deduplicate: same pair may appear in multiple shared cells
        const pairKey = a.id < b.id
          ? a.id * 1000000 + b.id
          : b.id * 1000000 + a.id;
        if (!seen.has(pairKey)) {
          seen.add(pairKey);
          pairs.push([a, b]);
        }
      }
    }
  }
  return pairs;
}

The deduplication step with a Set is necessary because an object spanning multiple cells will appear in every cell it touches. Two objects that both span the same two cells would otherwise be checked twice. The pair key uses a canonical ordering ($\min(a, b)$ first) so $(a, b)$ and $(b, a)$ map to the same key.

A Complete Per-Frame Implementation

For scenes with moving objects, the standard approach is to rebuild the hash map from scratch each frame. This sounds wasteful, but clearing a JavaScript Map and reinserting $n$ objects is O(n) and cache-friendly, which is faster than tracking and updating only moved objects:

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

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

  _key(cx, cy) {
    return (cx * 73856093) ^ (cy * 19349663);
  }

  insert(obj) {
    const { x, y, radius: r } = obj;
    const s = this.cellSize;
    const x0 = Math.floor((x - r) / s), x1 = Math.floor((x + r) / s);
    const y0 = Math.floor((y - r) / s), y1 = Math.floor((y + r) / s);
    for (let cx = x0; cx <= x1; cx++) {
      for (let cy = y0; cy <= y1; cy++) {
        const k = this._key(cx, cy);
        if (!this.map.has(k)) this.map.set(k, []);
        this.map.get(k).push(obj);
      }
    }
  }

  getPairs() {
    const pairs = [], seen = new Set();
    for (const bucket of this.map.values()) {
      for (let i = 0; i < bucket.length; i++) {
        for (let j = i + 1; j < bucket.length; j++) {
          const [a, b] = [bucket[i], bucket[j]];
          const pk = a.id < b.id
            ? a.id * 1000000 + b.id
            : b.id * 1000000 + a.id;
          if (!seen.has(pk)) { seen.add(pk); pairs.push([a, b]); }
        }
      }
    }
    return pairs;
  }
}

// Game loop usage
const spatialHash = new SpatialHash(cellSize);

function update(dt) {
  spatialHash.clear();
  for (const obj of objects) {
    obj.update(dt);
    spatialHash.insert(obj);
  }
  for (const [a, b] of spatialHash.getPairs()) {
    if (narrowPhaseOverlap(a, b)) resolveCollision(a, b);
  }
}

Tuning Cell Size: The Critical Trade-off

Cell size controls a fundamental trade-off in spatial hashing performance:

• Too small: Each object spans many cells. Insertion cost rises. More redundant pairs appear from objects sharing many small cells. Memory usage increases for the deduplication set.
• Too large: Each cell holds many objects. Bucket iteration approaches O(n²) again. In the extreme case of one giant cell, you're back where you started.
• Sweet spot: Roughly 1–2× the diameter of your most common dynamic object. Each object then overlaps at most a 2×2 or 3×3 block of cells.

A useful diagnostic: instrument your game loop to log the average bucket size across all occupied cells. If the average exceeds 5–8 objects per cell, your cell size is too large. If most objects span more than 4 cells, it's too small.

When objects vary dramatically in size, say a tiny bullet alongside a massive boss enemy, a single cell size cannot serve both well. Common solutions include:

• Multiple hash maps, one per object category, each with a cell size tuned to that category (bullets vs. large enemies).
• Hierarchical spatial hashing, which uses several grid resolutions simultaneously, inserting objects into the level whose cell size best fits them.

Spatial Hashing vs. Quadtrees vs. BVH

Spatial hashing is not the only broad-phase acceleration structure. Knowing when to use something else matters as much as knowing how to implement it:

• Spatial hashing is fastest to build per frame (O(n)), simplest to implement, and performs best when objects are roughly uniform in size and distributed somewhat evenly. No tree balancing, no node splitting: just hash and go.
• Quadtrees (2D) / Octrees (3D) adapt to object distribution by subdividing only where needed. They handle clustered, sparse scenes better than spatial hashing, but building and maintaining them is more complex and carries higher constant-factor overhead.
• Dynamic AABB Trees / BVH (Bounding Volume Hierarchies) handle arbitrary size variation and tight clustering best. They are used internally by Box2D, Bullet Physics, and Unity's physics engine. The trade-off is significantly higher implementation complexity.

For arcade-style games, top-down shooters, fluid simulations, and any scene with many similarly-sized moving objects, spatial hashing is almost always the right first choice. Add complexity only when profiling shows it's necessary.

3D Extension

Extending to 3D adds one more loop dimension and a third prime to the hash function. A sphere at $(x, y, z)$ with radius $r$ occupies at most a 2×2×2 = 8-cell block:

function hashCell3D(cx, cy, cz) {
  return (cx * 73856093) ^ (cy * 19349663) ^ (cz * 83492791);
}

function insert3D(hashMap, obj, cellSize) {
  const { x, y, z, radius: r } = obj;
  const s = cellSize;
  for (let cx = Math.floor((x-r)/s); cx <= Math.floor((x+r)/s); cx++) {
    for (let cy = Math.floor((y-r)/s); cy <= Math.floor((y+r)/s); cy++) {
      for (let cz = Math.floor((z-r)/s); cz <= Math.floor((z+r)/s); cz++) {
        const key = hashCell3D(cx, cy, cz);
        if (!hashMap.has(key)) hashMap.set(key, []);
        hashMap.get(key).push(obj);
      }
    }
  }
}

Real-World Examples

Bullet-Heaven / Survivor-like Games

Games like Vampire Survivors and Brotato have thousands of projectiles, enemies, and pickups simultaneously active. Spatial hashing is a natural fit: all bullets are small and similar in size, the world is 2D, and objects are relatively evenly distributed. A naive frame with 1,000 projectiles and 200 enemies requires 200,000 pair checks; spatial hashing reduces this to the low hundreds.

SPH Fluid Simulations

Smoothed Particle Hydrodynamics (SPH) fluid simulations require each particle to gather all neighbors within a fixed smoothing radius $h$. This is exactly the spatial hash query. Every particle is inserted with cell size $h$, and each particle queries its 3×3 neighborhood of cells. This is the foundation of real-time water effects in games and physics middleware like Flex and PhysX.

Real-Time Strategy Games

RTS titles like StarCraft II manage hundreds or thousands of units performing range checks every frame (attack range, vision range, ability range). Units within a class are roughly uniform in size, making spatial hashing a good fit for the broad phase. Only when a unit finds candidates within its spatial hash cell does it do the precise distance check.

Procedural Asset Placement

When populating an open-world terrain with millions of trees, rocks, and props, each new object must verify it doesn't overlap existing placements. A spatial hash of all placed objects reduces each placement check from O(n) linear scan to O(1) lookup. This is the technique behind procedural forest generation in engines like Unreal and Godot.

Performance Tips for Production Code

• Avoid string keys. Integer keys are 3–10× faster to hash and compare than string keys in JavaScript. Use the prime XOR formula.
• Pre-allocate bucket arrays. Instead of pushing to dynamic arrays, use a flat typed array for all object references and a separate count array per bucket. This eliminates garbage collection pressure entirely.
• Fixed-size hash table. For predictable worst-case performance, use a power-of-2 table size with key & (TABLE_SIZE - 1) instead of modulo. This turns a division into a bitwise AND.
• Layer by collision group. Maintain separate hash maps for logical groups (e.g., "player bullets vs. enemies", "enemy bullets vs. player"). This avoids bullet-bullet checks entirely.
• Profile bucket sizes. Average bucket size above ~6 objects signals that cell size is too large. Below ~1.5 objects per occupied cell and most objects spanning more than 4 cells signals it's too small.

Summary

Spatial hashing transforms the O(n²) collision detection bottleneck into an O(n) operation by exploiting one simple fact: objects can only collide with their spatial neighbors. A hash map finds those neighbors in constant time. The implementation is straightforward, handles thousands of dynamic objects well, and extends cleanly to 3D or multi-layer architectures.

Whether you are building a bullet-hell shooter, a fluid simulation, or a procedural world generator, spatial hashing is worth knowing. The demo below puts some numbers to that claim.