移动平台上100个人复杂障碍物寻路的思考和实现(理论篇)
yxriyin
yxriyin 13833 15
精华加亮 未分类 2016-01-07 21:55
ps:以下数据均以红米1手机为例。
 
        去年我做了一个项目,当时就为了十个人寻路的良好体验做了多方尝试,并最终通过改写A*算法,而且写了一篇文章:http://blog.csdn.net/yxriyin/article/details/40902063
当时能够做到良好的20人以下的多人寻路,在红米上每一帧也只消耗5ms不到的时间。
        但最近的一个项目是100人左右的在复杂的障碍物之间进行寻路,以前的方法在红米手机上每一帧消耗超过100ms,这是无法接受的。
        如果条件允许,我倒是想使用自带的寻路系统,自带的寻路用的是navmesh,本质上是节点寻路,效率比A*高1-2个数量级,但遗憾的是,游戏的逻辑让我必须使用A*才能实现对应的功能。
        
A*是以单元格子作为基本单位的,格子数越多,需要寻路时间越长,我们可以这么来衡量一次A*寻路的性能,此次寻路总共找了200个格子。以coc为例,
他们的格子大概是100*100,也就是10000个。这个概念可以用红米测试的时间来说明:假设一次寻路总共找了10000个格子,那么标准A*的耗时
是200ms左右(这里是我自己拿了一个A*插件在手机上的测试),而一个流畅的游戏一帧不会超过30ms。
       为了达到流畅的水平,那么每一帧只能寻找500个格子左右,大概耗时10ms,(100个人同时渲染已经占领了绝大多数的帧时间,即使实现这个目标,红米上也只能在20帧左右徘徊,不过渲染的优化还有其他手段,我们这里只考虑寻路优化先)。
      
第一个有效手段是排队,我们认为寻路的ai有一秒延迟是合理的。也就是说,一个单位在原地思考1s以内不动,是一个合理行为。那么假设我们维持在24帧,
那么就是1s内可以有24个单位排队寻路,每一个人能够尝试找500个格子。但是我们的目标是100个人,也就是说应该是每一帧要有5个人寻路,每一个人
找100个格子就能找到终点,这样就能实现目标。然而可想而知,在10000个格子内,用A*算法,想要用100个格子就找到目标,除非是毫无障碍物的情
况。
      于是我不得不开始思考为何需要消耗如此的点才能找到终点,再看了大量的文章和以下图片后:

图片:6941baebjw1epz9duun6rj20dn09rabv.jpg


      

图片:6941baebjw1epz9dw5wlij20em0agac5.jpg

图片:6941baebjw1epz9dv481tj20dn09rjtl.jpg






我得出一个结论,就是A*在有障碍物的情况下,实在是搜索了太多的无效的点了。而尝试了大半个月的方案后,有一天我突然灵光一闪:我们走迷宫的时
候,有一个策略,就是贴着墙壁一直往右走,那么假设我修改A*找格子的策略,不再以启发函数主导,而是饶墙主导,启发函数辅助的形式,是不是是就会得出一
个一直往前冲,碰到墙后绕,绕过去之后继续往前冲到达终点。假设这个能成立,那么寻找的格子将大大减少,因为你和墙壁之间的那一大片都不用找了。
当然即使行得通,找到的路径也是很奇怪的,会饶墙而行,不过我以前写过几个路径平滑算法,刚好有一个可以完美处理饶墙而行,让路径变成最短路径。
然后我就马上开始执行这个方案,一边执行一边想,为啥这么牛逼的idea以前没人想到过呢?然后我就发现了问题所在,这么做会出现一个无法解决的情况,就是死胡同,
假设你刚好走进了一个只有一个格子长度的死胡同,那么你就再也找不到路了。因为节点已经被Close了(写过A*的人应该知道这个意思)。不过生活就是这样,在我们的项目中是完全可以保证不存在这样的死胡同的。所以我就安安心心去做了。
最终成功实现。策略如下:
1.计算周围的四个格子,哪一个离终点最近,得到这个格子后,Open之,下面称它为格子A。
2.判断格子A是否贴墙,如果贴墙,那么就要Open周围的三个格子,进入步骤3。如果不贴墙,就直接跳过周围的其他三个格子,贪婪的跳转到步骤1.
3。进入A*正常的流程,用启发函数判断权值等等(具体参考标准A*)


其实很简单,只是通过1和2将大部分格子给pass了,这样的问题也描述了,就是可能找不到路,但是对于我的项目来说,是不会出现的。
这里有几个重点说明:
1.在这种策略下4格子搜索比8格子更快。
2.用这种方式找的路径,必须用路径平滑算法处理,不然走路会很奇怪。
3.判断是否贴墙要注意如果你在墙角边缘,你要判断周围8个格子,不然可能会忽略一些正确的路径导致绕远路。
4.如果障碍物不多,这种算法效率会比A*低。
5.如果障碍物太多,这种算法和A*效率一样,但是由于要路径平滑,所以也会比A*效率低。
哈哈,看了4和5,是不是坑爹啊。但大部分情况都是这样做效率高。最终测试性能结果和预期还是有点差距,一帧300个格子,10ms,可以让50个人一秒内从地图的一端经过复杂的障碍物寻路到另一端,这是目前的极限。100个人的话,会有2s的思考延迟。


目前项目就用这个来处理,体验也马马虎虎,当然如果后续有bug我会再说明。虽然我也很喜欢分享源代码,但这个代码是整合在我们整个项目中,分离出来比较麻烦,所以目前只打算做理论分享,实战分享希望以后有空专门写一个demo。      

更多细节参考以前的文章:http://blog.csdn.net/yxriyin/article/category/6057606

最近发现一个bug,那就是四个字走斜线会比直线要远,这样在我们的游戏中,斜着的墙壁的消耗就比横着的墙壁要大,导致寻路的结果老是斜着的墙壁优先,目前的方案是调整斜着墙壁的消耗值,让他的权重降低,大致和直的相等。
1条评分, 鲜花+500
  • 鲜花500
    原创奖励
分享:
游客
要评论请先登录 或者 注册
15条回应 只看楼主 最新
magicer 学徒 2016-01-13 08:28 1楼
很好的贴啊谢谢楼主
G.E.M. 新手 2016-01-17 15:21 2楼
niu b ,你签署保密协议了吗
yxriyin 师者 2016-01-17 19:13 3楼
G.E.M.:niu b ,你签署保密协议了吗回到原帖
小创业公司 而且整个东西就是我一个人做的 属于纯技术分享
zhmxiaowo 学徒 2016-01-20 11:29 4楼
四个格子寻路,close表完全没有必要,open表只要用个链表接起来就行了,不用排序,大地图能加快指数倍
bingheliefeng 学徒 2016-01-27 09:52 5楼
可以用二叉树优化,特别是障碍物固定的场景,寻路速度会快几倍
fatrony 新手 2016-02-04 15:59 6楼
写的不错,感谢
tf107 学者 2016-03-11 09:53 7楼
【假设你刚好走进了一个只有一个格子长度的死胡同,那么你就再也找不到路了。因为节点已经被Close了】 这句话也挺重要
太极尤 学徒 2016-05-12 16:38 8楼
楼主威武,帖子写的真棒~~~
笑三少 学者 2016-05-18 10:18 9楼
很厉害啊,楼主大牛
1 2
返回顶部