Game Development Reference
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