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