Build a 2D Spatial Hash Grid in TypeScript for Fast Collision

If you have ever attempted to build a survivor-like or bullet-hell shooter in the browser, you know the exact moment your dreams shatter. Everything runs like butter with 50 slimes on screen. Then your spawner hits 1,500 active projectiles, your laptop fan mimics a jet spooling up at Heathrow, and your lovely 60 FPS plunges straight down to a grim, juddering slideshow.

The culprit is almost always naive collision detection: checking every single entity against every other entity. That is classic $O(n^2)$ maths, and JavaScript engines will happily punish you for it.

Here is the good news: you do not need an over-engineered dynamic bounding-volume tree to fix it. A 2D spatial hash grid built in clean TypeScript provides lightning-fast broadphase collision checks without melting mobile browsers.

Direct Answer: What Is a 2D Spatial Hash Grid?

Spatial Hash Grid Definition:

A spatial hash grid is a 2D spatial partitioning data structure that subdivides a game world into uniform square cells. Entities register themselves into these cells based on their current world coordinates. When running collision checks, an object queries only its immediate neighbourhood of cells rather than checking every entity across the entire game scene, dropping average-case collision complexity from $O(n^2)$ to roughly $O(n)$.

The Broadphase Collision Bottleneck

Broadphase collision detection exists solely to discard pairs of entities that cannot possibly be touching. If an arrow is at $(10, 15)$ and a zombie is wandering around at $(900, 450)$, testing their bounding boxes is a waste of clock cycles.

While quadtrees are the darling of computer science lectures, real-world gamedev discussions across GitHub and web tech forums consistently point out their main browser drawback: constant object allocations and branchy node traversals trigger JavaScript's dreaded garbage collector.

A spatial hash grid bypasses this by using a flat mathematical mapping.

Implementing the Grid in TypeScript

To keep this lean and fast, we map floating-point coordinates into distinct integer cell coordinates using a fixed cellSize, then combine them into a string or 32-bit hash key.

Here is a streamlined implementation ready for your HTML5 canvas or Pixi.js loop:

export interface Entity {
  id: number;
  x: number;
  y: number;
  radius: number;
}

export class SpatialHashGrid<T extends Entity> {
  private cellSize: number;
  private cells: Map<string, T[]>;

  constructor(cellSize: number) {
    this.cellSize = cellSize;
    this.cells = new Map();
  }

  private getKey(cellX: number, cellY: number): string {
    return `${cellX}:${cellY}`;
  }

  public clear(): void {
    this.cells.clear();
  }

  public insert(entity: T): void {
    const minX = Math.floor((entity.x - entity.radius) / this.cellSize);
    const maxX = Math.floor((entity.x + entity.radius) / this.cellSize);
    const minY = Math.floor((entity.y - entity.radius) / this.cellSize);
    const maxY = Math.floor((entity.y + entity.radius) / this.cellSize);

    for (let x = minX; x <= maxX; x++) {
      for (let y = minY; y <= maxY; y++) {
        const key = this.getKey(x, y);
        let bucket = this.cells.get(key);
        if (!bucket) {
          bucket = [];
          this.cells.set(key, bucket);
        }
        bucket.push(entity);
      }
    }
  }

  public query(entity: T): T[] {
    const minX = Math.floor((entity.x - entity.radius) / this.cellSize);
    const maxX = Math.floor((entity.x + entity.radius) / this.cellSize);
    const minY = Math.floor((entity.y - entity.radius) / this.cellSize);
    const maxY = Math.floor((entity.y + entity.radius) / this.cellSize);

    const candidates = new Set<T>();

    for (let x = minX; x <= maxX; x++) {
      for (let y = minY; y <= maxY; y++) {
        const bucket = this.cells.get(this.getKey(x, y));
        if (bucket) {
          for (let i = 0; i < bucket.length; i++) {
            const candidate = bucket[i];
            if (candidate.id !== entity.id) {
              candidates.add(candidate);
            }
          }
        }
      }
    }

    return Array.from(candidates);
  }
}

Fine-Tuning Grid Performance

A spatial hash is only as clever as your configuration. Tuning requires avoiding two sneaky developer traps:

1. Choosing the Right Cell Size

A handy rule of thumb validated by countless indie tech post-mortems: make your cell size roughly double the diameter of your average entity.

• If your cells are tiny (say, 8 pixels), large entities span 16 different buckets, creating massive duplicate entries.
• If your cells are massive (say, 500 pixels), everything clumps into one cell, dragging you right back to naive $O(n^2)$ hell.

2. Guarding Against Garbage Collection Stalls

In the quick example above, this.cells.clear() drops arrays for garbage collection every frame, which can introduce micro-stutters. In production:

• Keep a persistent pool of array instances.
• Clear the arrays by setting bucket.length = 0 rather than instantiating new arrays or dropping keys.
• If you know your world bounds, replace the string keys (${x}:${y}) with a flat 1D index: (x * gridWidth) + y.

Key Takeaways

• Avoid Pairwise Checks: Any browser game dealing with hundreds of active bullets, enemies, or pick-ups needs spatial partitioning.
• Quadtrees Aren't King: Quadtrees require frequent branch splitting and pointer tracking. Spatial hashes rely on constant-time grid lookups, making them simpler and faster for moving crowds.
• Keep Buckets Sized Right: Size cells roughly twice the size of your standard sprite hitbox for the best balance between candidate density and grid overhead.
• Watch Allocations: Minimise runtime GC pauses by clearing bucket arrays in place instead of creating new objects inside your render or tick loop.