A* is a Shortest-Path
algorithm, based on graph searching techniques. It was developed in 1968 to combine the heuristic methods and formal methods of searches. It is faster than
Dijkstra's algorithm or Best-First Search, and is widely used in games since the paths do not have to be perfect. You can trade of speed for accuracy, or vise-versa. It is a very flexible algorithm and lends itself to all sorts of problems. Here is the generalized format:
f(p) = h(p) +g(p)
Where
p is the point being checked,
g(p) is the cost to get from the starting point to
p,
h(p) is the estimated distance to the goal from
p. This lets
f(p) represent the estimated "goodness" of the point (or grid location, or square, etc). In addition to the equation, there is usually an OPEN and a CLOSED list, to keep track of the nodes visited. The algorithm looks something like this:
Load starting point
While not at goal
For each neighbor
compute cost
if on the OPEN list
leave the lowest cost on the OPEN list
if on neither list
add it to OPEN list
if on the CLOSED list
if lower cost than the CLOSED one, take it off the CLOSED list and put it on the OPEN list
Sort OPEN list, lowest cost first
Select new node from list, lowest cost
At end trace path back to start
For more information, see these web sites:
http://www.gameai.com/ -- The Game AI Page by Steve Woodcock, great great page.
http://www-cs-students.stanford.edu/~amitp/gameprog.html -- Amit's Game Programming Page, where I got a lot of information about A* from. Has a great introduction to pathfinding.
A Game Developer's Arsenal -- soon to be THE source for game programming goodness.
Programming Metanode -- an ok node by me to get you where you want to go.