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 state graph can easily be searched to find a goal state. In this example,
the goal state is one where all the pieces are positioned on peg C in the cor
-
rect order. By searching the state space it’s possible to not only find a
single solution, but to find every possible solution or the solution requiring
the fewest moves (or the most moves if that’s what you are looking for).
The average number of child nodes radiating from each parent node is
known as a graph’s branching factor. For some problems, such as the puz
-
zle example we have discussed here, the branching factor is low — on the
order of one to three branches per node — making it possible to represent
with a graph the entire state space in a computers memory. For many
domains though, the branching factor is much higher and the number of
potential states grows enormously as the distance from the root node (the
depth of the graph) increases. With these types of systems it’s impossible to
represent the entire state space because it will quickly exceed the memory
capabilities of even the most powerful computer. Even if such a graph
could be stored, it would still take eons to complete a search. Conse-
quently, these types of graphs are created and searched by expanding a few
nodes at a time, typically (but not always) using algorithms that direct the
search toward the goal state.
Implementing a Graph Class
Two popular data structures used to represent graphs are adjacency matri-
ces and adjacency lists. Adjacency matrix graphs use a two-dimensional
matrix of Booleans or floats to store a graph’s connectivity information.
Booleans are used if there is no cost associated with traversing an edge and
floats are used when there is an associated cost, such as for a navigation
graph where each edge represents the distance between two nodes. The
exact implementation is, of course, up to the designer and the needs of his
problem. Figure 5.12 shows what the adjacency matrix looks like for the
digraph in Figure 5.6.
The Secret Life of Graphs | 203
Implementing a Graph Class
Figure 5.12. An adjacency matrix

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