在魔兽世界之类的游戏中，有一个非常重要的功能，那就是人物角色自动寻路。当人物处于游戏地图中的某个位置的时候，我们用鼠标点击另外一个相对较远的位置，人物就会自动地绕过障碍物走过去。你有没有想过，这个功能是怎么实现的呢？

实际上，这是一个非常典型的搜索问题。人物的起点就是他当下的位置，终点就是鼠标点击的位置。我们需要在地图中，找一条从起点到终点的路径。这条路径要绕过地图中所有障碍物，并且看起来要是一种非常聪明的走法。所谓“聪明”，笼统地解释就是，走的路不能太绕。理论上讲，最短路径显然是最聪明的走法，是这个问题的最优解。

不过，在地图软件如何计算出最优路径，我们也讲过，如果图非常大，那Dijkstra最短路径算法的执行耗时会很多。在真实的软件开发中，我们面对的是超级大的地图和海量寻路请求，算法的执行效率太低，这显然是无法接受的。

实际上，像出行路线规划，游戏寻路，这些真实软件开发中的问题，一般情况下，我闪都不需要非得求最优解（也就是最短路径）。在权衡路线规划质量和执行效率的情况下，我们只需要寻求一个次优解就足够了。那如何快速找出一条接近于最短路线的次优路线呢？

这就是我们今天要学习的 A 算法*。实际上，A* 算法是对Dijkstra算法的优化和改造。如何将Dijkstra算法改造成A* 算法呢？

Dijkstra算法有点儿类似BFS算法，它每次找到跟起点最近的顶点，往外扩展。这种往外扩展的，其实有些盲目。为什么这么说呢?举个例子来解释下。下面这个图对应一个真实的地图，每个顶点在地图中的位置，我们用一个二维坐标（x , y）来表示，其中，x表示横坐标，y表示纵坐标。

Dijkstra算法的实现中，我们用一个优先级队列，来记录已经遍历到的顶点以及这个顶点与起点的路径长度。基点与起点路径长度越小，就越先被从优先级队列中取出来扩展，从图中可以看出，尽管我们找的是从s到t的路径，但是最先被搜索到的顶点依次是1，2，3。这个搜索方向跟我们期望的路线方向（从s到t是从西向东）是反着的，路线搜索的方向明显“跑偏”了。

之所以会“跑偏”，那是因为我们是按照顶点与起点的路径长度大小，来安排出队列顺序的。与起点越近的顶点，就会越早出队列。这里并没有考虑顶点到终点的距离。所以，尽管1，2，3三个顶点离起始顶点最近，但离终点却越来越远。

如果我们综合更多因素，综合判断哪个顶点该出队列，那是不是就可以避免“跑偏”呢？

当我们遍历某个顶点的时候，从起点走到这个顶点的路径长度是确定的，我们记作 g(i)(i 表示顶点编号)。从这个顶点到络的路径长度，我们是未知的，但可以用其他估计值来代替。

这里我们通过这个顶点跟络之间的直线距离，也就是欧几里得距离，来近似地估计这个顶点跟终点的路径长度（路径长度跟直线距离是两个概念）。我们把这个距离记作h(i)(i表示这个顶点的编号)，专业的叫法是启发函数（heuristic function）。因为欧几里得距离的计算公式，会涉及耗时的开根号计算，所以，我们一般通过另外一个更加简单的距离计算公式，那就是**曼哈顿距离（Manhattan distance）**曼哈顿距离是两点之间横纵坐标的距离之和。计算的过程只涉及加减法、符号位反转，所以比欧几里得距离更加高效。

原来只是单纯地通过顶点与起点之间的路径长度g(i)，来判断谁先出队列，现在有了顶点到终点的路径长度估计值，我们通过两者之和 f(i) = g(i) + h(i)，来判断哪个顶点该先出队列。综合两部分，我们就能有效避免刚刚讲的“跑偏”。这里 f(i) 的专业叫法是估价函数（evaluation function）。

从刚刚的描述，我们可以发现，A算法就是对Dijkstra算法简单改造。实际上，代码实现方面，我们也只需要稍微改动几行代码，就能把Dijkstra算法的代码实现，改成A算法的代码实现。

在A*算法的代码实现中，顶点Vertex类的定义，跟 Dijdstra算法中的定义，稍微有点儿区别，多了x,y坐标，以及刚刚提到的f(i)值。图 Graph 类的定义跟 Dijkstra算法中的定义一样，这里就不再贴出来了。

A*算法的代码实现的主要逻辑是下面这段代码。它跟Dijkstra算法代码实现，主要有3点区别

尽管A*算法可以更加快速的找到从起点到终点的路线，但是它并不能像Dijstra算法那样，找到最短路线，这是为什么呢？

要找出起点 s 到终点 t 的最短路径，最简单的方法是，通过回溯穷举所有从s 到 t 的不同路径，然后对比找出最短的那个，不过显然，回溯算法的执行效率非常低，是指数级别的。

Dijkstra 算法在此基础上，利用动态规划的思想，对回溯搜索进行剪枝，只保留起点到某个顶点的最短路径，继续往外扩展搜索。动态规划相较于回溯搜索，只是换了一个实现思路，但实际上也考察到了所有从起点到终点的路线，所以才能得到最优解。

A算法不能像Dijkstra算法那样，找到最短路径，主要原因是两者while循环结束条件不一样。Dijkstra算法是在终点出队的时候才结束，A算法是一旦遍历到终点就结束。对于Dijkstra算法来主，当终点出队的时候，终点的dist值是优先级队列中所有顶点的最小值，即便再运行下去，终点的dist值也不会被更新了。对于 A* 算法来说，一旦遍历到终点，我们就结束while循环，这个时候，终点dist值未必是最小值。

A* 算法利用贪心算法的思路，每次都找 f 值最小的顶点出队列，一旦搜索到终点就不在继续考察其他顶点和路线了。所以，它并没有考察所有的路线，也就不可能找出最短路径了。

再来看下，如何借助A*算法解决今天的游戏寻路问题？

我们只需要把地图，抽象成图就可以了。不过，游戏中的地图跟平常用的地图是不一样的。因为游戏中的地图并不像现实生活中的那样，存在规划非常清晰的道路，更多的是宽阔的荒野、草坪等。所以没法把岔路口抽象成顶点，把道路抽象成边。

实际上，我们可以换一种抽象的思路，把整个地图分割成一个一个的小方块。在某一个方块上的人物，只能往上下左右四个方向的方块上移动。我们可以把每个方块看作一个顶点。两个方块相邻，我们就在它们之间，边两条有向边，并且边的权值都是1。所以，这个问题，就转化成了，在一个有向有权图中，找某个顶点到另一个顶点的路径问题。将地图抽象成边权值为1的有向图之后，我们就可以套用A*算法，来实现游戏中人物的自动寻路功能了。

我们今天讲的A算法，属于一种启发式搜索算法（Heuristically search Algorithm）。实际上，启发式搜索算法并不仅仅只有A算法，还有很多其它算法，如 IDA* 算法，蚁群算法、遗传算法、模拟退火算法等。

启发式搜索算法利用估价函数，避免“跑偏”，贪心地朝着最有可能到达终点的方向前进。这种算法找出的路线，并不是最短路径。但是，实际的软件开发中路径规划问题，我们往往并不需要非得找最短路径。所以，鉴于启发式搜索算法能很好的平衡路线质量和执行效率，它在实际软件开发中应用更加广泛。