This section is quite incomplete.
There is a little bit of information in the class notes for an AI course.
General graph searching algorithms can be used for pathfinding. Many algorithms textbooks describe graph searching algorithms that do not use heuristics (breadth-first search, depth-first search, Dijkstra's). Reading about them may help in understanding A*, which is a variant of Dijkstra's. Many AI textbooks will address graph searching algorithms that do use heuristics (best-first search, A*). Here are two that I have used:
- Russell and Norvig, AI: A Modern Approach
- Ginsberg, Essentials of Artificial Intelligence
For non-pathfinding algorithms, see John Lonningdal's web page (via Wayback Machine, since his site is no longer up).
For more about using non-grid graphs for pathfinding, see this detailed tutorial on Dijkstra's algorithm, which also includes some VB source code.
To learn more about unit movement after a path has been found, see Pottinger's articles on unit movement and group movement. Also highly recommended are Craig Reynold's pages on steering and flocking. Geoff Howland has a great article about unit movement in general.
Patrick Lester has a page describing a two-level pathfinder.
There's an interesting paper describing how to find Simplest Paths instead of Shortest Paths.
Here are some other papers I haven't classified:
Path Planning for Star Trek: Armada, with path smoothing
Back: AI techniques | Up: Home |