前言
之前我在论坛里做了一期相关《RCA寻路》算法的介绍，一些小伙伴使用我这套算法解决了自己的地图游戏项目大地图寻路卡的问题。游戏效率体验是很重要的，如果大地图寻路性能差，寻路时掉帧严重，玩家觉得体验不好可能就放弃你的游戏了，导致大量用户流失，进而对公司造成大量损失。
而我这次再次升级了RCA算法，减少了一半不必要的运算，让本来寻路速度就很快的RCA寻路算法的效率再次更上一层楼，并且做了一些优化，让寻路的最短路径更加精确，并且提供了地图外部提前烘焙寻路数据，减小了游戏运行时在线烘焙的耗时，大大提升了体验。新的寻路算法版本已经更新到地图前端框架，需要的小伙伴可到我写的在线地图编辑器页面的下载菜单免费下载
源码下载地址
进入链接后，菜单栏有个下载菜单，下载个免费前端框架，《RCA寻路》算法在里面
https://easymapeditor-1258223435.cos.ap-guangzhou.myqcloud.com/v2.0.0/web-mobile/index.html
《RCA寻路》的效率对比
在下面连接的贴子里有其它开发者证明寻路效率，这是《RCA寻路》之前未升级前的性能，从对比中可看出性能是远远甩开常用的“A星寻路”和“跳点寻路”的。而现在再次升级的版本，效率比之前再次大大提升。
对于不同的 Grid PathFinding(2D 网格寻路) 算法的性能比较与基准测试 - Showcase - Cocos中文社区
《RCA寻路》性能和原理的测试案例链接
在这个案例里可对比“RCA寻路”和“A星寻路”的性能，可以看到《RCA寻路》的工作原理和寻路效率
Cocos Creator | RCA_Demo
一、什么是RCA寻路算法
“RCA寻路”是本作者于2025年研发的一套新寻路算法，是现今速度最快的寻路算法之一，寻路速度远快于当下流行的“A星寻路”和“JPS寻路”，用于解决其它寻路算法在“大地图寻路”或“同屏多人同时寻路”效率不足的问题，如果你的项目遇到大地图寻路效果不佳的问题，使用这套RCA算法能解决你的烦恼。
二、什么是RCA寻路算法
RCA寻路即为 ：Ray(射线)，Corner(墙角)，Astar(A星寻路)，这三个元素的首选字母组合的简称。
1、Ray（射线）代表着视野，即从一个点到另一个点连线，先后经过哪些路点格子。
2、Corner（墙角），即路径的拐角处，分为“外墙角”和“内墙角”，比如一个方形的房间，屋外有4个外墙角，屋内有4个内墙角。外墙角的作用是作为视野观察点观察周围情况，内墙角的作用是查找周围有哪些外墙角。
3、Astar寻路，这里的Astar是仅基于“外墙角数据集”进行寻路。Astar不是直接用来搜寻终点的，而是寻下一个最优的外墙角用射线检测该点是否到达终点。
三、RCA寻路速度为什么最快
1、传统的A星寻路或Jps寻路都是基于4方向或8方向按启发策略公式拓展搜寻路径的，地图大并且路点格子多的时候寻路效率会受到影响。而RCA寻路用到射线检测，这个射线检测是不局限于8方向，而是“观察点”与“目标点”连线的任意角度发射射线是否可直达，就像现实世界中的我们看东西是不受角度限制的，所以RCA的射线检测能减少很多不必要曲折方向检测。
2、Ray（射线）代表着眼睛，基于“起始点”和“各墙角”位置做为视野观察点观察目标，Astar只是用于扩展下一个观察点，如果某个观察点观察到“目标点”说明路径找到了。
3、射线的检测的“观察点”只有“寻路起始点”和“外墙角”，而地图中“外墙角”的数量远少于地图总路点格子数量，所以Astar寻路阶段要搜索的数据会少很多，当然射线的检测次数同样也会少很多。
所以“RCA寻路”也可以称作带着眼睛的寻路算法，所以速度会比其它寻路算法快很多
举一个更直观的例子
如下图：
白色的是可走区域，黑色的是障碍区域，红色标记的是外墙角，一共4个。格子总数量是 50 * 30 = 1500个，黑色格子16个，白色格子数为1484个。
1、如果是传统的A星寻路或跳点寻路，那么最大是搜寻格子数1484个。
2、如果是RCA寻路，那么只用搜寻4个外墙角。并基于这4个点做射线观测点，无论终点在地图哪个位置，这4个点中一定存在一个点能观测到终点。
RCA寻路需要搜寻的格子的数量已经远远少于其它传统的寻路算法，寻路效率当然远远甩开其它寻路算法。
外墙角数量是由地形形状决定的，就算把下面的地图格子数量扩展到10000个，只要障碍区的形状不变，那么外墙角的数量还是4个，所以RCA寻路的效率受地图大小的影响比较小，只跟外墙角数量有关。
四、什么是Ray(射线)
Ray(射线)就是地图上任意两个点，位置可以是任意角度（不限于水平和垂直方向），从一个点直线去到另一个点时先后经过哪些路点格子。这个过程中如果中途遇到障碍路点格子则射线停止，没遇到障碍说明可以两点一线直达。
射线可以通过简单的几何计算，比如 “y = x * 两点间线段斜率” 计算得出射线会先后经过两点间的哪些点路点格子。
Ray代表着视野，相当于寻路算法的眼睛，能不能从一个点走到另一个点一眼就看得见。
案例1、
如下图，从蓝点向黄点发射射线先后经过标记的：1，2，3，4，5，6的格子，中间没有障碍可直达
案例2
如下图，从蓝点向黄点发射射线，先后经过标记的：1、2、3，到第4个格子时遇到黑色的障碍墙体，射线被挡住无法直达
五、什么是墙角
墙角分为“外墙角”和“内墙角”。
1、外墙角
如下图，一个可走格子有一个对角格子不可走，并且和这个对角相邻的两个格子也是可走的，那么这个就是“外墙角”，可以理解成房屋外的墙角，是用作视野观察点观察目标点用的。
2、内墙角
如下图，一个可走格子有一个对角格子不可走，并且和这个对角相邻的两个格子也是不可走的，那么这个就是“内墙角”，可以理解成房屋内的墙角，内墙角不作为观察点（因为没有意义），作用是方便找到附近可直达的外墙角。
六、什么是观察点
观察点就是用于向目标点发射线检测是否能直达的点，观察点只有2种：
1、寻路起始点。
2、外墙角。
如下图：黄色方格是终点，观察点是蓝色方格的“起始点”和标记为1，2，3，4的“外墙角”，黑色是障碍墙体。
观察点类型1：蓝色的起始点尝试向终点发射一条射线，射线被墙体挡住。
观察点类型2：有4个外墙角观察点，标记为1，2，3，4。外墙角1和2向终点发射射线被墙体挡住，3和4发射射线可直达终点。
七、地形烘焙
在地图初始化的时候，把所有墙角就要提前关联好，通过射线计算哪两个墙角是可以直达的，能直达就用数据结构存储好关联关系，用于搜索一个墙角周围可直达哪些其它的墙角，也用于Astar阶段的寻找观察点。
1、外墙角只和外墙角关联，外墙角不用关联内墙角（因为没意义，观察点只用外墙角）。
2、内墙角只和外墙角单向关联，目的是查找附近的外墙角，内墙角之间不用关联（因为没意义）。
如下图：
红色圆圈为外墙角，黄色圆圈为内墙角，初始化时通过射线检测，如果能直达就将它们连在一起，外墙角之间互相关联，内墙角单向连接外墙角。
八、AStar搜寻观察点
这里的AStar（A星寻路）是基于“外墙角数据集”搜寻的，不是像传统A星寻路那样以地图全部格子做为数据集合。AStar搜寻的是下一个最佳观察点用于观察目标点，传统A星搜的是目标点。
如下图，4个红圈标记的点就是外墙角，并且在地图初始化时已经烘焙好连接关系，AStar就是在这几个外墙角间做Astar搜寻。
备注：黄色标记的内墙角不参与观察，所以Astar不涉及内墙角（因为寻路路径的转折点一定是在外墙角处）
十、RCA寻路算法原理
RCA寻路分为3大阶段。
1、起始阶段
从起始点向终点发一条射线Ray，尝试检测是否能直达终点。
–备注：这个起始点也叫寻路“原始起始点”，因为第三阶段的Astar寻路的起始点用的不是这个，加个名称好区分。
（1）、如果射线能直达终点，寻路成功，结束寻路。
（2）、如果射线不能直达，即中途碰撞到墙壁，把射线碰壁信息带入到下一阶段即“摸墙阶段”。
如下图。向终点发射射线：“起始点2”能直达终点，寻路成功。“起始点1”射线被墙挡住不能直达。
2、摸墙阶段
取第1阶段的射线碰墙信息，先检测射线碰撞墙壁的碰撞方向，是水平方向还是垂直方向。
（1）、如果射线水平碰撞到墙壁，那么以碰撞点为起始点上下一步步摸墙，直到摸到最近的一个墙角为止。
（2）、如果射线是垂直方向碰撞到墙壁，那么以碰撞点为起始点左右一步步摸墙，直到摸到最近的一个墙角为止。
（3）、提取第（1）、（2)步摸到最近的墙角，检测是外墙角还是内墙角。
（4）、如果是外墙角并且可直达起始点，则提取这个墙角。不可直达则找这个墙角视野内周围离起始点最近并可直达起始点的外墙角。
（5）、如果是内墙角则找到这个内墙角视野范围内离起始点最近并且可直达起始点的外墙角
（6）、拿到第（4）、（5）步提取到的外墙角进入下一阶段即“基于外墙角数据集的Astar寻路阶段”。
效果图如下
3、基于“外墙角数据集”的Astar寻路阶段
这里的Astar寻路是基于所有“外墙角”做为一个数据集合做的寻路，把“摸墙阶段”第（6）步提取到的外墙角先关联到寻路原始起始点，然后再以这个外墙角做为这个Astar寻路的起始点。这个寻路是寻下一个最佳外墙角做为观察点（通过A星寻路的启发公式 f = g + h 算出下一个最佳观察点），不是找目标终点。
备注-- A星寻路的启发函数 f = g + h，这里不再赘述，感兴趣的朋友可网上查询
1、先从这个外墙角向终点发射线，如果射线能直达，则寻到目标，寻路结束。否则执行第2步。
2、把这个外墙角放进closeList（关闭列表）里面，并找出这个外墙角周围可直达的其它外墙角，通过启发函数 f = g + h计算好这些外墙角的f值，并放进openList(开放列表)里面。
3、在openList找f值最小的外墙角作为新观测点，以这个新的外墙角重复做第1步操作，直到找到目标为止。
4、如果openList里没有外墙角可观测时，则寻路失败，寻路结束。
十一、寻路过程演示图
下面各截图中，蓝色格子为起始点，黄色格子为终点，标记数字：1，2，3，4的是外墙角。
1、下图：起始点向终点尝试发射射线检测是否能直达，结果射线被墙挡住，尝试失败，进入下一步。
2、下图：起始点射线水平碰墙，做上下摸墙搜寻，找到最近的外墙角1，并且外墙角1能直达“起始点”。所以把外墙角1作为AStar阶段的搜寻起始点。
3、从外墙角1开始做AStar搜寻观测点，先射线检测外墙角1发现无法直达终点
4、搜寻下一个f值最小的观测点是外墙角2，但是射线检测外墙角2也无法直达终点
5、搜寻下一个f值最小的观测点是外墙角3，射线检测发现，外墙角3能直达终点，寻路成功。
6、寻到目标后，把搜寻路径回溯一下就得到寻路路径了。
RCA寻路源码获取
RCA寻路算法在我写的RPG地图编辑器前端框架内，可到地图编辑器下载菜单下载，可免费获取。
地图编辑器地址
https://easymapeditor-1258223435.cos.ap-guangzhou.myqcloud.com/v2.0.0/web-mobile/index.html
如下图：点击下载菜单，点击基础框架，下载一个cocoscreator2.4.15或cocoscreator3.8.6版本
项目中RCA寻路算法的位置
RCA寻路只写了typescript版本，其它编程语言如果需要可按这个版本抄写
如果遇到技术问题可咨询本作者，联系方式：
QQ： 583051842
微信： code2tang
cocos官方引擎到现在也没有一个内置的寻路算法，如果需要植入我这套算法，我愿意授权和提供技术支持。
