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

complete graph prior to the search, requiring the BFS to expand the nodes
as it explores, a search could take literally years to terminate. In their book
Artificial Intelligence: A Modern Approach, Russell and Norvig give an
example of a puzzle with a branching factor of 10; assuming that it takes
one millisecond to expand each node, the BFS will take 3,500 years to
reach a depth of 14! Computers have become much faster beasts since the
first edition of that book was published, but even so you would still be an
old man in the amount of time the BFS takes to get to this depth.
Cost-Based Graph Searches
For many problem domains, the related graph will have a cost (sometimes
referred to as a weight) associated with traversing an edge. For instance,
navigation graphs usually have edges with a cost proportional to the dis
-
tance between the nodes they connect. To find the shortest paths through
the graph these costs must be taken into account. It’s simply not enough —
as we did previously with the BFS — to find the path containing the fewest
number of edges because, with an associated cost, it can be much cheaper
to travel down many short edges than two long ones. See Figure 5.30.
Although it’s possible to use the BFS or DFS to exhaustively search
through all the routes to a target node, adding up the costs of each path as it
goes and then selecting the lowest cost path, it’s obviously a very ineffi
-
cient solution. Fortunately there are much better methods at our disposal.
Edge Relaxation
The search algorithms discussed in the remainder of this chapter are based
on a technique called edge relaxation. As an algorithm proceeds it gathers
information about the best path found so far (BPSF) from the source node
to any of the other nodes en route to the target. This information is updated
The Secret Life of Graphs | 231
Graph Search Algorithms
Figure 5.30. The path1-5-4-3isshorter than the path1-2-3even though it
contains more edges.
as new edges are examined. If a newly examined edge infers that the path
to a node may be made shorter by using it in place of the existing best path,
then that edge is added and the path is updated accordingly.
This relaxation process, as with all graph operations, is much easier to
understand by observing a diagram. Take a look at Figure 5.31. With the
graph shown in A, the best path from 1 to 4 via 3 is not improved by exam
-
ining the edge [5 - 4]. Therefore no relaxation is necessary. With graph B,
however, the edge [5 - 4] can be utilized to create a shorter path to 4; as a
result the BPSF must be updated accordingly by changing node 4’s parent
from 3 to 5 (giving the path1-2-5-4).
This process is called edge relaxation because it mimics the way a piece of
elastic stretched along the edges of the BPSF would relax (become less
taut) when an edge is found that facilitates a shorter path.
Each algorithm keeps a
std::vector of floats (indexed by node) repre
-
senting the best total cost to each node found by the algorithm so far. Given
the general case shown in Figure 5.32, pseudocode to relax a path would
look something like this:
if (TotalCostToThisNode[t] > TotalCostToThisNode[n] + EdgeCost(n-to-t))
{
TotalCostToThisNode[t] = TotalCostToThisNode[n] + EdgeCost(n-to-t));
Parent(t) = n;
}
232 | Chapter 5
Graph Search Algorithms
Figure 5.31
Shortest Path Trees
Given a graph, G, and a source node, the shortest path tree (SPT) is the
sub-tree of G that represents the shortest path from any node on the SPT to
the source node. Again, a picture is worth a thousand words, so take a look
at Figure 5.33. It shows an SPT with its root positioned at node 1.
The following algorithms find the shortest paths in weighted graphs by
“growing” a shortest path tree outward from the source node.
Dijkstra’s Algorithm
Professor Edsger Wybe Dijkstra has provided computer science with many
valuable contributions, but one of the most famous is his algorithm for
finding shortest paths in weighted graphs.
The Secret Life of Graphs | 233
Graph Search Algorithms
Figure 5.32
Figure 5.33. The shortest path tree for node 1 is shown on the left by the thick edges
and represented again on the right by a directed tree. To find the shortest path from
any node in the graph to node 1, all you have to do is trace the route backward
through the SPT from the node in question. For example, tracing the path from node 3
to node 1 gives the path1-6-4-3.

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