学游戏就上我学院woxueyua
com
A星算法详解教程
AA星算法一
记得好象刚知道游戏开发这一行的时候老师就提到过A星算法当时自己基础还不行也就没有去看这方面的资料前几天找了一些资料研究了一天觉的现在网上介绍A星算法的资料都讲的不够详细因为我下的那个资料基本算是最详细的了但是都有一些很重要的部分没有说清楚所以我自己重新写一篇讲解A星算法的资料还是借用其他资料的一些资源不过转载太多了只有谢谢原作者了我们将以下图作为地图来进行讲解图中对每一个方格都进行了编号其中绿色的方格代表起点红色的方格代表终点蓝色的方格代表障碍我们将用A星算法来寻找一条从起点到终点最优路径为了方便讲解本地图规定只能走上下左右4个方向当你理解了A星算法8个方向也自然明白
在地图中每一个方格最基本也要具有两个属性值一个是方格是通畅的还是障碍另一个就是指向他父亲方格的指针相当于双向链表结构中的父结点指针我们假设方格值为0时为通畅值为1时为障碍A星算法中有2个相当重要的元素第一个就是指向父亲结点的指针第二个就是一个OPEN表第三个就是CLOSE表这两张表的具体作用我们在后面边用边介绍第四个就是每个结点的F值F值相当于图结构中的权值而FHG其中H值为从网格上当前方格移动到终点的预估移动耗费。这经常被称为启发式的，可能会让你有点迷惑。这样叫的原因是因为它只是个猜测。我们没办法事先知道路径的长度，因为路上可能存在各种障碍墙，水，等等。虽然本文只提供了一种计算H的方法，但是你可以在网上找到很多其他的方法我们定义H值为终点所在行减去当前格所在行的绝对值与终点所在列减去当前格所在
U
ity3DCocosphpHTML5JavaiosA
droidCAS3UI设计原画设计动漫美术游戏策划
f学游戏就上我学院woxueyua
com
列的绝对值之和而G值为从当前格的父亲格移动到当前格的预估移动耗费在这里我们设定一个基数10每个H和G都要乘以10这样方便观察好了我们开始对地图进行搜索首先我们将起点的父亲结点设置为NULL然后将起点的G值设置为0再装进ope
表里面然后将起点作为父亲结点的周围4个点20283038因为我们地图只能走4个方向如果是8方向则要加个点进去都加进ope
列表里面并算去每个结点的H值然后再将起点从ope
列表删除放进close表中我们将放进close表的所有方格都用浅蓝色线条进行框边处理所以这次搜索以后图片变为如下格式其中箭头代表的是其父结点
其中每个格子的左下r