This section is quite incomplete.

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*).

Paul Tozour has a demo showing various map representations (Windows app, no source).

For non-pathfinding algorithms, see John Lonningdal’s web page (via Wayback Machine, since his site is no longer up).

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. Hierarchical Planning A* (HPA*) can turn a grid representation into a simplified graph.

Clearance-based pathfinding annotates the graph with the sizes of the objects that can pass through there. This is useful if you want small units to be able to pass through an area but large units to be blocked.

There’s an interesting paper describing how to find Simplest Paths instead of Shortest Paths.

This StackOverflow question includes a summary of lots of variants of A*.

Triangulation A* converts a polygonal obstacle representation into a navigation mesh using triangles, and Triangulation Reduction A* simplifies the resulting pathfinding graph by removing nodes.

Here are some other papers I haven’t classified:

ALT A* uses landmarks and the triangle inequality to preprocess the pathfinding graph in order to make pathfinding much faster. As much as you can, you want to reduce the graph size to make A* run faster. However, you can also make A* faster if you make the heuristic more closely match the actual distance. ALT preprocesses the graph to construct a more accurate heuristic. If the heuristic exactly matches the actual distance, A* will only expand the nodes along the path and not explore anything else.

Real-time heuristic search augments A* and other algorithms with additional data to speed up pathfinding.

Fringe Search looks at large sets of nodes (the fringe or frontier) at a time. They greatly reduce the cost of processing each node. A* sorts one node at a time (either on insertion and deletion from the set, or both), and batch sorting is faster. But even faster is not sorting at all. In the batches of nodes that Fringe search is processing, there’s no need to sort them. The downside is that more nodes have to be processed, sometimes more than once. But if you can make processing them really cheap, then it’s okay to process lots of nodes.

Biased Cost Pathfinding alters the movement costs of areas where other units are going to move, so that subsequent paths avoid colliding with those units.

Parallel Ripple Search is designed for multi-core pathfinding, without the sort bottleneck that A* has.

Corridor Maps are a way to construct a pathfinding graph that greatly reduces the number of nodes, especially in maps with lots of corridors.

Learning Real-Time A* updates the heuristic as it explores the map. Prioritized Learning Real-Time A* prioritizes the search to favor areas where it is learning more.

IDA* runs faster with a hex grid than a square grid(!).

Probabilistic Roadmaps (PRMs) build pathfinding graphs from polygonal obstacle maps.

This is page 13 of 13 of Amit’s Thoughts on Pathfinding.
←Back: Up: Table of contents