O'Reilly logo

Programming Game AI by Example by Mat Buckland

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

a Warcraft-like 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 “death-slide”
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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required