共计 4048 个字符，预计需要花费 11 分钟才能阅读完成。
摘要：在游戏中，只须要鼠标微微的一点，零碎会立刻寻找离角色最近的一条路线。这背地的行为逻辑又有什么神秘呢？
作者：_JohnserfSeed_
可是，这背地的行为逻辑又有什么神秘呢？你会怎么写这个寻路算法呢？
个别咱们遇到这种门路搜寻问题，大家首先能够想到的是 广度优先搜索算法 (Breadth First Search)、还有 深度优先 (Depth First Search)、 弗洛伊德（Floyd）、迪杰斯特拉 (Dij) 等等这些十分驰名的门路搜索算法，然而在绝大多数状况下这些算法面临的毛病就裸露了进去：工夫复杂度比拟高。
所以，大部分环境里咱们用到的是一个名叫 A* (A star) 的搜索算法
说到最短门路呢，咱们就不得不提到广度优先遍历（BFS），它是一个万能算法，它不单单能够用在 寻路或者搜寻的问题上。windows的零碎工具：画板 中的油漆桶就是其比拟典型一个的例子。
这里对门路搜寻做一个比拟简洁的示例
假如咱们是在一个网格下面进行最短门路的搜寻
咱们只能上下左右挪动，不能够穿梭障碍物。算法的目标是为了能让你寻找到一条从终点到站点的最短门路
假如每次都能够上下左右朝 4 个方向进行挪动
算法在每一轮遍历后会标记这一轮摸索过的方块称为边界（Frontier）, 就是这些绿色的方块。
而后算法呢会周而复始的从这些边界方块开始，朝他们上下左右四个方向进行摸索，直到算法遍历到了起点方块才会进行。而最短门路呢就是算法之前一次摸索过的门路。为了失去算法摸索过的整条门路呢，咱们能够在搜寻的过程中趁势记录下门路的来向。
比方这里方块上的红色箭头就代表了之前方块的地位
在每一次摸索门路的时候，咱们要做的也只是额定的记录下这个信息
要留神，所有摸索过的门路咱们须要将它们标记成灰色，代表它们“曾经被拜访过“，这样子算法就不会反复摸索曾经走过的门路了。
广度优先算法显然能够帮忙咱们找到最短门路, 不过呢它有点傻, 因为它对门路的寻找是没有方向性的，它会向各个方向探测过来。
最坏的状况可能是找到起点须要遍历整个地图，因而很不智能，咱们须要一个更加高效的算法。
就是本次咱们要介绍的 A *（A star） 搜索算法
A* Search Algorithm
”A* 搜索算法“也被叫做“启发式搜寻”
与广度优先不同的是，咱们在每一轮循环的时候不会去摸索所有的边界方块（Frontier），而会去抉择以后“代价（cost）”最低的方块进行摸索。
这里的“代价”就很有意思了，也是 A * 算法智能的中央。
咱们能够把这里的代价分成两局部，一部分是“以后途程代价（可示意成 f-cost）”：比方你从终点登程一共走过多少个格子，f-cost 就是几。
另一部分是“预估代价（可示意成g-cost）”：用来示意从以后方块到再起点方块大略须要多少步，预估预估所以它不是一个准确的数值，也不代表从以后地位登程就肯定会走那么远的间隔，不过咱们会用这个估计值来领导算法去优先搜寻更有心愿的门路。
最罕用到的“预估代价”有欧拉间隔（Euler Distance）“，就是两点之间的直线间隔(x1 – x2)^2 + (y1 – y2)^2
当然还有更容易计算的“曼哈顿间隔（Manhattan Distance）”，就是两点在竖直方向和程度方向上的间隔总和|x1 – x2|+|y1 – y 2|
曼哈顿间隔不必开方，速度快，所以在 A * 算法中咱们能够用它来充当g-cost。
接下来，咱们只有把之前讲到的这两个代价相加就得出了总代价：f-cost + g-cost。
而后在摸索方块中，优先筛选总代价最低的方块进行摸索，这样子就会少走很多弯路
而且搜寻到的门路也肯定是最短门路。
在第一轮循环中，算法对终点四周的四个方块进行摸索，并计算出“以后代价”和“预估代价”。
比方这里的 1 代表从起步到以后方块走了 1 步
这里的 4 代表着方块到起点的曼哈顿间隔，在这四个边界方块中，左边方块代价最低，因而在下一轮循环中会优先对它进行搜查
在下一轮循环中，咱们已同样的形式计算出方块的代价，发现最左边的方块价值仍然最低，因而在下一轮的循环中，咱们对它进行搜查
算法就这样子周而复始上来，直到搜查到起点为止
减少一下方块的数量级，A* 算法同样能够找到正确的最短门路
最为要害的是，它搜查的方块个数显著比广度优先遍历少很多，因而也就更高效。
了解了算法的基本原理后，接下来就是上代码了，这里我间接援用 redblobgames 的Python代码实现，因为人家切实写的太好了！
Plain Text
1
def heuristic(a, b): #Manhattan Distance
2
(x1, y1) = a
3
(x2, y2) = b
4
return abs(x1 – x2) + abs(y1 – y2)
5
6
def a_star_search(graph, start, goal):
7
frontier = PriorityQueue()
8
frontier.put(start, 0)
9
came_from = {}
10
cost_so_far = {}
11
came_from[start] = None
12
cost_so_far[start] = 0
13
14
while not frontier.empty():
15
current = frontier.get()
16
17
if current = goal:
18
break
19
20
for next in graph.neighbors(current):
21
new_cost = cost_so_far[current] + graph.cost(current, next)
22
if next not in cost_so_far or new_cost < cost_so_far[next]:
23
cost_so_far[next] = new_cost
24
priority = new_cost + heuristic(goal, next)
25
frontier.put(next, priority)
26
came_from[next] = current
27
28
return came_from, cost_so_far
先来看看最下面几行，frontier中寄存了咱们这一轮探测过的所有边界方块(之前图中那些绿色的方块)
Plain Text
1
frontier = PriorityQueue()
PriorityQueue代表它是一个优先队列，就是说它可能用“代价”主动排序，并每次取出”代价“最低的方块
Plain Text
1
frontier.put(start, 0)
队列外面呢咱们先寄存一个元素，就是咱们的终点
Plain Text
1
came_from = {}
接下来的的 came_from 是一个从以后方块到之前的映射，代表门路的来向
Plain Text
1
cost_so_far = {}
这里的 cost_so_far 代表了方块的“以后代价”
Plain Text
1
came_from[start] = None
2
cost_so_far[start] = 0
这两行将终点的 came_from 置空，并将终点的以后代价设置成 0，这样子就能够保障算法数据的有效性
Plain Text
1
while not frontier.empty():
2
current = frontier.get()
接下来，只有 frontier 这个队列不为空，循环就会始终执行上来，每一次循环，算法从优先队列里抽出代价最低的方块
Plain Text
1
if current = goal:
2
break
而后检测这个方块是不是起点块，如果是算法完结，否则继续执行上来
Plain Text
1
for next in graph.neighbors(current):
接下来，算法会对这个方块上下左右的相邻块，也就是循环中 next 示意的方块进行如下操作
Plain Text
1
new_cost = cost_so_far[current] + graph.cost(current, next)
算法会先去计算这个 next 方块的“新代价”，它等于之前代价 加上从 current 到 next 块的代价
因为咱们用的是网格，所以后半局部是 1
Plain Text
1
if next not in cost_so_far or new_cost < cost_so_far[next]:
而后只有 next 块没有被检测过，或者 next 以后代价比之前的要低
Plain Text
1
frontier.put(next, priority)
咱们就间接把他退出到优先队列，并且这里的总代价 priority 等于 “以后代价” 加上”预估代价“
Plain Text
1
priority = new_cost + heuristic(goal, next)
预估代价就是之前讲到的“曼哈顿间隔”
Plain Text
1
def heuristic(a, b): (x1, y1) = a (x2, y2) = b return abs(x1 – x2) + abs(y1 – y2)
之后程序就会进入下一次循环，反复执行之前的所有步骤
这段程序真的是写的特地奇妙，可能比拟难以了解可是多看几遍说不定你就忽然灵光乍现了呢
拓展
如果把地图拓展成网格模式（Grid），因为图的节点太多，遍历起来会十分的低效
于是咱们能够吧网格地图简化成 节点更少的路标模式（WayPoints）
而后须要留神的是：_这里任意两个节点之间的间隔就不再是 1 了，而是节点之间的理论间隔_
咱们还能够用自上而向下分层的形式来存储地图
比方这个 四叉树（Quad Tree）
又或者像 unity 中应用的 导航三角网（Navigation Mesh），这样子算法的速度就会失去进一步优化
另外，我还举荐 redblobgames 的教程
各种算法的可视化，以及分明的看见各种算法的遍历过程、两头后果
以及各种办法之间的比拟，十分的直观形象，对于算法的了解也很有帮忙。
参考：
[1]周小镜. 基于改良 A_算法的游戏地图寻径的钻研[D]. 东北大学,2010._ _[2]_https://www.redblobgames.com/… _[3]_https://en.wikipedia.org/wiki…
点击关注，第一工夫理解华为云陈腐技术~
