资源描述：
《a星算法详解-通俗易懂初学者必看》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
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列,则行数相差为0,列数相差为5,总和为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表中,然后在判断结点30周围4个结点,因为结点31为障碍,结点29存在于CLOSE表中,我们将不处理这两点,只将2
6、1和39号结点加入OPEN表中,添加完后地图变为下图样式当前OPEN表中的值:20,28,38,21,39 当前CLOSE表中的值:29,30接着我们重复上面的过程,寻找OPEN表中F值为低的值,我们发现OPEN表中所有结点的F值都为60,我们随即取一个结点,这里我们直接取最后添加进OPEN表中的结点,这样方便访问(因为存在这样的情况,所有从一个点到另外一个点的最短路径可能不只一条),我们取结点39,将他从OPEN表中删除,并添加进CLOSE表中,然后观察39号结点周围的4个结点,因为40号结点为障碍,所以我们不管它,而30号结点已经存在与OP
7、EN表中了,所以我们要比较下假设39号结点为30号结点的父结点,30号结点的G值会不会更小,如果更小的话我们将30结点的父结点改为39号,这里我们以39号结点为父结点,得出30号结点的新G值为20,而30号结点原来的G值为10,并不比原来的小,所以我们不对30号进行任何操作,同样的对38号结点进行上述操作后我们也不对它进行任何操作,接着我们把48号结点添加进OPEN表中,添加完后地图变为下图样式当前OPEN表中的值:20,28,38,21,48 当前CLOSE表中的值:29,30,39以后的过程中我们都重复这样的过程,一直到遍历到了最后终点,通
8、过遍历父结点编号,我们能够得出一条最短路径,具体完整的推导过程我就不写出来了,因为和刚才那几步是一样的，这里我再讲出一个特例,然后基本A
