“RCA寻路”和“A星寻路”算法是效率对比，通过测试案例对比性能

之前公布了个自研的RCA寻路算法，效率比传统的A星算法快很多，因为没有很好的测试案例验证，所以一些开发者半信半疑，现在把测试案例补上，让大家验证一下。

测试案例链接

Cocos Creator | RCA_Demo

image3273×1900 383 KB

测试案例里能测“RCA寻路”和“A星寻路”的过程都做了哪一步，所消耗的寻路深度是多少，寻路深度代表着寻路的时间复杂度，时间复杂度随着寻路深度的增加呈指数上涨（不是线性上涨）。

点击页面上面工具栏的 “RCA寻路”和“A星寻路”可切换不同的算法，可点击拖拽玩家到任意位置，鼠标滚轮可放大缩小视野，键盘方向键可上下作用滚屏。另外左下角有3个地图的入口按钮，点击可切换不同大小不同类型的地图。

如果测了对RCA寻路性能还有疑惑的可评论提出。

RCA寻路相关的介绍
比“A星寻路”和“跳点寻路”更快的寻路算法《RCA寻路》介绍，对付大地图寻路的利器。 - Creator 3.x - Cocos中文社区

RCA寻路源码获取
RCA寻路算法在我写的RPG地图编辑器前端框架内，可到地图编辑器下载菜单下载，可免费获取。

地图编辑器地址
https://easymapeditor-1258223435.cos.ap-guangzhou.myqcloud.com/v2.0.0/web-mobile/index.html

如下图：点击下载菜单，点击基础框架，下载一个cocoscreator2.4.15或cocoscreator3.8.6版本

image1524×948 763 KB

项目中RCA寻路算法的位置

image1662×1009 84.7 KB

大神牛逼啊

有么有git，拜读一下。

上面截图有代码下载的地方

image1016×767 31.5 KB

图中红框拐角处还是撞墙了，如果认真计较，这个结果是不太对的。

提示说的步数是指的1条直线算1步，步数少不能说明就快，因为1步还是有很多计算量。

这个地图依然不够复杂，容易画线

其实那根线是跨过左边的空格的，属于坐标空格格子的地界，因为太接近障碍界，所以你以为碰撞到边界了，需要放大视野开看得见，两点一线间的射线确实没有碰撞到障碍。

image985×468 14.9 KB

这里人物移动都有快一半身体进墙了

玩家行走时使用RVO动态避障就可以了，角色有自己的半径范围，走到靠墙那位置，角色的半径区域会被墙壁挤开到正确贴墙的位置。我的地图项目里内置有动态避障接口。

每一步都是一次射线检测，射线有长有短，也可能被拐角处zh的墙体立即挡住了。射线只是几何运算，也就是我们以前学的“一元一次方程”，不涉及什么复杂的运算，如果射线被挡住立即停止运算，这个消耗是很小的。

我设置有3个地图，你要复杂的还有其它地图，点击左下角3个切换按钮。

初始这个地图虽然看着不起眼，但是是最复杂的地形，也就是死胡同，这是A星寻路最怕的地形，一旦钻入死胡同，就很可能把死胡同里的格子全部遍历一遍才找到出口，你可以切换A星寻路测一下是不是很难寻到目标。

撞墙了就是撞墙了，怎么可能交给RVO就行。寻路你寻了一条会撞墙的路怎么能行

你说的撞墙大概是这样吧，射线线段只是靠近一点墙角，但是并没有碰撞到。所以默认这是可以通过的。如果要更精确的一点，只能给射线加上宽度，这样就能更偏离一下墙角，可在我源码上的射线逻辑上修改。

image897×767 9.32 KB

截图没有吧。

你说的是指什么？

RCA源代码，以及这个Demo的代码，有开源吗？

贴子里有前面提到lRCA源码下载的地方。这个demo是论坛系统发不了文件，你可以从前面贴子地图编辑器链接里找到我的qq再加我，我把这个对比rca寻路和A星寻路的demo发给你

作者那个能通过其实是个无限小的点能通过。如果是格子地图，只要这里有一个点能通过，就是那个点所在的格子能通过，应该没问题吧。我是这么理解的。当然，视觉上可能角色有大小，那里看起来像撞墙了，你优化一下在那个格子里移动的路线应该可以（比如作者所说的rvo）。

不懂就问，这种寻路可以用在3D场景吗？之前做了一个3D的小镇。里面的npc自动寻路我没有什么好的解决办法，NV没搞懂，就用的比较基础的路点寻路，但总撞墙，设置和调整路点花了我好长时间

如果是基于3d平面寻路，我这套寻路算法是可以应用的，比如王者荣耀和英雄联盟这些3d游戏是基于一个平面的地面行走的，所以寻路可以用2d，我的寻路组件同时支持A星和RCA算法，可以自由切换使用哪种算法。

博毅创维的讲师就用我这套寻路组件做过3D的基于xoz平面的寻路，把基于y轴顶视角把的3d场景截个平面图，把平面图放到我写的在线地编工具里编辑地形行走数据，导出数据给3d游戏用，3d寻路的xoz平面坐标点按正确比例缩放成地图数据坐标点就可以用了

其实他说檫墙行走的问题可以理解成这样，把玩家体型放大10倍，基本每条行走路线都会檫墙走。或者把格子尺寸放大2倍，还是那条檫边的路径，因为格子放大了，边与墙的微小距离就清晰可见了，和墙之间空间够，也不会檫墙了。

要想解决这种问题，要么选用寻路+rvo的办法，要么选按玩家半径大小做A星寻路。这两种我的寻路组件都支持。