A×算法：

In
games we often want to find paths from one location to another. We’re
not just trying to find the shortest distance; we also want to take
into account travel time. In this map, walking through water is
significantly slower, so we want to find a path that avoids water
when possible. This is an interactive diagram. Click on the map to
cycle through floor, grass, sand, water, and walls/trees. Move the
blob (start point) and “X” (end point) to see the shortest path.	

在游戏中我们经常想要找到从一个点到另一个点的路径。我们不仅仅尝试着找到最短的距离；我们也想要考虑到耗费时间。在图中，越过水时明显慢了，所以我们想要找一个路径，如果可能的话避开水路。这是一个交互的图表。在地图上点击去绕过洪水，草地，沙子，水池，以及墙或者树。找到从起始点到终点的最短路。

How
would we calculate this path? A* is the most
commonly used algorithm in games. It is one of a family of graph
search algorithms that follow the same structure. These
algorithms 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. For this article, graph nodes will be
locations on the map. 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*.

我们该怎么计算这样的一条路径呢？A*在游戏领域是个最常用的算法。它是路径搜索算法家族中遵循这同样结构的一个。这些算法把地图看成图的结构，然后在图中找到这样的一条路径。如果你之前没有接触到节点-边缘图，这里有一个介绍该内容的文章（http://www.redblobgames.com/pathfinding/grids/graphs.html）。文章中，图中节点将被分配到地图中。广度有限算法是图形搜索算法中最容易的算法，所以然我们从这里开始，我们将按着我们的方式去学习A*算法。

The
key idea for all of these algorithms 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:

我们该怎样实现这个算法呢？重复下面这些步骤直到前驱为空：

1.从前驱中挑选并且移除一个节点位置；

2.标记这个位置为已经访问过，以使我们直到不再去路过它；

3.靠观察它的另据来扩大范围。任何我们没有观察过的邻居要添加到前驱中。

让我们看一下直到结束。这些瓷砖是以我们访问过来编号。以这个方式去模拟，来看看这个扩张过程。

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

用python写的话只有十行代码：

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 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:

这个循环在页面中的图搜索算法是必须的，包括A*算法。但是我们该怎么去找到最短的路径呢？这个循环事实上不能构造出这样的路径；它只是告诉我们怎样去访问所有的查找路径；在这个文章中，我将展示如何将它应用在塔防游戏中，但是它也不能被用于远距离的地图中，程序中地图的生成，以及大量的其他的事情上。然而我们想要将它使用到路径搜索上，所以让我们修改这个循环去跟踪我们来时的每一个已经访问过的路径，并且重新标记visited给来的路径节点上。

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.

现在