Special intereSt page
Pathfinding
C h a p t e r
7 7
Pathfinding—as the name suggests—seeks to find a path
from point x to point y, more specifically, the shortest
path. This is a problem encountered in video games,
when entities must move to a target point while avoiding obstacles. On a much larger scale, Google Maps and
other Web mapping sites allow us to enter a source x and
a destination y and, in a very short time, receive driving
directions to get from x to y.
Well, don’t we already know how to do that?
Dijkstra’s algorithm is the classic shortest-path algorithm, but it’s an Θ(n
2
) algorithm. In the context of a
real-time video game, quick response is essential. For
Google maps, an Θ(n
2
) algorithm might not be a problem for a graph with 50, 500, or 2000 nodes, but scale
up to the hundreds of thousands of cities and towns, and
you’ll want to find a way to speed up the search. This
is an important problem, and much research has been
directed toward improving shortest-path performance.
One generalization of Dijkstra’s algorithm, called
the a* algorithm, is used by many video game designers. The exact techniques used by Google and other sites
aren’t publicly revealed, but the a* algorithm may well
be part of their arsenal. The a* algorithm generalizes
Dijkstra’s algorithm by adding ideas borrowed from
artificial intelligence. In fact, a*, strictly speaking, isn’t
even an algorithm because there’s a big hole where one
must plug in a “heuristic” (read an “educated guess”).
The heuristic function used varies with the specifics of
the application, and it’s the hard part of using a*.
Here’s an outline of how a* works. The general
problem is that there is a graph with a source node x
and a destination node y (for simplicity, assume that it’s
a connected graph so that a path from x to y exists), and
the arcs of the graph are weighted with known distances
between nodes. At any point in time, a “closed set”
represents nodes that have been examined and need not
be considered further. There is also an “open set” that
represents nodes available for evaluation as the next
node along the path. Initially, only node x is in the open
set. Evaluation of a node n consists of three values that
are maintained for each node in the open set:
G = the distance to get from x to n along the path
being constructed
H = the result of the heuristic function that “guesses”
the distance to get from n to y. This is a guess because
the exact path from n to y is not yet known.
F = G + H
Pseudocode:
Put node x into the open set
Repeat the following process until y gets moved to the
closed set:
Select the node p from the open set with the lowest F
value (with some tie-breaking rule)
Move p to the closed set
For each node z that is adjacent to p and not in the
closed set (you don’t want to go back to a previous node on the path), do the following:
If z is not in the open set, move z to the open set,
compute its G, H, and F values (the G value
is just the G value for p + the weight of the
p−z arc), and set p as z’s parent node.
If z is in the open set, compute a new G value for
z by going through node p; if this value is
lower than z’s current G value, then recompute z’s F value (which will also be lower
than before) and set p as z’s parent node.
Once the target node y is in the closed set, walk back
through the parents to the start node x. Reversing this
walk gives the shortest path from x to y.
Note the similarities to Dijkstra’s algorithm (DA).
There is a closed set (like the IN set of DA) that begins
with the start node and eventually includes the end
node. There is a next node p that gets moved into the
closed set (moved into IN in DA). Once p is moved into
the closed set, G values (distances from x in DA) are
recomputed to see whether going through node p is an
improvement. The algorithm terminates when the target node y is moved into the closed set (moved into IN
in DA). The path is found by walking backward from y
to x through a parent list (the s array in DA).
The difference between a* and Dijkstra’s algorithm is that in a* the next node p is chosen based on
the lowest F value, whereas in Dijkstra’s algorithm p is
chosen based on the shortest distance from the source
node (which is the same as the G value). So a* uses
Pathfinding
C h a p t e r
7 7
Pathfinding—as the name suggests—seeks to find a path
from point x to point y, more specifically, the shortest
path. This is a problem encountered in video games,
when entities must move to a target point while avoiding obstacles. On a much larger scale, Google Maps and
other Web mapping sites allow us to enter a source x and
a destination y and, in a very short time, receive driving
directions to get from x to y.
Well, don’t we already know how to do that?
Dijkstra’s algorithm is the classic shortest-path algorithm, but it’s an Θ(n
2
) algorithm. In the context of a
real-time video game, quick response is essential. For
Google maps, an Θ(n
2
) algorithm might not be a problem for a graph with 50, 500, or 2000 nodes, but scale
up to the hundreds of thousands of cities and towns, and
you’ll want to find a way to speed up the search. This
is an important problem, and much research has been
directed toward improving shortest-path performance.
One generalization of Dijkstra’s algorithm, called
the a* algorithm, is used by many video game designers. The exact techniques used by Google and other sites
aren’t publicly revealed, but the a* algorithm may well
be part of their arsenal. The a* algorithm generalizes
Dijkstra’s algorithm by adding ideas borrowed from
artificial intelligence. In fact, a*, strictly speaking, isn’t
even an algorithm because there’s a big hole where one
must plug in a “heuristic” (read an “educated guess”).
The heuristic function used varies with the specifics of
the application, and it’s the hard part of using a*.
Here’s an outline of how a* works. The general
problem is that there is a graph with a source node x
and a destination node y (for simplicity, assume that it’s
a connected graph so that a path from x to y exists), and
the arcs of the graph are weighted with known distances
between nodes. At any point in time, a “closed set”
represents nodes that have been examined and need not
be considered further. There is also an “open set” that
represents nodes available for evaluation as the next
node along the path. Initially, only node x is in the open
set. Evaluation of a node n consists of three values that
are maintained for each node in the open set:
G = the distance to get from x to n along the path
being constructed
H = the result of the heuristic function that “guesses”
the distance to get from n to y. This is a guess because
the exact path from n to y is not yet known.
F = G + H
Pseudocode:
Put node x into the open set
Repeat the following process until y gets moved to the
closed set:
Select the node p from the open set with the lowest F
value (with some tie-breaking rule)
Move p to the closed set
For each node z that is adjacent to p and not in the
closed set (you don’t want to go back to a previous node on the path), do the following:
If z is not in the open set, move z to the open set,
compute its G, H, and F values (the G value
is just the G value for p + the weight of the
p−z arc), and set p as z’s parent node.
If z is in the open set, compute a new G value for
z by going through node p; if this value is
lower than z’s current G value, then recompute z’s F value (which will also be lower
than before) and set p as z’s parent node.
Once the target node y is in the closed set, walk back
through the parents to the start node x. Reversing this
walk gives the shortest path from x to y.
Note the similarities to Dijkstra’s algorithm (DA).
There is a closed set (like the IN set of DA) that begins
with the start node and eventually includes the end
node. There is a next node p that gets moved into the
closed set (moved into IN in DA). Once p is moved into
the closed set, G values (distances from x in DA) are
recomputed to see whether going through node p is an
improvement. The algorithm terminates when the target node y is moved into the closed set (moved into IN
in DA). The path is found by walking backward from y
to x through a parent list (the s array in DA).
The difference between a* and Dijkstra’s algorithm is that in a* the next node p is chosen based on
the lowest F value, whereas in Dijkstra’s algorithm p is
chosen based on the shortest distance from the source
node (which is the same as the G value). So a* uses