jack-wang
小王
C++博客
首页
新随笔
联系
聚合
管理
随笔-376 评论-37 文章-0 trackbacks-0
一种高效的寻路算法 - B*寻路算法
转:
http://qinysong.iteye.com/blog/678941
在此把这个算法称作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*)
衍生算法
通过以上封闭障碍,可以看出,这个方法在判断地图上的两个点是否可达上,也是非常高效的,在不可达情况下,时间复杂度与封闭障碍的周长相当,而不是整个地图的面积。
posted on 2011-04-07 00:07
小王
阅读(4775)
评论(0)
编辑
收藏
引用
所属分类:
游戏服务器端开发
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
C++中使用Lua脚本 和lua中调用c的方法
一种高效的寻路算法 - B*寻路算法
魔兽世界私服trinitycore2的架构——世界对象
游戏对象的实现
号称是目标软件的服务器架构(转载的,不关我事哦,图片就不发了,懒)
网络游戏中的同步问题
一种经典的服务器架构(和我的体会太接近了,不得不转)
从腾讯QQgame高性能服务器集群架构看“分而治之”与“自治”等分布式架构设计原则
无缝世界网游服务器架构的设计思路(转)
网游服务器架构的设计
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
<
2017年9月
>
日
一
二
三
四
五
六
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
6
7
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(16)
给我留言
查看公开留言
查看私人留言
随笔分类
(438)
Android(7)
Boost(8)
C#
c++ 程序设计基础(11)
CMake(2)
Cocos2d-X(1)
CUDA(3)
DB(21)
DirectX(2)
Docker(5)
Dubbo(3)
Erlang(5)
Git(6)
GO(1)
IE(1)
iOS(1)
Java(19)
JPA(2)
LibTorch(1)
linux(98)
MQTT(2)
node.js(3)
OpenGL(2)
Python(14)
Qt(7)
Redis(5)
ROS(4)
SpringBoot(4)
TensorRT(3)
UI(5)
Unreal Engine(1)
VC(44)
VLC(2)
Web开发(12)
Win32(4)
编译(34)
操作系统(3)
调试(2)
多核编程(3)
分布式系统(4)
汇编(1)
脚本(1)
开源项目(3)
其他(16)
嵌入式(1)
软件工程(5)
设计模式(7)
算法与数据结构(1)
网络通讯(17)
音视频(7)
游戏服务器端开发(17)
游戏引擎(7)
随笔档案
(376)
2024年6月 (2)
2024年5月 (4)
2024年4月 (4)
2024年3月 (9)
2024年2月 (1)
2024年1月 (6)
2023年12月 (2)
2023年10月 (8)
2023年9月 (1)
2023年7月 (2)
2023年5月 (1)
2023年4月 (3)
2023年3月 (2)
2022年12月 (2)
2022年11月 (3)
2022年10月 (3)
2022年9月 (5)
2022年8月 (2)
2022年7月 (10)
2022年6月 (5)
2022年5月 (7)
2022年4月 (4)
2022年3月 (1)
2022年2月 (11)
2022年1月 (6)
2021年12月 (7)
2021年10月 (3)
2021年6月 (2)
2021年4月 (1)
2021年3月 (3)
2021年2月 (1)
2021年1月 (3)
2020年12月 (2)
2020年11月 (1)
2020年10月 (2)
2020年9月 (2)
2020年7月 (4)
2020年6月 (2)
2020年4月 (3)
2020年3月 (2)
2020年2月 (2)
2020年1月 (3)
2019年11月 (2)
2019年10月 (5)
2019年9月 (1)
2019年8月 (3)
2019年7月 (1)
2019年6月 (6)
2019年5月 (4)
2019年4月 (2)
2019年3月 (2)
2019年2月 (1)
2019年1月 (4)
2018年1月 (2)
2017年12月 (8)
2017年11月 (3)
2017年9月 (4)
2017年8月 (1)
2017年3月 (1)
2017年2月 (2)
2017年1月 (5)
2016年12月 (1)
2016年5月 (1)
2016年4月 (1)
2016年1月 (1)
2015年8月 (3)
2015年6月 (1)
2015年5月 (1)
2015年4月 (1)
2014年7月 (2)
2014年6月 (2)
2014年5月 (1)
2014年3月 (1)
2014年2月 (2)
2013年11月 (3)
2013年9月 (4)
2013年8月 (1)
2013年6月 (1)
2013年5月 (1)
2013年4月 (3)
2013年3月 (5)
2013年2月 (1)
2013年1月 (2)
2012年11月 (1)
2012年10月 (3)
2012年9月 (1)
2012年7月 (3)
2012年6月 (3)
2012年5月 (1)
2012年3月 (5)
2012年2月 (2)
2012年1月 (1)
2011年12月 (3)
2011年9月 (1)
2011年8月 (2)
2011年6月 (1)
2011年4月 (1)
2011年3月 (2)
2011年2月 (2)
2010年12月 (1)
2010年11月 (7)
2010年10月 (7)
2010年9月 (2)
2010年8月 (2)
2010年7月 (3)
2010年6月 (2)
2010年4月 (4)
2010年3月 (6)
2010年2月 (12)
2010年1月 (22)
2009年11月 (6)
2009年8月 (5)
2009年6月 (2)
2009年2月 (4)
2009年1月 (15)
2008年10月 (1)
Linux
chinaunix
游戏开发
金庆
云风
综合
Intel
λ-calculus
周伟明
最新随笔
1. 执行torch.load(模型名称, map_location='cpu')报错:from torchvision.transforms.functional_tensor import rgb_to_grayscale
2. pip安装basicsr报错:To fix this you could try to:
3. cmake文件中D_GLIBCXX_USE_CXX11_ABI=0,导致无法到入第三方库libjsoncpp.so
4. 链接libjsoncpp.a时报错:which may bind externally can not be used when making a shared object; recompile with -fPIC
5. vs code中git push代码报错:Missing or invalid credentials.
6. git clone报错:SSL certificate problem: self signed certificate in certificate chain
7. openEuler系统中修改系统时间
8. 在CANN推理程序中,执行aclmdlExecute()函数失败。 返回错误码:507011
9. 导入ffmpeg头文件,编译报错:undefined reference to `avformat_open_input,,,
10. 编译安装ffmpeg后,代码中include ffmpeg头文件,报错找不到此头文件
搜索
最新随笔
1. 执行torch.load(模型名称, map_location='cpu')报错:from torchvision.transforms.functional_tensor import rgb_to_grayscale
2. pip安装basicsr报错:To fix this you could try to:
3. cmake文件中D_GLIBCXX_USE_CXX11_ABI=0,导致无法到入第三方库libjsoncpp.so
4. 链接libjsoncpp.a时报错:which may bind externally can not be used when making a shared object; recompile with -fPIC
5. vs code中git push代码报错:Missing or invalid credentials.
6. git clone报错:SSL certificate problem: self signed certificate in certificate chain
7. openEuler系统中修改系统时间
8. 在CANN推理程序中,执行aclmdlExecute()函数失败。 返回错误码:507011
9. 导入ffmpeg头文件,编译报错:undefined reference to `avformat_open_input,,,
10. 编译安装ffmpeg后,代码中include ffmpeg头文件,报错找不到此头文件
最新评论
1. re: DirectUI Lib XML编写说明
这个不错,很有用。
--dictbox
2. re: MFC:为CListCtrl添加背景图片[未登录]
没用
--123
3. re: DirectUI Lib XML编写说明[未登录]
很好,对于我这样的初学者很用帮助,谢谢楼主
--king
4. re: WindowXP下PHP5开发环境配置
谢谢楼主分享,已经按楼主的方法配置成功
--bbreay
5. re: error C2220: 警告被视为错误 - 没有生成“object”文件
你好,我用的是vs2012,没有你说的“选择该cpp”,如:
--coco
阅读排行榜
1. protobuf使用方法(9341)
2. 执行pip install报错: WARNING: Running pip as the 'root' user can result in broken permissions and conflicting behaviour with the system package manager. It is recommended to use a virtual environment instead: https://pip.pypa.io/warnings/venv(8565)
3. 1>c:\program files\microsoft visual studio 9.0\vc\atlmfc\include\afx.h(24) : fatal error C1189: #error : Building MFC application with /MD[d] (CRT dll version) requires MFC shared dll version. Please #define _AFXDLL or do not use /MD[d](8547)
4. 编译cmake报错:Cannot find a C++ compiler that supports both C++11 and the specified C++ flags.(7565)
5. 把python3的版本从3.6升级到3.10(6644)
评论排行榜
1. Ubuntu9.10 VI下方向键变成ABCD的解决办法(3)
2. 公司散伙啦。杯具!反思!(3)
3. 网游服务器通信架构的设计(3)
4. 服务器宕机(2)
5. 没有找到MSVCR90.dll,因此这个应用程序未能启动,重新安装应用程序可能会修复此问题(2)