Introduction to A*

 

from Red Blob Games

In games we often want to find paths from one location to another. A* is a commonly recommended algorithm. Breadth First Search, Dijkstra’s Algorithm, and A* are graph search algorithms that use the same basic structure. They represent the map as a graph and then find a path in that graph. If you haven’t seen node-and-edge graphs before, here’s my introductory article. Breadth First Search is the simplest of the graph search algorithms, so let’s start there, and we’ll work our way up to A*.

The key idea is that we keep track of an expanding ring called the frontier. Start the animation to see how the frontier expands:

The expanding frontier can be viewed as contour lines that stop at walls; this process is sometimes called “flood fill”:

How do we implement this? Repeat these steps until the frontier is empty:

1. Pick and remove a location from the frontier.
2. Mark the location as visited so that we know not to process it again.
3. Expand it by looking at its neighbors. Any neighbors we haven’t we haven’t seen yet we add to the frontier.

Let’s see this up close. The tile are numbered in the order we visit them. Step through to see the expansion process:

It’s only ten lines of (Python) code:

frontier = Queue()
frontier.put(start)
visited = {}
visited[start] = True

while not frontier.empty():
   current = frontier.get()
   for next in graph.neighbors(current):
      if next not in visited:
         frontier.put(next)
         visited[next] = True

This loop is the essence of the graph search algorithms on this page, including A*. But how do we find the shortest path? The loop doesn’t actually construct the paths; it only tells us how to visit everything on the map. That’s because Breadth First Search can be used for a lot more than just finding paths; in the this article I show how it’s used for tower defense, but it can also be used for distance maps, procedural map generation, and lots of other things. Here though we want to use it for finding paths, so let’s modify the loop to keep track of where we came from for every location that’s visited, and rename visited to came_from:

frontier = Queue()
frontier.put(start)
came_from = {}
came_from[start] = None

while not frontier.empty():
   current = frontier.get()
   for next in graph.neighbors(current):
      if next not in came_from:
         frontier.put(next)
         came_from[next] = current

Now came_from for each location points to the place where we came from. That’s enough to reconstruct the entire path. Mouse over any location on the map and see how following the arrows gives you a path back to the start position.

The code to reconstruct paths is simple:

current = goal
path = [current]
while current != start:
   current = came_from[current]
   path.append(current)

That’s the simplest pathfinding algorithm. It works not only on grids as shown here but on any sort of graph structure. Next we’ll explore the variants and why you might use them.

We’ve found paths from one location to all other locations. Often we don’t need all the paths; we only need a path from one location to one other location. We can stop expanding the frontier as soon as we’ve found our goal. Drag the X around see how the frontier stops expanding as soon as it reaches the X.

The code is straightforward:

frontier = Queue()
frontier.put(start)
came_from = {}
came_from[start] = None

while not frontier.empty():
   current = frontier.get()

   if current == goal:
      break           

   for next in graph.neighbors(current):
      if next not in came_from:
         frontier.put(next)
         came_from[next] = current

So far we’ve made step have the same “cost”. In some pathfinding scenarios there are different costs for different types of movement. For example in Civilization, moving through plains or desert might cost 1 move-point but moving through forest or hills might cost 5 move-points. We’d like the pathfinder to take these costs into account. Let’s compare the number of steps from the start with the distance from the start:

We want Dijkstra’s Algorithm for this. How does it differ from Breadth First Search? We need to track movement costs, so let’s add a new variable, cost_so_far, to keep track of the total movement cost from the start location. We want to take the movement costs into account when deciding how to evaluate locations; let’s turn our queue into a priority queue. Less obviously, we may end up visiting a location multiple times, with different costs, so we need to alter the logic a little bit. Instead of adding a location to the frontier if the location has never been visited, we’ll add it if the new path to the location is better than the best previous path.

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = {}
cost_so_far = {}
came_from[start] = None
cost_so_far[start] = 0

while not frontier.empty():
   current = frontier.get()

   for next in graph.neighbors(current):
      new_cost = cost_so_far[current] + graph.cost(current, next)
      if next not in cost_so_far or new_cost < cost_so_far[next]:
         cost_so_far[next] = new_cost
         priority = new_cost
         frontier.put(next, priority)
         came_from[next] = current

Using a priority queue instead of a regular queue changes the way the frontier expands. Contour lines are one way to see this. Start the animation to see how the frontier expands more slowly through the forests, finding the shortest path around the central forest instead of through it:

Movement costs other than 1 allow us to explore more interesting graphs, not only grids. Here’s an example where the movement costs are based on distance from room to room:

Movement costs can also be used to avoid or prefer areas based on proximity to enemies or allies.

An implementation detail: a regular priority queue supports insert and remove operations, but with Dijkstra’s Algorithm, we sometimes want to adjust the priority of an element already in the priority queue. We need a priority queue that supports reprioritizing. I’ll explain more on the implementation notes page.

With Breadth First Search and Dijkstra’s Algorithm, the frontier expands in all directions. This is a reasonable choice if you’re trying to find a path to all locations or to many locations. However, a common case is to find a path to only one location. Let’s make the frontier expand towards the goal more than it expands in other directions. First, we’ll define a heuristic function that tells us how close we are to the goal:

def heuristic(a, b):
   # Manhattan distance on a square grid
   return abs(a.x - b.x) + abs(a.y - b.y)

In Dijkstra’s Algorithm we used the actual distance from the start for the priority queue ordering. Here instead, in Greedy Best First Search, we’ll use the estimated distance to the goal for the priority queue ordering. The location closest to the goal will be explored first. The code uses the priority queue from Breadth First Search but not cost_so_far from Dijkstra’s Algorithm:

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = {}
came_from[start] = None

while not frontier.empty():
   current = frontier.get()

   if current == goal:
      break
   
   for next in graph.neighbors(current):
      if next not in came_from:
         priority = heuristic(goal, next)
         frontier.put(next, priority)
         came_from[next] = current

Let’s see how well it works:

Wow!! Amazing, right? But what happens in a more complex map?

Those paths aren’t the shortest. So this algorithm runs faster when there aren’t a lot of obstacles, but the paths aren’t as good. Can we fix this? Yes.

Dijkstra’s Algorithm works well to find the shortest path, but it wastes time exploring in directions that aren’t promising. Greedy Best First Search explores in promising directions but it may not find the shortest path. The A* algorithm uses both the actual distance from the start and the estimated distance to the goal.

Let’s look at the contour lines for Dijkstra’s Algorithm and Greedy Best First Search to build our intuition. In Dijsktra’s Algorithm, we start at the bottom of a hole centered at the start and climb upwards to find the goal. We’re not sure where the goal is, so we have to check all directions out of the hole. In Greedy Best First Search, we start at the bottom of a hill centered at the goal and climb up a hill to find the goal. We know where the goal is, so as long as we can move in that direction, we’re good.

A* combines the two. Instead of contour lines showing distances from start or goal, in A* the contour lines show the length of the paths. The inner region has the shortest paths. A* starts by exploring that inner region, and moves outwards only if it can’t find a path in there. Try drawing some walls to see how A* has to climb out of the innermost region to find a path.

The code is very similar to Dijkstra’s Algorithm:

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = {}
cost_so_far = {}
came_from[start] = None
cost_so_far[start] = 0

while not frontier.empty():
   current = frontier.get()

   for next in graph.neighbors(current):
      new_cost = cost_so_far[current] + graph.cost(current, next)
      if next not in cost_so_far or new_cost < cost_so_far[next]:
         cost_so_far[next] = new_cost
         priority = new_cost + heuristic(goal, next)
         frontier.put(next, priority)
         came_from[next] = current

Compare the algorithms:

You can see that A* tries to stay within the same estimated path length (which we use as the priority for the queue) as much as possible. Why does it run faster than Dijkstra’s Algorithm? Both algorithms explore the same set of locations. However, the heuristic function lets us visit the locations in a different order that makes it more likely that the goal node will be encountered sooner.

And … that’s it! That’s the A* algorithm.

Which algorithm should you use for finding paths on a game map?

• If you want to find paths from or to all all locations, use Breadth First Search or Dijkstra’s Algorithm. Use Breadth First Search if movement costs are all the same; use Dijkstra’s Algorithm if movement costs vary.
• If you want to find paths to one location, use Greedy Best First Search or A*. Prefer A* in most cases. When you’re tempted to use Greedy Best First Search, consider using A* with an “inadmissible” heuristic.

What about optimal paths? Breadth First Search and Dijkstra’s Algorithm are guaranteed to find the shortest path given the input graph. Greedy Best First Search is not. A* is guaranteed to find the shortest path if the heuristic is never larger than the true distance. As the heuristic becomes smaller, A* turns into Dijkstra’s Algorithm. As the heuristic becomes larger, A* turns into Greedy Best First Search.

What about performance? The best thing to do is to eliminate unnecessary locations in your graph. If using a grid, see this. Reducing the size of the graph helps all the graph search algorithms. After that, use the simplest algorithm you can; simpler queues run faster. Greedy Best First Search typically runs faster than Dijkstra’s Algorithm but doesn’t produce optimal paths. A* is a good choice for most pathfinding needs.

What about implementations? There are lots of implementations out there; I am not maintaining a comprehensive list. If you’re implementing it yourself, take a look at my implementation notes, which shows how to implement graphs and queues that are needed for the search algorithms. I have unoptimized Python and C++ code there, and more optimization notes.

What about non-maps? I show maps here because I think it’s easier to understand how the algorithms work by using a map. However, these graph search algorithms can be used on any sort of graph, not only game maps. Movement costs on the maps become arbitrary weights on graph edges. The heuristics don’t translate as easily to arbitrary maps; you have to design a heuristic for each type of graph. For planar maps, distances are a good choice, so that’s what I’ve used here.

I have lots more written about pathfinding here. Keep in mind that graph search is only one part of what you will need. A* doesn’t itself handle things like cooperative movement, moving obstacles, map changes, evaluation of dangerous areas, formations, turn radius, object sizes, animation, path smoothing, or lots of other topics.