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

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

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

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

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

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

N路分叉后的逻辑判断，N路分叉后你是怎么记录路径和探索点的头位置，你怎么做的
对已走过点的处理,主要是对进口袋后的处理 ， 是怎么做的
对各分叉后的走位方向判断怎么做的，有四个方向
这仅仅是我对着你的算法想的，另外还有很多问题还没出来。
貌似这些联合起来都是一个问题，很想看看楼主的代码

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

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

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

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

 这是A*的结果

如果是你那【B*】的话就会把梳子的缝隙都填满了再找到路径，而且寻路的过程中还会出现多次返寻的问题，

如果从遍历的地图来看，你的算法是把并行的思路用几率或选择的方法来进行寻找，但其中选择的条件很容易

会导致重复的动作，就拿布袋的示例来看就出现了返寻得问题了

不过还是很鼓励你的想法：）

从起点开始，进行广度优先搜索，搜索的过程中标记和起点的距离。移动的过程中走向距离最小的点即可。

因为代码没有整理比较乱，先发到你邮件里了，后面整理了再贴出来。另外你说的问题联合起来就是一个问题，怎么绕过障碍。

非常高兴和你谈到这个问题，之前我也想过这种情况，我先把你这种阻挡下的B*寻路贴出来

 

你所担心的其实是上面第三种情况，看起来这种路线确实非常笨，呵呵。不过这个问题其实不难解决——在寻路过程中做个拉直，比如上面的73，92节点做个拉直，这样路线会趋近于最优，而优化所带来的性能损耗不会超过寻路本身，即优化后的时间复杂度<O(B*) × 2 = O(B*)， O(B*) 为B*基本算法的复杂度

另外我想说一下，你演示的A星，可能没有做过任何的优化，那确实不能比较.
我通常都是8方向，再在里面进行一点枝剪和预处理

很高兴能看到你这么认真的回复，这里首先肯定的是你的算法的效率感觉上是高，不过不知道你有没有留意到上面图里，第二个和第三个的例子的起始条件是相同的，

但在第二个节点的时候就开始出现不同的分线了，这个在特定的条件下可能会产生不稳定的情况，就好比导航的时候会让航线结果不一致，

还有的就是在第三个例子里面，你第108个节点往下走的出发条件是什么，为什么不在107~102之间发生，这些也就是个问题所在啦。

A*的优势在于当地形越复杂，就越能体现其效能啦：P
谢谢指教啦。

吃饭归来，继续这么有意思的讨论：）

 

“这个在特定的条件下可能会产生不稳定的情况”

不是这样的，这个算法除非为了需要加上随机性，否则结果还是确定的。第二和第三分线之所以不同，是因为他们的重点不一样。为了让基本的B*走出梳子的轮廓，我特意把第二个图的重点往下放中间调了。

 

“还有的就是在第三个例子里面，你第108个节点往下走的出发条件是什么，为什么不在107~102之间发生，这些也就是个问题所在啦”

在帖子正文算法过程中，第一条说明了这个原因：

1、起始，探索节点为自由节点，从原点出发，向目标前进。

即这是目标方向的引导性，和第二与第三图的分线不同是一个原因。