A quadtree spatial index written from
scratch in ~200 lines of Rust (src/quadtree.rs, no
dependencies beyond Bevy's math types), with an interactive Bevy visualization
that uses it for real work: collision detection between 1000 moving points.
- 1000 points drifting randomly and pushing each other apart on contact
- grey rectangles — the quadtree cells, re-subdividing live as points move
- a white rectangle following the cursor — a range query against the tree
- red points — the query results
| Input | Action |
|---|---|
| Left mouse (hold) | Draw new points |
| Right/middle mouse (drag) | Pan camera |
| Mouse wheel | Zoom |
Each tree node holds up to QUADTREE_CAPACITY points; on overflow it splits
into four children and routes further insertions by quadrant. A range query
(query_rect / query_circle) descends only into nodes whose boundary
intersects the range, so it touches O(log n) nodes instead of scanning every
point.
That is what makes the collision step affordable: for each point the system asks the tree for neighbors within a small radius and resolves overlaps only against those, instead of the naive all-pairs O(n²) check.
The tree is rebuilt every frame. Points move constantly, and at this scale a full rebuild is simpler and cheaper than incremental updates with point removal and rebalancing.
cargo run
On Linux, Bevy needs the usual system packages first — see the official list. For Fedora:
sudo dnf install -y gcc-c++ libX11-devel alsa-lib-devel systemd-devel
The quadtree logic is plain Rust with no Bevy runtime involved, covered by unit tests (insertion, subdivision, boundary handling, rect/circle queries):
cargo test
- Points that drift outside the world bounds are skipped on insert, so queries and collisions stop seeing them.
- No point removal — the per-frame rebuild sidesteps it by design.
- The visualization draws with gizmos (immediate mode), which is the bottleneck long before the tree is.