Spatial Partitioning in 2D Games: Quadtrees, Spatial Hashing & Collision Optimization

The Quadratic Collapse of Naive Collision Detection

Consider a top-down arena shooter or bullet hell game with $N$ active projectiles, enemies, and obstacles. The naive approach iterates over all entities using nested loops:

// Evaluating 1,000 entities = 499,500 collision tests per frame!
for (let i = 0; i < entities.length; i++) {
  for (let j = i + 1; j < entities.length; j++) {
    if (checkIntersection(entities[i], entities[j])) {
      resolveCollision(entities[i], entities[j]);
    }
  }
}

The mathematical complexity is $O(N^2)$, specifically $rac{N(N - 1)}{2}$ collision tests. At 100 entities, 4,950 checks are manageable. At 2,000 entities, the engine must perform nearly 2,000,000 complex intersection calculations 60 times per second. In single-threaded JavaScript, this locks up the CPU, triggering severe frame drops.

Quadtrees: Hierarchical Recursive Spatial Subdivision

A Quadtree is a 2D spatial tree structure where each node represents a rectangular boundary. As entities are inserted, a node tracks its population. When the entity count within a node exceeds a predefined capacity (e.g. 4 to 8 entities) and the node has not reached the maximum depth limit, it subdivides into four equal quadrants:

• North-West (NW): Upper-left quadrant
• North-East (NE): Upper-right quadrant
• South-West (SW): Lower-left quadrant
• South-East (SE): Lower-right quadrant

When querying collision candidates for a moving entity, the engine traverses only the tree nodes that intersect that entity's Axis-Aligned Bounding Box (AABB). Entities residing on opposite ends of the map are never compared, reducing computational complexity from $O(N^2)$ to $O(N log N)$.

export interface Rect { x: number; y: number; width: number; height: number; }

export class Quadtree<T extends { bounds: Rect }> {
  private bounds: Rect;
  private capacity: number;
  private depth: number;
  private maxDepth: number;
  private objects: T[] = [];
  private nodes: Quadtree<T>[] = [];

  constructor(bounds: Rect, capacity: number = 4, depth: number = 0, maxDepth: number = 6) {
    this.bounds = bounds;
    this.capacity = capacity;
    this.depth = depth;
    this.maxDepth = maxDepth;
  }

  public insert(obj: T): void {
    if (this.nodes.length > 0) {
      const idx = this.getIndex(obj.bounds);
      if (idx !== -1) {
        this.nodes[idx].insert(obj);
        return;
      }
    }

    this.objects.push(obj);

    if (this.objects.length > this.capacity && this.depth < this.maxDepth) {
      if (this.nodes.length === 0) this.subdivide();

      let i = 0;
      while (i < this.objects.length) {
        const idx = this.getIndex(this.objects[i].bounds);
        if (idx !== -1) {
          const removed = this.objects.splice(i, 1)[0];
          this.nodes[idx].insert(removed);
        } else {
          i++;
        }
      }
    }
  }

  public retrieve(returnList: T[], bounds: Rect): T[] {
    const idx = this.getIndex(bounds);
    if (idx !== -1 && this.nodes.length > 0) {
      this.nodes[idx].retrieve(returnList, bounds);
    } else if (this.nodes.length > 0) {
      for (const node of this.nodes) node.retrieve(returnList, bounds);
    }

    returnList.push(...this.objects);
    return returnList;
  }

  private subdivide(): void {
    const hw = this.bounds.width / 2;
    const hh = this.bounds.height / 2;
    const x = this.bounds.x;
    const y = this.bounds.y;

    this.nodes[0] = new Quadtree({ x: x + hw, y, width: hw, height: hh }, this.capacity, this.depth + 1, this.maxDepth);
    this.nodes[1] = new Quadtree({ x, y, width: hw, height: hh }, this.capacity, this.depth + 1, this.maxDepth);
    this.nodes[2] = new Quadtree({ x, y: y + hh, width: hw, height: hh }, this.capacity, this.depth + 1, this.maxDepth);
    this.nodes[3] = new Quadtree({ x: x + hw, y: y + hh, width: hw, height: hh }, this.capacity, this.depth + 1, this.maxDepth);
  }

  private getIndex(rect: Rect): number {
    const midX = this.bounds.x + this.bounds.width / 2;
    const midY = this.bounds.y + this.bounds.height / 2;
    const top = rect.y < midY && rect.y + rect.height < midY;
    const bot = rect.y > midY;
    if (rect.x < midX && rect.x + rect.width < midX) {
      if (top) return 1;
      if (bot) return 2;
    } else if (rect.x > midX) {
      if (top) return 0;
      if (bot) return 3;
    }
    return -1; // Intersects boundary
  }
}

Spatial Hashing: Constant-Time O(1) Bucket Indexing

While Quadtrees provide adaptive granularity for clustered entities, they require continuous object allocation and pointer traversal. In games where entities move dynamically across the map every frame, re-inserting thousands of actors into a Quadtree triggers memory fragmentation.

Spatial Hashing replaces tree pointers with a flat mathematical grid. The entire game world is partitioned into uniform grid cells of size $S imes S$ (where $S$ is typically $2 imes$ the diameter of an average entity).

Each entity computes which grid cells its bounding box overlaps and registers its pointer into a hash map or flat array:

ext{hashKey}(x, y) = lfloor x / S floor imes 73856093 oplus lfloor y / S floor imes 19349663

Insertion and query lookups execute in guaranteed $O(1)$ constant time. To test collisions for entity $A$, the engine simply inspects the entities present in entity $A$'s immediate grid cell and adjacent 8 neighbors, achieving blistering throughput with zero tree rebalancing.

Broad-Phase vs. Narrow-Phase Architecture

High-performance collision engines operate in two distinct architectural tiers:

1. The Broad-Phase: Uses spatial partitioning (Quadtree or Spatial Hash) and coarse Axis-Aligned Bounding Boxes (AABBs) to prune away 99% of impossible collisions at near-zero CPU cost.
2. The Narrow-Phase: Takes only the surviving candidate pairs from the broad-phase and executes exact, computationally expensive mathematical collision routines—such as the Separating Axis Theorem (SAT) for oriented bounding boxes (OBB) or convex polygon Minkowski difference calculations.

Comparative Architectural Matrix: 2D Spatial Partitioning

Comparing performance and capabilities across spatial partitioning algorithms:

Conclusion

Eliminating quadratic collision bottlenecks is mandatory for professional web game engineering. By routing collision queries through Quadtrees for static multi-scale geometry and Spatial Hashing for high-speed dynamic entities, developers ensure steady 60 FPS performance across complex interactive browser simulations.