Pathfinding

This page is a hub for information about pathfinding of all types. The focus here is primarily on grid-based pathfinding, but I’ll be collecting information on all pathfinding topics as I encounter them.

Note: The topic here is pathfinding algorithms for computers. If you’re looking for information about wilderness pathfinding, your princess is in another castle. I’d recommend starting here and expanding your search from there.

You’ll find me using the terms “search” and “pathfinding” interchangably here. That’s because pathfinding is just a type of searching; you’re exploring some sort of search space to find a way to get from your starting point to a goal point, and that way is literally just a path through the search space.

What Is Pathfinding?

Pathfinding is about finding a path from one place (the start) to another (the goal). If that feels really abstract, that’s because it is. Most of the time, we think of pathfinding in terms of moving along a map of some kind, trying to find a way to move from point A to point B. But that’s just one example of pathfinding, trying to find a physical movement path. There are plenty of others, including action planning, computer networking, manufacturing, warehousing, and more. Pathfinding is about navigation through a search space, whatever form that takes.

Problems and Algorithms

Pathfinding in the literature is broken up into various types of problems that each algorithm is intended to solve. An algorithm for solving one problem won’t necessarily work for another problem, as you might expect. For instance, A* is a general graph search algorithm. It can be applied to any sort of search where you can come up with an admissible heuristic, which is a decent number of them. But ANYA is intended for solving the any-angle pathfinding problem on 2D grids, and simply won’t work on non-grid graphs (or even grid graphs with higher dimensionality).

Knowing what problem an algorithm is intended to solve, as well as figuring out what problem your particular pathfinding situation needs, is critical for choosing an appropriate algorithm and not spinning your wheels researching algorithms that aren’t appropriate for your problem.

Graph Search

Good ol’ graph searching. Graphs are nifty, and let us operate at the highest levels of abstraction. Raw nodes and connections, baby. If your problem can be represented as a collection of things that are connected to each other somehow, you can encode that as a graph and use 60+ years of academic research to fold, spindle, mutilate, and pathfind across it.

Some useful definitions:

Heuristic Function

A heuristic function (often shortened to heuristic) is a function used to estimate the minimum cost of moving from one node to another.

Choosing the right heuristic function can make a world of difference in your search algorithms. Using a heuristic function at all is what separates A* from Dijkstra’s.

Incremental Algorithm

An incremental algorithm is one that allows for multiple pathfinding searches to be made, without having to start from scratch for subsequent searches.

Algorithms

• A* is your bread and butter here. It requires you to have a heuristic that you can use to help guide the search, but most problems have one that makes sense. A* has really good properties, including guarantees about the path being optimal, and it’ll also complete if the graph is finite, regardless of whether a path exists.
• Dijkstra’s Shortest Paths is your fallback for graph search when A* isn’t viable. It’s guaranteed to find the shortest paths from your start node to the goal node, but it’s not as efficient as A*. A* is based on Dijkstra’s, so the principles are very similar.
• BFS (Breadth-First Search) is your final resort for pathfinding on generic graphs. It’ll find a path if one exists, but there’s no guarantee that that path will be a shortest path, and it’s going to be slooooooow. You’d only use this if your problem doesn’t have any sort of costs, since that means that the graph is unweighted, meaning the bookkeeping necessary to perform Dijkstra’s and A* provide no benefit and just slow things down with extra work. If your graph edges have weights, use Dijkstra’s instead.
• LPA* (Lifelong Planning A*) is an incremental heuristic algorithm that keeps track of additional information about nodes as it performs a normal A* search through the graph. Then when the graph changes (connectivity or edge weights), the previous path gets re-examined and costs adjusted appropriately before allowing search to resume.
• D*-Lite is an incremental heuristic algorithm that is based on LPA*, but behaves differently. LPA* does its work from start to goal, whereas D*-Lite does its work starting at the goal and working backwards through the graph.

Grid Search

Alas, this is not a digital frontier, Quorra will not be making an appearance. A grid is a collection of tiles that are connected to one another in a regular fashion. A chessboard is a grid. A hexcrawl map is a grid. The voxel world of Minecraft is a (3D) grid. Typically someone will mean a rectangular grid when they talk about a grid or a gridworld.

Grid search is a subtype of graph search. If it works on graphs, it’ll work on grids.

Grids have more constraints than a graph, though, and those constraints are what let us design more efficient algorithms for pathfinding across them.

For example, when moving across a grid, you will have a direction of movement from one tile to another. General graphs do not have that notion of direction, only connectivity. That directionality allows us to optimize which tiles we should explore next, and which ones we can ignore; there’s no reason to explore the tile we just came from, nor is there a reason to explore that tile’s neighbors, which on an 8-connected grid will be 2 of the 8 neighbors for the current tile. That’s almost half of the potential tiles from our search space, just because the structure of the grid lets us know that those tiles aren’t worth exploring.

Grid search, especially 2D grid search, is a heavily researched topic, and there are a number of problems and terms worth discussing:

4-Connected Grid

A 4-connected grid is one where movement between tiles is only allowed in the 4 cardinal directions (N/S/E/W). As this means that each tile is connected to at-most 4 other tiles, the naming becomes apparent.

8-Connected Grid

An 8-connected grid is one where movement between tiles is allowed in the 4 cardinal directions, as well as the diagonals between them (NE/SE/SW/NW).

Movement Cost

The movement cost on a grid is the cost incurred to move from one tile to another.

This cost is very abstract, and can mean just about anything. Difficulty of movement through terrain, uphill-downhill slopes, etc. You can encode terrain types with it, such as Roads have a cost of 1, Grass has a cost of 2, and Swamps have a cost of 10. This would result in A* (as well as most others) exploring at least 5 Grass tiles away from a Swamp tile before deciding to explore that tile to potentially be used in a final path.

Very often you’ll see folks encoding preferences into the cost function; for instance, if you want to avoid a specific tile if at all possible, but still allow it as a valid tile for a path if you don’t have better options, you can crank up the cost of that specific tile to well above the cost of other tiles. While conceptually different, the math of this works out the exact same as for different terrain types.

Uniform Cost Grid

A uniform cost grid is one that does not have any difference in the cost for moving between tiles.

Algorithms

• JPS (Jump Point Search) is a standard algorithm for pathfinding on grids. It uses the same baseline search as A*, but structures the order in which it explores the grid to allow it to optimize more heavily in excluding tiles from being explored. This allows it to perform several orders of magnitude faster than a regular A* search.
  • JPS is normally described in terms of a uniform cost grid, but it can be adapted to variable cost grids by adding a single additional movement cost check to it’s tile exploration criteria.
  • There are also further optimizations to JPS (referred to as JPS+), but these involve preprocessing the map, or are restricted to uniform cost grids. Sometimes this makes sense, sometimes it does not.
• RSR (Rectangular Symmetry Reduction) is an optimization for uniform cost grids where you preprocess your grid into rectangles composed entirely of tiles with a single cost. Since the cost of every tile inside the rectangle is the same, you can ignore everything that isn’t on the perimeter of the rectangle when pathfinding across the overall grid, because you know the optimal path between any two tiles on the perimeter of the rectangle.
• HAA* (Hierarchical Annotated A*) is an algorithm that preprocesses the grid into chunks that it then uses for an A* search. This reduces the search space significantly, speeding up A* significantly compared to searching across the individual tiles directly.
  • HAA* also includes clearance values for tiles, which allows it to handle pathfinding for agents that don’t have a uniform size on the grid (larger units, squads of units in formation, etc.).

Why This Page?

Honestly, there are plenty of pages covering pathfinding out on the internet. But I primarily have two goals with this section of the site:

Aggregation

I want to have a place where I can easily aggregate and reference my knowledge as I keep exploring the field. After a while, it’s easy to forget precisely which paper you read that introduced a particular concept, and where you can find that paper. This is just made harder by the fact that most academic papers are distributed as PDFs, so you can quickly end up with a giant pile of files and a bunch of free-floating knowledge in your head but no good way to cross-reference them.

Distribution

Pathfinding as a field is unfortunately inaccessible to the average developer. There have been 6 decades of progress since A* was first introduced, but it’s still the most advanced tool that we tend to hand to folks when they’re looking to do some sort of search process. Most of that boils down to the academic literature being very difficult to read. This isn’t unique to CS, but it’s still a hurdle that most folks simply can’t overcome.

If I’m going to the effort of gathering together my knowledge and distilling it into something useful for myself, I might as well make it usable for other folks. Hopefully my descriptions of the more complicated algorithms will help others understand them enough to be able to use them on their own problems.

Raw Papers List

Here’s a non-comprehensive list of pathfinding research papers, for ease of reference and access. Not all of these have been distilled into this page.

Paper Name	Algorithm(s)	Notes
Computing the Shortest Path: A* Search Meets Graph Theory	ALT	Introduces the idea of ALT algorithms, A*-based algorithms that use landmarks, locations with precomputed paths to all other nodes, as a minimum bound heuristic for A*. This works for all types of graphs, not just grids.
Near Optimal Hierarchical Path-Finding	HPA*
Hierarchical Path Planning for Multi-Size Agents in Heterogeneous Environments	HAA*
Fast and Optimal Pathfinding	JPS, JPS+, RSR, ANYA	Thesis laying out JPS, JPS+, and RSR, 3 very useful algorithms for grid-based search. Also includes discussion of how to apply JPS to weighted cost grids.
D* Lite	D*-Lite
Using Swamps to Improve Optimal Pathfinding	Swamps	Original paper discussing Swamps; subsumed by Swamp Hierarchies (but still good for getting a detailed understanding of Swamps as a concept).
Search Space Reduction Using Swamp Hierarchies	Swamps, Swamp Hierarchies	Improves on Swamps by combining them into hierarchies, allowing more use of detected swamps, and allowing detection (and use) of dependent swamps. Also provides a generic algorithm for building Swamp hierarchies, and mentions that anything adjacent to an obstacle can be a seed node.
Fast, Optimal Pathfinding with Compressed Path Databases	CPD	Original paper presenting the idea of compressed path databases, including some simple optimizations to reduce required space.
Path Planning with Compressed All-Pairs Shortest Paths Data	CPD, Copa	Introduces the List Trimming optimization for CPD compression, as well as the Copa pathfinding algorithm which uses it.
Moving Target Search with Compressed Path Databases	MtsCopa, CPD	First publication of MtsCopa, an extension of the Copa algorithm which applies CPDs to moving-target search problems.
Fast Algorithm for Catching a Prey Quickly in Known and Partially Known Game Maps	MtsCopa, CPD	Updates MtsCopa to handle traversability changes on the underlying graph.
Compressed Path Databases with Ordered Wildcard Substitutions	CPD	Provides further optimizations for CPDs to reduce their size.
Path Planning with CPD Heuristics	CPD, A*	Uses CPDs as a heuristics source for A*, providing upper and lower bounds on the path to speed up the search.
Repairing Compressed Path Databases on Maps with Dynamic Changes	CPD	Provides an algorithm for updating a CPD when the graph changes, without needing to recompute the entire CPD from scratch.
Cutting the Size of Compressed Path Databases With Wildcards and Redundant Symbols	CPD	Provides optimizations for reducing CPDs, by using heuristic wildcard symbols that trade explicit movement storage for online data calculation, and also abstracting away square sections of heuristic wildcards (proximity wildcards).
Bounded Suboptimal Path Planning with Compressed Path Databases	CPD
Contracting and Compressing Shortest Path Databases	CPD, A*	Combines contraction hierarchies with CPDs to produce an algorithm that mixes the static path lookups of CPDs with the online searching of A* across a smaller graph than the original input graph.
More Flexible Proximity Wildcards Path Planning with Compressed Path Databases	CPD	Provides optimizations for CPDs, generalizing proximity wildcards to rectangular areas (instead of the squares used by previous work), and building on rectangular proximity wildcards to produce quadrants of RPWs.
The Fringe-Saving A* Search Algorithm - A Feasibility Study	FSA*	Introduces FSA*, an incremental version of A* that improves performance across repeated pathfinding calls where traversability changes.
Dynamic Fringe-Saving A*	DFSA*	Builds on FSA* to make it capable of handling moving goal nodes in addition to traversability changes.
Multi-agent Path Planning and Network Flow