Game Development Reference
In-Depth Information
using an inadmissible heuristic. But if catapults are rare and roads are the norm,
we might stay with our inadmissible heuristic. We do this because it is more
aggressive about discarding paths early, and that is a performance win. The effect
in our example would be that sometimes, the pathfinder neglects to exploit
catapults when they are off the beaten path. In our example, the catapult is
8 times faster than the heuristic. If we tune for catapults instead of roads, we have
to expand our searching by a factor of 8 to get to the point where we say, ''Even a
catapult won't help you when you are this far away,'' and that could be a lot of
useless searching.
Since reexamining nodes on the closed list does not guarantee getting the shortest
path when the heuristic is inadmissible, and reexamining nodes on the closed list
is pointless when the heuristic is admissible, the case for reexamining nodes on
the closed list is too weak to justify.
Besides holding the f, g, and h numbers, each node also tracks what node came
before it in the path. When our code reached X via A, X would store A. When a
node is placed on the open list for the first time or updated with better numbers,
the node is also updated with the new predecessor in the path. When our example
reached X via Y, it updated the costs and also overwrote the stored A with Y. This
way, when A* completes, the nodes have stored the best path.
A* is popular because it usually performs well and gives optimal results. Per-
forming well does not make it free, however; A* can be costly to run. When no
path exists, A* exhibits maximum cost as it is forced to explore every node in the
graph. If the usual case is that paths usually exist and obstacles are localized, then
dealing with the difference in performance between the usual case and the worst
case presents a difficult engineering challenge.
A* also depends heavily on the concept of ''here'' in the graph. The world may be
represented at a low level by a mesh of tiny triangles that can be fed to the
graphics engine, but that mesh makes for expensive path finding. A room may
have a large number of triangles that make up the floor, but for navigation
purposes it can be reduced to a single ''here'' or a small number of ''heres.'' To
help with path finding, many games have a coarse navigation mesh with far fewer
nodes than the graphics mesh. The navigation mesh makes the global pathfinder
run quickly by greatly reducing the number of nodes. The nodes in the navi-
gation mesh can be forced to have nice properties that make them easier to deal