Game Dev Mechanics: Quadtrees — How It Works

Quadtrees: The Data Structure That Makes Fast Games Possible

Every frame, a game engine asks a deceptively simple question: which objects are close enough to each other that they might be interacting? In a small scene with ten objects, you can check every pair — that's only 45 checks. But in a scene with 1,000 objects, naïve pairwise checking requires nearly 500,000 comparisons per frame. At 60 frames per second, that's 30 million wasted checks every second, most of them between objects on opposite sides of the map.

Quadtrees solve this problem elegantly. By recursively subdividing 2D space into four quadrants, they let you skip entire regions of the world at once. Instead of asking "does object A collide with every other object?", you ask "which quadrant is object A in?" — and then only check against objects in nearby quadrants. The result is collision detection that scales from hundreds of objects to tens of thousands without breaking a sweat.

The Core Idea: Divide and Conquer

A quadtree is a tree data structure where each internal node has exactly four children, corresponding to four spatial quadrants: top-left (NW), top-right (NE), bottom-left (SW), and bottom-right (SE). The root node covers the entire game world. When a quadrant contains more objects than a defined threshold (called the capacity), it splits into four smaller quadrants and redistributes its objects.

Visualize it like this: imagine your game world as a blank sheet of paper. You place objects on it. When one region gets crowded, you fold that section in half both ways, creating four smaller sections. If one of those gets crowded, you fold it again. You keep folding until every section has a manageable number of objects — or until the sections are too small to subdivide further.

The key insight is that objects in a far corner of the map are never checked against objects on the opposite side, because they live in completely different branches of the tree.

The Algorithm: Building a Quadtree

Each quadtree node stores:

• Its boundary — a rectangle defining what region of space it covers
• A capacity — the maximum number of objects before splitting
• A list of points/objects currently in this node
• Four optional child nodes (NW, NE, SW, SE)
• A boolean divided flag indicating whether it has been split

The insertion algorithm is recursive and straightforward:

class Rectangle {
  constructor(x, y, w, h) {
    this.x = x; // center x
    this.y = y; // center y
    this.w = w; // half-width
    this.h = h; // half-height
  }

  contains(point) {
    return (
      point.x >= this.x - this.w &&
      point.x <= this.x + this.w &&
      point.y >= this.y - this.h &&
      point.y <= this.y + this.h
    );
  }

  intersects(range) {
    return !(
      range.x - range.w > this.x + this.w ||
      range.x + range.w < this.x - this.w ||
      range.y - range.h > this.y + this.h ||
      range.y + range.h < this.y - this.h
    );
  }
}

class QuadTree {
  constructor(boundary, capacity) {
    this.boundary = boundary;
    this.capacity = capacity;
    this.points = [];
    this.divided = false;
  }

  insert(point) {
    // Ignore points outside this node's boundary
    if (!this.boundary.contains(point)) return false;

    // If there's room, add the point here
    if (this.points.length < this.capacity) {
      this.points.push(point);
      return true;
    }

    // Otherwise, subdivide and insert into children
    if (!this.divided) this.subdivide();

    return (
      this.northeast.insert(point) ||
      this.northwest.insert(point) ||
      this.southeast.insert(point) ||
      this.southwest.insert(point)
    );
  }

  subdivide() {
    const { x, y, w, h } = this.boundary;
    const ne = new Rectangle(x + w / 2, y - h / 2, w / 2, h / 2);
    const nw = new Rectangle(x - w / 2, y - h / 2, w / 2, h / 2);
    const se = new Rectangle(x + w / 2, y + h / 2, w / 2, h / 2);
    const sw = new Rectangle(x - w / 2, y + h / 2, w / 2, h / 2);

    this.northeast = new QuadTree(ne, this.capacity);
    this.northwest = new QuadTree(nw, this.capacity);
    this.southeast = new QuadTree(se, this.capacity);
    this.southwest = new QuadTree(sw, this.capacity);
    this.divided = true;
  }
}

Querying the Quadtree

Insertion is only half the story. The real power comes from range queries: given a search rectangle (or circle), find all objects within it. This is what makes collision detection fast — instead of checking every object, you query only the relevant region.

query(range, found = []) {
  // If the search range doesn't overlap this node, bail early
  if (!this.boundary.intersects(range)) return found;

  // Check each point in this node
  for (const p of this.points) {
    if (range.contains(p)) found.push(p);
  }

  // Recursively query children
  if (this.divided) {
    this.northwest.query(range, found);
    this.northeast.query(range, found);
    this.southwest.query(range, found);
    this.southeast.query(range, found);
  }

  return found;
}

The critical line is the first one: if (!this.boundary.intersects(range)) return found. This is the pruning step — if the search rectangle doesn't overlap a node's boundary at all, the entire subtree below it is skipped instantly. This is where the performance gains come from.

Complexity Analysis

For a uniformly distributed set of $n$ objects in a quadtree with capacity $k$:

$$\text{Tree depth} = \log_4\left(\frac{n}{k}\right)$$

A range query touching $r$ results examines roughly $O(r + \log n)$ nodes instead of $O(n)$. In practice, collision detection for each object only needs to query its immediate neighborhood, so the total work per frame scales far better than the naïve $O(n^2)$.

For the common case of collision detection where you query a small radius around each object:

$$\text{Naïve: } O(n^2) \quad \text{Quadtree: } O(n \log n)$$

That difference is night and day. With 10,000 objects, naïve checking requires 100 million comparisons; a quadtree brings that down to roughly 130,000.

Dynamic Quadtrees: Rebuilding Every Frame

In a game, objects move every frame. The simplest approach — and often the most practical — is to rebuild the quadtree from scratch each frame. This might sound wasteful, but construction is $O(n \log n)$ and very cache-friendly, often faster in practice than maintaining a dynamic structure with complex rebalancing.

function updatePhysics(objects, worldBounds) {
  // Rebuild the quadtree
  const qt = new QuadTree(worldBounds, 4);
  for (const obj of objects) qt.insert(obj);

  // Query each object's neighborhood
  for (const obj of objects) {
    const searchArea = new Rectangle(obj.x, obj.y, obj.radius * 2, obj.radius * 2);
    const nearby = qt.query(searchArea);

    for (const other of nearby) {
      if (other !== obj) checkCollision(obj, other);
    }
  }
}

The Capacity Parameter

Choosing the right capacity (how many objects a node holds before splitting) is a tuning decision. A capacity that's too small causes excessive subdivision — the tree becomes very deep, with lots of overhead per node. Too large, and nodes hold too many objects, reducing the effectiveness of pruning. Values between 4 and 16 work well for most games; the sweet spot depends on your object density and query patterns.

Handling Objects That Span Multiple Quadrants

A subtle challenge: large objects can overlap multiple quadrants. The classic solutions are:

• Insert at the lowest common ancestor — place the object in the node whose boundary fully contains it. Simple, but large objects end up near the root.
• Insert into all overlapping quadrants — duplicate the reference in every leaf it touches. More complex, requires deduplication during queries.
• Loose quadtrees — expand each node's effective boundary by a factor (e.g., 2×), so objects are inserted into the node whose center they fall in. This bounds duplication while keeping objects near their natural quadrant.
• Use bounding-box centers only — insert based on object center, use the query radius to compensate. Works well when objects have similar sizes.

For most games with similarly-sized objects, inserting by center and using a generous query radius is the pragmatic choice.

Real-World Usage in Games

Quadtrees appear throughout the game industry, often under the hood of physics engines and spatial APIs:

• Box2D uses a dynamic tree (a variant of a bounding-volume hierarchy, similar in spirit to quadtrees) for its broad-phase collision detection. Unity's 2D physics, which wraps Box2D, inherits this.
• Starcraft II's pathfinding and unit queries use spatial hashing and hierarchical spatial structures for its legendary handling of 200-unit battles.
• Minecraft-style voxel games use octrees (the 3D extension of quadtrees) for chunk visibility, collision, and ray queries.
• Real-time strategy games universally use some form of spatial partitioning for unit selection (click-drag selection boxes), fog of war, and attack range detection.
• Bullet Hell shooters need to check thousands of projectiles against the player and enemies every frame — a quadtree or spatial hash is essential for these to run at 60fps.

Quadtrees vs. Spatial Hashing

Quadtrees are often compared to spatial hashing, another popular spatial acceleration structure. Here's how they differ:

• Spatial hashing divides space into a fixed uniform grid, storing objects in hash buckets by their cell coordinates. It's very fast to insert and query, but the fixed cell size is a weakness — if objects vary greatly in size, you either waste memory (too small) or lose precision (too large).
• Quadtrees adapt to the actual distribution of objects. Dense regions subdivide deeply; sparse regions stay as large single nodes. This makes them superior for non-uniform distributions, but slightly more complex to implement.

A useful rule of thumb: if your objects are all roughly the same size and distributed somewhat uniformly, spatial hashing may be faster due to simpler cache behavior. If your scene has wildly varying density — an open world with cities and wilderness — quadtrees win decisively.

Extending to 3D: Octrees

The direct 3D analog is the octree, which splits each node into eight children (the eight octants of 3D space) instead of four. The algorithm is identical; you simply add a $z$ component to your boundary checks and subdivision logic. Octrees are used extensively in 3D game engines for frustum culling, ray-triangle intersection acceleration, and spatial queries in open-world games.

// 3D equivalent: Box boundary instead of Rectangle
class Box {
  constructor(x, y, z, w, h, d) {
    this.x = x; this.y = y; this.z = z;
    this.w = w; this.h = h; this.d = d; // half-extents
  }

  contains(point) {
    return (
      Math.abs(point.x - this.x) <= this.w &&
      Math.abs(point.y - this.y) <= this.h &&
      Math.abs(point.z - this.z) <= this.d
    );
  }
}
// OctTree follows the same pattern with 8 children instead of 4

Implementation Tips for Game Developers

• Pre-allocate node pools. Creating thousands of small objects every frame is hard on the garbage collector. Maintain a pool of pre-allocated node objects and reset them instead of allocating new ones.
• Flatten your tree for cache performance. A classic object-oriented tree with pointer chasing is cache-unfriendly. Consider storing nodes in a flat array where children are at predictable offsets.
• Profile before optimizing. Many games never need a quadtree — if you have fewer than a few hundred objects, the naïve $O(n^2)$ check is often fast enough and much simpler. Measure first.
• Consider your query shapes. Circular range queries ("find everything within radius $r$") are extremely common. After the rectangular quadtree query, add a secondary distance check to filter out corner objects: $d = \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2} \leq r$.

Quadtrees are one of those foundational data structures that, once you understand them, you'll find everywhere in game development. They're a perfect example of how a small algorithmic insight — recursively subdivide dense regions — can deliver an order-of-magnitude performance improvement with modest implementation complexity. Whether you're building a 2D bullet hell shooter or a sprawling strategy game, quadtrees are a tool worth having in your toolkit.