a Warcraftlike RTS game the edges might indicate the resources required
to upgrade each unit.
Ü
NOTE Although a graph may have multiple connections to the same node or
even looped connections connecting a node to itself, these features are rarely
necessary for game AI and will not be considered in the following pages.
Trees
Most programmers are aware of the tree data structure. Trees are used pro

fusely throughout all programming disciplines. However, you may not
realize that trees are the subset of graphs comprising all graphs that are
acyclic (containing no cyclic paths). Graph E in Figure 5.3 is a tree, and
that’s probably the shape you are familiar with, but graph D is also a tree.
Graph F is a forest of trees.
Graph Density
The ratio of edges to nodes indicates whether a graph is sparse or dense.
Sparse graphs have few connections per node and dense graphs many. Fig
ure 5.4 shows an example of both types. In order to reduce complexity and
keep CPU and memory usage to a minimum, you should prefer sparse
graphs whenever possible, for example, when designing a graph for use in
path planning (see Chapter 8).
Knowing whether a graph is dense or sparse is helpful when selecting an
appropriate data structure to encode the graph’s structure, since an imple
mentation that is efficient for a dense graph is probably not going to be
efficient for one that is sparse.
Digraphs
So far we have assumed that if it’s possible to travel from node A to node
B, then it’s also possible to do the reverse. This may not always be the
case. Sometimes you may need to implement a graph where the connec

tions are directional. For example, your game may have a “deathslide”
positioned across a river. An agent should only be able to traverse this one
196  Chapter 5
Graphs
Figure 5.4. Examples of dense and sparse graphs