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. This leaves us with the edge case where some children are just too big. What happens if two objects happen to overlap at a point? No matter how far we subdivide, they will never separate:

To avoid this Infinite Subdivision, we can assign a maximum depth to the quad tree. But there are other edge cases to consider as well. What happens when an object...