A*寻路算法笔记 2011

时间:2022-12-28 12:25:45

寻路是很多游戏需要实现的功能,简言之,就是确定起点和终点,找出到达的路线。常见应用:电脑怪物对主人公进行追踪打击。

AStar是目前使用较多的一种寻路算法,最近比较感兴趣研究了下,记录一些要点:

 

1,寻路的基础是将地图网格化,转化为二维数组,这样做的好处是节省计算资源,简化计算模型,也很接近真实。

2,AStar是从起点开始向外依次计算临近网格到目标网格的距离,得出最短距离。

3,F = H + G;G值是从起点到该网格累加的距离值,两个网格如果是垂直或水平相邻则G值差为10,如果是斜角相邻G值差为14,为什么是14很简单:等腰直角三角形直角边是10,斜边就是14...,为了节省计算资源,用整数14近似替代。H值是当前网格到目标网格的近似距离,这是一个系数,有多种公式实现,比较简化的算法是垂直距离与横向距离之和。  F值就表明的是当前点到目标点的近似距离,F值越小,就表明该网格很有可能是最优路线上的一个节点。

4,开放列表中存放的是检查过的所有节点(除了放入封闭列表的),封闭列表中存放的是每次寻路中F值最小的节点

5,当开放列表中已经没有节点时,表明寻路失败,当目标节点被添加到开放列表中时,表明寻路成功。