一种高效的寻路算法 - 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出来跑跑吧..仅仅上面的几个例子还是不够的.