Menu

关于A*算法的几点感悟(结合项目经验)

2018年5月2日 - 算法,数据结构

A*算法是游戏中常用的寻路算法,经常看到MMORPG的自动寻路原型就有A* 算法的影子,A*算法求较短路径,注意较短路径,不是最短路径,因为你不能保证求出的一定是最短路径,因为求出的路径可能不止一条。

说一说A* 算法的应用环境:2D还是3D场景都是可以的

1.先初始化场景地图,把地图分成一个一个的小格子(格子越小,精度越高,搜索效率会低)

2.F=G+H(A*核心思想)

F总的路径步数

G=当前结点到起始点的距离

H=代表当前结点到终点的距离

3.A*算法具体描述

1首先将起始点添加进“开启列表”

2重复如下步骤:

a寻找列表中F值最低的节点,也就是当前结点。

b把它从“开启列表”中移除,并添加进“关闭列表”

c检查当前结点是否为目标结点

如果是,停止搜索,跳到下面步骤3

如果不是,继续下面步骤

d寻找当前结点临近的结点

如果它不可通过或者已经在关闭列表中,略过它。反之如下

如果它不在开启列表中,把它添加到开启列表中,并把当前结点作为这一结点的父节点,记录F,G,H的值。

如果它已经在开启列表中,检查新路径对它G值的产生的影响

a如果它的G值因为新路径变大,那么保持原理的状态,不做任何改变

b如果G值变小,说明新路径更好,将其父节点改为当前结点,更新G,F

d 检查列表是否为空,如果为空,说明路径未找到,直接返回,不继续任何步骤。

3.保存路径。从目标结点开始,沿着每一个结点的父结点移动直到回到起使结点。这就是我们要找的路径。

A*寻路算法采用启发式搜索方法,避免了很多无谓的搜索,可以使用二叉堆进行优化。

博主参考了一下这篇博客:https://blog.csdn.net/yiyikela/article/details/46134339

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

%d 博主赞过: