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.