qinysong
- 浏览: 190787 次
- 性别:
- 来自: 北京
-
最新评论
-
nfsfairytale：
求附件求附件
一种高效的寻路算法 - B*寻路算法 -
wafer1021：
想在服务端运用这种
一种高效的寻路算法 - B*寻路算法 -
zhezhelin：
最新代码有吗
一种高效的寻路算法 - B*寻路算法 -
zyh2018：
你好！很开心看到你写的B*算法，但是C++版本的代码看起来很吃 ...
一种高效的寻路算法 - B*寻路算法 -
asuralove：
学习了~~~~
一种高效的寻路算法 - B*寻路算法
我的论坛
jerry3aa 写道我也发现是有这个bug。楼主快点解决了，再发个来看看吧。
抱歉这么长时间才修正这个问题
已经解决，欢迎测试
执行文件（PathThinkerExe）和源工程文件（PathCompare）见附件
- 2011-03-30 23:50:47
- 浏览 47416
- 评论(45)
附件是b×程序源代码（一个包含B×和A×比较的vc6.0工程）
为解决变态阻挡，b×中引入了两个概念：
1、弯曲度，解决此类阻挡
2、弯曲回归，解决此类阻挡
本代码有一处已经发现的bug，就是在寻路的两个点上会不停遍历，后面有时间再把他修复
- 2011-01-12 17:19:01
- 浏览 47416
- 评论(45)
丶Lo丨痕灬 写道尝试了一下! 发现Lz程序在有的时候会进入一个死循环而找不到正确的路!
多谢发现了一个Bug，修了，试试这个
(更新附件，上一个有死循环的现象)
- 2010-06-09 18:46:24
- 浏览 47416
- 评论(45)
主体代码段如下（一气呵成有点流水账，仅参考吧），附件为执行演示程序
bool CPathFinder::BStar()
{
std::list<Cell> opened;
std::list<Cell> backup;
Cell& firstCell = Cells[Origin.y][Origin.x];
opened.push_back(firstCell);
opened.sort();
std::list<Cell>::iterator iter = NULL;
while (opened.s ...
- 2010-06-05 23:50:15
- 浏览 47416
- 评论(45)
leemissen 写道
谢谢你的解析，我也明白你的意思。
但你之前提过的拉直的这个问题不知道会不会在拉直的动作中产生新的中节点，然后又有新的拉直，会不会产生连锁的返寻呢？
而且，那些节点之间需要拉直，该谁和谁拉直，这又是一个新的课题了，如果要实现里面的思路，最后的性能，还有内存方面的损耗会很可观的：P
你说过你的寻路方法比较接近动物的思考方法，
但我的观点是A*的思路，更接近于自然界的法则--水满则溢：）
嗯。
这就回归到算法的使用范围和场景，B*不适合解决最优寻路，B*适合作为游戏系统中服务器端的长距离寻路。且在无策划需求的话，我认为不大需要进行拉直优化。
但是 ...
- 2010-06-01 15:36:40
- 浏览 47416
- 评论(45)
leemissen 写道
qinysong 写道
非常高兴和你谈到这个问题，之前我也想过这种情况，我先把你这种阻挡下的B*寻路贴出来
你所担心的其实是上面第三种情况，看起来这种路线确实非常笨，呵呵。不过这个问题其实不难解决— ...
- 2010-06-01 13:31:50
- 浏览 47416
- 评论(45)
leemissen 写道
这是A*的结果
如果是你那【B*】的话就会把梳子的缝隙都填满了再找到路径，而且寻路的过程中还会出现多次返寻的问题，
如果从遍历的地图来看，你的算法是把并行的思路用几率或选择的方法来进行寻找，但其中选择的条件很容易
会导致重复的动作，就拿布袋的示例来看就出现了返寻得问题了
不过还是很鼓励你的想法：）
非常高兴和你谈到这个问题，之前我也想过这种情况，我先把你这种阻挡下的B*寻路贴出来
你所担心的其实是上面第三种情况，看起来这种路线确实非常笨，呵呵。不过这个问题其实不难解决——在寻路过程中做个拉直，比如上面的73，92节点做个拉直，这样路线会 ...
- 2010-06-01 12:35:33
- 浏览 47416
- 评论(45)
jesse_luzexi 写道N路分叉后的逻辑判断，N路分叉后你是怎么记录路径和探索点的头位置，你怎么做的
对已走过点的处理,主要是对进口袋后的处理 ， 是怎么做的
对各分叉后的走位方向判断怎么做的，有四个方向
这仅仅是我对着你的算法想的，另外还有很多问题还没出来。
貌似这些联合起来都是一个问题，很想看看楼主的代码
因为代码没有整理比较乱，先发到你邮件里了，后面整理了再贴出来。另外你说的问题联合起来就是一个问题，怎么绕过障碍。
- 2010-06-01 12:11:01
- 浏览 47416
- 评论(45)
morroky 写道大哥自动寻路除了判定效率还要考虑最短路径问题，否则多走冤枉路跑半小时才到谁还玩啊。。。。
对！你说的没错，这就涉及到适用性问题（不过B*寻出来路也没有夸张到需要走半小时的程度）
B*适合于游戏服务器端的Boss怪物寻路，在服务器端性能是极其关键的，大地图长距离的A*算法服务器端基本不可以接受，除非把AI模块分离为独立的线程。所以目前服务器端应用A*只能是近距离的寻路，或通过其他优化（比如航站楼导航）处理。
其次本B*算法寻找的路径，更加生动更加形象，更像自然界中真实的动物寻路。
对于玩家的自动地图寻路，一般的做法是在客户端来做的，根本不需要考虑服务器性能问题，所以可以用 ...
- 2010-06-01 10:01:34
- 浏览 47416
- 评论(45)
抛出异常的爱 写道与A*的性能比较是多少呢?
测了，比A×还是好。
刚才那个口袋的阻挡情况，5秒钟寻路次数：
B* 寻路：68362 次
A* 寻路：14581 次
大概5倍
- 2010-05-31 15:28:55
- 浏览 47416
- 评论(45)