Chapter 5
The Secret Life of Graphs
his chapter focuses on a mind-bogglingly 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
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.
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
Figure 5.1. A typical graph
school — something like the familiar shape shown in Figure 5.1, for
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
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.