如何使用代码？

进入游戏后，有机器人控制的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做了另一个纯功能向演示来验证我的设计思路，感兴趣的朋友可以在这里下载。