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-graph-search 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.

The grid-based pathfinding competition results paper describes optimizations for A* running on unweighted grids: contraction hierarchies, subgoal graphs, jump point search, visibility graphs, compressed path databases, and more.

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.

The landmark approach stores lots of data that could be compressed. The Compressed Differential Heuristic shows the results of compressing the landmark data. You can store a lot more landmarks in the same space, so you get improved heuristic values.

Landmarks may be a special case of a more general approach. This paper explores transforming a map into a map where a regular distance metric works.

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.

Contraction Hierarchies (long paper) can find paths faster by adding shortcut edges. Also great reading is the related work section, which summarizes A* improvements from landmarks, arc flags, transit nodes, highway hierarchies, and other approaches.

Arc flags (note to self: need a better link here) restrict the set of edges expanded in the main pathfinding loop. First divide the world into regions, then precalculate which edges are part of a shortest path to each region. Instead of looking at all edges to neighbors, look at only the edges that are part of a shortest path to the region the goal is in. Steve Rabin calls this approach “goal bounding”.

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(!).

Compressed Path Databases tests how well all-pairs shortest path (Floyd-Warshall or Johnson’s Algorithm) on grids can be compressed. It applies if you’re using a grid and the map isn’t changing; I suspect you’d be better off reducing the graph size first.

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