A* algorithm

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.

Algorithms A and A*: Algorithm A is a version of best-first search that tries to find shorter paths to the goal than regular best-first. The algorithm is exactly the same as in best-first; it is the heuristic that differs.

The value used to sort the nodes in the agenda becomes the sum of the best-first heuristic and the length of the path to get to the node. That is, if you have two alternative routes:

Start ------------------------- Node A - - - - Goal
            7 branches                 Heuristic
                                       estimate:       Sum: 10
                                      3 branches

Start ------- Node B - - - - - - Goal
     4 branches       Heuristic
                      estimate:       Sum: 8
                     4 branches

Then ordinary best-first search will look at node A first (it has a better heuristic estimate). Algorithm A, however, will sum the two values together, and look at node B first.

Algorithm A* is almost identical to algorithm A. However, it has one more condition; the heuristic for estimating the distance still to go must be optimistic. That is, it must never overestimate how far away the goal is. In the picture above, the goal must be at least 3 branches away from node A, and at least 4 branches away from node B.

The effect of this condition is that algorithm A* always finds the shortest path to the goal. (As opposed to best-first, which finds the most obvious path, and algorithm A, which finds a fairly short path, but not neccessarily the shortest.)

The only disadvantage to algorithms A and A* is that they take up a lot of memory; almost as much as breadth-first search. This can be fixed in an algorithm similar to iterative deepening, known as 'IDA(*)' (Iterative Deepening A / A*).