`
qinysong
  • 浏览: 192425 次
  • 性别: Icon_minigender_1
  • 来自: 北京
文章分类
社区版块
存档分类
最新评论

一种高效的寻路算法 - B*寻路算法

阅读更多

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

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

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

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

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


演示如下: 
    
   



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

寻路次数比较(5秒钟寻路次数) 


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

     
 

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

   

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

      


4、封闭障碍(目标不可达)
此种情况,根据以上测试数据,B*算法效率是普通A*的581倍(左为A*,右为B*)
    

衍生算法
通过以上封闭障碍,可以看出,这个方法在判断地图上的两个点是否可达上,也是非常高效的,在不可达情况下,时间复杂度与封闭障碍的周长相当,而不是整个地图的面积。

 

分享到:
评论
59 楼 wulanchun 2013-09-18  
where is "附件"
58 楼 wulanchun 2013-09-18  
where is "附件"
57 楼 唐厚文 2013-07-06  
这个算法明显行不通的
56 楼 SNOOPY_qhy 2013-05-17  
楼主那个B*与A*的性能比较能传下源代码吗~
55 楼 kcl_70 2013-04-05  
这个要下下来看看,多谢楼主了
54 楼 woopengcheng 2013-02-17  
53 楼 woopengcheng 2013-02-16  
lz用最新一个加了弯曲度的版本在这里出现是否是Bug呢?[img][/img]?
52 楼 wavehuang1111 2012-12-15  
来迟了
51 楼 mycoolmc2010 2012-11-21  
算法成熟了吗,没有看到附件
50 楼 杀手的腿毛 2012-11-20  
支持楼主的想法,但是名字感觉不妥,B*算法和博弈树上面的B*算法重名了。我本来是在收索博弈树的B*算法无意中搜到这里来了
49 楼 Cn_kavin 2012-08-20  
楼主探索精神可嘉,但是4方向的A*测试数据不准确,差别非常大。
############################################################
#  ## #                                                    #
#  &# #                                                    #
# %## #    %                                               #
#  %  # % % %                                    %%%       #
#   % #%#%#  %                                  %###%      #
#    %#%# #   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% #@#%      #
#    %#%# #                                      #%#%      #
#     % # #                                      #%#%      #
#         #                                      # %       #
############################################################
48 楼 chengyun57 2012-08-16  
请教问题
您好,我對您寫的B*算法有興趣,可惜自己程度不夠,不知是否有一般C語言版本的,非C++版本的,因為程度不夠,希望能使用DevC就可以執行的原始碼,不知是否有嗎?謝謝您

47 楼 GodJohnny 2012-02-01  
Gavin.Chen 写道
where is "附件"

同问
46 楼 Gavin.Chen 2011-09-06  
where is "附件"
45 楼 seedjyh 2011-05-13  
如果是静态搜索,用BFS应该也够了
如果是游戏的话,由于目的地是动态变化的,因此算法要考虑避免重复运算吧
44 楼 macro776 2011-04-15  
C++不熟,楼主是否有可能改成Java版本的?
43 楼 qinysong 2011-03-30  
jerry3aa 写道
我也发现是有这个bug。楼主快点解决了,再发个来看看吧。

抱歉这么长时间才修正这个问题
已经解决,欢迎测试
执行文件(PathThinkerExe)和源工程文件(PathCompare)见附件
42 楼 jerry3aa 2011-02-09  
我也发现是有这个bug。楼主快点解决了,再发个来看看吧。
41 楼 抛出异常的爱 2011-01-28  
qinysong 写道
附件是b×程序源代码(一个包含B×和A×比较的vc6.0工程)
为解决变态阻挡,b×中引入了两个概念:
1、弯曲度,解决此类阻挡


2、弯曲回归,解决此类阻挡


本代码有一处已经发现的bug,就是在寻路的两个点上会不停遍历,后面有时间再把他修复


如果放入实际的地图可否达到GPS寻路?
40 楼 jerry3aa 2011-01-27  
嗯,不错,不错,看看。楼主真是国家的栋梁,产业的支柱呀。

相关推荐

    寻路算法 - A*算法(简易函数接口)

    最新在研究寻路算法,在此要感谢大佬的技术支持 https://bbs.egret.com/thread-2524-1-1.html 我研究大佬的代码后,取出了A* 的计算函数。 我在大佬的帖子里,看到有高人提出:分帧计算的概念 下一篇博,会根据...

    b* 寻路算法

    总的来说,B*寻路算法是一种适应性强、准确度高的路径规划方法,尤其适用于动态或不确定的环境。通过理解和应用B*算法,我们可以设计出更智能的路径搜索系统,广泛应用于游戏开发、机器人导航、物流规划等领域。

    A*寻路算法 源码

    A*寻路算法(A* Pathfinding Algorithm)是游戏开发、地图导航、机器人路径规划等领域广泛应用的一种高效路径搜索算法。它结合了Dijkstra算法的全局最优性和BFS(广度优先搜索)的效率,通过引入启发式函数来指导搜索,...

    四方向走迷宫&寻路算法C语言

    - **寻路算法**:用于在复杂环境中寻找从起点到终点最短或最优路径的算法,如A*算法、Dijkstra算法、深度优先搜索(DFS)和广度优先搜索(BFS)等。 2. **四方向与八方向**: - **四方向**:上、下、左、右四个基本...

    a*寻路算法,c++类

    **A*寻路算法**是一种广泛应用的路径搜索算法,它结合了Dijkstra算法的最短路径特性以及优先级队列的效率,同时引入了启发式信息以提高搜索速度。在游戏开发、图形图像处理、地图导航等领域,A*算法被广泛用于计算两...

    cocos creator 实现A*寻路

    A*(A-Star)寻路算法是路径规划领域中一种广泛应用的算法,它结合了Dijkstra算法的最短路径特性与优先级队列的效率优势。在Cocos Creator中,利用JavaScript实现A*寻路算法可以为游戏或交互式应用提供高效、智能的...

    优秀程序员必须知道的32个算法

    - **定义**: 一种高效的多项式乘法算法,特别适用于大整数乘法。 - **特点**: - 通过递归将乘法问题转化为加法问题。 - 时间复杂度为O(n^log2(3))。 - **应用场景**: - 计算机代数系统。 - 大整数计算。 #### ...

    自动寻路算法(A*算法)分享

    自动寻路算法是计算机科学和游戏开发中的一个重要领域,它主要解决的是在复杂环境中找到从起点到终点的最优路径问题。A*(A-Star)算法是其中一种广泛应用且高效的算法,它结合了Dijkstra算法的最优化路径寻找和...

    A*自动寻路算法实现(java)

    下载本程序仅可演示A*自动寻路算法实现(java),该程序是基于我写的网络版贪吃蛇基础上编写的(网络版贪吃蛇...wasd键控制太阳的方向,鼠标左击目的地,会根据A*自动寻路算法计算出一条最优路线,太阳按最优路线移动。

    A星寻路算法(A*)Flex 实现

    A星(A*)寻路算法是一种在图形中寻找从起点到终点最短路径的搜索算法,广泛应用在游戏开发、路径规划、地图导航等领域。它结合了Dijkstra算法的全局最优性和 Greedy Best-First Search的效率,通过引入启发式函数来...

    A*寻路算法

    A*寻路算法是一种广泛应用于游戏开发、机器人路径规划等领域的重要算法。它结合了最佳优先搜索策略与启发式搜索技术,能够有效地找到从起点到终点的最短路径。尽管A*算法在初次接触时可能显得复杂,但一旦掌握了其...

    寻路系统之A*算法原理

    通过以上分析,我们可以看出A*算法是一种结合了贪心策略和启发式搜索策略的强大寻路算法。通过对节点成本的有效估计,A*算法能够在众多候选路径中快速找到最优路径。掌握A*算法不仅有助于解决实际的寻路问题,也能为...

    a*算法 寻路算法 寻路寻路寻路寻路寻路寻路寻路寻路寻路寻路寻路

    a*(A-star)算法是一种在图形搜索中用于寻找从起点到终点最短路径的启发式搜索算法。它结合了Dijkstra算法的最优性和BFS(广度优先搜索)的效率,通过引入启发式函数来指导搜索方向,从而更快地找到目标。a*算法...

    软件价值3-A*算法寻路

    A*(A-star)算法作为其中的一种高效寻路算法,因其智能性和准确性而备受青睐。本项目将深入探讨A*算法的原理、实现及其在实际应用中的价值。 A*算法是一种启发式搜索算法,由Peter Hart、Nils Nilsson和Brendan ...

    A*走路 自动寻路A*算法 易语言源码优化版

    A*(A-star)算法是一种广泛应用的路径搜索算法,它在自动寻路系统中起着核心作用。易语言是一种中国本土开发的、面向对象的编程语言,它以其简单易学的特点受到很多程序员的喜爱。这个“A*走路 自动寻路A*算法 ...

    实用算法基础教程--算法和数据结构

    - **概念**: 动态规划是一种优化技术,通过把原问题分解为互相重叠的子问题,再递归求解子问题,存储子问题的解而避免重复计算。 - **案例**: 最长公共子序列问题、编辑距离问题等。 - **第二节:动态规划与递推**...

    A* 寻路算法实例

    A*(发音为 "A-star")寻路算法是一种在图形中寻找最短路径的高效算法,广泛应用于游戏开发、地图导航、网络路由等领域。它结合了Dijkstra算法的全局最优性和最佳优先搜索的效率,通过引入启发式函数来估计从起点到...

Global site tag (gtag.js) - Google Analytics