Spatial simulations often ask a deceptively simple question: which bodies are close enough to matter? The expensive answer is to measure every body. A quadtree gives a cheaper first response: ask only the quadrants that intersect the search area, then perform exact checks on what they return.
Move the pointer across the model. The proof-red circle is the requested neighborhood; chartreuse points are exact matches. The recursive grid changes with population and split pressure, making the broad phase visible rather than hiding it behind a performance claim.
A movable query over a recursive spatial index
INTERACTIVE- Start by moving apart ✓
- A group can still disagree ✓
- Alignment creates a flock ✓
- Limit who can matter +
Move the query across the index, then drag its green rim. Candidate and exact-hit counts should update independently.
Accessible experiment transcript
Points recursively subdivide the plane; a movable query radius highlights only candidates returned from intersecting cells. Canvas gesture: move to query; drag the ring to resize.
A tree made from rectangles
The root node begins with the whole canvas. It stores bodies until its capacity is exceeded. If the maximum depth has not been reached, it creates four child rectangles—top-left, top-right, bottom-left, and bottom-right—then reinserts its current children.
The archived implementation accepts both points and bodies with width and height. A body can intersect more than one child, so insertion may place the same object into several branches. That makes a later deduplication step necessary.
Capacity creates structure only when it is needed
FOLLOW THE ARROWSA point or body enters the smallest current node that contains its corners.
Accessible diagram transcript
Insertion tests node capacity. A full node below maximum depth splits into four and recursively redistributes its children.
Querying is deliberately incomplete
The query begins with a region. Each node asks which child quadrants that region touches and visits only those branches. The result is a broad-phase candidate array, not a geometric guarantee.
This distinction is easy to miss in visual demos. A point can share an intersecting quadrant while still sitting outside a circular perception radius. A rectangular body can span several cells and appear more than once. The caller therefore needs two follow-up operations:
- remove duplicate object references;
- apply the exact shape or distance test required by the domain.
The tree returns candidates; geometry returns truth
FOLLOW THE ARROWSA square or radius defines the requested neighborhood.
Accessible diagram transcript
A query shape selects intersecting cells, deduplicates candidates, then applies exact geometry before returning verified results.
What the grid teaches
A uniform grid allocates equal attention everywhere. A quadtree allocates detail where bodies cluster. Sparse regions remain broad; dense regions split until capacity or maximum depth stops the recursion.
That makes it suitable for the boids experiment, collision broad phases, selection tools, and other uneven 2D fields. It is less magical than its diagrams suggest. A poor capacity, shallow depth, or highly overlapping set of large bodies can still produce large candidate lists. Rebuilding the tree every animation frame also has a cost.
The original repository exposes maximum capacity, depth, query shape, debugging outlines, and candidate stats. Its most important design decision is that the quadtree remains a reusable utility instead of absorbing boid-specific behavior.
The next experiment
I would add a side-by-side counter: total bodies, cells visited, broad-phase candidates, duplicates removed, and exact matches. Then I would let the reader switch between all-pairs, a uniform grid, and the quadtree on the same point distribution.
Performance becomes understandable when the reader can see where work disappeared. The quadtree’s contribution is not that it knows what is near. It knows where not to look.