The Experiment
Quadtree Nav is a research project exploring spatial data structures for real-time NPC navigation in 3D environments. The core question: can a quadtree-based spatial index provide efficient enough lookups to power pathfinding, proximity queries, and collision detection for large numbers of autonomous agents in a browser-rendered 3D world?
Quadtree Fundamentals
A quadtree recursively subdivides 2D space into four quadrants, creating a hierarchical spatial index where nearby objects share tree nodes. This makes spatial queries (find all entities within radius, find nearest neighbor, detect collisions) dramatically faster than brute-force approaches. For N entities, a brute-force proximity check is O(N squared). A well-balanced quadtree reduces this to O(N log N) for most practical cases.
The implementation handles dynamic insertion and removal as NPCs move, automatic tree rebalancing when nodes exceed capacity, and range queries that traverse only relevant subtrees. The quadtree is projected onto the XZ plane of the 3D scene, providing 2D spatial indexing for ground-based navigation.
NPC Navigation
Each NPC uses the quadtree for three operations: pathfinding (A* search with quadtree-accelerated neighbor lookups), obstacle avoidance (proximity queries to detect nearby entities and terrain), and target acquisition (range queries to find the nearest enemy, resource, or objective). NPCs run autonomous behavior loops -- wandering, pursuing targets, fleeing threats, gathering resources -- with the quadtree providing the spatial awareness that makes these behaviors efficient.
Battle Royale Layer
The project includes battle royale mechanics as a stress test for the navigation system. A shrinking safe zone forces NPCs into increasingly dense areas, which tests the quadtree's performance under high entity density. Crafting and inventory systems provide resource management that drives NPC decision-making.
Rendering
The 3D visualization is built with Three.js, rendering NPCs, terrain, and the quadtree structure itself (you can visualize the tree subdivisions as wireframe boxes). OrbitControls allow free camera navigation. The quadtree debug visualization makes it possible to watch the tree rebalance in real-time as entities move.
Tech Stack
Three.js (WebGL rendering), custom quadtree implementation, A* pathfinding, vanilla JavaScript, HTML5.