# References

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

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

To see the proof that A* is optimal, see A Formal Basis for the Heuristic Determination of Minimum Cost Paths[2].

To learn more about unit movement after a path has been found, see Pottinger’s articles on unit movement[3] and group movement[4]. Also highly recommended are Craig Reynold’s pages on steering[5] and flocking[6]. Geoff Howland has a great article[7] about unit movement in general.

The grid-based pathfinding competition results paper[8](alternate link)[9] describes optimizations for A* running on unweighted grids: contraction hierarchies, subgoal graphs[10], jump point search, visibility graphs, compressed path databases, and more.

Patrick Lester has a page describing a two-level pathfinder[11]. Hierarchical Planning A*[12] (HPA*) can turn a grid representation into a simplified graph.

In games we often multiply the heuristic by some constant factor to make A* run faster. This is called Weighted A* in the literature. My belief is that it’s useful to compensate for a heuristic that’s too low, but improving the heuristic makes this technique less useful. Also note that Weighted A* can be slower than A* in some cases[13].

Clearance-based pathfinding[14] 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[15] instead of Shortest Paths.

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

Triangulation A*[17] 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:

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

Fringe Search[19] 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[20] (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[21] (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[22] alters the movement costs of areas where other units are going to move, so that subsequent paths avoid colliding with those units.

Corridor Maps[24] 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*[25] updates the heuristic as it explores the map. Prioritized Learning Real-Time A*[26] prioritizes the search to favor areas where it is learning more.

Compressed Path Databases[28] 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)[29] build pathfinding graphs from polygonal obstacle maps.

Email me at , or tweet to @redblobgames, or post a public comment: