比“A星寻路”和“跳点寻路”更快的寻路算法《RCA寻路》介绍,对付大地图寻路的利器。

那这是一位成都的同学了哟 王者在成都天府3街 , 王者不是unity吗

一个本来挺好的技术贴,终究是变味了!

这么一说有这个帖子的即视感啊

就算你在法院打官司,你质疑对方,你也是需要举证的。既然你质疑作者的RCA,请你提供证据,举证作者说的不对。反反复复一直在说自己的go语言法拉利V12比作者的小米SU7要快。

哈哈,好久没吃到这么香的瓜了,嘲讽楼主反而自爆身份刚毕业的桀骜反骨骚年。

还面试什么王者荣耀,直接去竞争嘴强王者去吧,tang还是脾气太好了素质有待降低。

以前也刷到过这种技术争论帖,好像是muziki和水煮饭,争的好像是枚举还是啥的,也盖了很多层。后面好像也开吵了,反正也很有意思:joy:

求放过,我已经1个月没说话了


为啥删了(0, 1)就找不到路径了

重新获取一遍CusHeap文件

RCA寻路

好牛逼,看不懂,学(抄)习(袭)一下,塞我项目里面用了先。

关于寻路,我以前设想过一个思路,不保证最优但是保证大多数情况下较优:
因为地图一般都是固定的,那么配置路点的时候可以直接规划出一条“高速公路”,玩家在任意地点开始寻路,本质上都是在计算从起点到最近的高速路口的寻路,说白了别的算法都是在找几千上万个路点找最优路径,我的高速公路算法本质上就是在一百个路点以下找最近的路径(至少从原理上说肯定是我这个方法更优,除非我算法写的稀烂)。等玩家走到高速公路了,则直接开始沿着路线走到最近的出口再到终点的寻路。这种方式的缺点在于一开始设计的高速公路需要更优势才行。

1赞

想法很好,敢于构思想象一套算法,有最求精神值得鼓励!

这不就是高德地图的寻路么。。

高德怎么寻路我不清楚,这个是以前我做回合mmo游戏的时候想到的寻路方式。

自己没实现,只是一个想法而已。

本来只是来学技术,没想到看了一场这么精彩的博弈。
up不要太和对方置气,是非对错大家心里都有评判了。
然后我想说的是,要不起个好记的中文名吧,咱们小厂,人均英语水平没过4级,哈哈哈,请大佬来个响当当的中文名吧!

已经重新开了一贴,寻路算法已经升级过,这个贴子里提到的有小概率不是最短路径,会多走几个格子的问题已经修复,并且减少了一半的寻路运算,现在这个寻路更完善了,无论效率和准确性都进一步提升了。寻到的路径距离很多时候比A星寻到的路径更短,就算不比A星寻路更短最少也能和A星持平(说明这个路径已经是最短路径)。

新的算法介绍帖子。

你提到RCA寻路的路径有概率不是最短的问题已经修复,包括A星寻路路径有可能不是最短的问题也都修复。这是因为之前寻路时,从openlist查找f值最小的路点时,遇到多个相同权重f值的路点时随便选一个引起的。后面修改了一下,多个路点f值相同时再判断谁的h值最小,f值和h值都相同时再判断谁的g值最小,这样就解决问题了。现在这套“RCA寻路”和“A星寻路”组件已经趋于完美,不会发生找到的路径不是最短的情况了,寻到的路径100%是最短路径。新代码可从地图编辑器下载菜单的“基础框架”或“高级框架”获取

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


用在线地图编辑器绘制下面截图这种地形障碍再验证一下。还有文章里有人提到其它地形遇到不是最短路径的情况也可以再验证一下。

这个问题不是4方向或8方向寻路的问题,而是我上面提到的寻路时,从openlist查找最小f值的路点时。如果存在多个f值相同的路点随机选一个引起的,只要做一下处理就可以。多个路点f值相同时,再对比谁的h值谁更小,h值也相同时再判断谁的g值更小。


我的寻路组件优化如下截图,因为openlist用的是堆叉存储结构,f值小的放左子树,大的放右子树,所以存放路点时做了f值是否相同的判断,然后分别判断h谁更小,再判断g值谁更小。做了这层判断后,寻路路径有概率不是最短的问题解决了。

2赞