`
qinysong
  • 浏览: 192632 次
  • 性别: 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*)
    

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

 

分享到:
评论
79 楼 nfsfairytale 2019-05-21  
求附件求附件
78 楼 wafer1021 2018-10-18  
想在服务端运用这种
77 楼 zhezhelin 2018-04-29  
最新代码有吗
76 楼 zyh2018 2017-11-18  
你好!很开心看到你写的B*算法,但是C++版本的代码看起来很吃力,原谅我C++学的不好,请问楼主有没有C或者matlab版本的代码,或者有详细的伪代码流程也可以,能不能发给我一份呢?如果可以,不胜感激,邮箱1982435427@qq.com
75 楼 asuralove 2017-07-07  
学习了~~~~
74 楼 yiubian 2015-12-21  
写得不错,学习了。
73 楼 cctvwspc 2015-09-10  
要附件啊!
72 楼 zzz郑家兴 2015-04-30  
71 楼 h348592532 2015-03-18  
如果可以斜着走,很明显你这没法可以找到最佳路径,就知道不停的往前冲,说白你这个是可以分支的贪心算法的确还会出各种未知的问题,伦理验证性不强,谁敢用,呵呵
70 楼 余庆楚 2015-03-16  
非常的厉害,想了解具体的实现
69 楼 adomi 2015-01-29  
附件在哪里啊啊 我靠
68 楼 AirTayork 2014-06-10  
可以试试,但是似乎无法保证最短路径
67 楼 simbi 2014-05-26  
看起来不错
66 楼 stongan 2014-03-31  
感谢楼主。。。。。
65 楼 cpjsjxy 2014-03-20  
附件呢?111
64 楼 pu_user 2014-03-12  
看看到底什么东东
63 楼 a1991221 2014-01-14  
附件在哪里啊啊 我靠
62 楼 bugsou 2014-01-10  
搞下来看看-。-
61 楼 Tree168 2013-11-09  
附件是在评论后才显示的吗?
60 楼 ligyu110 2013-09-27  
wulanchun 写道
where is "附件"

同求

相关推荐

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

    JS实现贪吃蛇自动寻路算法,使用JS完成的贪吃蛇游戏,在此基础上增加了寻路算法自动寻找食物

    3. **寻路算法**: - **A*算法**:A*算法是一种启发式搜索算法,结合了Dijkstra算法的最短路径特性与曼哈顿距离等启发式函数,以更高效地找到目标。在这个项目中,我们可能用食物的位置作为目标节点,蛇头作为起始...

Global site tag (gtag.js) - Google Analytics