Game Development Reference
In-Depth Information
Precomputed paths are cheaper than A* paths, but two major issues crop up
quickly. The first issue is that the number of paths explodes as the number of
places increases. The number of paths is related to the square of the number of
places. The second issue is that precomputed paths require knowing all the places
in advance. They cannot be used with dynamically created maps. Precomputed
paths fail if elements such as bridges can be rendered unusable during play. When
you lack a static map with a small number of places, you need a general path
finder, and A* is hard to beat.
A* works with two core concepts. The first is, ''I know how much it costs to get
from the starting point to here,'' for any particular ''here'' to which the algorithm
has progressed. The second concept is, ''I can estimate the cost of getting from
here to the goal,'' again for any particular ''here.'' In technical terms, A* is a best-
first graph search algorithm to determine the lowest cost path between two
nodes. We will examine what all these words mean and why they are important.
The best-first part is one of the major reasons why A* is so popular. A* is
reasonably fast, and that speed comes from examining the most promising steps
first. A character standing in a building would first check if he or she can walk
directly toward his or her goal. If the character is standing in an open-air gazebo,
this will in fact be the best way to go. If the character is standing in a room with
walls and doors, the extremely high cost of going through a wall would force the
character to examine less direct paths. If there is a door in the wall blocking the
direct path, that door will probably be checked before other doors that lead away
from the goal.
''Reasonably fast'' is a relative term. A* is a search method, and search as a
computational problem is not cheap. The difference between ''cheaper than the
alternatives'' and ''cheap'' should be kept in mind.
A* is a graph search algorithm. For navigation purposes, most virtual worlds are
not really contiguous. Unlike on Earth, in games, the concept of ''here'' is not a
set of coordinates such as latitude and longitude that can always be more finely
specified. In games, ''here'' is some discrete space, perhaps a triangle. Board
games often use squares or hexagons for this purpose; they are spaces that cannot
be subdivided. Whether in board games or computer games, every ''here'' has
some neighboring places that are directly connected to it. To A*, a graph is a set
of points and a set of lines connecting those points to their neighbors. These
points represent the ''here'' for any location in the virtual world; in graph-theory
terms, these are called nodes. Every square or hexagon in a board game becomes
Search Nedrilad ::

Custom Search