Game Development Reference
In-Depth Information
real distanceSquared = (center - other->center).squareMagnitude();
}
In a full collision detection system it is common to have a method to query the hi-
erarchy against a known object too. This is simpler still: the object's bounding volume
is checked against the root of the hierarchy, and as long as it overlaps, each descendent
is checked recursively.
12.3.2
B UILDING THE H IERARCHY
An important question to ask at this stage is how the hierarchy gets constructed. It
may be that your graphics engine has a bounding volume hierarchy already in place.
Bounding volume hierarchies are used extensively to reduce the number of objects
that need to be drawn. The root node of the hierarchy has its volume tested against
the current camera. If any part of the bounding volume can be seen by the camera,
then its child nodes are checked recursively. If a node can't be seen by the camera,
then none of its descendents need to be checked. This is the same algorithm we used
for collision detection: in fact it is effectively checking for collisions with the viewable
area of the game.
In cases where a graphics engine does not have an existing bounding volume hi-
erarchy to determine what objects can be seen, or if you are creating a game from
scratch, you'll have to create your own. Ideally the hierarchy should have some key
properties:
The volume of the bounding volumes should be as small as possible, at each
level of the tree. This is true when a parent node groups together two bound-
ing volumes that are close together.
Child bounding volumes of any parent should overlap as little as possible. Of-
ten this clashes with the first requirement, and in general it is better to favor
smaller volumes over minimal overlaps. In fact, if you choose a minimal over-
lap at some low level of the tree, it is likely to cause greater overlaps higher up
the tree: so a tree with an overall low overlap is likely to fulfill both require-
ments.
Thetreeshouldbeasbalancedaspossible.Youshouldavoidhavingsome
branches of the tree that are very deep while others are very shallow. The
worst-case scenario is a tree with one long branch. In this case the advan-
tage of having a hierarchy is minimal. The biggest speed-up is gained when all
branches are roughly at the same length.
There are various ways to construct a hierarchy, and each is a compromise be-
tween speed and quality. For relatively static worlds, where objects don't move much,
a hierarchy can be created offline (i.e., while the game is not running: either while the
level is loading or, more likely, while building the level before it ships). For very dy-