The state
would often be the tile or position the entity occupies. But if needed,
it can represent orientation and velocity as well (for example, for
finding a path for a tank or most any vehicle-their turn radius gets
worse the faster they go).
Neighboring
states would vary depending on the game and the local situation.
Adjacent positions may be excluded because they are impassable or are
between the neighbors. Some terrain can be passable for certain units
but not for others; units that cannot turn quickly cannot go to all
neighboring tiles.
The cost of going from one position to another can represent
many things: the simple distance between the positions; the cost in
time or movement points or fuel between them; penalties for traveling
through undesirable places (such as points within range of enemy artillery);
bonuses for traveling through desirable places (such as exploring new
terrain or imposing control over uncontrolled locations); and aesthetic
considerations-for example, if diagonal moves are just as cheap as orthogonal
moves, you may still want to make them cost more, so that the routes
chosen look more direct and natural.
The estimate is usually the minimum distance between the current
node and the goal multiplied by the minimum cost between nodes. This
guarantees that h(n) is admissible. (In a map of square tiles where
units may only occupy points in the grid, the minimum distance would
not be the Euclidean distance, but the minimum number of orthogonal
and diagonal moves between the two points.)
The goal does not have to be a single location but can consist
of multiple locations. The estimate for a node would then be the minimum
of the estimate for all possible goals.
Search cutoffs can be included easily, to cover limits in path cost,
path distance, or both.
From my
own direct experience, I have seen the A* star search work very well
for finding a variety of types of paths in wargames and strategy games.
The Limitations of A*
There are situations where A* may not perform very well, for a variety
of reasons. The more or less real-time requirements of games, plus the
limitations of the available memory and processor time in some of them,
may make it hard even for A* to work well. A large map may require thousands
of entries in the Open and Closed list, and there may not be room enough
for that. Even if there is enough memory for them, the algorithms used
for manipulating them may be inefficient.
The quality of A*'s search depends on the quality of the heuristic estimate
h(n). If h is very close to the true cost of the remaining path, its
efficiency will be high; on the other hand, if it is too low, its efficiency
gets very bad. In fact, breadth-first search is an A* search,
with h being trivially zero for all nodes-this certainly underestimates
the remaining path cost, and while it will find the optimum path, it
will do so slowly. In Figure
10A, we see that while searching in expensive terrain (shaded
area), the frontier of nodes searched looks similar to Dijkstra's algorithm;
in 10B,
with the heuristic increased, the search is more focused.
Let's look at ways to make the A* search more efficient in problem areas.
Transforming
the Search Space
|
|
|
|
Features
