开通VIP，畅享免费电子书等14项超值服
首页
好书
留言交流
下载APP
联系客服
2021.08.11
A*搜寻算法俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。
1
Dijkstra算法
Dijkstra算法的原理不难理解，但是假如用文字表达会增大初学者的理解难度，所以树根直接上图：
其中箭头边的数值代表两点之间的距离。
我们假设从点1出发，计算出点1到点8的最短路径。我们可以看一下Dijkstra算法是怎么求出点1到点8的最短距离的（其中S表示已求出最短路径的点的集合）：
（1）点1直接到点4的距离最短，所以点1到点4的距离P4=1，同时点4加入S集合：
（2）显而易见，点1直接到点2的距离是最短的，为2，因此距离P2=2，点2加入集合S中：
（3）同理，点1直接到点6的距离是最短的，P6=3，点6加入S：
（4）点1到点7的最短路径为：1->4->7，距离P7=1+2=3，点7加入S：
同理遍历所有节点：
这样我们就可以得到点到所有节点的最短路径，可以得到点1到点8的最短路径为：1->4->7->5->8，P8=10
因此，计算任意两点的最短距离时，Dijkstra算法每一步会选择离初始点最近的结点。
还有没有其他的方法呢？
2
最佳优先搜索（BFS）
A-StarAlgorithm
最佳优先搜索（BFS）算法按照类似的流程运行，不同的是它能够评估（称为启发式）任意结点到目标点的代价。
与选择离初始结点最近的结点不同的是，BFS选择离目标点最近的结点。
BFS不能保证找到一条最短路径。然而，它比Dijkstra算法快的多，因为它用了一个启发式函数（heuristicfunction）快速地导向目标结点。例如，如果目标位于出发点的南方，BFS将趋向于导向南方的路径。
在下面的图中，颜色越浅的结点代表越高的启发式值（移动到目标的代价高），而越黑的结点代表越低的启发式值（移动到目标的代价低）。这表明了与Dijkstra算法相比，BFS运行得更快，但是在存在障碍物的情况下，它找到的路径可能不是一条好的路径：
问题在于，BFS是基于贪心策略的，它试图向目标点移动，尽管这不是正确的路径。由于它仅仅考虑到达目标的代价，而忽略了当前已花费的代价，于是尽管路径变得很长，它仍然继续走下去。
假如能结合两者的优点不是更好吗？
3
A*（A星）算法
让我们想象一下，有一款游戏，游戏中一只猫想要找到获取骨头的最短路线：
一、简化搜索区域
寻路的第一步是简化成容易控制的搜索区域。
作为代替，我们使用方块（一个正方形）作为寻路算法的单元。其他的形状类型也是可能的（比如三角形或者六边形），但是正方形是最简单并且最适合我们需求的。
现在让我们基于目前的区域，把区域划分成多个方块来代表搜索空间（在这个简单的例子中，7*6个方块=42个方块）：
我们的猫没有好的记忆力，所以它需要两个列表：
一个记录下所有被考虑来寻找最短路径的方块的列表（称为open列表）
一个记录下不会再被考虑的方块的列表（称为closed列表）
猫首先在closed列表中添加当前位置（我们把这个开始点称为点“A”）。然后，把所有与它当前位置相邻的可通行小方块添加到open列表中。
下图是猫在某一位置时的情景（绿色代表open列表）:
我们将会给每个方块一个和值：
F=G+H
G：从开始点A到当前方块的移动量（可以与Dijkstra算法联系起来理解）。所以从开始点A到相邻小方块的移动量为1，该值会随着离开始点越来越远而增大。
H：从当前方块到目标点（可以与BFS算法联系起来理解）的移动量估算值。这个常被称为探视，因为存在障碍物，我们不确定实际的移动量是多少，仅仅是一个估算值。
你也许会对“移动量”感兴趣。在游戏中，这个概念很简单–仅仅是方块的数量。
然而，在游戏中你可以对这个值做调整。例如：
·如果你允许对角线移动，你可以针对对角线移动把移动量调得大一点（因为存在根号会增大计算量）。
·如果你有不同的地形，你可以将相应的移动量调整得大一点。
关于G值：
G是从开始点A到达当前方块的移动量（在本游戏中是指方块的数目）。
为了计算出G的值，我们需要从它的上一个方块获取，然后加1。所以，每个方块的G值代表了从初始点A到该方块所形成路径的总移动量。
例如，下图展示了两条到达不同骨头的路径，每个方块都标有它的G值（我们现在只允许前后左右移动，不允许对角线移动）：
关于H值：
H值是从当前方块到终点的移动量估算值（在本游戏中是指方块的数目）。移动量估算值离真实值越接近，最终的路径会更加精确。
为了让它更简单，我们将使用“曼哈顿距离方法”，它只是计算出距离目标点B剩下的水平和垂直的方块数量，同时略去了障碍物或者不同陆地类型的数量（我们在估算距离的时候往往不确定前方会有怎么样的障碍物）。
例如，下图展示了使用“曼哈顿距离”，从不同的开始点到终点，去估算H的值（黑色数字表示H值）：
在下图中，和大家说一下每个方块图例的意思：
F（方块的和值）：左上角的数字
G（从A点到方块的移动量）：左下角的数字
H（从方块到B点的估算移动量):右下角的数字
箭头指示了到达相应方块的移动方向。
红色方块表示closed列表，绿色方块表示open列表。
好的，我们开始吧！
第二步：
注意被添加到open列表的两个新方块，相对于现在选中的方块来说，他们的G值都只是增加了1：
第三步：
再次，我们选择了相对于初始点A有最小F值（5）的方块，继续重复之前的步骤。现在，只有一个可能的方块被添加到open列表中了，因为已经有一个相邻的方块在close列表中，其他两个是墙壁方块：
现在我们遇到了一个有趣的情况。正如你看到的，相对于初始点A，有4个方块的F值都为7，我们要怎么做呢？！
对于四个方块的F值都是7的情况，有几种解决方法可以使用，但是最简单（快速）的方法是一直跟着最近被添加到open列表中的方块。现在继续沿着最近被添加的方块前进：
这次有两个可通过的相邻方块了，我们还是像之前那样计算他们的和值F。
第五步：
接着我们选择了最小和值（7）的方块，继续重复之前的步骤：
在我们的例子中，有两条最短路径：
1->2->3->4->5->6
1->2->3->4->5->7
选择哪一条其实没关系，然后，算法要做的所有事情就是返回，计算出最终的路径！
现在到了真正用代码实现的时候了。超级鸡冻的有木有~
4
算法实现
Python版：
运行后的结果为：
MATLAB版：
代码很长，树根就不放出来了。链接可以后台问树根拿，回复关键词：“matlab_A-Star”即可
运行后会形成UI界面，并且起始点，目标点和障碍物的位置可自己调节：