Game Development Reference
child that contains its center. We could instead place the object into all the children
that it touches, as we did for the BSP tree, and have the same simple coarse collision
detection: only objects in the same leaf can possibly be in collision.
Quad-trees are particularly useful for outdoor scenes, where objects are placed on
a landscape. They are less useful than BSP trees for indoor games because they can't
be used as easily for collision detection with the walls of the level. And, just like BSP
trees, they are often used for optimizing rendering and may be part of any existing
rendering engine you are using.
Because they are so similar to BSPs in practice, I will avoid repeating the code to
work with them. On the CD, there is a complete implementation for BSPs, quad-trees,
Our penultimate spatial data structure takes the idea of a quad-tree further. If we
draw the split pattern of a halving quad-tree that is several layers deep, we see that
it forms a grid (figure 12.11). Rather than use a tree structure to represent a regular
grid, we could simply use a regular grid.
A grid is an array of locations in which there may be any number of objects. It
is not a tree data structure because the location can be directly determined from the
position of the object. This makes it much faster to find where an object is located
than recursing down a tree.
F IGURE 12.11
A quad-tree forms a grid.