使用事件表实现A星自动寻路
-
使用事件表实现A星自动寻路
这个帖子主要是探讨下如何在唤境引擎里通过事件表实现A星自动寻路算法。其实实际的实现方式在官方的策略战棋模板里面已经有写，不过官方没有出详细的教程，所以我把模板里寻路的模块单独拿了出来，打算自己讲一讲，有什么不对的地方各位可以指正。
-
先讲几个概念
搜索区域：本质上，我们是将寻路的区域划分成等量的节点，这些节点可以是正方形格子，也可以是多边形格子，或者是单纯的点坐标（取决于你的移动方式）。为了方便理解，我们选择最简单的正方形节点，4个移动方向（上下左右）。
寻路公式：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。如下图所示，箭头代表节点指向的父节点。
前面提到过，F=G+H。
在本例中，每个格子的移动开销为10，从起点A到达这4个目标节点都只经过了一个节点，因此这4个节点G都是10。
H的计算就简单很多，上面提到过：不考虑障碍物，横向移动加纵向移动，从当前点到达终点需要经过的格子数量 X 就是H移动开销。
以下图中起始点右侧的节点为例，横向要经过4个格子，纵向经过1个格子才能到达终点。每经过一个节点，H增加10，因此，H的值为50。(移动开销是10，和G一样)
按照上述算法，我们计算出了周围4个节点的F、G、H值。 参见下图，F位于左上角，G位于左下角，H位于右下角。
计算完毕后，将起点A从openList中移除，加入closeList，后续不需要再去管他。
现在openList当中有4个节点，在从当中选一个F最小的。 如果有多个F值一样的，可以自定义选择规则。本例中选中右侧的节点。
重复上面的步骤，获取周围节点。该节点左侧是起始点，已经被加入closeList，所以不管它。 右侧是障碍物，我们也不管。因此要检查的只有上下两个节点。还是按照上述步骤，加入openList后计算F值。
其中，要到达上方节点，必须经过当前节点，而当前节点在上一次计算时，已经算出G是10。因此，上方节点的G是当前节点G+10=20。
检查完后，将该节点也加入closeList。
不断的重复上述步骤，直到将终点加入openList，或openList中没有节点存在。
最终，我们会得到大致为这样的一幅图（我在事件表里实现的，自己画太麻烦）。
可以发现，从终点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. 【寻路控制全局事件表】，用于触发寻路。 有两条事件：场景开始时生成寻路节点用于计算，点击寻路节点开始寻路。
2. 【动作组全局事件表】用于实现寻路逻辑，用两个事件组。 【生成可移动区域】可以不看，这个只是生成铺满全场的寻路节点。 重点在【展示路径】里面。
3. 事件7、8算是一个整体，7初始化寻路数据，重置openList和closeList。8 将起始点加入openList。
4. 事件9就是寻路的主要内容。这里是一个无限循环，必须同过子事件里的逻辑来主动跳出循环。上面提到的调试改动循环就是指这里。
5. 9下面的结构我个人感觉还是挺清晰的，这个是按照官方的写法优化了下表达式。 其中10和11是从openList当中找F最小的节点，下面的就是判断上下左右4个节点了。【将终点加入openList后退出循环】的逻辑在13、20、27、34的子事件下面。
6. 还是在这个循环下面，检查完周围节点后从openList中移除当前节点并加入closeList，然后判断openList为空后退出循环
7. 循环结束后，寻路就算是完成了。 下面的这两条事件主要就是把最短路径显示出来。从终点开始，不断的向前找父节点，知道找到起点。
总结一下整个流程：
1. 从openList当中选择F值最小的节点
2. 检查该节点周围节点
3. 不存在与openList和closeList中的节点加入openList，并设置父节点
4. 存在于openList的节点，重新计算F值，小于原先的F值则重新设置父节点
5. 重复步骤直到将终点加入openList(寻路完成)或OpenList中没有数据(不存在路线)。
-
A星自动寻路.evk工程在这里，其实没改啥，就是从官方的模板里把多余的部分去除，自己重新写了一遍
-
@Dionysus0 前面计算F值都看懂了，能说说是怎么选出路来的吗，最后是怎么参考计算结果选择路径的
-
路就是通过F最小的选出来的，F最小的节点本身就是当前综合考虑最短的节点(G+H，在看一下上面的描述)。如果说这个最短路径上有障碍物走不通，那么根据上面的算法，就会去找除此之外另一个最小F的节点继续寻路。
也不存在最后怎么去参考结果，你每次都去查找移动开销最小的节点，最后终点连接的这条路肯定就是最短路径。
还是要自己画个图才会明白，给你举个例子。下图要到达蓝点，前两步只有下面可以走，因为四周都是障碍物。
走了两步之后，会有一个岔路，这个时候，根据算法，其实是选择右边的路继续走(自己代入H和G)。走到最右边之后，如果没有障碍物，那就是向上或者向右走(F是一样的)，但是有障碍物，这条路走不通。 那么根据算法，我们需要在去openList中找一个F最小的。这个时候之所以没有重复选择已经走过的"最短"节点，是因为我们在检查完后会把这些节点从openList中移除，加入closeList(你经过了一个节点，要么他就是正确的最短路径的节点之一，要么他就是走不到终点，不管是哪种情况，都不需要再去重复的经过这个节点)。
-
-
@Dionysus0 好!干货满满!
-
@Dionysus0 前面计算F值都看懂了，能说说是怎么选出路来的吗，最后是怎么参考计算结果选择路径的
大佬 你的工程打不开了~图太小了 看不清楚~~~~
-
@我的个妈呀666 可以打开啊，我下载下来试了。 你用最新的官网引擎重新下载工程试试
