Game Development Reference

In-Depth Information

means that the paths between nodes can be traversed in both directions

or directed, in which case the paths are one way. Think of this as the

difference between two-way streets and one-way streets. Graphs are

drawn with nodes represented as circles and edges as lines as shown

in
Figure 5.2
. Nodes and edges can be drawn where nodes represent

coordinates such as those on a flight plan or as symbolic states where

the physical location in the graph is meaningless. For example, the state

diagram in
Figure 5.2
could be drawn with nodes in any position and any

distance from one another. Some directed graphs allow bidirectional

traversal from one node to another in the same way as undirected graphs.

However, if arrows are already being used in a directed graph to show

some one-way-only paths, they should also appear on bidirectional

edges for consistency.

Both nodes and edges can have associated values. These values could be the

distance between nodes, such as those representing distances in the flight

plan of
Figure 5.2
, or the time it takes to complete an action, such as nodes

in the action plan of
Figure 5.2
.

The ways in which graphs are useful in games AI will become evident

as we progress through the chapter.

FIG 5.2
Undirected and directed

graph representations and some

examples.