way — from the top to the bottom — so we have to find a way of repre
senting this type of connection.
Alternatively, it may be possible to travel between two nodes in either
direction but the cost of each traversal may be different. A good example
of this is if you want your agents to take the terrain’s gradients into consid
eration. After all, it’s easy for a vehicle to travel efficiently and quickly
downhill, but it takes a lot more fuel for a vehicle to move uphill, and its
top speed will be much slower. We can reflect this information using a
graph called a digraph, or DAG for short.
A digraph has edges that are directed, or one way. The nodes that define
a directed edge are known as an ordered pair and specify the direction of
the edge. For example, the ordered pair 16-6 indicates that it’s possible to
travel from node 16 to node 6 but not from node 6 to 16. In this example,
node 16 is known as the source node and node 6 the destination node.
Figure 5.5 shows a small digraph. The edges are drawn using arrows to
indicate their direction.
When designing a data structure for graphs it’s often helpful to think of
undirected graphs as digraphs with two edges connecting each connected
pair of nodes. This is convenient because both types of graphs (directed
and undirected) can then be represented by the same data structure. For
example, the sparse undirected graph shown in Figure 5.4 can be repre-
sented by the digraph shown in Figure 5.6.
Graphs in Game AI
Before we move on to the implementation of the code for a graph, let’s
take a quick look at some of the things you can use a graph for in the
development of a game’s AI, starting with the most popular use: navigation
The Secret Life of Graphs | 197
Figure 5.5. A simple digraph. Note that
in the world of digraphs, unconnected
graphs are more frequent as they may
contain nodes that are only reachable
from one direction.
Figure 5.6. Representing an undirected
graph as a digraph