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.
Recommended: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.
Recommended:Route Planning in Transportation Networks[11] is a nice paper describing many different optimizations including differential heuristics, arc flags, geometric containers, cluster distances, path databases, vertex/arc separators, contraction hierarchies, reach, labeling algorithms, transit nodes, batching, and more. This paper is focused on road networks but many of these techniques apply to other types of graphs too. They list optimizations that can make pathfinding one million times faster than Dijkstra’s Algorithm.
Patrick Lester had a page describing a two-level pathfinder[12]. Hierarchical Planning A*[13] (HPA*) can turn a grid representation into a simplified graph.
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 a paper Simplest Paths: Automated Route Selection for Navigation (2003)[15] that says that simpler paths aren’t too much longer than shortest paths, and easier for people to understand.
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:
Fringe Search[18] 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[19] (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[20] (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[21] alters the movement costs of areas where other units are going to move, so that subsequent paths avoid colliding with those units.
Corridor Maps[23] 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*[24] updates the heuristic as it explores the map. Prioritized Learning Real-Time A*[25] prioritizes the search to favor areas where it is learning more.
IDA* runs faster with a hex grid than a square grid[26](!).
Compressed Path Databases[27] 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)[28] build pathfinding graphs from polygonal obstacle maps.
Engineering Route Planning Algorithms[29] (Delling, Sanders, Schultes, Wagner) describes various optimizations developed between 2005 and 2008: separators, edge flags, landmarks, highway hierarchies, transit nodes, contraction hierarchies, and gives estimates of the speedups (including some over 1,000,000X times faster). This looks like a nice survey paper.