Spatial hashing

Checking all pairs of entities for collision is O(n²). A grid-based spatial hash reduces lookup to O(1) by assigning entities to cells and only testing neighbours.

A game with 200 entities checks 200 × 199 / 2 = 19,900 pairs for collision every frame. At 500 entities that becomes 124,750. At 1,000 entities: almost half a million. Even cheap rectangle checks become a measurable frame-rate cost at these scales. This is the O(n²) problem: work grows as the square of entity count.

Spatial hashing solves it by observing that two entities more than twice the largest entity's radius apart can never collide — there is no point checking them.

The grid idea

Divide the game world into a grid of cells. Each cell has a size chosen to match the largest entity (or twice the collision radius, whichever is larger). When an entity is inserted, determine which cell(s) it overlaps and add it to those cells' lists.

To find collision candidates for entity E:

Determine which cell(s) E overlaps.
Return the contents of those cells and their immediate neighbours.

Only entities in the same or adjacent cells are tested. Entities in distant cells are never touched. For uniformly distributed entities the average number of entities per neighbourhood is roughly constant, so each query is O(1) regardless of total entity count. Total collision work is O(n).

Implementation

from collections import defaultdict

class SpatialHash:
    def __init__(self, cell_size):
        self.cell_size = cell_size
        self._cells    = defaultdict(list)

    def _cell(self, x, y):
        """Map a world coordinate to a cell (col, row) key."""
        return (int(x // self.cell_size), int(y // self.cell_size))

    def insert(self, entity, rect):
        """
        Add entity to every cell its rect overlaps.
        Call clear() + re-insert all entities each frame.
        """
        min_cx, min_cy = self._cell(rect.left,  rect.top)
        max_cx, max_cy = self._cell(rect.right, rect.bottom)
        for cx in range(min_cx, max_cx + 1):
            for cy in range(min_cy, max_cy + 1):
                self._cells[(cx, cy)].append(entity)

    def query(self, rect):
        """
        Return all entities in cells overlapping rect (may include duplicates).
        The caller is responsible for deduplication if needed.
        """
        min_cx, min_cy = self._cell(rect.left,  rect.top)
        max_cx, max_cy = self._cell(rect.right, rect.bottom)
        seen    = set()
        results = []
        for cx in range(min_cx, max_cx + 1):
            for cy in range(min_cy, max_cy + 1):
                for entity in self._cells.get((cx, cy), []):
                    if id(entity) not in seen:
                        seen.add(id(entity))
                        results.append(entity)
        return results

    def clear(self):
        self._cells.clear()

Usage in the game loop:

spatial_hash = SpatialHash(cell_size=64)

# Each frame: rebuild, then query
spatial_hash.clear()
for entity in entities:
    spatial_hash.insert(entity, entity.rect)

# Collision detection: only test nearby entities
for entity in entities:
    nearby = spatial_hash.query(entity.rect)
    for other in nearby:
        if other is entity:
            continue
        if entity.rect.colliderect(other.rect):
            resolve_collision(entity, other)

Choosing the cell size

Too small — entities span many cells, insertion is slow, and the cell dictionary grows large.
Too large — many entities share a cell, defeating the purpose.
Rule of thumb — set cell_size to 2× the diameter of the largest entity. Tweak based on profiling if needed.

When to use it

Spatial hashing is worth adding when:

You have more than ~100 simultaneously active entities.
Collision checking is measurably eating frame budget (pygame.time.Clock.get_fps() drops when enemies spawn).
Entities are reasonably uniformly distributed (not all clustered in one corner).

For fewer entities, pygame's groupcollide or spritecollide with a spatial group is fast enough and requires no extra infrastructure.

The spatial hash is rebuilt from scratch every frame (clear() then re-insert). This is simpler and faster than incremental updates for objects that move each frame. The defaultdict allocation is cheap because it only creates entries for populated cells.

Finished reading? Mark it complete to track your progress.

The grid idea

Implementation

Choosing the cell size

When to use it

On this page