Testing collision between every pair of objects in a game with $N$ entities requires $O(N^2)$ checks. At $N = 1,000$, this results in 500,000 distance calculations every single frame, crippling CPU performance. Spatial partitioning organizes entities into geographic buckets so objects only test collisions against immediate spatial neighbors.
1. Quadtrees vs Spatial Hash Grids
| Algorithm | Best Suited Scene Topology | Memory Overhead | Update Complexity |
|---|---|---|---|
| Quadtree | Sparse scenes with localized clusters (e.g. RTS maps). | Dynamic tree node allocations. | O(log N) tree re-insertion on movement. |
| Spatial Hash Grid | Dense, uniformly distributed moving entities (e.g. Bullet hell). | Fixed 1D array / Map of cell keys. | O(1) constant-time cell coordinate lookup. |
