A星算法详解-通俗易懂初学者必看

《A星算法详解-通俗易懂初学者必看》由会员分享，可在线阅读，更多相关《A星算法详解-通俗易懂初学者必看（17页珍藏版）》请在金锄头文库上搜索。

1、t(智乐圆智乐圆 入门入门 1)A*(A 星)算法(一)记得好象刚知道游戏开发这一行的时候老师就提到过 A 星算法,当时自己基础还不 行,也就没有去看这方面的资料,前几天找了一些资料,研究了一天,觉的现在网上介 绍 A 星算法的资料都讲的不够详细(因为我下的那个资料基本算是最详细的了- -但 是都有一些很重要的部分没有说清楚.),所以我自己重新写一篇讲解 A 星算法的资 料,还是借用其他资料的一些资源.不过转载太多了,只有谢谢原作者了:) 我们将以下图作为地图来进行讲解,图中对每一个方格都进行了编号,其中绿色的方 格代表起点,红色的方格代表终点,蓝色的方格代表障碍,我们将用 A 星算法来寻找一

2、 条从起点到终点最优路径,为了方便讲解,本地图规定只能走上下左右 4 个方向,当你 理解了 A 星算法,8 个方向也自然明白在地图中,每一个方格最基本也要具有两个属性值,一个是方格是通畅的还是障碍,另 一个就是指向他父亲方格的指针(相当于双向链表结构中的父结点指针),我们假设方 格值为 0 时为通畅,值为 1 时为障碍 A 星算法中,有 2 个相当重要的元素,第一个就是指向父亲结点的指针,第二个就是一 个 OPEN 表,第三个就是 CLOSE 表,这两张表的具体作用我们在后面边用边介绍,第 四个就是每个结点的 F 值(F 值相当于图结构中的权值) 而 F = H + G;其中 H 值为从网格上

3、当前方格移动到终点的预估移动耗费。这经常 被称为启发式的，可能会让你有点迷惑。这样叫的原因是因为它只是个猜测。我们 没办法事先知道路径的长度，因为路上可能存在各种障碍(墙，水，等等)。虽然本 文只提供了一种计算 H 的方法，但是你可以在网上找到很多其他的方法,我们定义 H 值为 终点所在行减去当前格所在行的绝对值 与 终点所在列减去当前格所在列的绝对值 之和,而 G 值为从当前格的父亲格移动到当前格的预估移动耗费,在 这里我们设定一个基数 10,每个 H 和 G 都要乘以 10,这样方便观察 好了,我们开始对地图进行搜索 首先,我们将起点的父亲结点设置为 NULL,然后将起点的 G 值设置为

4、0,再装进 open 表里面,然后将起点作为父亲结点的周围 4 个点 20,28,30,38(因为我们地图只能走 4 个方向,如果是 8 方向,则要加个点进去)都加进 open 列表里面,并算去每个结点的 H 值,然后再将起点从 open 列表删除,放进 close 表中,我们将放进 close 表的所有方 格都用浅蓝色线条进行框边处理,所以这次搜索以后,图片变为如下格式,其中箭头代 表的是其父结点其中每个格子的左下方为 G 值,右下方为 H 值,左上方为 H 值,我们拿 28 号格子为例 来讲解一写 F 值的算法,首先因为终点 33 在 4 行 7 列,而 28 在 4 行 2 列,则行数相

5、 差为 0,列数相差为 5,总和为 5,再乘以我们先前定的基数 10,所以 H 值为 50,又因为 从 28 的父结点 29 移动到 28,长度为 1 格,而 29 号为起点，G 值为 0,所以在父亲结 点 29 的基础上移动到 28 所消耗的 G 值为(0 + 1) *10 = 10,0 为父亲结点的 G 值,1 为从 29 到 28 的消耗 当前 OPEN 表中的值: 20,28,30,38 当前 CLOSE 表中的值: 29 现在我们开始寻找 OPEN 列表中 F 值最低的,得出结点 30 的 F 值最低,且为 40,然后 将结点 30 从 OPEN 表中删除,然后再加入到 CLOSE

6、表中,然后在判断结点 30 周围 4 个结点,因为结点 31 为障碍,结点 29 存在于 CLOSE 表中,我们将不处理这两点,只 将 21 和 39 号结点加入 OPEN 表中,添加完后地图变为下图样式 当前 OPEN 表中的值: 20,28,38,21,39 当前 CLOSE 表中的值: 29,30接着我们重复上面的过程,寻找 OPEN 表中 F 值为低的值,我们发现 OPEN 表中所有 结点的 F 值都为 60,我们随即取一个结点,这里我们直接取最后添加进 OPEN 表中的 结点,这样方便访问(因为存在这样的情况,所有从一个点到另外一个点的最短路径可 能不只一条),我们取结点 39,将他

7、从 OPEN 表中删除,并添加进 CLOSE 表中,然后观 察 39 号结点周围的 4 个结点,因为 40 号结点为障碍,所以我们不管它,而 30 号结点 已经存在与 OPEN 表中了,所以我们要比较下假设 39 号结点为 30 号结点的父结点, 30 号结点的 G 值会不会更小,如果更小的话我们将 30 结点的父结点改为 39 号,这 里我们以 39 号结点为父结点,得出 30 号结点的新 G 值为 20,而 30 号结点原来的 G 值为 10,并不比原来的小,所以我们不对 30 号进行任何操作,同样的对 38 号结点进 行上述操作后我们也不对它进行任何操作,接着我们把 48 号结点添加进

8、OPEN 表中,添 加完后地图变为下图样式 当前 OPEN 表中的值: 20,28,38,21,48 当前 CLOSE 表中的值: 29,30,39以后的过程中我们都重复这样的过程,一直到遍历到了最后终点,通过遍历父结点编 号,我们能够得出一条最短路径,具体完整的推导过程我就不写出来了,因为和刚才那 几步是一样的，这里我再讲出一个特例,然后基本 A 星算法就没问题了 上面的最后一推导中,我们在观察 39 号结点时,发现他周围已经有结点在 OPEN 表 中了,我说“比较下假设 39 号结点为 30 号结点的父结点,30 号结点的 G 值会不会更 小,如果更小的话我们将 30 结点的父结点改为 3

9、9 号“,但是刚才没有遇到 G 值更小 的情况，所以这里我假设出一种 G 值更小的情况,然后让大家知道该怎么操作,假设 以 39 号为父结点,我们得出的 30 号的新 G 值为 5(只是假设),比 30 号的原 G 值 10 还要小,所以我们要修改路径,改变 30 号的箭头,本来他是指向 29 号结点的，我们现 在让他指向 39 号结点,38 号结点的操作也一样 好了,A 星算法的大体思路就是这样了，对于 8 方向的地图来说，唯一的改变就是 G 值方面,在上下左右,我们的 G 值是加 10,但是在斜方向我们要加 14,其他的和上面 讲的一样:) PS: 今天下午去天门网络面试,我竟然连简历都没

10、带- -空着个手带了个人就去了. 都不晓得我当时杂想的.汗(智乐圆入门 2)终于把 A*寻路算法看懂了，虽然还有点小问题，但 A*寻路算法我已经略知一二，帮助还不知道的朋友进入 A*算法入门阶级，应该不成问题，下面就来看看 A*算法的原理（以下讲解不带入任何程序语言，因此只要你看懂了下面所有的话，那么你可以随意用在任意程序语言中）在下也是初学，写这篇文章的目的只是让新手入门，因此高手看到这就飘过吧，当然愿意给予指点的高手请继续往下看前言：在文中可能会出现一些专业术语或者是我信口雌黄的话语，未免看官不明白，前面我先加以注解，具体意思可以从文中体会到方格：一个一个的小方块方格：一个一个的小方块障碍

11、物：挡着去路的东西障碍物：挡着去路的东西目标方格：你想到达的方格目标方格：你想到达的方格操控方格：你控制的寻路对象操控方格：你控制的寻路对象标记：临时为某一个方格做的标记标记：临时为某一个方格做的标记父标记：除了操控方格所创建的临时标记，每个标记都有个父标记，但父标记不是随便乱定的，请看下文父标记：除了操控方格所创建的临时标记，每个标记都有个父标记，但父标记不是随便乱定的，请看下文开启标记列表：当该标记还未进行过遍历，会先加入到开启标记列表中开启标记列表：当该标记还未进行过遍历，会先加入到开启标记列表中关闭标记列表：当该标记已经进行过遍历，会加入到关闭标记列表中关闭标记列表：当该标记已经进行过

12、遍历，会加入到关闭标记列表中路径评分：通过某种算法，计算当前所遍历的标记离目标方格的路径耗费估值（后面会讲一种通用的耗费路径评分：通过某种算法，计算当前所遍历的标记离目标方格的路径耗费估值（后面会讲一种通用的耗费算法）算法）首先描述一个环境，在一望无际的方格中，我身处某某方格，如今我想去某某方格， 接下来我开始寻路！在脑海中，先创建开启标记列表、关闭标记列表，然后把我的初始位置设置为开始标 记进行遍历，同时因为开始标记已经遍历过了，因此把开始标记加入到关闭列表。通过开 始标记我们找出了相邻的八个方格，为它们创建相应的标记，加入到开启标记列表中，并 把每个标记的父标记设置为开始标记，是因为开始标

13、记才让我们这些方格创建了属于自己 的标记，它就是我们的再生父母。但不符合条件的我们就不加入开启标记列表（下面的条 件符合任何一条都不要加入到开启标记列表中）：1、它在我们的搜寻地图范围外，比如你地图的寻路范围是 0*0 - 50*50，那么但这个 点在边缘的时候，那它相邻的八个方格，必定有几个是处在外面的！2、搜寻的这个方格是否有障碍物、或不可到达，比如河流，石头，山川等3、判断它是否已经加入关闭标记列表，若已经加入表示该方格已经遍历过了，在遍历 一次也无济于事，还会影响效率4、判断它是否已经加入开启标记列表，若已经加入那么咋们就来判断一下该标记是否 离开始标记更近一些5、判断当斜着走的时候，

14、它的上下或左右是否有障碍，如果有则表示你无法斜着走， 需要先横走一下，再竖走一下或者是竖走一下，再横走一下把相邻的八方向都添加到开启标记列表中后，现在从开启标记列表中取出一个路径评 分最低标记，对他开始进行遍历相邻的八个方格，并进行创建标记、添加到开启标记列表、设置父标记为该标记，并且重复判断上面的创建条件，然后把这个标记加入到关闭标记列 表如此循环的做着上面所说的事，然后每次判断下面条件：1、判断开启列表是否已经为空，如果空了则表示从操控方格到目标方格是不可能达到， 是死路！2、判断当前所遍历的标记的坐标与目标方格的坐标是否相同，如果相同则表示到达了 目标方格！当得到第一个条件，则表示这条路

15、是死路，因此咱们不用遍历了，宣告结果吧。当得 到第二个条件，则表示咱们已经找到路了，从最后创建的这个标记开始，一直向上访问它 的父标记，直到开始标记的时候没有父标记为止，这就是一条从操控方格到目标方格的路 径，但这可能不是捷径。A*寻路算法，只是保证在低消耗的情况在最短的时间找出路径，但 A*寻路算法寻出来 的路不一定是最近，但也绝对不会远的离谱，可也不排除你对路径评分算法的优化可以做 到最快最短最低消耗，或者对最终路径的优化来达到目的，下面就来讲讲通用的路径评分 计算公式：首先看公式： F = G + HF 值表示路径评分，G 值表示当前所判断的标记离开始标记的路径耗费，H 值表示当 前所判

16、断的标记离目标方格的路径估值耗费G 值的计算方式是，如果为斜走判断则用父标记的 G 值加上 14 表示当前标记的 G 值， 如果为直走判断则用父标记的 G 值加上 10 表示当前标记 G 值H 值通常的计算方式是一种称作为曼哈顿方法的方式，当前标记离目标方格横着的方 格数加上竖着的方格数，然后乘以 10，最后得值就是 H 值。当然若你想通过 A*寻出最好 的路径，那么改善算法的主要地方就是这个 H 值的算法根据上面讲的 A*算法的做法来讲，则表示前面判断哪个标记离开始标记更近一些只需 判断一下 G 值即可；前面所说的取出一个路径评分最低标记，也就是将 F 值进行升序排序 取出第一个，或降序排序取出最后一个。总结：本文只是初略的讲解 A*寻路算法的入门，相信仔细看过该文用心体会肯定能入 门 A*算法，但该文不是 A*算法的权威，因为我自己也知道这篇文章是按照我自己的想法 对 A*的理解所写出来的，可能跟 A*算法的原理是一样的，但讲解方式可能大不同，毕竟 国内大部分 A*算法的讲解都是来自于国外的译本。希望还不懂 A*寻路算法的朋友通