Post
Keep subdividing space into smaller boxes until finding nearby objects is trivially fast.
Quadtrees and octrees are hierarchical spatial data structures that recursively subdivide 2D and 3D space respectively. A quadtree starts with a single rectangle representing the entire world and splits it into four equal quadrants. If a quadrant contains too many objects, it splits again into four smaller quadrants, and so on until each leaf node contains a manageable number of objects. Octrees do the same thing in three dimensions, splitting into eight child cubes. The power is in the search -- to find all objects near a point, you traverse the tree from root to leaf, only visiting branches that overlap your search area. This turns an O(n) brute-force check into roughly O(log n) in practice. They are fundamental to collision detection, frustum culling, ray casting, and any system that needs to answer 'what is near this point?' efficiently.
Example
The original Quake engine used a BSP tree (a close relative of octrees) to determine which parts of the level were visible from the player's position, enabling it to render complex 3D environments on hardware that had no business running them. Modern engines still use octree variants for scene management in games like Unreal Engine's world partition system.
Why it matters
Without hierarchical spatial structures, games would grind to a halt as soon as they had more than a few hundred objects. Octrees and quadtrees are the reason your game can have thousands of entities and still run collision checks in microseconds instead of milliseconds.
Related concepts