最近接触到MOBA(Multiplayer Online Battle Arena)这个新名词,发现npc寻路有点意思。于是回顾了一下经典的A*算法。
相关数据结构
- open列表:记录可用来被寻找的点
- closed列表:记录排除在路线之外的点
- 对于路线中的一个点:
3.1 G值:从开始到此点的移动量
3.2 H值:从此点到终点的估计移动量,一般为不考虑障碍的最短距离。
3.3 F值:等于G+H,此值的含义是选取当前点的一个评价值,即如果此值越小,表明选此点后,离终点越近。
算法
- 初始化
将起点加入open列表 -
循环开始
-
从open列表取出一个G+H值最小的点,并将此点加入closed列表
由于open列表中会有若干个具有同样G+H值的点,为了快速,自己习惯在此引入DFS:优先选取其中G值较大的点
遍历每一个与此点相通的点:
如果此点在closed列表中,则跳过;
如果此点不在open列表中,计算相应的值,并将此点加入open列表;
如果此点在open列表中,检查如果新的G+H值小于原值,则更新此点的G值与H值;
-
- 结束条件
直到终点从open列表中挑出。
代码
代码