记A-Star算法

是去年参加某比赛的时候使用到的算法,感觉还是挺有用的就准备写一个博客了
是去年差不多自己研究完就写了,但是因为博客挂了一次了导致之前的东西都没了……只能现在来重写,顺便当做复习了,导致这一篇可能跟原来自己写的那篇文章略有出入

概述

这个部分是对A-Star算法有一个简单的介绍,然后提一些粗略的使用环境。很多都是个人见解,如果有问题请滴滴我o<-<
如果没有兴趣观看可以直接前往算法理论介绍部分

Q1:这是一种什么样的算法

A-Star算法的应用环境一般是当前环境有最短路径寻找的需求,当然,这种最短路径寻找有那么些个前提:

全地图静止/移动因素不会对于寻路结果造成极大改变

我们都知道,游戏场景里面会有很多的这种场景:你在一个安全的地方,需要接任务,但是你初来乍到,人生地不熟,人自然是找不到了。这个时候游戏系统里面一般会配置一个自动导航系统,你只需要点击都能够直接前往你想去的地方。
显而易见的,你并不会绕着这个安全的地方一大圈才能到这个目的地,而是找到了绕过障碍物的最短路径,然后到达目的地。
但是这种导航放在有敌对生物的野外就不适用了,你不可能说你直接跑路的时候,撞到怪上面然后猝不及防开始一场战斗吧?啊,当然,假如说怪一直是在那一格站着,就可以把他看成一个障碍物绕开就行了。
假若说这个怪物是随机移动的,我们同样的将这个怪物视作一个障碍物,那性质完全不一样了。因为你一开始计算出来得到的路径,在你真正走到那个地方的时候已经产生了改变。那就已经不是你自己期望的理论值了。
对于这种情况机智的我们怎么可能没有解决办法呢?不过那是另外一种算法了。
(称D-Star算法,基于Dijkstra算法,有兴趣可以自己去找一些博客看看)

已知全部地图
寻路比不上在地牢里面探索,寻路是基于全地图已知的情况下进行的。当然是预设置好的全局地图但是用地牢的性质表现是没有问题的,但是如果有一些东西是跟随玩家的探索进度而随机产生的,那就会极大地影响寻路结果或者效率

Q2:适用环境

一般是运用在游戏里面进行寻路,当然,你也可以根据你自己不同的需求来对于这个算法进行一些更改/扩展以达到你的目的。
毕竟这个算法的产生只是告诉你一种思路,其他的部分都可以靠你自己来进行实现。

Q3:有什么特别的地方吗

第一个是计算方式,相比起同样是最短路径寻找的Dijkstra算法,两者的效率比较还是A-Star算法的效率稍微偏高。主要是A-Star算法里面通过检索点限定的方式减少了整个地图的探索范围(只是相对于Dijkstra,并不是绝对的)
第二个是计算结果,因为A-Star的最短路径判断的方式带有一定的估算性,导致最后寻找到的路径并不一定是绝对最短路径,只能说是一个近似最短路径,但是这样的近似路径在某些对于最短路径在静态地图里面已经近似于最优解了。
啊……这也可能是为什么在移动通信网里面计算包的传输最短路径还是通过Dijkstra的原因吧。

话不多说,开始实践吧。

算法实践

注:图源->传送门,
还有一篇挺不错的博客,个人认为这是一篇挺不错的A-Star算法讲解

场景构造

首先,我们在这里构造一个简单的场景。
假若说你在绿色格,因为有人欠你钱了,想找到这个人并揍他一顿(在红色的格子)

场景构建

那你一定会说:绕过那堵墙不就完了吗?

但是你得知道一个问题:计算机并不知道怎么走。这个时候就需要算法来解决这样的问题了。
啊,你兴许有些疑惑,为什么这个场景构建里面都被画上了辅助线。但是这样的辅助线只是帮助我们来简化我们原来的搜索区域,这样,我们可以将整个地图作为一个二维数组记录下来,并开始计算。
自然,这个区域的划分方式在实际运用里面也可以通过自己不同的需求进行更改,在这里才用正方形的划分方法只是便于讲解。

概念引入

在正式的开始讲解这个算法之前,现在这里讲述一些在里面会使用到的一些词汇/概念,以便于稍后讲解的时候能够更加理解
自然,后文提及这些名词的时候不会做仔细的讲解了,随时可以翻到该条目进行查阅:>

  • open list:开放列表
    这个列表存储的是你所有需要检索的方格条目,也可以理解为被考虑来寻找最短路径的列表。

  • close list:关闭列表
    这个列表存储的是你已经考虑过了,或者是不需要进行考虑的方格条目,譬如说已经进行检索过的方格,或者说是障碍物方格。

  • 父节点
    在进行探索的时候,在进行路径生成的时候都需要记住是从哪个方块走过来的,这个方格就称之为父节点

  • 检索点
    正在进行路径评分的点

  • 代价
    嘛,可以粗略的理解为一个“越小越好”的东西吧

  • 路径评分
    这个内容算作是A-Star算法里面的一个核心部分了,因为摘选最终的最短路径就是通过每一个方格的路径评分来选出那个最小值作为下一个检索点。
    公式为F = G + H

    • F -> 指总评分

    • G -> 指从起始点到检索点需要付出的代价
      注意:这个是不是从每个中心点到检索点的固定代价,而是一个累加和

    • H -> 指检索点到终点需要付出的预估算代价
      在本文里面是采用的曼哈顿距离方式,给出一个预估算代价。
      该方式的计算方式可以通俗的理解为d(i,j)=|xi-xj|+|yi-yj|,即两点距离只通过非对角线方式进行计算,而不是遵循两点之间直线最短的方式进行预估。
      这样的原因主要是因为利用整数计算远优越于浮点数计算。

第一次探索

当然,如果开始探索最短路径的话,起点一定是自己最开始站立的初始位置,这个时候就需要把这个中心点加入到开放列表之中,然后对于这个方块邻接的方块进行检索。
你可能会问,这个邻接方块怎么定义?
一般来说有两种定义方式:

  • 四个方向
    这个一般是指上下左右,同时,也定义了这个移动方式也是上下左右的。自然,走这四个方向的路付出的代价是等价的。
  • 八个方向
    这个除了通常的上下左右四个方向,同时还加入了对角线移动。不过在这个里面就需要注意一下往对角线方向走,和跟直接走上下左右付出的代价是有区别的

在这个示意图里面,我们采用有八个方向的移动方式, 同时定义定义非对角线移动付出的代价是1格,对角线移动付出的代价为1.4格(这个就相当于是已知两直角边算斜边的计算公式得出的近似代价)

在确定了邻接方块之后,将每个邻接方格的父节点设置为当前的中心点,以及将这些方格加入到开放列表之中,表示这个方格是被考虑范围内的。
自然,在列举出所有的邻接方格之后,可以计算出相应的路径评分,如下图。
(在下图中按照F在左上角,G在左下角,H在右下角的方式依次标记出来,其对应的值是格数x10,每个邻接方格指向的方向就是对应的父节点的位置)

示意图1

在之后,我们要在已知的开放列表里面选择一个路径评分最小的点,作为下一次探索的时候的中心点。显然,现在是原来中心点右边的那一个点。那我们现在就将中心点转移到这个方格里面去,与此同时将原来的中心点从开放列表里面删去,并加入到关闭列表里面,表示这个点已经不需要被进行检索了。
可以参见下图,被圈了蓝色方框的,一个是已经加入到关闭列表的中心点,一个是即将进行下一次检索的中心点。

示意图2

继续探索

继续探索跟我们原来的第一步很多步骤都是相似的,譬如说确定邻接方块,加入到开放列表内,并设置父节点。但是在这个过程里面我们需要注意:
1.那些视为障碍物的邻接方格直接加入到关闭列表之中,不参与路径计算。

2.原来已经有父节点的部分需要通过是否路径更短这个判定来决定更不更新这个邻接方格的父节点。
在上图之中,我们就可以看见现在下方的那个方格已经有一个父节点了,这个时候我们就要通过G值的判断来确定我们是否来更新我们的父节点。
那我们怎么来判断G值呢,我们只需要利用两个G值来进行比较即可。

  • 按照原有方式需要付出的代价(原G值)
    在这里就是指从起点出发,按照原来的方式来到现在的这个点的一个代价总和值
    但是在实际运用里面这个值是不用计算的,因为这个值已经被存入了open list之中,只需要调用比较
  • 按照现有方式需要付出的代价(现G值)
    即通过现在的中心点到达该邻接方格需要的G值
    这个值的计算就用现在中心点的G值加上从该中心点到检索点付出的代价即可

假若说原G值小于现G值,则该检索点的父节点不变,还是原来的那一个点。
但是假若说现G值小于原G值,那么该检索点的父节点就可以被我们更改为现在的那一个中心点。

这样就A-Star算法里面一个寻找最优路径的方式,通过每次寻找的时候修正其最优值,达到最终是一个近似最优的路径方式。当然这样的每次校对是有缺点的,会导致这个算法在一些极大的地图,或者是在单线程里面同时进行寻路的太多了就会导致一定的运行速度减缓。

在更新了父节点之后,按照同样的方式,在整个开放列表里面选出一个F值最小的方块,确定为下一次检索的中心点,同时将现在的中心点加入到关闭列表里面。
但这样的规则就会导致有时候会出现一个开放列表里面有多个F值相等的情况。就还是方才的那个图:

示意图3

我们可以发现,在新的中心点上下两个邻接方格都是路径评价为54的方格,这个时候可能就犯难了,我们选择哪一个呢?
在这种情况,我们一般会选择最近加入开放列表的那个邻接方格作为我们下一个中心点。原因其实很简单,最后加入的那个邻接方格从某种意义上来说这个是距离我们当前的中心点较近的一个点,这样大概率这下一个点是紧接着我们上一个中心点的。
某种程度上算是一个加快探索效率的方式。

如此进行往复,就可以开辟一条路径出来。

结束探索

经历了一段步骤的重复,现在的示意图已经成为了下图这个样子

示意图4

怎么算作探索结束呢?当我们的目的地代表的格子已经被加入到了关闭列表里面,就算做整个路径寻找的过程已经结束了。
结束了之后,我们需要复现我们最后确定下来的路径。
这个时候父节点的作用就出来了。我们只需要从目标格开始,依次寻找该格子对应的父节点,最后我们寻找出来的一个路径,这就是我们需要的一个最优路径了。如下图红点展示的那样。

示意图5

这样,我们一次寻路就算已经完成了。

优/缺点

  • 路径自动修正
    在整个探索过程之中,可能暂时有一些错误路径的权值会小于正确路径的,但是在最后我们还是找到了相对接近的最短路径。
    这个程度很大的一个原因是最后我们获得路径的时候是从目的地的那个格子出发,通过每一个点的父节点来确定最终的路径。
    这样极大程度减少了出现误差的概率。
  • 内存耗费较高
    对于开放列表中每一个已经加入的方格都需要开辟内存来进行存储,在针对一些大型地图里面通过这样的方式来计算最优解可能异常耗费内存。
  • etc…想到了再补充吧