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

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

 

分享到:
评论
19 楼 qinysong 2010-06-01  
<div class="quote_title">leemissen 写道</div>
<div class="quote_div">
<div class="quote_title">qinysong 写道</div>
<div class="quote_div">
<p><br>非常高兴和你谈到这个问题,之前我也想过这种情况,我先把你这种阻挡下的B*寻路贴出来</p>
<p><img style="vertical-align: text-top;" src="http://dl.iteye.com/upload/picture/pic/64155/4ae25086-134d-32ba-b2ea-3a051ceec541.gif" alt="" width="731" height="403"></p>
<p> </p>
<p>你所担心的其实是上面第三种情况,看起来这种路线确实非常笨,呵呵。不过这个问题其实不难解决——在寻路过程中做个拉直,比如上面的73,92节点做个拉直,这样路线会趋近于最优,而优化所带来的性能损耗不会超过寻路本身,即优化后的时间复杂度&lt;O(B*) × 2 = O(B*), O(B*) 为B*基本算法的复杂度</p>
</div>
<p>很高兴能看到你这么认真的回复,这里首先肯定的是你的算法的效率感觉上是高,不过不知道你有没有留意到上面图里,第二个和第三个的例子的起始条件是相同的,</p>
<p>但在第二个节点的时候就开始出现不同的分线了,这个在特定的条件下可能会产生不稳定的情况,就好比导航的时候会让航线结果不一致,</p>
<p>还有的就是在第三个例子里面,你第108个节点往下走的出发条件是什么,为什么不在107~102之间发生,这些也就是个问题所在啦。<br>谢谢指教啦。</p>
</div>
<p><br>吃饭归来,继续这么有意思的讨论:)</p>
<p> </p>
<p>“这个在特定的条件下可能会产生不稳定的情况”</p>
<p>不是这样的,这个算法除非为了需要加上随机性,否则结果还是确定的。第二和第三分线之所以不同,是因为他们的重点不一样。为了让基本的B*走出梳子的轮廓,我特意把第二个图的重点往下放中间调了。</p>
<p> </p>
<p>“还有的就是在第三个例子里面,你第108个节点往下走的出发条件是什么,为什么不在107~102之间发生,这些也就是个问题所在啦”</p>
<p>在帖子正文算法过程中,第一条说明了这个原因:</p>
<p><span style="font-family: 'Times New Roman'; font-size: 10.5pt;">1、</span><span style="font-family: 'Times New Roman'; font-size: 10.5pt;">起始,探索节点为自由节点,<span style="color: #ff0000;">从原点出发,向目标前进。</span></span></p>
<p><span style="font-family: 'Times New Roman'; font-size: 10.5pt;"><span style="font-family: Verdana; font-size: x-small;">即这是目标方向的引导性,和第二与第三图的分线不同是一个原因。</span></span></p>
<p> </p>
18 楼 leemissen 2010-06-01  
<div class="quote_title">qinysong 写道</div>
<div class="quote_div">
<div class="quote_title">leemissen 写道</div>
<div class="quote_div">
<p><br><img src="http://dl.iteye.com/upload/attachment/257990/4b4edfbd-9398-3a41-a7cd-5156d97a26f4.jpg" alt=""><br> 这是A*的结果</p>
<p>如果是你那【B*】的话就会把梳子的缝隙都填满了再找到路径,而且寻路的过程中还会出现多次返寻的问题,</p>
<p>如果从遍历的地图来看,你的算法是把并行的思路用几率或选择的方法来进行寻找,但其中选择的条件很容易</p>
<p>会导致重复的动作,就拿布袋的示例来看就出现了返寻得问题了</p>
<p>不过还是很鼓励你的想法:)</p>
</div>
<p><br>非常高兴和你谈到这个问题,之前我也想过这种情况,我先把你这种阻挡下的B*寻路贴出来</p>
<p><img style="vertical-align: text-top;" src="http://dl.iteye.com/upload/picture/pic/64155/4ae25086-134d-32ba-b2ea-3a051ceec541.gif" alt="" width="731" height="403"></p>
<p> </p>
<p>你所担心的其实是上面第三种情况,看起来这种路线确实非常笨,呵呵。不过这个问题其实不难解决——在寻路过程中做个拉直,比如上面的73,92节点做个拉直,这样路线会趋近于最优,而优化所带来的性能损耗不会超过寻路本身,即优化后的时间复杂度&lt;O(B*) × 2 = O(B*), O(B*) 为B*基本算法的复杂度</p>
</div>
<p>很高兴能看到你这么认真的回复,这里首先肯定的是你的算法的效率感觉上是高,不过不知道你有没有留意到上面图里,第二个和第三个的例子的起始条件是相同的,</p>
<p>但在第二个节点的时候就开始出现不同的分线了,这个在特定的条件下可能会产生不稳定的情况,就好比导航的时候会让航线结果不一致,</p>
<p>还有的就是在第三个例子里面,你第108个节点往下走的出发条件是什么,为什么不在107~102之间发生,这些也就是个问题所在啦。</p>
<p>A*的优势在于当地形越复杂,就越能体现其效能啦:P<br>谢谢指教啦。</p>
17 楼 jesse_luzexi 2010-06-01  
另外我想说一下,你演示的A星,可能没有做过任何的优化,那确实不能比较.
我通常都是8方向,再在里面进行一点枝剪和预处理
16 楼 qinysong 2010-06-01  
<div class="quote_title">leemissen 写道</div>
<div class="quote_div">
<p><br><img src="http://dl.iteye.com/upload/attachment/257990/4b4edfbd-9398-3a41-a7cd-5156d97a26f4.jpg" alt=""><br> 这是A*的结果</p>
<p>如果是你那【B*】的话就会把梳子的缝隙都填满了再找到路径,而且寻路的过程中还会出现多次返寻的问题,</p>
<p>如果从遍历的地图来看,你的算法是把并行的思路用几率或选择的方法来进行寻找,但其中选择的条件很容易</p>
<p>会导致重复的动作,就拿布袋的示例来看就出现了返寻得问题了</p>
<p>不过还是很鼓励你的想法:)</p>
</div>
<p><br>非常高兴和你谈到这个问题,之前我也想过这种情况,我先把你这种阻挡下的B*寻路贴出来</p>
<p><img style="vertical-align: text-top;" src="http://dl.iteye.com/upload/picture/pic/64155/4ae25086-134d-32ba-b2ea-3a051ceec541.gif" alt="" width="731" height="403"></p>
<p> </p>
<p>你所担心的其实是上面第三种情况,看起来这种路线确实非常笨,呵呵。不过这个问题其实不难解决——在寻路过程中做个拉直,比如上面的73,92节点做个拉直,这样路线会趋近于最优,而优化所带来的性能损耗不会超过寻路本身,即优化后的时间复杂度&lt;O(B*) × 2 = O(B*), O(B*) 为B*基本算法的复杂度</p>
15 楼 qinysong 2010-06-01  
jesse_luzexi 写道
N路分叉后的逻辑判断,N路分叉后你是怎么记录路径和探索点的头位置,你怎么做的
对已走过点的处理,主要是对进口袋后的处理 , 是怎么做的
对各分叉后的走位方向判断怎么做的,有四个方向
这仅仅是我对着你的算法想的,另外还有很多问题还没出来。
貌似这些联合起来都是一个问题,很想看看楼主的代码

因为代码没有整理比较乱,先发到你邮件里了,后面整理了再贴出来。另外你说的问题联合起来就是一个问题,怎么绕过障碍。
14 楼 whitesock 2010-06-01  
从起点开始,进行广度优先搜索,搜索的过程中标记和起点的距离。移动的过程中走向距离最小的点即可。
13 楼 leemissen 2010-06-01  
<p><br><img src="http://dl.iteye.com/upload/attachment/257990/4b4edfbd-9398-3a41-a7cd-5156d97a26f4.jpg" alt=""><br> 这是A*的结果</p>
<p>如果是你那【B*】的话就会把梳子的缝隙都填满了再找到路径,而且寻路的过程中还会出现多次返寻的问题,</p>
<p>如果从遍历的地图来看,你的算法是把并行的思路用几率或选择的方法来进行寻找,但其中选择的条件很容易</p>
<p>会导致重复的动作,就拿布袋的示例来看就出现了返寻得问题了</p>
<p>不过还是很鼓励你的想法:)</p>
12 楼 leemissen 2010-06-01  
qinysong 写道
morroky 写道
大哥自动寻路除了判定效率还要考虑最短路径问题,否则多走冤枉路跑半小时才到谁还玩啊。。。。

对!你说的没错,这就涉及到适用性问题(不过B*寻出来路也没有夸张到需要走半小时的程度)

B*适合于游戏服务器端的Boss怪物寻路,在服务器端性能是极其关键的,大地图长距离的A*算法服务器端基本不可以接受,除非把AI模块分离为独立的线程。所以目前服务器端应用A*只能是近距离的寻路,或通过其他优化(比如航站楼导航)处理。

其次本B*算法寻找的路径,更加生动更加形象,更像自然界中真实的动物寻路。

对于玩家的自动地图寻路,一般的做法是在客户端来做的,根本不需要考虑服务器性能问题,所以可以用任意性能的算法来到达策划目的,比如可以用A*寻找最近路线。

我也一个问题,怪物寻路为什么非要找到最近路线呢?

我按照你的模型测试了下 按道理来说可以找到路径
但要是找到优秀路径的话 你那算法会有很大的几率找到没用的路径的

很明显的例子就是前方遇到一个梳子行的路障的时候,这个算法就显示问题了
我也见过外国的论坛有人提过类似的算法,但其算法的可靠性就成了被人质疑的对象了

你说为什么怪物要找最优路径的问题,我想的是要不用最优路径
那还有必要讨论寻路的问题么?直接让怪物一直走,等碰壁后再转弯也可以啊

不过还是很高兴有人能在这个点子上讨论:)

11 楼 jesse_luzexi 2010-06-01  
N路分叉后的逻辑判断,N路分叉后你是怎么记录路径和探索点的头位置,你怎么做的
对已走过点的处理,主要是对进口袋后的处理 , 是怎么做的
对各分叉后的走位方向判断怎么做的,有四个方向
这仅仅是我对着你的算法想的,另外还有很多问题还没出来。
貌似这些联合起来都是一个问题,很想看看楼主的代码
10 楼 qinysong 2010-06-01  
morroky 写道
大哥自动寻路除了判定效率还要考虑最短路径问题,否则多走冤枉路跑半小时才到谁还玩啊。。。。

对!你说的没错,这就涉及到适用性问题(不过B*寻出来路也没有夸张到需要走半小时的程度)

B*适合于游戏服务器端的Boss怪物寻路,在服务器端性能是极其关键的,大地图长距离的A*算法服务器端基本不可以接受,除非把AI模块分离为独立的线程。所以目前服务器端应用A*只能是近距离的寻路,或通过其他优化(比如航站楼导航)处理。

其次本B*算法寻找的路径,更加生动更加形象,更像自然界中真实的动物寻路。

对于玩家的自动地图寻路,一般的做法是在客户端来做的,根本不需要考虑服务器性能问题,所以可以用任意性能的算法来到达策划目的,比如可以用A*寻找最近路线。

我也一个问题,怪物寻路为什么非要找到最近路线呢?
9 楼 zzy8712 2010-06-01  
感谢楼主!
8 楼 morroky 2010-05-31  
大哥自动寻路除了判定效率还要考虑最短路径问题,否则多走冤枉路跑半小时才到谁还玩啊。。。。
7 楼 qinysong 2010-05-31  
抛出异常的爱 写道
与A*的性能比较是多少呢?


测了,比A×还是好。
刚才那个口袋的阻挡情况,5秒钟寻路次数:
B* 寻路:68362 次
A* 寻路:14581 次

大概5倍
6 楼 抛出异常的爱 2010-05-31  
与A*的性能比较是多少呢?

这个太像摸墙走迷宫法则了.
5 楼 qinysong 2010-05-31  
抛出异常的爱 写道

由于没有墙所有正常走....走进布口袋的话怎么办


它会钻进口袋里,再出来,如下:
4 楼 抛出异常的爱 2010-05-31  
qinysong 写道
老抛,呵呵,好久不见了呀

不会卡死在墙角的
环形障碍起点终点发过来是这样走出来的

由于没有墙所有正常走....走进布口袋的话怎么办

这个图怎么样

3 楼 qinysong 2010-05-31  
老抛,呵呵,好久不见了呀

不会卡死在墙角的
环形障碍起点终点发过来是这样走出来的
2 楼 抛出异常的爱 2010-05-31  
可能会死在墙角里.....
比如
3、环形障碍
的起始与结束点颠倒一下可以达成么
1 楼 dreampuf01 2010-05-30  
写个demo出来跑跑吧..仅仅上面的几个例子还是不够的.

相关推荐

    寻路算法 - 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