找传奇、传世资源到传世资源站!

B星寻路算法

8.5玩家评分(1人评分)
下载后可评
介绍 评论 失效链接反馈

在此把这个算法称作B* 寻路算法(Branch Star 分支寻路算法,且与A*对应),本算法适用于游戏中怪物的自动寻路,其效率远远超过A*算法,经过测试,效率是普通A*算法的几十上百倍。 

通过引入该算法,一定程度上解决了游戏服务器端无法进行常规寻路的效率问题,除非服务器端有独立的AI处理线程,否则在服务器端无法允许可能消耗大量时间的寻路搜索,即使是业界普遍公认的最佳的A*,所以普遍的折中做法是服务器端只做近距离的寻路,或通过导航站点缩短A*的范围。 

算法原理 
本算法启发于自然界中真实动物的寻路过程,并加以改善以解决各种阻挡问题。 
前置定义: 
1、探索节点: 
为了叙述方便,我们定义在寻路过程中向前探索的节点(地图格子)称为探索节点,起始探索节点即为原点。(探索节点可以对应为A*中的开放节点) 

2、自由的探索节点: 
探索节点朝着目标前进,如果前方不是阻挡,探索节点可以继续向前进入下一个地图格子,这种探索节点我们称为自由探索节点; 

3、绕爬的探索节点: 
探索节点朝着目标前进,如果前方是阻挡,探索节点将试图绕过阻挡,绕行中的探索节点我们成为绕爬的探索节点; 
算法过程 
1、起始,探索节点为自由节点,从原点出发,向目标前进; 
2、自由节点前进过程中判断前面是否为障碍, 
     a、不是障碍,向目标前进一步,仍为自由节点; 
     b、是障碍,以前方障碍为界,分出左右两个分支,分别试图绕过障碍,这两个分支节点即成为两个绕爬的探索节点; 
3、绕爬的探索节点绕过障碍后,又成为自由节点,回到2); 
4、探索节点前进后,判断当前地图格子是否为目标格子,如果是则寻路成功,根据寻路过程构造完整路径; 
5、寻路过程中,如果探索节点没有了,则寻路结束,表明没有目标格子不可达; 

演示如下:  
B星寻路算法 C/C++语言基础-第1张     B星寻路算法 C/C++语言基础-第2张
B星寻路算法 C/C++语言基础-第3张    B星寻路算法 C/C++语言基础-第4张
B星寻路算法 C/C++语言基础-第5张

B*与A*算法的性能比较 

寻路次数比较(5秒钟寻路次数) 
B星寻路算法 C/C++语言基础-第6张

  
B*与A*性能比较实例 
1、 无障碍情况 
此种情况,根据以上测试数据,B*算法效率是普通A*的44倍(左为A*,右为B*) 

B星寻路算法 C/C++语言基础-第7张      B星寻路算法 C/C++语言基础-第8张
  

2、线形障碍 
此种情况,根据以上测试数据,B*算法效率是普通A*的28倍(左为A*,右为B*) 

B星寻路算法 C/C++语言基础-第9张    B星寻路算法 C/C++语言基础-第10张

   
3、环形障碍 
此种情况,根据以上测试数据,B*算法效率是普通A*的132倍(左为A*,右为B*) 

B星寻路算法 C/C++语言基础-第11张     B星寻路算法 C/C++语言基础-第12张 

4、封闭障碍(目标不可达) 
此种情况,根据以上测试数据,B*算法效率是普通A*的581倍(左为A*,右为B*) 
B星寻路算法 C/C++语言基础-第13张     B星寻路算法 C/C++语言基础-第14张

评论

发表评论必须先登陆, 您可以 登陆 或者 注册新账号 !


在线咨询: 问题反馈
客服QQ:174666394

有问题请留言,看到后及时答复