Game Development Reference
F IGURE 12.4
Top-down hierarchy building in action.
together. The same algorithm then applies to each group, splitting it into two,
until there is only one object in each group. Each split represents a node in the
Insertion The insertion approach (illustrated in figure 12.5) is the only one
suitable for use during the game. It can adjust the hierarchy without hav-
ing to rebuild it completely. The algorithm begins with an existing tree (it
can be an empty tree if we are starting from scratch). An object is added to
the tree by descending the tree recursively: at each node the child is selected
that would best accommodate the new object. Eventually an existing leaf is
reached, which is then replaced by a new parent for both the existing leaf and
the new object.