交点与A星寻路系统
功能扩展
12.4
11-07
使用两条线段的交点和A星算法,生成基于手动放置的节点的路径

如何使用代码?

进入游戏后,有机器人控制的76、源氏和半藏,他们会互相攻击,也会攻击玩家。

不需要额外的操作,如果机器人看到你了就会尝试移动到你附近的节点。当然,它们只会沿着节点走,爬墙和跳过障碍目前是不行的。因此你可能会看到它们绕了一个大弯过来。

原理讲解

一、什么是交点与A星寻路系统?

1.A星算法大部分接触过编程的玩家都了解,我不再过多赘述,第一次听说的朋友可以百度或查看下方链接。

https://www.redblobgames.com/pathfinding/a-star/introduction.html

2.交点是指两条线段的交点。在守望先锋的地图中,有许多悬崖地形,而我们在进行寻路导航时,往往要绕过这些悬崖。这时我就采用交点算法来解决。

我在需要避让的悬崖上方设置一条或多条障碍线,这些线段的两端通过“矢量”保存到数组中。当我在进行导航时,我会让系统判断两个节点连成的线段和障碍线进行计算,看看它们之间是否存在一个交点,如果有,这个交点是否在两根线段上。如果是,那么说明这两个节点被障碍线给隔开了,因此是不能直接到达的,只能再寻找下一个点。

有了A星与交点两个系统的帮助,我就可以实现寻路时避障和择优选择节点的目的了。

二、运行逻辑

1.前期准备

工欲善其事,必先利其器。由于我的寻路系统是基于“手动放置的节点”工作的,因此准备好节点是第一步。

在寻路时,我的系统通常会遍历每一个节点来找出最优选项,如果我设置了100个节点,那么为了完成一次寻路可能要循环5050次,这很显然是非常死板的。于是我将地图划分为多个区域,每个区域中存放至多20个左右的节点,每个区域之间通过一个或多个关键节点连接。

节点:寻路的基础单位,同一个区域内的节点之间如果在彼此的“视野”内,且没有被障碍线隔开,就可以相连。摆放时应该尽量放在地图的转折处,一个节点不应有太多可以相连的其他节点,如果不想让某个节点与其他节点相连,可以把它用游戏原生的障碍物遮挡起来。

关键节点:特殊的节点,用来连接两个或以上的区域,把一个节点拷贝到另一个区域就会形成一个关键节点。

区域:用来区分节点,当起点和终点处在同一个区域时,可以直接进行寻路;如果不在一个区域,则需要先规划可能通过的区域。

2.确定起点和终点所在的区域

当定下起点和终点后,系统会先遍历每一个区域,记录起点和终点可能存在的区域。遍历完成后,对比起点和终点的区域,如果其中有相同的区域,就可以直接进行寻路,反之则进行下一步。

3.规划区域

当起点和终点不在同一个区域时,系统会先遍历起点所在区域内的每一个点,找出与该区域相邻的区域和他们与起点区域的关键节点。

找到这些相邻区域和关键节点后,系统会对关键节点以“该关键节点到起点的距离+该关键节点到终点的距离”进行排序,也就是A星的排序。排序完成后,将优先级最高的关键节点和对应的区域视为最优选项,其余的区域则为候选。

重复上一步,直到找到终点所在的区域,完成区域规划和关键节点筛选;或者碰到死路,则排除最后选择的区域,重新在候选的区域中寻找。

区域规划完成后,系统会给我们一组区域列表和对应的关键节点列表,我们需要这两样东西进行下一步。

4.寻找节点

如果起点和终点在同一个区域,那么直接进行这一步,系统会从起点开始,根据A星的运行逻辑,逐个找出适合的节点,直到到达终点。

而如果经过了规划区域的步骤,那么终点就不再是一个而是多个,每到达一个区域,就需要找到该区域中的终点,依次找到该区域的终点就可以到达最终的目的地,这就是关键节点的作用。

5.完成寻路

在经过上述几个步骤之后,系统最终会给出一个完整的路径,机器人会根据这条路径移动。

三、使用效果

在本帖放出的演示中,我选择了“铁阪”这张地图作为参考,它不算大,但很复杂,我一共使用了125个节点和11个区域来概括这张地图。

经过多次测试和Debug,我设计的这套系统表现良好,它的反应迅速,从地图的一段到另一端进行寻路最快只需要0.4秒左右,而对服务器造成的压力最高也不过70峰值(单个机器人)。

当然这还是得益于我不断调试节点与区域的布局和Debug。

目前这套系统基本上制作完成,我把他公开出来给大家做一个参考,如果有人发现了Bug,请加熔火工坊官方群464623297与我联系。

另外我用Gamemaker做了另一个纯功能向演示来验证我的设计思路,感兴趣的朋友可以在这里下载。

评论
这里空空如也~
这里空空如也~