To make thousands of objects fast, only test things that are near each other. Spatial data structures — grids, quadtrees, and BVHs — organize objects by location so the broad phase stays cheap.
Even with bounding volumes, comparing every object to every other is quadratic and collapses with scale. Spatial partitioning organizes objects by where they are so you only compare objects that share a region of space. This is the structural fix behind a fast broad phase, and the same structures accelerate rendering culling and ray casts.
Goal: given thousands of objects, quickly find only the NEARBY pairs.
brute force every pair -> O(n²) (dies at scale)
spatial partition bucket objects by LOCATION, only compare within/near a
bucket -> near O(n) in practice
The idea: two objects can only collide if they're close, so DON'T compare
distant ones. Partitioning structures organize space so "who's near me?" is fast.
(The same structures speed up render culling + ray casting.)The simplest partition is a uniform grid: divide space into fixed cells and put each object in the cell(s) it overlaps. To find collisions you only compare objects sharing a cell. Grids are trivial to build and update and work beautifully when objects are similar in size and evenly spread — think a bullet-hell shooter. They struggle when object sizes vary wildly.
from collections import defaultdict
def build_grid(objects, cell_size):
grid = defaultdict(list)
for obj in objects: # obj = (id, x, y)
cx, cy = int(obj[1] // cell_size), int(obj[2] // cell_size)
grid[(cx, cy)].append(obj)
return grid
def candidate_pairs(grid):
pairs = []
for cell_objects in grid.values():
for i in range(len(cell_objects)): # only compare within a cell
for j in range(i+1, len(cell_objects)):
pairs.append((cell_objects[i][0], cell_objects[j][0]))
return pairs
# fast + simple when objects are similar in size and evenly spread.When objects cluster or vary in size, a uniform grid wastes memory or over-fills cells. A quadtree (2D) or octree (3D) adapts by subdividing only dense regions: a node splits into four/eight children when it holds too many objects. This gives fine resolution where it is needed and coarse elsewhere, handling non-uniform scenes far better than a fixed grid.
class Quadtree:
def __init__(self, bounds, capacity=4):
self.bounds = bounds # (x, y, w, h)
self.capacity = capacity
self.objects = []
self.children = None
def insert(self, obj):
self.objects.append(obj)
# subdivide only when a node gets crowded -> fine detail where needed
if len(self.objects) > self.capacity and self.children is None:
self.subdivide()
def subdivide(self):
x, y, w, h = self.bounds
hw, hh = w/2, h/2
self.children = [Quadtree((x, y, hw, hh)), Quadtree((x+hw, y, hw, hh)),
Quadtree((x, y+hh, hw, hh)), Quadtree((x+hw, y+hh, hw, hh))]
# adapts to clustering: dense areas subdivide, empty areas stay coarse.A bounding volume hierarchy (BVH) is a tree of nested bounding volumes: each node’s box contains its children’s boxes. To test or ray-cast, you descend only into nodes whose box is hit, skipping whole subtrees cheaply. BVHs (often with AABBs, "AABB trees") are the go-to for complex or static geometry and are also the backbone of modern ray tracing. The right structure depends on your scene — grid for uniform, quadtree for clustered, BVH for complex geometry.
BVH (bounding volume hierarchy): a TREE of nested bounding boxes.
[ box around everything ]
/ \
[box: left half] [box: right half]
/ \ / \
objects objects objects objects
test/ray-cast: descend only into child boxes that are HIT; skip whole
subtrees whose box is missed -> O(log n) queries.
Choosing a structure:
uniform-size, spread out -> uniform grid
clustered / varied sizes -> quadtree / octree
complex or static meshes -> BVH (AABB tree) — also powers ray tracing