Chapter 5
The Secret Life of Graphs
T
his chapter focuses on a mindbogglingly useful mathematical abstrac

tion called a graph. You’ll be using graphs a lot in game AI. In fact,
you’ve already seen them: The state transition bubble diagrams from Chap

ter 1 are a type of graph. Graphs and their baby brothers, trees, are used by
game AI programmers all the time. They can be used for a whole variety of
things — from enabling game agents to travel between two points effi

ciently, to deciding what to build next in a strategy game and solving
puzzles.
The first part of this chapter will be spent introducing you to the differ
ent kinds of graphs and the terminology associated with them. You’ll learn
what graphs actually are, how they can be used, and how to code them effi
ciently. The remainder of the chapter will describe, in lots of detail, many
of the search algorithms available to exploit the full power of graphs.
Graphs
When developing the AI for games, one of the most common uses of
graphs is to represent a network of paths an agent can use to navigate
around its environment. When I first learned this I was confused, as all my
life I’d known a graph to look like the graphs I was taught to draw at
193
Figure 5.1. A typical graph
school — something like the familiar shape shown in Figure 5.1, for
example.
I’d always thought of graphs as useful for visualizing the rise and fall of
some property, like the temperature charts shown on TV weather reports or
sales figures, stuff like that, and so I was left wondering how this sort of
graph could possibly be used to represent the paths weaving around the
walls and obstacles in a game environment. If you have never studied
graph theory, then this is possibly the way you think about graphs too. I
guess it’s just the way we are conditioned. However, let me show you
something interesting. Check out Figure 5.2.
This is the same graph, but I’ve changed the axis labeling to represent the x
and y coordinates of Cartesian space, adding a few cosmetic embellish

ments so that now it represents a path meandering close to a river. In fact it
looks like something your average person on the street would refer to as a
map. Indeed, the whole image is a map, but the series of waypoints and the
footpath connecting them is represented by a very simple graph. Now I
realize a few of you will be thinking this is no big deal, but I believe that
for many this subtle shift in perspective can be a revelation. It certainly was
for me. In graph terminology, the waypoints are called nodes (or some

times vectors) and the footpaths connecting them are called edges (or
sometimes arcs).
Figure 5.3 shows some more examples of graphs. As you can see, they
can assume a wide variety of configurations.
194  Chapter 5
Graphs
Figure 5.2
Get Programming Game AI by Example now with O’Reilly online learning.
O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.