A*（A星）寻路算法讲解

 A*（A星）寻路算法讲解

　

点击播放/隐藏媒体

/uploads/flash/move4.swf

引言

终于把A*寻路算法看懂了，虽然还有点小问题，但A*寻路算法我已经略知一二，帮助还不知道的朋友进入A*算法入门阶级，应该不成问题，下面就来看看A*算法的原理（以下讲解不带入任何程序语言，因此只要你看懂了下面所有的话，那么你可以随意用在任意程序语言中）
在下也是初学，写这篇文章的目的只是让新手入门，因此高手看到这就飘过吧，当然愿意给予指点的高手请继续往下看

前言

在文中可能会出现一些专业术语或者是我信口雌黄的话语，未免看官不明白，前面我先加以注解，具体意思可以从文中体会到
该寻路算法是在一个由很多方格组成的图像中，你操纵一个蓝色小方格进行寻路的环境下进行讲解，具体请看文章一开始的flash示例，或者是查看A*寻路算法例子
　
方格：一个一个的小方块
障碍物：挡着去路的东西
目标方格：你想到达的方格
操控方格：你控制的寻路对象
标记：临时为某一个方格做的标记
父标记：除了操控方格所创建的临时标记，每个标记都有个父标记，但父标记不是随便乱定的，请看下文
开启标记列表：当该标记还未进行过遍历，会先加入到开启标记列表中
关闭标记列表：当该标记已经进行过遍历，会加入到关闭标记列表中
路径评分：通过某种算法，计算当前所遍历的标记离目标方格的路径耗费估值（后面会讲一种通用的耗费算法）

　　首先描述一个环境，在一望无际的方格中，我身处某某方格，如今我想去某某方格，接下来我开始寻路！
　　在脑海中，先创建开启标记列表、关闭标记列表，然后把我的初始位置设置为开始标记进行遍历，同时因为开始标记已经遍历过了，因此把开始标记加入到关闭列表。通过开始标记我们找出了相邻的八个方格，为它们创建相应的标记，加入到开启标记列表中，并把每个标记的父标记设置为开始标记，是因为开始标记才让我们这些方格创建了属于自己的标记，它就是我们的再生父母。但不符合条件的我们就不加入开启标记列表（下面的条件符合任何一条都不要加入到开启标记列表中）：
　　1、它在我们的搜寻地图范围外，比如你地图的寻路范围是 0*0 - 50*50，那么但这个点在边缘的时候，那它相邻的八个方格，必定有几个是处在外面的！
　　2、搜寻的这个方格是否有障碍物、或不可到达，比如河流，石头，山川等
　　3、判断它是否已经加入关闭标记列表，若已经加入表示该方格已经遍历过了，在遍历一次也无济于事，还会影响效率
　　4、判断它是否已经加入开启标记列表，若已经加入那么咋们就来判断一下该标记是否离开始标记更近一些
　　5、判断当斜着走的时候，它的上下或左右是否有障碍，如果有则表示你无法斜着走，需要先横走一下，再竖走一下或者是竖走一下，再横走一下
　　如果想象不出来，可以看着这个A*寻路算法例子进行学习和比较。
　
　　把相邻的八方向都添加到开启标记列表中后，现在从开启标记列表中取出一个路径评分最低标记，对他开始进行遍历相邻的八个方格，并进行创建标记、添加到开启标记列表、设置父标记为该标记，并且重复判断上面的创建条件，然后把这个标记加入到关闭标记列表
　　如此循环的做着上面所说的事，然后每次判断下面条件：
　　1、判断开启列表是否已经为空，如果空了则表示从操控方格到目标方格是不可能达到，是死路！
　　2、判断当前所遍历的标记的坐标与目标方格的坐标是否相同，如果相同则表示到达了目标方格！
　
　　当得到第一个条件，则表示这条路是死路，因此咱们不用遍历了，宣告结果吧。当得到第二个条件，则表示咱们已经找到路了，从最后创建的这个标记开始，一直向上访问它的父标记，直到开始标记的时候没有父标记为止，这就是一条从操控方格到目标方格的路径，但这可能不是捷径。
　
　　A*寻路算法，只是保证在低消耗的情况在最短的时间找出路径，但A*寻路算法寻出来的路不一定是最近，但也绝对不会远的离谱，可也不排除你对路径评分算法的优化可以做到最快最短最低消耗，或者对最终路径的优化来达到目的，下面就来讲讲通用的路径评分计算公式：
　
　　首先看公式：　F = G + H
　
　　F值表示路径评分，G值表示当前所判断的标记离开始标记的路径耗费，H值表示当前所判断的标记离目标方格的路径估值耗费
　　G值的计算方式是，如果为斜走判断则用父标记的G值加上14表示当前标记的G值，如果为直走判断则用父标记的G值加上10表示当前标记G值
　　H值通常的计算方式是一种称作为曼哈顿方法的方式，当前标记离目标方格横着的方格数加上竖着的方格数，然后乘以10，最后得值就是H值。当然若你想通过A*寻出最好的路径，那么改善算法的主要地方就是这个H值的算法（如果你对本计算方式还有更好的办法可以到我博客中去发表自己的意见）
　　根据上面讲的A*算法的做法来讲，则表示前面判断哪个标记离开始标记更近一些只需判断一下G值即可；前面所说的取出一个路径评分最低标记，也就是将F值进行升序排序取出第一个，或降序排序取出最后一个。
　　
　　sunbright总结：本文只是初略的讲解A*寻路算法的入门，相信仔细看过该文用心体会肯定能入门A*算法，但该文不是A*算法的权威，因为我自己也知道这篇文章是按照我自己的想法对A*的理解所写出来的，可能跟A*算法的原理是一样的，但讲解方式可能大不同，毕竟国内大部分A*算法的讲解都是来自于国外的译本。希望还不懂A*寻路算法的朋友通过这篇文章能理解过来！——本文出至sunbright博客
　　
对于高手看过本文后，有什么见解可以提出来，在下也是菜鸟，也希望能得到进步；如果新手看过本文后，有什么好的建议或疑问，也可以提出来，我尽量解答！