Grid pathfinding optimizations

 from Red Blob Games
Mar 2014, updated Jun 2020

Pathfinding algorithms like A* and Dijkstra’s Algorithm work on graphs. To use them on a grid, we represent grids with graphs. For most grid-based maps, it works great. However, for those projects where you need more performance, there are a number of optimizations to consider.

I’ve not needed any of these optimizations in my own projects.

Change the map representation#

The first thing to consider is whether you can use a simpler graph for pathfinding. Consider the same grid map with two different pathfinding graphs:

Entire grid
Waypoints

In general, the fewer nodes A* has to process, the faster it will run. Common ways to reduce the graph size:

Note that movement can be on grid even if your map representation is not. These two have the same set of waypoints:

Line movement
Grid movement

There are multiple algorithms in computer science literature that can improve pathfinding for grid maps with grid (“L1”) movement. This paper[2] [PDF] is one example. See l1-path-finder[3] for a fast implementation and also more references to papers. There are also some approaches from the game developer community; see this paper[4] [PDF] for descriptions of those techniques (including JPS+).

Harness the grid structure#

If you can’t use an alternate graph structure for pathfinding, there are optimizations that can be applied to pathfinding running on a grid. Grids contain additional structure that graph search algorithms don’t take advantage of.

For example, if you move east one space on the grid, it’s likely that moving east again is going to be a good move. Graph algorithms however don’t know about “east” or that two edges can be in the same direction. Another example: going north then east is usually the same as going east then north. Graph algorithms don’t know this, and have to try both. These two examples suggest that there’s additional efficiency to be gained by not using pathfinding directly on the grid.

If movement is along grid nodes and you have large areas of uniformly weighted nodes, Jump Point Search jumps ahead in the grid instead of processing nodes one by one. Think of it as constructing the waypoint graph dynamically. Read about the algorithm here[5] and here[6] and here[7]. Read a discussion of JPS pros and cons here[8].

If movement is not along grid nodes and you are pathfinding on a grid, you’ll want to straighten the paths[9]. However, the straightened paths aren’t guaranteed to be the shortest. To have the pathfinder directly analyze the straightened paths, look at the Theta* Algorithm, described here[10]. AnyA is another variant to consider.

Traverse nodes faster#

Another generality in weighted graphs is the weights (varying movement costs). Dijkstra’s Algorithm and A* analyze the weights when finding the paths. Many situations don’t call for weights, and set them to 1 everywhere. This suggests that there’s additional efficiency gains that we could get if you have uniform movement costs in your map. For example, Breadth First Search is a better choice than Dijkstra’s Algorithm if you don’t need weights.

If your movement costs are uniform, or in a narrow range, consider these:

Improve the heuristic#

The purpose of the heuristic is to give an estimate of the length of the shortest path. The closer the heuristic is to the actual shortest path length, the faster A* runs. When the heuristic is 0, A* becomes Dijkstra’s Algorithm. When the heuristic is equal to the shortest path length, A* immediately finds the shortest path and doesn’t have to explore other areas. When the heuristic is larger than the shortest path length, A* no longer guarantees shortest paths. For grids, we typically use distance as the heuristic. It’s greater than 0, but less than the shortest path length, so it gives us shortest paths, but not the best speed.

For maps in general, not only grid maps, we can analyze the map to generate better heuristics. Pick a set of pivot points and then find the shortest paths between them. The path length between pivot points can then be used in the heuristic to calculate a better estimate of the shortest path length, with significant speedups possible. For more, read this A* paper from Goldberg and Harrelson[12]. I implemented this myself and got a significant speedup with under 20 lines of code. I have an incomplete writeup with some tests on real game maps.

Summary#

  1. Grids can be viewed as a special case of a graph.
  2. Grids contain additional structure not in all graphs. Standard graph search algorithms don’t take advantage of that structure.
  3. Often our maps have uniform movement costs, leading to graphs with unweighted edges. Many standard graph search algorithms spend time analyzing the weights.
  4. We use distance for the A* heuristic. It’s easy to understand and calculate, but it’s not the best heuristic. Most maps can be preprocessed to generate a better heuristic.
  5. Often the map is a grid but object movement isn’t limited to a grid. Standard graph search algorithms don’t take this into account.

Most of the time, the standard graph search algorithms are all you need. But if you need more, I hope this list gives you some ideas. Which approaches work best will depend on your game, size and style of map, number of units pathfinding, and so on. I’d love to hear what you’ve used and how well it worked.

Email me , or tweet @redblobgames, or comment: