EX1——A星寻路算法理论基础

A星寻路算法

A星寻路是用来计算玩家行进的最短路径的，且可以避开中间的阻挡

基本原理

不停的找周围的点，选出一个新的点作为起点，再循环的找周围的点，直到找到终点

1. 先设定起点和阻挡（红色即遮挡）

   

2. 设定终点，起点开始找周围的点

   

3. 发现a3离终点最近，搜寻a3周围没有搜寻过的点，阻挡点不搜寻

   

4. 发现b3离终点最近，搜寻b3周围没有搜寻过的点，阻挡点不搜寻

   

5. 重复上述步骤，直到走到终点

   

6. 最后将起点与终点联通起来，得到路径

   

详细原理

1. 寻路消耗公式：

   $f(寻路消耗)=g(离起点距离)+h(离终点距离)$

   $g(离起点距离)$即上下左右相邻格子的距离是1，斜边相邻的格子是1.4（约等于$\sqrt{2}$）

   ​​

   $h(离终点距离)$最常用的算法是曼哈顿街区算法
   简单来说，就是将x轴和y轴距离加起来算出的距离
   如下图：x轴距离为5，y轴距离为1，两者加起来距离为1

   

   最后加起来就是$f(寻路消耗)$

2. 开启列表

   即上图中黄色的格子即被搜索的格子，计算并记录所有格子寻路消耗，进行寻路消耗排序，寻路消耗最小的那个格子送入关闭列表
   （如果有并列，只送其中之一）
   每次把格子放入开启列表时，需要该格子不是阻挡点，且该格子不在开启列表或者关闭列表内

3. 关闭列表

   即上图中绿色的格子即一次开启列表寻路消耗排序中寻路消耗最小的那个格子，
   关闭列表的格子周围的格子将被搜寻，没搜寻过的格子放入开启列表参与开启列表的排序
   每次最优点放入关闭列表时，需要判断该点是否为终点，如果是，则寻路结束，不是，就继续寻路

4. 格子对象的父对象

   用于确认最终路径，一个格子对象的父对象，就是将该格子送入开启列表的格子对象，起点没有父对象
   当找到终点时，会寻找终点格子的父对象，再寻找父对象的父对象，以此类推，直到找到起点，将这条父子关系链上的所有格子连起来，就是路径

死路情况的确定：

当开启列表为空，且关闭列表的所有格子周围的格子全部都搜寻也无法再找到新格子，即为死路