寻路算法之A*

时间:2021-10-13 04:24:56

最近接触到MOBA(Multiplayer Online Battle Arena)这个新名词,发现npc寻路有点意思。于是回顾了一下经典的A*算法。

相关数据结构

  1. open列表:记录可用来被寻找的点
  2. closed列表:记录排除在路线之外的点
  3. 对于路线中的一个点:
    3.1 G值:从开始到此点的移动量
    3.2 H值:从此点到终点的估计移动量,一般为不考虑障碍的最短距离。
    3.3 F值:等于G+H,此值的含义是选取当前点的一个评价值,即如果此值越小,表明选此点后,离终点越近。

算法

  1. 初始化
    将起点加入open列表
  2. 循环开始

    1. 从open列表取出一个G+H值最小的点,并将此点加入closed列表

      由于open列表中会有若干个具有同样G+H值的点,为了快速,自己习惯在此引入DFS:优先选取其中G值较大的点

    2. 遍历每一个与此点相通的点:
      如果此点在closed列表中,则跳过;
      如果此点不在open列表中,计算相应的值,并将此点加入open列表;
      如果此点在open列表中,检查如果新的G+H值小于原值,则更新此点的G值与H值;

  3. 结束条件
    直到终点从open列表中挑出。

代码

代码