A*寻路算法 - 橘子汁

今天看了一篇文章《Introduction to the A* Algorithm》讲A*算法，讲的很通透，虽然篇幅较长，不过这个算法的来源和延伸都讲得比较透彻。所以强烈建议观看原网站跟着走一遍，原网站的动画演示十分直观。
如果你不喜欢大段英文，那么这篇文章是对该博客的总结和转述，希望对各位看官有所帮助。

表达地图

首先我们要了解整个算法要处理一些什么，又会输出些什么。
对于算法来说，它不会在意你的地图上有什么元素，它唯一在意的东西就是图的位置(节点)和连接(边界)。
当你把图的顶点和边告诉它，它就会告诉你一条通往目标位置的“路”。
当然，这个“路”只是一个抽象概念，实际上只是返回一个节点接着另一个节点的数组。
所以本质上算法只会告诉你从原点到终点会经过哪些点，如何反应到游戏里那就是另外的事情了（比如通过门要开门、下水要游泳、走直线还是曲线，这些东西还得另外考虑）。
是的，你的寻路图不一定都是规则网格状的，也可能是不规则的图，虽然对于算法来说都是一样的，但是游戏里的角色穿门而过那就是影响游戏质量的BUG了。

算法

接下来是算法时间。
首先总结一下涉及到的算法：
广度优先算法 -> 迪科斯彻算法（Dijkstra’s Algorithm） -> 贪心最优搜索（Greedy Best First Search）-> A*
“->” 是原文章介绍的顺序，一步步的探索算法的演变过程，可以清晰的理解算法之间的差异和特点。

广度优先（Breadth First Search）

开始的开始，最原始的查找，往往都是遍历所有元素。
广度优先就是这样一种算法，它在做什么：

找到一个相邻点。
将它标记为已访问，扩展它的邻居（记得跳过墙，或者说障碍物）。
重复以上过程，直到没有一个未访问的相邻点。
这是最原始的广度优先算法，它会像涟漪一样泛起，然后扩散到整个地图。
所以那一圈涟漪被叫做“frontier”,边界或者前线。
```
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)
```
这样的查找实际上并不能告诉我们最短的路径在哪，它只是自由的泛滥。
广度优先算法不只是能查找路径，实际上还有很多其他的应用存在，比如距离地图、程序化地图生成等。

所以我们需要构建一个关联(came_from)，以知道来时的方向。

frontier = Queue()
frontier.put(start )
came_from = dict() # 通路 A->B 存储为 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

这只是相当于在全地图记录了一下起点方向信息，想要知道通路，我们只需要从终点倒推回起点。

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

不过就算我们获得了想要的通路，算法依然会持续下去，直到遍历完所有的节点。
而我们想要在获取目标路径之后停止循环，这样能节省很多资源。

frontier = Queue()
frontier.put(start )
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:
         frontier.put(next)
         came_from[next] = current

Dijkstra’s Algorithm

对于广度优先算法来说，所有的节点他们的“代价”是相同的，就像如履平地一般。
但是如果我想表示地图上不同的状态（比如山川、河流与平原），可能会需要不同的值来表示通过的难度。
那就需要引入“代价”这个概念了。

使用cost_so_far来记录从起点到当前节点的代价（也叫“距离场（distance field）”）
现在需要把我们记录边界节点的队列变成优先队列，以便找到下一个更优节点（代价值最小的节点）。

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

graph.cost(current, next) 这里只是返回了next的代价值。有的时候判断会用到current, next两个值。

图中绿色的地块代表高代价值的森林。
你会发现路过森林的部分走的很慢，最终最佳路线绕着森林走了过去，而广度优先直接穿过了森林。
这是因为每次找出边缘的最优节点的时候，都会在该节点的相邻节点里找到一个局部代价最优结点。
所以循环往复找到的通路也一定是最优解。

不过这样的算法边界还是往四方蔓延，所以寻找全部目标比较适用。
一般来说，目标点只有一个，如果我只往目标节点方向走，岂不是节省很多时间。

启发式搜索/贪心最佳优先搜索（Greedy Best First Search）

为了向目标方向迈进，这里引入了“启发函数”

def heuristic(a, b):
   # 方格地图的曼哈顿距离
   return abs(a.x - b.x) + abs(a.y - b.y)

启发函数有很多种：
对于四方移动（上下左右）来说，曼哈顿距离是最适合的。
八方向移动可以用切比雪夫距离。
任意方向移动一般用路点和导航网络来描述地图，比较适用欧几里得距离（勾股距离）
开方开销比较大，所以可以使用Octile距离代替

启发函数的作用是为了估算两点间距离。
在Dijkstra算法中，使用最优节点与起始节点的实际距离来作为优先级。
而在启发式搜索，改用启发函数对最优节点与目标节点的估算距离来作为节点的优先级。
不参考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

这样的好处是更快的接近目标节点

坏处是在复杂情况无法做到最优解

A*

显然最优解是很重要的，这也是为什么要使用A*而不是启发式搜索。
Dijkstra算法告诉了我们最短路线，却无法控制走向。
启发式搜索让我们更快找到目标点，却不是最短路线。
每当面临两难结局，总有人会跳出来说我全都要，这个“人”就是A*。

A*结合了Dijkstra的真实距离和启发式搜索的估计距离。
这段代码和Dijkstra的几乎一样：

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

由以上两图可以看出，当Dijkstra算法找出最佳通路的时候A*也找到了，还访问了更少的节点。
启发式搜索访问了少量的节点，但是结果却不是最优解。
只要启发函数没有高估距离，A*就能在使用启发函数排序以便快速找到方向的同时，像Dijkstra算法一样找到最优通路。

问题

寻路算法应该用哪个？

如果寻找多个目标，应该使用Dijkstra算法和广度优先算法，Dijkstra算法用于有代价的状况，广度优先适用于没有代价的状况。
如果寻找单个目标，或者最短路径，应该考虑A*算法。

关于最优解

广度优先和Dijkstra保证找出最优解。A*在估值小时倾向于Dijkstra，估值大的时候倾向于启发式搜索。

关于性能

最好的办法是减少图中不必要的位置点，减小寻路图的大小。使用最简单的算法；更简单的队列运行得更快。贪婪最佳优先搜索通常比 Dijkstra 算法运行得更快，但不会产生最佳路径。 A* 是满足大多数寻路需求的不错选择

关于非地图

这些图搜索算法可以用于任何类型的图，而不仅仅是游戏地图。地图上的移动成本可以变成图连接上的任意权重。启发式方法并不容易转化为任意地图；你必须为每种类型的图表设计一个启发式方法。