这是用户在 2025-1-23 11:24 为 https://www.redblobgames.com/pathfinding/a-star/introduction.html 保存的双语快照页面,由 沉浸式翻译 提供双语支持。了解如何保存?

Introduction to the A* Algorithm
A* 算法简介

  from Red Blob Games
来自 Red Blob Games
Created 26 May 2014, updated Aug 2014, Feb 2016, Jun 2016, Jun 2020, Jul 2023
创建于 2014 年 5 月 26 日,更新于 2014 年 8 月、2016 年 2 月、2016 年 6 月、2020 年 6 月、2023 年 7 月

Graph search algorithms let us find the shortest path on a map represented as a graph. Move the blob (start point) and cross (end point) to see the shortest path found by the A* Algorithm:
图形搜索算法让我们可以找到以图形表示的地图上的最短路径。移动 blob (start point) 和 cross (end point) 以查看 A* 算法找到的最短路径:

A* is one of a family of related graph search algorithms:
A* 是一系列相关图形搜索算法之一:

Breadth First Search[1] explores equally in all directions.
广度优先搜索[1] 在各个方向上均等地探索。
Dijkstra’s Algorithm[2] takes into account movement costs.
Dijkstra 的算法[2] 考虑了移动成本。
A*[3] explores more towards a single destination.
A*[3] 更多地探索了单一目的地。

In addition to finding a shortest path, these algorithms can be used for distance maps, flow field pathfinding, connected components, map analysis, garbage collection algorithms, flow networks, and procedural map generation. There are many optimizations and specializations of these algorithms.
除了查找最短路径外,这些算法还可用于距离图、流场寻路、连通分量、地图分析、垃圾收集算法、流网络和程序化地图生成。这些算法有许多优化和专业化。

Representing the map  表示地图#

The first thing to do when studying an algorithm is to understand the data. What is the input? What is the output?
研究算法时要做的第一件事是理解数据。输入是什么?输出是什么?

Input: Graph search algorithms, including A*, take a “graph” as input. A graph is a set of locations (“nodes”) and the connections (“edges”) between them. Here’s the graph I gave to A*:
输入:图形搜索算法(包括 A*)将“图形”作为输入。图表是一组位置(“节点”)和它们之间的连接(“边缘”)。这是我给 A* 的图表:

Different map with the same pathfinding graph
Sprites by StarRaven - see footer for link
StarRaven 的精灵 - 见页脚的链接

A* doesn’t see anything else. It only sees the graph. It doesn’t know whether something is indoors or outdoors, or if it’s a room or a doorway, or how big an area is. It only sees the graph! It doesn’t know the difference between this map and .
A* 看不到任何其他内容。它只能看到图表。它不知道某物是在室内还是室外,或者是房间还是门口,也不知道区域有多大。它只能看到图表!它不知道这张地图和<按钮 data-immersive-translate-walked=“687ac0ed-5671-46d3-8148-dcca5cf72c6f” id=“show-graphs1-different-map” class=“hover”>另一个之间的区别。

Output: The path found by A* is . The edges are abstract mathematical concepts. A* will tell you to move from one location to another but it won’t tell you how. Remember that it doesn’t know anything about rooms or doors; all it sees is the graph. You’ll have to decide whether a graph edge returned by A* means moving from tile to tile or walking in a straight line or opening a door or swimming or running along a curved path.
输出:A* 找到的路径是 。边是抽象的数学概念。A* 会告诉您从一个位置移动到另一个位置,但不会告诉您如何移动。请记住,它对 rooms 或 doors 一无所知;它看到的只是图表。您必须确定 A* 返回的图形边缘是表示从一个图块移动到另一个图块,还是沿直线行走,或者打开一扇门,或者游泳,还是沿着弯曲的路径跑步。

Tradeoffs: There are many different ways of turning a game map into a pathfinding graph. Instead of making doorways into nodes, what if we made ? What if we used ?
权衡:将游戏地图转换为寻路图的方法有很多种。如果我们?如果我们使用

The pathfinding graph doesn’t have to be the the same as the original problem being solved. A grid map can use a non-grid pathfinding graph, or vice versa. A* runs fastest with the fewest graph nodes; grids are often easier to work with but result in lots of nodes. This page covers the A* algorithm but not graph design; see my other page[4] for more about graphs. For the explanations on the rest of the page, I’m going to use grids because it’s easier to visualize the concepts, but all of these algorithms and sample code work on non-grids too.
寻路图不必与要解决的原始问题相同。网格映射可以使用非网格寻路图,反之亦然。A* 运行速度最快,图形节点最少;网格通常更容易使用,但会导致大量节点。本页介绍 A* 算法,但不介绍图形设计;有关图表的更多信息,请参阅我的其他页面。对于本页其余部分的解释,我将使用网格,因为它更容易可视化概念,但所有这些算法和示例代码也适用于非网格。

The key idea for all of these algorithms is that we keep track of an expanding ring called the frontier. On a grid, this process is sometimes called “flood fill”, but the same technique also works for non-grids. Start the animation to see how the frontier expands    
所有这些算法的关键思想是,我们跟踪一个称为 frontier 的扩展环。在网格上,此过程有时称为 “flood fill”,但相同的技术也适用于非网格。启动动画,了解 Frontier 如何扩展   


How do we implement this? Repeat these steps until the frontier is empty:
我们如何实现这一点?重复这些步骤,直到 frontier 为空:

  1. Pick and remove a location from the frontier  
    边界中选取并删除一个位置  
  2. Expand it by looking at its neighbors          . Skip walls. Any unreached neighbors we add to both the frontier and the reached set      .
    通过查看其邻居  来扩展它 跳过墙壁。我们添加到边界到达集合中的任何未得之邻 → 。   

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:
它只有十行 (Python) 代码:

frontier = Queue()
frontier.put(start )
reached = set()
reached.add(start)

while not frontier.empty():
   current = frontier.get()
   for next in graph.neighbors(current):
      if next not in reached:
         frontier.put(next)
         reached.add(next)

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 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 been reached, and rename the reached set to a came_from table (the keys of the table are the reached set):
这个循环是本页图搜索算法的精髓,包括 A*。但是我们如何找到最短的路径呢?循环实际上并不构造路径;它只告诉我们如何访问地图上的所有内容。这是因为广度优先搜索的用途不仅仅是查找路径;在本文中,我将展示它如何用于塔防,但它也可以用于距离图、程序化地图生成和许多其他内容。在这里,我们想用它来查找路径,所以让我们修改循环以跟踪我们到达的每个位置的来源,并将到达的集合重命名为came_from表(表的键是到达的集合):

frontier = Queue()
frontier.put(start )
came_from = dict() # path A->B is stored as came_from[B] == A
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. They form a “flow field” and act like “breadcrumbs”. They’re enough to reconstruct the entire path. Move the cross to see how following the arrows gives you a reverse path back to the start position.
现在,每个位置的 came_from 都指向我们来自的地方。它们形成一个 “流场” 并充当 “面包屑”。它们足以重建整个路径。移动十字,看看跟着箭头走怎么能让你的反向路径回到起始位置。

To reconstruct paths: follow the arrows backwards from the goal to the start. A path is a sequence of edges, but often it’s easier to store the nodes:
要重建路径:按照箭头目标向后走到起点。路径是一系列边缘,但通常存储节点更容易:

current = goal path>
path = []
while current != start: 
   path.append(current)
   current = came_from[current]
path.append(start) # optional
path.reverse() # optional

That’s the simplest pathfinding algorithm. It works not only on grids as shown here but on any sort of graph structure. In a dungeon, graph locations could be rooms and graph edges the doorways between them. In a platformer, graph locations could be locations and graph edges the possible actions such as move left, move right, jump up, jump down. In general, think of the graph as states and actions that change state. I have more written about map representation here[5]. In the rest of the article I’ll continue using examples with grids, and explore why you might use variants of breadth first search.

Early exit#

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 around see how the frontier stops expanding as soon as it reaches the goal.

Without early exit
With early exit

We add a test when removing a node (not when adding a node):

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

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

   if current == goal: path>
      break           

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

There are lots of cool things you can do with early exit conditions.

Movement costs#

So far we’ve made steps 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. In the map at the top of the page, walking through water cost 10 times as much as walking through grass. Another example is diagonal movement on a grid that costs more than axial movement. 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:

Number of steps
Distance

For this we want Dijkstra’s Algorithm (or Uniform Cost Search). How does it differ from Breadth First Search? We need to track movement costs, so let’s add a new variable, cost_so_far. This stores the total movement cost from the start location, also called a “distance field”. 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 reached, 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 = dict()
cost_so_far = dict()
came_from[start] = None
cost_so_far[start] = 0

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

   if current == goal:
      break
   
   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:

Breadth First Search
Dijkstra’s Algorithm

Movement costs other than 1 allow us to explore more interesting graphs, not only grids. In the map at the top of the page, movement costs were based on the distance from room to room. Movement costs can also be used to avoid or prefer areas based on proximity to enemies or allies.

Implementation notes: We want this priority queue to return the lowest value first. On the implementation page I show PriorityQueue  in Python using heapq to return the lowest value first and also in C++ using std::priority_queue configured to return the lowest value first. Also, the version of Dijkstra’s Algorithm and A* I present on this page differs from what’s in algorithms textbooks. It’s much closer to what’s called Uniform Cost Search. I describe the differences on the implementation page.

Heuristic search#

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 Dijkstra’s Algorithm but without cost_so_far:

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = dict()
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:

Dijkstra’s Algorithm
Greedy Best-First Search

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

Dijkstra’s Algorithm
Greedy Best-First Search

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!

The A* algorithm#

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.

The code is very similar to Dijkstra’s Algorithm:

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

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

   if current == goal:
      break
   
   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: Dijkstra’s Algorithm calculates the distance from the start point. Greedy Best-First Search estimates the distance to the goal point. A* is using the sum of those two distances.

Dijkstra’s Algorithm
Greedy Best-First
A* Search

Try opening a hole in the wall in various places. You’ll find that when Greedy Best-First Search finds the right answer, A* finds it too, exploring the same area. When Greedy Best-First Search finds the wrong answer (longer path), A* finds the right answer, like Dijkstra’s Algorithm does, but still explores less than Dijkstra’s Algorithm does.

A* is the best of both worlds. As long as the heuristic does not overestimate distances, A* finds an optimal path, like Dijkstra’s Algorithm does. A* uses the heuristic to reorder the nodes so that it’s more likely that the goal node will be encountered sooner.

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

More#

Are you ready to implement this? Consider using an existing library. If you’re implementing it yourself, I have companion guide that shows step by step how to implement graphs, queues, and pathfinding algorithms in Python, C++, and C#.

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

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 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 maps, and I’ve tried to present the algorithm code in a way that’s independent of 2D grids. Movement costs on the maps become arbitrary weights on graph edges. The heuristic encodes information about the graph, so 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 written more notes about pathfinding[7]. 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.

Email me , or tweet @redblobgames, or comment: