【数据结构与算法】-＞算法-＞ A* 搜索算法-＞如何实现游戏中的寻路功能？

Ⅰ 前言

你可能玩过魔兽世界，仙剑奇侠和英雄联盟这类 MMRPG 游戏，在这些游戏中，有一个非常重要的功能，就是人物角色自动寻路。当人物处于游戏地图中的某个位置的时候，我们用鼠标点击另外一个相对较远的位置，人物就会自动地绕过障碍物走过去。那么这个功能是如何实现的呢？这篇文章我们就来探索一下这个功能。

Ⅱ 算法解析

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

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

【数据结构与算法】-＞算法-＞地图软件的最优路线是如何计算的？

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

这个快速的路径规划算法，就是我们这篇文章要讲的 A 算法*。实际上，A* 算法是对 Dijkstra 算法的优化和改造。如何将 Dijkstra 算法改造成 A* 算法呢？我们逐步来看一下。如果你对 Dijkstra 算法 不熟悉，可以先跳转到我上面链接的文章中看一下。

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）。曼哈顿距离是两点之间横纵坐标的距离之和，计算的过程只涉及加减法和符号位反转，所以比欧几里得距离更加高效。

	private int hManhattan(Vertex v1, Vertex v2) {
    return Math.abs(v1.x - v2.x) + Math.abs(v1.y - v2.y);}

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

经过上面的描述，我们可以发现，A* 算法就是对 Dijkstra 算法的简单改造。实际上，在代码实现上，我们也只需要改动几个地方就可以了。

在 A* 算法的代码实现中，顶点 Vertex 类的定义，跟 Dijkstra 算法中的定义，稍微有点区别，多了 x, y 坐标，以及刚刚提到的 f(i) 值。图 Graph 类的定义跟 Dijkstra 算法中的定义一样。我还是将完整代码贴出来，具体的讲解大家可以看我的将 Dijkstra 算法的文章—— Dijkstra 算法 。

首先是 Vertex 顶点类

package com.tyz.astar.core;/*** 构造一个顶点* @author Tong*/
public class Vertex {
    int id; //顶点编号int distance; //从起始点到这个顶点的距离int f; //f(i) = g(i) + h(i)int x; //顶点在地图中的横坐标int y; //顶点在地图中的纵坐标Vertex(int id, int x, int y) {
    this.id = id;this.x = x;this.y = y;this.f = Integer.MAX_VALUE;this.distance = Integer.MAX_VALUE;}}

边的构造

package com.tyz.astar.core;/*** 构造边* @author Tong*/
public class Edge {
    private int start; 	//边的起始顶点编号private int end;	//边的终止顶点编号private int weight;	//边的权重public Edge() {
    }public Edge(int start, int end, int weight) {
    this.start = start;this.end = end;this.weight = weight;}public int getStart() {
    return start;}public void setStart(int start) {
    this.start = start;}public int getEnd() {
    return end;}public void setEnd(int end) {
    this.end = end;}public int getWeight() {
    return weight;}public void setWeight(int weight) {
    this.weight = weight;}}

优先级队列（小顶堆）

package com.tyz.astar.core;/*** 实现一个优先级队列（小顶堆）* @author Tong*/
class PriorityQueue {
    private Vertex[] nodes;private int count;public PriorityQueue(int vertex) {
    this.nodes = new Vertex[vertex+1];this.count = 0;}/*** 队首元素出队列* @return 队首元素*/Vertex poll() {
    Vertex vertex = this.nodes[1];this.nodes[1] = this.nodes[this.count--];heapifyUpToDown(1);return vertex;}/*** 添加元素并按优先级堆化* @param vertex*/void add(Vertex vertex) {
    this.nodes[++this.count] = vertex;vertex.id = this.count;heapifyDownToUp(count);}/*** 更新队列中元素的distance值* @param vertex*/void update(Vertex vertex) {
    this.nodes[vertex.id].distance = vertex.distance;heapifyDownToUp(vertex.id);}boolean isEmpty() {
    return this.count == 0;}void clear() {
    this.count = 0;}/*** 自上而下堆化* @param index*/private void heapifyUpToDown(int index) {
    while (index <= this.count) {
    int maxPos = index;if (index * 2 <= this.count && this.nodes[maxPos].distance > this.nodes[index*2].distance) {
    maxPos = 2 * index;} else if ((index * 2 + 1) <= count &&this.nodes[maxPos].distance > this.nodes[index*2+1].distance) {
    maxPos = index * 2 + 1;} else if (maxPos == index) {
    break;}swap(index, maxPos);index = maxPos;}}/*** 自下而上堆化* @param index*/private void heapifyDownToUp(int index) {
    while (index / 2 > 0 && this.nodes[index].distance < this.nodes[index / 2].distance) {
    swap(index, index / 2);index /= 2;}}/*** 交换两个元素对应的下标的值* @param index* @param maxPos*/private void swap(int index, int maxPos) {
    this.nodes[index].id = maxPos; //下标交换记录this.nodes[maxPos].id = index;Vertex temp = this.nodes[index];this.nodes[index] = this.nodes[maxPos];this.nodes[maxPos] = temp;}
}

A* 算法的代码实现和 Dijkstra 算法的代码实现，主要有三点区别：

• 优先级队列构建的方式不同。A* 算法是根据 f 值（即 f(i) = g(i) + h(i) ），来构建优先级队列，而 Dijkstra 算法是根据 distance 值（也就是 g(i) ）来构建优先级队列；
• A* 算法在更新顶点 distance 值的时候，会同步更新 f 值；
• 循环结束的条件也不一样， Dijkstra 算法是在终点出队列的时候才结束，A* 算法是一旦遍历到终点就结束。

代码实现如下?

package com.tyz.astar.core;import java.util.LinkedList;/*** A*算法实现有向有权图的两点间路径查找* @author Tong*/
public class Graph {
    private LinkedList<Edge>[] adj; //邻接表private int vertex; //顶点个数private Vertex[] vertexs;@SuppressWarnings("unchecked")public Graph(int vertex) {
    this.vertex = vertex;this.vertexs = new Vertex[this.vertex];this.adj = new LinkedList[vertex];for (int i = 0; i < vertex; i++) {
    this.adj[i] = new LinkedList<Edge>();}}/*** 添加顶点* @param id* @param x* @param y*/public void addVetex(int id, int x, int y) {
    this.vertexs[id] = new Vertex(id, x, y);}public void addEdge(int start, int end, int weight) {
    this.adj[start].add(new Edge(start, end, weight));}/*** 用A*算法求strat顶点到end顶点之间的最短距离* @param start 起始顶点* @param end 终止顶点*/public void astar(int start, int end) {
    int[] predecessor = new int[this.vertex]; //用来还原最短路径//按照顶点的f值来构建小顶堆PriorityQueue queue = new PriorityQueue(this.vertex); //小顶堆boolean[] inqueue = new boolean[this.vertex];inqueue[start] = true;this.vertexs[start].distance = 0;this.vertexs[start].f = 0;queue.add(this.vertexs[start]);inqueue[start] = true;while (!queue.isEmpty()) {
    Vertex minVertex = queue.poll(); //取堆顶元素并从队列中将其从队列中删除for (int i = 0; i < this.adj[minVertex.id].size(); i++) {
    Edge edge = this.adj[minVertex.id].get(i);Vertex nextVertex = this.vertexs[edge.getEnd()];if (nextVertex.distance > minVertex.distance + edge.getWeight()) {
    nextVertex.distance = minVertex.distance + edge.getWeight();nextVertex.f = nextVertex.distance + hManhattan(nextVertex, this.vertexs[end]);predecessor[nextVertex.id] = minVertex.id;if (inqueue[nextVertex.id] == true) {
    queue.update(nextVertex); } else {
    queue.add(nextVertex);inqueue[nextVertex.id] = true;}}if (nextVertex.id == end) {
     //只要到达终点就可以停下了queue.clear(); //将queue状态变成empty才能跳出循环break;}}}//输出路径System.out.print(start);print(start, end, predecessor);}private int hManhattan(Vertex v1, Vertex v2) {
    return Math.abs(v1.x - v2.x) + Math.abs(v1.y - v2.y);}/*** 递归打印路径* @param start* @param end* @param predecessor*/private void print(int start, int end, int[] predecessor) {
    if (start == end) {
    return;}print(start, predecessor[end], predecessor);System.out.println("->" + end);}}

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

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

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

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

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

Ⅲ 如何实现游戏寻路问题

要利用 A* 算法解决游戏寻路的问题，我们只需要将地图抽象成图就可以了。不过，游戏中的地图和一般的地图是不一样的，因为游戏中的地图并不像我们现实生活中那样，存在规划非常清晰的道路，更多的是宽阔的荒野、草坪等。所以，我们没办法用普通的抽象方法，把岔路口抽象成顶点，把道路抽象成边。

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

Ⅳ 总结

这篇文章我们说的 A* 算法属于一种启发式搜索算法（Heuristically Search Algorithm）。实际上，启发式搜索算法并不仅仅只有 A* 算法，还有很多其他算法，比如 IDA* 算法，蚁群算法，遗传算法，模拟退火算法等等，大家有兴趣可以再去看看。

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