Intro
A quadtree is a tree Data Structure in which each internal node has exactly 4 children. It is used to divide 2D space recursively into four regions so you can store and query objects efficiently.
Quote
While QuadTrees and Octrees are often praised for their performance, they aren’t always ideal for certain tasks, especially in physics engines that require advanced features like raycasting or shape/sphere casting. These data structures struggle with irregularly sized objects that exceed the size of a cell, and there’s significant overhead when performing raycasting because of the DDA-style stepping required through the Quadtree or Octree cells
Overview
- Start with full world
- If a region has too many objects → split into 4
- Repeat recursively
- Stop when regions are small or sparse
So dense areas get more subdivision, empty areas stay coarse.