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

No credit card required

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
or pathfinding.
The Secret Life of Graphs | 197
Graphs
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
A navigation graph,ornavgraph, is an abstraction of all the locations in a
game environment the game agents may visit and of all the connections
between those points. Consequently, a well-designed navgraph is a data
structure embodying all the possible paths through the game environment
and is therefore extremely handy for helping your game agents decide how
to get from A to B.
Each node in a navgraph usually represents the position of a key area or
object within the environment and each edge represents the connections
between those points. Furthermore, each edge will have an associated cost,
which in the simplest case represents the distance between the nodes it con
-
nects. This type of graph is known to mathematicians as a Euclidian graph.
Figure 5.7 shows a navigation graph created for a small walled environ
-
ment and highlights a path through that graph.
I’d like to make it clear that a game agent is not restricted to moving along
the graph edges as though it were a train traveling along rails. An agent can
move to any unobstructed position within the game environment, but it
uses the navigation graph to negotiate its environment — to plan paths
between two or more points and to traverse them. For example, if an agent
positioned at point A finds it necessary to move to position B, it can use the
navgraph to calculate the best route between the nodes closest to those
points.
Figure 5.7 is typical of a navigation graph created for a first-person
shooter. Other types of games may find a different node layout more effec
-
tive. RTS/RPG type games, for instance, are often based upon a grid of
tiles or cells, where each tile represents a different type of terrain such as
198 | Chapter 5
Graphs
Figure 5.7. A simple navigation graph. The collection of all the edges and nodes con
-
stitute the graph. The highlighted edges represent a possible path through the graph.

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

No credit card required