QuadTree Collision Visualizer

Demo ✨

A Visual demonstration of how Quadtrees group entities and perform in order to optimize collision detection alogrithms

Background

Quadtrees help with gathering information about which collisions in an environment are worth testing by only making computations between objects in similar nodes/quads.

• Quadtree nodes split into four evenly-sized leaf nodes when the number of objects inside them reach a certain capacity.
• Objects are inserted into a fresh Quadtree every iteration, which places each object in its deepest possible node.
• The Quadtree algorithm improves upon the naive T(n) = θ(n²) algorithm and achieves T(n) = O(n²), T(n) = Ω(nlog(n)).
• Quadtrees based on pixels are incidentally a type of trie.

Simulation

This Visualizer provides an interactive environment where you can change configurations of the Quadtree and Physics at runtime.
The Quadtree visualization sits atop a 2D Collision System with a configurable coefficient of restitution, used to adjust between elastic and inelastic collisions.

Development

Run the development server:

npm run dev

Opens on http://localhost:3000.