How to Build: Spatial Hash

When the combat system needs to find enemies within aggro range of the player, the naive approach is to loop through every enemy entity in the world and check the distance. With 10 enemies, that's fine. With 200 enemies spread across a large level, you're burning cycles checking entities that are nowhere near the player.

A spatial hash solves this by dividing the world into a grid of cells. Each entity is "hashed" into the cell it occupies based on its position. When you need to find nearby entities, you only check entities in the same cell and its immediate neighbors. The query goes from O(n) to O(k) where k is the number of entities in nearby cells -- usually a tiny fraction of the total.

The SpatialGrid class

The entire data structure fits in one class with three methods:

class SpatialGrid {
  constructor(cellSize: number)
  insert(entity: Entity, x: number, z: number): void
  query(x: number, z: number, radius: number): Entity[]
  clear(): void
}

The cellSize parameter controls how large each cell is in world units. A cell size of 50 means each cell covers a 50x50 area. Since the aggro radius is about 2 hex tiles (roughly 10-15 world units), any entity within aggro range is guaranteed to be in the same cell or an adjacent cell. Picking a cell size that's comfortably larger than your largest query radius means you only need to check a 3x3 neighborhood.

How insert works

Convert the world position to a cell coordinate by dividing by cellSize and flooring. Use the cell coordinate as a key into a Map<string, Set<Entity>>. Add the entity to that cell's set.

How query works

Convert the query position to a cell coordinate the same way. Calculate how many cells the radius spans (Math.ceil(radius / cellSize)). Then iterate over a square of cells centered on the query cell, collecting all entities from each cell.

query(x: number, z: number, radius: number): Entity[] {
  const results: Entity[] = []
  const cellRadius = Math.ceil(radius / this.cellSize)
  const cx = Math.floor(x / this.cellSize)
  const cz = Math.floor(z / this.cellSize)

  for (let dx = -cellRadius; dx <= cellRadius; dx++) {
    for (let dz = -cellRadius; dz <= cellRadius; dz++) {
      const cell = this.cells.get(`${cx + dx},${cz + dz}`)
      if (cell) cell.forEach(e => results.push(e))
    }
  }
  return results
}

Notice that this returns all entities in nearby cells, not just those within the exact radius. The caller is responsible for the precise distance check if needed. For combat aggro, the slight over-reporting doesn't matter -- a secondary filter like entity.has(IsEnemy) && !entity.has(IsDead) handles it.

How clear works

Just this.cells.clear(). Wipe the entire map. We rebuild it every frame anyway.

The per-frame update system

Every frame, clear the grid and re-insert all positioned entities:

function updateSpatialHashing(world: World): void

This system queries all entities with a Transform trait, reads their position, and inserts them into the grid. Because we clear and rebuild every frame, destroyed entities are automatically excluded -- there's no need for a separate cleanup pass to remove dead references.

You might wonder: isn't clearing and rebuilding every frame wasteful? In practice, the insert operation is just a hash lookup and a set add. For a few hundred entities, this takes microseconds. The alternative -- tracking entity movement and updating cells incrementally -- adds complexity for negligible performance gain at our entity count.

The world-level trait

The spatial grid lives as a world-level trait in Koota:

const SpatialHashMap = trait(() => new SpatialGrid(50))

This means there's exactly one grid instance, accessible from any system via world.get(SpatialHashMap). The cell size of 50 is a reasonable default -- large enough to contain any aggro radius query in a 3x3 cell check, small enough that cells aren't packed with hundreds of entities.

Using it from combat

The combat system queries the spatial hash to find enemies near the player:

const grid = world.get(SpatialHashMap)
const playerPos = player.get(Transform).position
const nearby = grid.query(playerPos.x, playerPos.z, AGGRO_RADIUS_WORLD_UNITS)
const enemies = nearby.filter(e => e.has(IsEnemy) && !e.has(IsDead))

Two lines to find nearby entities, one line to filter to living enemies. Compare this to the naive approach of iterating every entity in the world -- the spatial hash keeps the combat system clean and fast.

File organization

src/core/utils/spatial-hash.ts                # SpatialGrid class
src/core/systems/update-spatial-hashing.ts     # Per-frame clear + re-insert system

That's the entire spatial hash implementation. It's one of those systems that's simple to build, easy to forget about once it's working, and quietly makes everything that depends on proximity queries fast. Combat aggro, auto-targeting, area-of-effect abilities -- they all benefit from this foundation.