quadtrees

I ran into performance issues in several simulations. Agents and particles were doing neighbor comparisons, and in the worst case the update step devolved into $N^2$ checks. For a while I treated it as an unavoidable tax of realism: if every particle can influence every other particle, perhaps every pair must be tested.

But intuition kept interrupting that assumption. Most particles do not need global awareness to behave locally. Influence is usually spatial, and locality is exploitable.

A QuadTree is a hierarchical spatial data structure that recursively subdivides a 2D space into quadrants. Each node is a rectangular region; each region can split into four child regions once capacity is exceeded. Instead of placing all points in one flat list, we place them into a structure that mirrors physical proximity.

Suppose each particle needs its 3 nearest neighbors to update state. The naive approach compares against all particles: expensive and redundant. With a QuadTree, query time is focused on relevant regions. Subtrees that do not intersect the search range are skipped immediately.

• naive global comparisons trend toward $N^2$,
• spatial indexing can push expected behavior toward $N \log_2 N$ for build/query patterns,
• and in real scenes (e.g., 1000 particles), speedups can exceed 100x depending on density and query radius.

A QuadTree has two primary operations:

1. Insert(point) Place a particle into the proper region. Each node has a capacity (I often use 8 or 16). When capacity is reached, subdivide into 4 children and redistribute or continue insertion.
2. Query(range) Traverse from root. If a node’s bounds do not intersect the query region, skip that subtree. If they do intersect, inspect local points and recurse. This yields roughly $\log_2(N) + K$ behavior per query, where (K) is returned points.

The QuadTree is not merely an optimization trick; it is a statement: global ignorance is acceptable when local fidelity is enough. You do not accelerate simulations by making particles smarter. You accelerate them by making search space smaller.

In high-agent systems, performance is often less about arithmetic and more about architecture. When structure aligns with physics, complexity falls out almost as a side effect.

The lesson is simple: if your world is local, your data structure should be too.