Spatial Partitioning (uniform grid)

Spatial Partitioning (uniform grid)

function buildGrid(entities, cellSize):
    grid = empty map from (cellX, cellY) -> list of entities
    for e in entities:
        cellX = floor(e.x / cellSize)
        cellY = floor(e.y / cellSize)
        grid[(cellX, cellY)].add(e)
    return grid

function nearbyEntities(entity, grid, cellSize):
    cellX = floor(entity.x / cellSize)
    cellY = floor(entity.y / cellSize)
    result = []
    for dx in [-1, 0, 1]:
        for dy in [-1, 0, 1]:
            result += grid.get((cellX+dx, cellY+dy), [])
    return result

Spatial partitioning addresses the real bottleneck: naive collision checking is O(n²) — every object checked against every other. A uniform grid buckets objects by position so you only check pairs within the same or neighboring cells, dropping the practical cost close to O(n) for evenly distributed objects. The tradeoff is choosing a good cell size — too small and objects span many cells, too large and cells become crowded and you're back to near-O(n²) inside each one. Quadtrees solve the same problem adaptively for unevenly distributed objects, subdividing dense regions further.