使用事件表实现A星自动寻路



  • 使用事件表实现A星自动寻路

      这个帖子主要是探讨下如何在唤境引擎里通过事件表实现A星自动寻路算法。其实实际的实现方式在官方的策略战棋模板里面已经有写,不过官方没有出详细的教程,所以我把模板里寻路的模块单独拿了出来,打算自己讲一讲,有什么不对的地方各位可以指正。



  • 先讲几个概念

    搜索区域:本质上,我们是将寻路的区域划分成等量的节点,这些节点可以是正方形格子,也可以是多边形格子,或者是单纯的点坐标(取决于你的移动方式)。为了方便理解,我们选择最简单的正方形节点,4个移动方向(上下左右)。
    undefined
    寻路公式:F=G+H,下面会讲到具体使用方法,现在先有个印象。
    G:是从起点A到达当前节点的移动开销,在本例中,开销定义为10
    H:不考虑障碍物,从当前节点,横向加纵向直线移动,到达终点B所需的移动开销。
    G和H的值是我们自己去定义的,我们可以根据自己的游戏设计去定义G和H的计算方式。
     
    待搜索列表(openList)和已搜索列表(closeList):我们还需要维护两个列表,openList存放我们需要去检查的节点,closeList存放已经检查过不需要再去考虑的节点。
     
     
    在了解了上述概念后,我们就可以正式开始寻路。






  • 寻路流程

    A*寻路的整体流程如下:
    1.    将起始点A加入openList
    2.    从openList中获取F值最小的一个节点,称作【当前节点】
    3.    依次检查【当前节点】周围的节点,称作【目标节点】。
    4.    如果【目标节点】在closeList中,则忽略该【目标节点】,不做任何处理
    5.    如果【目标节点】在openList中,重新计算该【目标节点】的F值,如果小于原来的F值,则将【目标节点】的父节点设置为【当前节点】
    6.    如果【目标节点】不在openList也不在closeList中,将其加入openList,设置其G、H、F的值,并将父节点设置为【当前节点】
    7.    判断是否将终点B加入到openList当中,如果是,则停止寻路流程
    8.    当周围的【目标节点】全部检查完毕后,将【当前节点】加入closeList,并从openList当中移除
    9.    判断openlist是否为空,如果为空,结束流程,否则重复第二步。
     
    现在开始一步一步的跟着这个流程走。
    首先将起点A加入openList,并检查周围节点。 此时,周围的4个节点既不在openList当中也不在closeList当中,因此,我们将4个周围节点加入openList,设置F值并将父节点设置为起点A。如下图所示,箭头代表节点指向的父节点。
    undefined
    前面提到过,F=G+H。
    在本例中,每个格子的移动开销为10,从起点A到达这4个目标节点都只经过了一个节点,因此这4个节点G都是10。
    H的计算就简单很多,上面提到过:不考虑障碍物,横向移动加纵向移动,从当前点到达终点需要经过的格子数量 X  就是H移动开销。
    以下图中起始点右侧的节点为例,横向要经过4个格子,纵向经过1个格子才能到达终点。每经过一个节点,H增加10,因此,H的值为50。(移动开销是10,和G一样)
     
    undefined
     
    按照上述算法,我们计算出了周围4个节点的F、G、H值。 参见下图,F位于左上角,G位于左下角,H位于右下角。
     
    undefined
     
    计算完毕后,将起点A从openList中移除,加入closeList,后续不需要再去管他。
    现在openList当中有4个节点,在从当中选一个F最小的。 如果有多个F值一样的,可以自定义选择规则。本例中选中右侧的节点。
    undefined
    重复上面的步骤,获取周围节点。该节点左侧是起始点,已经被加入closeList,所以不管它。 右侧是障碍物,我们也不管。因此要检查的只有上下两个节点。还是按照上述步骤,加入openList后计算F值。
    其中,要到达上方节点,必须经过当前节点,而当前节点在上一次计算时,已经算出G是10。因此,上方节点的G是当前节点G+10=20。
    undefined
    检查完后,将该节点也加入closeList。
    不断的重复上述步骤,直到将终点加入openList,或openList中没有节点存在。
    最终,我们会得到大致为这样的一幅图(我在事件表里实现的,自己画太麻烦)。
    undefined
     
    可以发现,从终点B开始往前找父节点,最终会指向起点,这样出现的这条路就是最短路径。
     
    如果对于这个流程还不明白的,最好自己手动的画一下,起点和终点不要距离太远,两格就行。 然后自己去根据这个流程,在纸上画一下。参照我上面讲到的整体流程,一步一步来。





  • 拓展思路:
    1.    G值的计算可以根据自己的游戏进行变化,比如说,默认每个格子移动开销是10,但如果下一个格子是沼泽地等比较难行走的路线,那该格子的移动开销是17。相反,如果在一些加速通道上,移动开销是6。
    2.    为了方便理解,这里只是列举了上下左右四种移动方式。其实网上的教程多数是8种,还包含了左上、左下、右上、右下。 这4种移动方式的移动开销G会比前4种高一些,例如:上下左右的G开销是10,斜方向移动的G开销是14。
    3.   基本的移动开销应该是G和H一样,这点我不是很清楚是不是有别的规则。 我自己试过H的开销是1,G是10,结果是寻路检测了很多原本不需要检测的节点,因为H的权重太小了,导致远离终点的节点也被检测,这一点各位可以自己试一下。
     

    事件表实现

    在大致明白了这套算法的原理后,就可以通过事件表实现看看了。 讲讲几个关键的点怎么实现,具体的内容我会附上工程,感兴趣的可以自己下载下来看。
    1.    寻路节点的生成:新手刚刚尝试的话,就先在场景里循环创建节点对象就好了。 这个节点对象包含了一个实例变量:父节点UID,用来标识该节点指向的节点。等到非常熟练之后,其实这些节点都可以完全数据化,保存到数组里。
    2.    openList和closeList用数组来实现。 这里就比较麻烦了,会频繁的从数组中读取数据并添加新的数据,因此不熟悉数组的朋友建议先去熟悉下数组。
    3.    openList里面保存了我们能用到的所有数据:节点UID,坐标,F、G、H。closeList由于只是用来保存不需要在关心的数据,所以只要保存UID就行。
    4.    关于检查bug,我在写事件表的时候,其实最初也写错了几行事件,导致游戏死循环卡主了…..其实到现在为止我还真没有什么好的方法来调试。所以我把每个节点的F、G、H都写在了文本组件里,然后需要调试的时候,我可能会把循环改成固定的重复几次。 有可能会因此无法寻路完整,只寻路了一部分,但是用来看问题应该是足够了。毕竟算法都是一样的,如果后面错了,那前面的也应该错了,也不需要寻路完整。如果有什么更好的调试方法,也欢迎提出来。
     
    另外为了方便解读事件表,我在这里划分一下事件表的结构。
    1.    【寻路控制全局事件表】,用于触发寻路。 有两条事件:场景开始时生成寻路节点用于计算,点击寻路节点开始寻路。
    undefined
     
    2.    【动作组全局事件表】用于实现寻路逻辑,用两个事件组。 【生成可移动区域】可以不看,这个只是生成铺满全场的寻路节点。 重点在【展示路径】里面。
    undefined
    3.    事件7、8算是一个整体,7初始化寻路数据,重置openList和closeList。8 将起始点加入openList。
    undefined
    4.    事件9就是寻路的主要内容。这里是一个无限循环,必须同过子事件里的逻辑来主动跳出循环。上面提到的调试改动循环就是指这里。
    undefined
    5.    9下面的结构我个人感觉还是挺清晰的,这个是按照官方的写法优化了下表达式。 其中10和11是从openList当中找F最小的节点,下面的就是判断上下左右4个节点了。【将终点加入openList后退出循环】的逻辑在13、20、27、34的子事件下面。
    undefined
    6.    还是在这个循环下面,检查完周围节点后从openList中移除当前节点并加入closeList,然后判断openList为空后退出循环
    undefined
    7.    循环结束后,寻路就算是完成了。 下面的这两条事件主要就是把最短路径显示出来。从终点开始,不断的向前找父节点,知道找到起点。
    undefined

    总结一下整个流程:
    1.    从openList当中选择F值最小的节点
    2.    检查该节点周围节点
    3.    不存在与openList和closeList中的节点加入openList,并设置父节点
    4.    存在于openList的节点,重新计算F值,小于原先的F值则重新设置父节点
    5.    重复步骤直到将终点加入openList(寻路完成)或OpenList中没有数据(不存在路线)。
     



  • A星自动寻路.evk工程在这里,其实没改啥,就是从官方的模板里把多余的部分去除,自己重新写了一遍



  • @Dionysus0 前面计算F值都看懂了,能说说是怎么选出路来的吗,最后是怎么参考计算结果选择路径的



  • 路就是通过F最小的选出来的,F最小的节点本身就是当前综合考虑最短的节点(G+H,在看一下上面的描述)。如果说这个最短路径上有障碍物走不通,那么根据上面的算法,就会去找除此之外另一个最小F的节点继续寻路。
    也不存在最后怎么去参考结果,你每次都去查找移动开销最小的节点,最后终点连接的这条路肯定就是最短路径。
    还是要自己画个图才会明白,给你举个例子。下图要到达蓝点,前两步只有下面可以走,因为四周都是障碍物。
    undefined

    走了两步之后,会有一个岔路,这个时候,根据算法,其实是选择右边的路继续走(自己代入H和G)。走到最右边之后,如果没有障碍物,那就是向上或者向右走(F是一样的),但是有障碍物,这条路走不通。 那么根据算法,我们需要在去openList中找一个F最小的。这个时候之所以没有重复选择已经走过的"最短"节点,是因为我们在检查完后会把这些节点从openList中移除,加入closeList(你经过了一个节点,要么他就是正确的最短路径的节点之一,要么他就是走不到终点,不管是哪种情况,都不需要再去重复的经过这个节点)。
    undefined
    undefined







  • @Dionysus0 好!干货满满!


Log in to reply