Introduction

Your game has hundreds of units on a battlefield. Each one needs to know which enemies are nearby. The naive approach: compare every unit to every other unit. That is O(n²). Double the units and you quadruple the work. It does not scale.

The fix: organize objects by where they are in space. Then when you ask "what is near this point" you only look at a small slice of the world instead of the entire thing.

The Problem.

function handleMelee(units: Unit[]) {
  for (let a = 0; a < units.length; a++) {
    for (let b = a + 1; b < units.length; b++) {
      if (distance(units[a], units[b]) < ATTACK_RANGE) {
        handleAttack(units[a], units[b]);
      }
    }
  }
}

Every unit checks every other unit. 100 units means ~5,000 checks. 1,000 units means ~500,000 checks. Per frame. Most of those checks are pointless because most units are nowhere near each other.

The Core Idea.

Divide your world into regions. Put each object in the region that matches its position. When you need to find nearby objects, only check the region the object is in and its neighbors. Skip everything else.

The simplest version of this: a flat grid.

The Grid.

Overlay a grid on your world. Each cell holds a list of the objects inside it. When checking for combat, only compare objects within the same cell.

class Grid {
  private cells: Map<string, Unit[]> = new Map();
  private cellSize: number;

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

  private key(x: number, y: number): string {
    const cx = Math.floor(x / this.cellSize);
    const cy = Math.floor(y / this.cellSize);
    return `\({cx},\){cy}`;
  }

  add(unit: Unit) {
    const k = this.key(unit.x, unit.y);
    if (!this.cells.has(k)) this.cells.set(k, []);
    this.cells.get(k)!.push(unit);
  }

  remove(unit: Unit) {
    const k = this.key(unit.x, unit.y);
    const cell = this.cells.get(k);
    if (!cell) return;
    const i = cell.indexOf(unit);
    if (i !== -1) cell.splice(i, 1);
  }

  move(unit: Unit, newX: number, newY: number) {
    const oldKey = this.key(unit.x, unit.y);
    const newKey = this.key(newX, newY);
    unit.x = newX;
    unit.y = newY;
    if (oldKey !== newKey) {
      this.remove(unit);
      this.add(unit);
    }
  }

  getNearby(x: number, y: number): Unit[] {
    const cx = Math.floor(x / this.cellSize);
    const cy = Math.floor(y / this.cellSize);
    const result: Unit[] = [];
    // Check this cell and all 8 neighbors.
    for (let dx = -1; dx <= 1; dx++) {
      for (let dy = -1; dy <= 1; dy++) {
        const cell = this.cells.get(`\({cx + dx},\){cy + dy}`);
        if (cell) result.push(...cell);
      }
    }
    return result;
  }
}

Now combat only compares units in the same neighborhood:

function handleMelee(grid: Grid, units: Unit[]) {
  for (const unit of units) {
    const nearby = grid.getNearby(unit.x, unit.y);
    for (const other of nearby) {
      if (other === unit) continue;
      if (distance(unit, other) < ATTACK_RANGE) {
        handleAttack(unit, other);
      }
    }
  }
}

Instead of checking against every unit in the game, you check against the handful that are actually close. The rest do not exist as far as this code is concerned.

Moving Objects.

When an object moves, you need to check if it crossed a cell boundary. If it did, remove it from the old cell and add it to the new one. If it stayed in the same cell, just update its position. This is cheap: a couple of index calculations and a pointer swap.

Cell Size Matters.

Too large: many objects per cell, you are back to checking too many pairs.

Too small: lots of empty cells wasting memory, and you have to check many neighboring cells for range queries.

A good starting point: make cells roughly the size of your largest interaction range. If your attack distance is 20 units, make cells 20x20. That way nearby objects are always in the same cell or direct neighbors.

Flat Grid vs Hierarchical.

A flat grid is the simplest option. Fixed cells, fixed memory, easy to update when objects move. Works great when objects are spread fairly evenly across the world.

When objects clump together, a flat grid breaks down. One cell gets overloaded while most sit empty. Hierarchical structures like quadtrees solve this. They subdivide crowded areas into smaller regions and leave empty areas as one big region. They adapt to where the objects actually are.

The trade off: hierarchical structures are more complex to implement and more expensive to update when objects move. If your objects are spread reasonably well, a flat grid is usually enough.

Common Spatial Partition Structures.

Grid: simplest. Fixed cells. Good for evenly distributed objects. Basically a bucket sort extended to 2D.

Quadtree: subdivides crowded areas recursively into four squares. Good balance between adaptability and simplicity. Its 3D version is called an octree.

BSP (binary space partition): splits space with planes. Often used for static level geometry. Basically a binary search tree in multiple dimensions.

K-d tree: similar to BSP but alternates which axis it splits on. Good for point queries.

Bounding volume hierarchy: groups objects into bounding boxes, then groups those boxes into bigger boxes. Good when objects have varying sizes. Also a binary search tree at its core.

When To Use It.

You have many objects with positions. You frequently ask "what is near X." The naive approach is too slow. That is it. If your object count is small enough that brute force works, do not bother.

Also consider: if your objects move a lot, you pay a cost to keep the partition updated. Make sure the savings from faster queries outweigh the cost of maintenance.

One Sentence Summary.

Do not search the entire world to find what is right next to you.