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

graph such as that for the Towers of Hanoi puzzle, then the best path
will be the one reaching the solution in the fewest steps.
Before I get to the nitty-gritty I’d like to make it clear that many of you are
initially going to find some of these algorithms difficult to understand. In
fact I think graph search algorithms should come with a health warning.
Something like the following would be appropriate:
WARNING!
Beware! Search algorithms have the ability to create in the average human
brain terrible amounts of frustration and confusion, leading to headaches,
nausea, and sleep deprivation. Spontaneous and excessive howling is not
uncommon. Please be aware these symptoms are commonplace in the early
stages of the learning curve and are not generally cause for concern. Nor
-
mal service is usually resumed within a reasonable length of time. (If
symptoms persist, however, stay clear of busy roads, razor blades, and
loaded weapons. Seek medical advice at the earliest opportunity.)
Seriously though, for many people this stuff can be difficult to understand.
For this reason I’m going to take my time explaining each algorithm. It’s
very important that you understand the theory and don’t just use these tech-
niques in a “cut and paste” fashion, because often you may want to modify
an algorithm to suit your own requirements. Without an understanding of
how these searches work, any modification will be almost impossible and
you’ll be left scratching your head in frustration.
Strap yourself into your seat then. Let’s get on with it!
Uninformed Graph Searches
Uninformed graph searches, or blind searches as they are sometimes
known, search a graph without regard to any associated edge costs. They
can distinguish individual nodes and edges however, enabling them to
identify a target node or to recognize previously visited nodes or edges.
This is the only information required to either completely explore a graph
(to visit every node) or find a path between two nodes.
Depth First Search
Meet little Billy. Billy is standing at the entrance to a typical theme park: a
conglomeration of rides and other attractions and the paths meandering
through the park that connect them. Billy doesn’t have a map but he’s eager
to discover what rides and other entertainment the park has to offer.
Fortunately Billy knows about graph theory and he quickly spots the
similarity between the layout of a theme park and a graph. He sees that
each attraction can be represented by a node and the paths between them
by edges. Knowing this, Billy can ensure he visits every attraction and
walks down every path using a search algorithm called the depth first
search, or DFS for short.
210 | Chapter 5
Graph Search Algorithms
The depth first search is so named because it searches by moving as
deep into the graph as possible. When it hits a dead end it backtracks to a
shallower node where it can continue its exploration. Using the theme park
as an example, this is how the algorithm works:
From the entrance to the park (the source node), Billy makes a note of
its description and of the paths that extend outward from it (the edges) on a
slip of paper. Next, he chooses one of the paths to walk down. It makes no
difference which — he can choose one at random provided it’s a path he
hasn’t already explored. Every time a path leads Billy to a new attraction
he makes a note of its name and of the paths connected to it. The illustra
-
tions labeled A to D in Figure 5.14 demonstrate the first few steps of this
process. The thin black lines represent unexplored paths and the high
-
lighted lines show the paths Billy has chosen to walk down.
When he reaches the position shown at D, Billy notices that no new paths
lead from the Pirate Ship (in graph parlance this node is known as a termi
-
nal node). Therefore, to continue the search he backtracks to the 3D
Cinema where there are further unexplored paths to traverse. See Figure
5.15 E.
When he reaches the Ice Blaster there are four unexplored paths to try.
The first two he navigates lead back to previously visited places — the
Entrance and the Funhouse — so he marks each path as explored before
backtracking to the Ice Blaster to try another route. Eventually he finds a
path leading to the Slot Machines. See Figure 5.15 F, G, and H.
The Secret Life of Graphs | 211
Graph Search Algorithms
Figure 5.14

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