学习A*寻路

1.A*寻路是什么

这是一种在图形平面上，求出从起点到终点最低通过成本的算法。常用于游戏中的NPC的移动计算。 该算法综合了 Dijkstra(狄克斯特拉)算法与BFS(最佳优先搜索)的优点：在进行启发式搜索提高算法效率的同时，可以保证找到一条最优路径（基于评估函数）。

2.A*寻路是怎么出现的

狄克斯特拉算法是解决有权图中从一个顶点到其余各顶点的最短路径算法。主要特点是以起始点为中心向外层扩展，知道扩展到终点为止。他一定可以找到最短路径，但是他也很耗费性能。

image.png

图中，粉红色的结点是初始结点，蓝色的是目标点，而有色区域则是Dijkstra算法扫描过的区域。颜色最淡的区域是那些离初始点最远的。我们可以看到该算法耗性能的原因就是扫描了太多区域。

最佳优先搜索算法是解决从一个点到另一个点的算法，他不能保证找到一条路径，但是它比迪克斯特拉算法快的多。因为他有一个能够评估任意节点到目标点的代价的启发式函数，所以他总是趋向于向代价小的的点前进。

image.png

图中，越黄的结点代表越高的启发式值（移动到目标的代价高），而越黑的结点代表越低的启发式值（移动到目标的代价低）。扫描范围就表明了与Dijkstra 算法相比，BFS运行得更快。

但是这两个例子都是最简单的情况-地图中没有障碍物。下面我们来举一个有障碍物的例子。

image.png

可以看到，虽然多了障碍物但是Dijkstra 算法总能找到一条最短路径。但是他的消耗也很大。

image.png

BFS在有障碍物的情况下，虽然速度快，但是找到的路径却不是最短路径。这个问题就在于BFS是基于贪心策略的。它试图向目标移动尽管这不是正确的路径。由于它仅仅考虑到达目标的代价，而忽略了当前已花费的代价，于是尽管路径变得很长，它仍然继续走下去。

所以我们就会想到结合两者的有点不是会变得更好吗。1968年发明的A算法就是把启发式方法（heuristic approaches）如BFS，和常规方法如Dijsktra算法结合在一起的算法。有点不同的是，类似BFS的启发式方法经常给出一个近似解而不是保证最佳解。然而，尽管A基于无法保证最佳解的启发式方法，A*却能保证找到一条最短路径。

3.A*寻路可以干什么

和其它的图搜索算法一样，A星潜在的搜索图中一个很大的区域。和Dijkstra一样，A星能用于搜索最短路径。和BFS一样，A*能用启发式函数引导它自己。在简单的情况中，它和BFS一样快。

image.png

在有障碍物的搜索图中，A星找到了最短路径并且效率也很高。

原因是A星算法拥有一个寻找节点的方式f(n) = g(n) + h(n)，g(n)代表起始节点到当前节点的实际代价，h(n)代表了从当前节点到终点的预估代价。在搜索过程中A星算法总会找f值最小的节点为下一节点。

启发式函数（h(n)）告诉A星从任意节点到目标节点的预估代价值，它可以控制A*的行为：

• 一种极端情况，如果h(n)是0，则只有g(n)起作用，此时A*演变成Dijkstra算法，这保证能找到最短路径。

• 如果h(n)经常都比从n移动到目标的实际代价小（或者相等），则A保证能找到一条最短路径。h(n)越小，A扩展的结点越多，运行就得越慢。

• 如果h(n)精确地等于从n移动到目标的代价，则A将会仅仅寻找最佳路径而不扩展别的任何结点，这会运行得非常快。尽管这不可能在所有情况下发生，你仍可以在一些特殊情况下让它们精确地相等（译者：指让h(n)精确地等于实际值）。只要提供完美的信息，A会运行得很完美，认识这一点很好。

• 如果h(n)有时比从n移动到目标的实际代价高，则A*不能保证找到一条最短路径，但它运行得更快。

• 另一种极端情况，如果h(n)比g(n)大很多，则只有h(n)起作用，A*演变成BFS算法。

所以我们得到一个很有趣的情况，那就是我们可以决定我们想要从A星中获得什么。理想情况下，我们想最快地得到最短路径。如果我们的h(n)太低，我们仍会得到最短路径，不过速度变慢了；如果我们的h(n)太高，那我们就放弃了最短路径，但A*运行得更快。

在游戏中，A*的这个特性非常有用。例如，你会发现在某些情况下，你希望得到一条好的路径而不是一条完美的路径。为了权衡g(n)和h(n)，你可以修改任意一个。

网格地图中的启发式算法有：曼哈顿距离、对角线距离、欧几里得距离。用的最多的是曼哈顿距离。

4.A*寻路大致流程抽象

do
{
寻找开启列表中F值最低的格子, 我们称它为当前格.
把它切换到关闭列表.
对当前格相邻的8格中的每一个
if (它不可通过 || 已经在 "关闭列表" 中)
{
什么也不做.
}
if (它不在开启列表中)
{
把它添加进 "开启列表", 把当前格作为这一格的父节点, 计算这一格的 FGH
if (它已经在开启列表中)
{
if (用G值为参考检查新的路径是否更好, 更低的G值意味着更好的路径)
{
把这一格的父节点改成当前格, 并且重新计算这一格的 GF 值.
}
} while( 目标格已经在 "开启列表", 这时候路径被找到)
如果开启列表已经空了, 说明路径不存在.

最后从目标格开始, 沿着每一格的父节点移动直到回到起始格, 这就是路径。

参考博客：https://blog.csdn.net/coutamg/article/details/53923717
https://www.cnblogs.com/technology/archive/2011/05/26/2058842.html