Game Physics Cookbook

Quad tree

A quad tree recursively subdivides a game world into smaller and smaller sections. It's called a quad tree because each non-leaf node is divided into four smaller nodes. Usually, quad trees are dynamic, meaning they rearrange at runtime. Every node has a maximum number of children, if the number of objects in a node exceeds this, the node is split:

To build a quad tree we must start with a root node. This root node encompasses all of the objects in a given scene. If the root node contains more than some arbitrary number of game objects, it subdivides into four new leaf nodes. The same splitting process is recursively applied to each child. ...