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