Spatial partitioning
Testing every object against every other is n²/2 tests, and n² is a cliff. 200 objects is 20,000 tests a frame — fine. 2,000 objects is two million, and 2,000 is not a big level. The job of a broadphase is to throw away the 99.9% of pairs that are nowhere near each other, cheaply, so narrowphase only ever sees plausible candidates.
That split matters: broadphase produces candidate pairs; narrowphase confirms them. Broadphase is allowed to be sloppy and return pairs that turn out not to touch. It is never allowed to miss a real pair.
The structures, and what each is actually for
Uniform grid / spatial hash — best when objects are similar in size and reasonably spread out. Divide space into fixed cells, drop each object into the cells its bounding box covers, then only test objects sharing a cell. Insert is O(1) arithmetic, with no tree to walk. A spatial hash is the same idea with a hash map instead of an array, so the world can be unbounded. Cell size should be roughly the size of your average object: too small and one object spans many cells, too large and each cell degenerates toward brute force. The failure mode is clustering — a thousand objects piled into one cell is brute force again, with extra steps.
Quadtree (2D) / octree (3D) — adapts to clustering. Each node splits into four or eight children when it exceeds a capacity. Dense areas subdivide deep, empty areas stay a single node, so uneven distributions cost what they should. You pay for it in pointer-chasing and in rebuild cost.
BVH — the right answer for static geometry and for raycasts. A tree of nested AABBs built bottom-up over the level once at load. A ray or a query box descends it in O(log n), skipping whole subtrees by one AABB test. This is also what raytracing uses; it is the same structure.
Sort and sweep (sweep and prune) — sort AABBs by their min on one axis, then walk the list. You only need to compare an object against the ones whose intervals haven't ended yet. Nearly free to maintain frame to frame, because mostly-coherent motion means the sorted list is almost already sorted (insertion sort loves this). Degrades when everything is lined up along the sweep axis.
Moving objects: rebuild or refit
Dynamic bodies rebuild, static geometry refits — or is built once and left alone. Grids are cleared and refilled every frame; that's cheap enough to be the norm. Trees are more expensive, so a BVH over moving objects is usually refit instead — keep the topology, just re-expand each node's AABB bottom-up. Refit is fast but the tree's quality decays as objects drift apart, so engines periodically rebuild. The common production split is one grid or dynamic tree for movers, one static BVH for the world, and three query passes: mover–mover, mover–world, done.
Demo
Several hundred circles, three broadphases, live pair counts — drag the count slider with brute force selected, then switch to the grid. The pair-test number is the entire argument.
Gotchas
| Symptom | Cause |
|---|---|
| Grid no faster than brute force | Cell size far off object size, or everything clustered in one cell |
| Collisions resolved twice, objects jolt | Pairs duplicated because two objects share more than one cell; dedupe per query |
| Rare missed collisions | Object inserted by centre instead of by its full bounding box |
| Broadphase cost dominates the frame | Rebuilding a tree every frame where a grid or a refit would do |
| Fine with 100 objects, dies at 2,000 | Still O(n²) somewhere — often the "which cells do I overlap" loop |
| Raycasts slow despite a grid | Grids are for overlap queries; rays want a BVH |
| Objects outside the grid bounds vanish | Fixed-array grid with no clamping or hashing; clamp into edge cells |