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