Also see Amit’s introduction to A*^{[1]}. The following was posted to Usenet in 1996:

From: cd000450@interramp.com (Bryan Stout) Newsgroups: rec.games.programmer Subject: Re: Shortest path algorithm? Date: 27 Feb 1996 02:32:33 GMT

kathi@lightside.com says...

Many times I have seen people ask here about a shortest path algorithm... the answer is almost always “Look in a good algorithm’s book.” Can anyone recommend such a book?

My problem is that I am trying to find paths on a 640x480 grid... with any of the algorithms I’ve seen so far, the worst-case scenarios would take tremendous amount of memory to store the tree...

--

Katherine Lynne

kathi@lightside.com

From my own experience, I would absolutely say the algorithm to try is the A* (pronounced “A-star”) algorithm. This is described in most good introductory Artificial Intelligence textbooks. If you want a specific reference, try the *Encyclopedia of Artificial Intelligence*, Stuart C. Shapiro, ed. (see articles on “Search” and “A* Search”); *The Handbook of Artificial Intelligence*, vol. 1, Barr and Feigenbaum, eds. (chapter 2 is on search); *Principles of Artificial Intelligence*, Nils J. Nilsson (a bit dated, but good discussion of A*).

If your domain is not hard to maneuver around, A* should take up *much* less memory than Dijkstra’s algorithm, say. If your heuristic estimate function is on the average not very close to the true remaining cost of the path, then A* ends up being close to a full breadth-first search. If you memory problems, options you have include: a) trying a higher estimate function, even one which sometimes overestimates the distance; b) beam search (limit the size of the Open list, discarding the worst entry when it’s full); c) try the iterative-deepening A* search (IDA*); d) use more efficient data structures for the Open and Closed lists. The *Encyclopedia* mentioned above discusses the beam search and IDA*; Sedgewick’s *Algorithms in C++* has a good discussion of various data structures for representing priority queues, and their tradeoffs. (Although, oddly enough, he does not mention the possible use of balanced search trees for a priority queue, though he has a chapter about them elsewhere; I would probably try using height-balanced trees (aka AVL trees), as discussed in Reingold et al’s *Combinatorial Algorithms*.)

There, I’ve just given you a preview of my talk at the Computer Game Developers’ Conference!

Bryan Stout

bstout@interramp.com