48搜索：如何用A星搜索算法实现游戏中的寻路功能

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

游戏中常有一个功能——人物自动绕过障碍物寻路。这是怎么实现的呢？

算法解析

这是一个非常典型的搜索问题。人物经过的路径要绕过地图上所有的障碍物，并且走的路不能太绕。理论上，最短路径显然是最好的走法，是这个问题的最优解。

但是在第43节最优出行路线规划问题中说过，若地图非常大，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）。它是两点之间横纵坐标的距离之和。

int hManhattan(Vertex v1, Vertex v2) { // Vertex表示顶点，后面有定义
  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*算法。

在A*算法的代码实现中，顶点 Vertex 类的定义，跟Dijkstra 算法中的定义相比，多了x、y坐标以及 f(i) 值。而图Graph类的定义和Dijkstra 算法一样。

private class Vertex {
  public int id; // 顶点编号ID
  public int dist; // 从起始顶点，到这个顶点的距离，也就是g(i)
  public int f; // 新增：f(i)=g(i)+h(i)
  public int x, y; // 新增：顶点在地图中的坐标（x, y）
  public Vertex(int id, int x, int y) {
    this.id = id;
    this.x = x;
    this.y = y;
    this.f = Integer.MAX_VALUE;
    this.dist = Integer.MAX_VALUE;
  }
}
// Graph类的成员变量，在构造函数中初始化
Vertex[] vertexes = new Vertex[this.v];
// 新增一个方法，添加顶点的坐标
public void addVetex(int id, int x, int y) {
  vertexes[id] = new Vertex(id, x, y)
}

A*算法的实现主要是下面这段代码。跟Dijkstra 算法的代码实现相比，主要有一下三点区别：

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

public void astar(int s, int t) { // 从顶点s到顶点t的路径
  int[] predecessor = new int[this.v]; // 用来还原路径
  // 按照vertex的f值构建的小顶堆，而不是按照dist
  PriorityQueue queue = new PriorityQueue(this.v);
  boolean[] inqueue = new boolean[this.v]; // 标记是否进入过队列
  vertexes[s].dist = 0;
  vertexes[s].f = 0;
  queue.add(vertexes[s]);
  inqueue[s] = true;
  while (!queue.isEmpty()) {
    Vertex minVertex = queue.poll(); // 取堆顶元素并删除
    for (int i = 0; i < adj[minVertex.id].size(); ++i) {
      Edge e = adj[minVertex.id].get(i); // 取出一条minVetex相连的边
      Vertex nextVertex = vertexes[e.tid]; // minVertex-->nextVertex
      if (minVertex.dist + e.w < nextVertex.dist) { // 更新next的dist,f
        nextVertex.dist = minVertex.dist + e.w;
        nextVertex.f 
           = nextVertex.dist+hManhattan(nextVertex, vertexes[t]);
        predecessor[nextVertex.id] = minVertex.id;
        if (inqueue[nextVertex.id] == true) {
          queue.update(nextVertex);
        } else {
          queue.add(nextVertex);
          inqueue[nextVertex.id] = true;
        }
      }
      if (nextVertex.id == t) { // 只要到达t就可以结束while了
        queue.clear(); // 清空queue，才能推出while循环
        break; 
      }
    }
  }
  // 输出路径
  System.out.print(s);
  print(s, t, predecessor); // print函数请参看Dijkstra算法的实现
}

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

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

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

A* 算法之所以不能像 Dijkstra 算法那样，找到最短路径，主要原因是两者的 while 循环结束条件不一样。Dijkstra 算法是在终点出队列的时候才结束，A* 算法是一旦遍历到终点就结束。对于 Dijkstra 算法来说，当终点出队列的时候，终点的 dist 值是优先级队列中所有顶点的最小值，即便再运行下去，终点的 dist 值也不会再被更新了。对于 A* 算法来说，一旦遍历到终点就结束 while 循环，这时终点的 dist 值未必是最小值。A* 算法利用贪心算法的思路，每次都找 f 值最小的顶点出队列，一旦搜索到终点就不在继续考察其他顶点和路线了。所以，它并没有考察所有的路线，也就不可能找出最短路径了。

那么如何借助A*算法解决今天的游戏寻路问题呢？游戏地图中更多的是宽阔的荒野、草坪等，所以没办法把岔路口抽象成顶点，道路抽象成边。实际上，换一种抽象的思路，把整个地图分割成一个一个的小方块。在某个方块上的人物，只能往上下左右四个方向的方块上移动。把每个方块看作一个顶点，若两个方块相邻，则在它们之间连两条有向边，边的权值为1。所以，问题转变为了在一个有向有权图中，找某个顶点到另一个顶点的路径问题，可以套用A*算法了。

总结引申

本节讲的A*算法是一种启发式搜索算法（Heuristically Search Algorithm）。除了这个算法，像IDA* 算法、蚁群算法、遗传算法、模拟退火算法等都属于这类算法。

启发式搜索算法利用估价函数，避免“跑偏”，贪心地朝着最有可能到达终点的方向前进。这类算法找到的路线，并不是最短路线，但是很好地平衡路线质量和执行效率，所以应用非常广泛。

课后思考

之前讲的“迷宫问题”是否可以借助 A* 算法来更快速地找到一个走出去的路线呢？

答：对于这个问题，当前顶点与终点之间的估计距离不好定义，路径和方向相关性不强。A*算法中的贪心策略是基于方向的，所以A*算法求解迷宫问题路径可能不会更效率。