面向三维游戏场景的动态寻路算法的研究与应用

发布时间：2020-04-26 19:04

【摘要】：针对在三维游戏场景中游戏角色动态寻路存在路径搜索结点过多,效率低下以及避让动态障碍物引起的振荡问题。本文分别在全局路径搜索和局部动态避免上做出了改进。在全局路径搜索方面,运用八叉树体素化法光栅化三维场景空间,然后根据体素坡度、高度等性质生成可行走的区域,利用Delaunay三角剖分算法生成导航网格。最后针对导航网格,分别对A*算法的启发式函数和Open列表进行了改进,并且对生成的路径进行平滑处理,从而提高了A*算法的搜索效率和搜索路径的准确性。在局部动态碰撞避免方面,引入了速度障碍的概念并分析了动态碰撞避免过程中的振荡原因,给出了基于目标区域的优先级相互速度最优碰撞避免算法,打破了碰撞避免过程中的对称性,有效的解决了动态寻路中的振荡问题。在实验仿真部分,基于Unity3D游戏引擎搭建了全局路径搜索实验仿真,比较基于导航网格改进A*算法与常规的基于方格地图A*算法的性能差异。最后制作了三维游戏场景的动态寻路仿真,模拟了在三维场景下游戏人物动态寻路的状态。最后通过实验仿真得出结论,基于导航网格改进A*算法结合目标区域相互速度动态碰撞避免算法可以大幅度的提高动态寻路中搜索效率并且解决动态碰撞避免引起的振荡问题。
【图文】：

间进行抽象化处理，生成底层数据结数据结构来表示场景中的搜索空间对要。针对不同的场景，应该选择合适高寻路算法的效率。目前搜索空间处，可视图法和路径点法。种简单的场景地图划分方式，多用于戏地图。使用大小的相同的栅格划分息，每个栅格都代表着场景地图中的。根据障碍物占栅格的百分比判断游域。如图 2-1，黑色部分代表障碍物可以定义栅格为障碍物，不可通过。

当场景地图存在不规则的障物，设置单元栅格过小会导致寻路结点能准确的表示障碍物，从而导致寻路算用于机器人路径规划领域，主要通过人定可视顶点[48-50]。首先对障碍物进行矩形点和终点的相互连接生成路线网络，如果物，，则称该直线为可视路径，所有的可的路径。如图 2-2 所示，将两个障碍物进顶点分别为{N1,N2,N3,N4}和{N5,N6,N7相互连接，与障碍物不相交的连线就是可
【学位授予单位】：武汉工程大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP301.6

【相似文献】

相关期刊论文 前10条

1 欧阳普仁,杨叔子;一种改进的Marple算法[J];南京理工大学学报(自然科学版);1988年01期

2 黄小蓓;隆永红;;分布式数据库管理系统中的N&发控制——算法及其性能分析[J];计算技术与自动化;1988年02期

3 冯成进;;0—1规划新算法的改进[J];曲阜师范大学学报(自然科学版);1988年02期

4 曾秀;魏振华;;猴群算法及其改进综述[J];电脑知识与技术;2017年32期

5 许灿英;;算法合谋反竞争问题初探[J];合肥工业大学学报(社会科学版);2019年02期

6 段艳明;肖辉辉;林芳;;新授粉方式的花授粉算法[J];计算机工程与应用;2018年23期

7 肖海军;王芬艳;卢常景;曹颖;;一种有效的多峰优化鸟群算法[J];中南民族大学学报(自然科学版);2018年04期

8 覃远年;梁仲华;;蚁群算法研究与应用的新进展[J];计算机工程与科学;2019年01期

9 肖辉辉;段艳明;;基于改进花授粉算法的移动机器人路径规划研究[J];软件导刊;2018年11期

10 莫海淼;赵志刚;曾敏;石静;温泰;;具有自适应步长与协同寻优的蝙蝠烟花混合算法[J];小型微型计算机系统;2019年07期

相关会议论文 前10条

1 苗强;刘晓琳;王仲奇;;随机球重叠判断算法改进研究工作进展[A];中国原子能科学研究院年报 2013[C];2014年

2 李超;余昭平;;基于矩阵的Apriori算法改进研究[A];第二届全国信息检索与内容安全学术会议（NCIRCS-2005）论文集[C];2005年

3 王蓬;宋明玉;张林芳;王新远;;广义自适应相干累积算法改进及其在线谱增强中的应用[A];中国声学学会2007年青年学术会议论文集（上）[C];2007年

4 郝红星;吴玲达;宋汉辰;;一种残损图像修补算法改进与实现[A];第18届全国多媒体学术会议（NCMT2009）、第5届全国人机交互学术会议（CHCI2009）、第5届全国普适计算学术会议（PCC2009）论文集[C];2009年

5 解迎刚;王志良;郑珊山;;基于LANDMARC及其算法改进的RFID室内定位研究[A];第二十九届中国控制会议论文集[C];2010年

6 王笃侠;冷晟;周燕飞;;单件小批生产模式下的MRP算法改进[A];全国先进制造技术高层论坛暨第七届制造业自动化与信息化技术研讨会论文集[C];2008年

7 邹锦峰;;水面仿真研究及算法改进[A];全国首届数字（虚拟）科技馆技术与应用学术研讨会论文集[C];2007年

8 林关成;李亚安;;一种支持向量机训练集选取算法改进[A];2009’中国西部地区声学学术交流会论文集[C];2009年

9 李国栋;;定点DSP实现均衡的算法改进与仿真[A];系统仿真技术及其应用（第7卷）——'2005系统仿真技术及其应用学术交流会论文选编[C];2005年

10 吴铁洲;郑丹丹;;蓝牙的密钥算法改进[A];湖北省电工技术学会、武汉电工技术学会2008年学术年会暨理事会换届大会论文集[C];2008年

相关重要报纸文章 前2条

1 记者 宛霞;风云卫星云导风算法改进[N];中国气象报;2018年

2 记者 陈姝;深企为大桥定制人脸识别方案[N];深圳商报;2018年

相关博士学位论文 前10条

1 张代雨;多学科优化算法及其在水下航行器中的应用[D];西北工业大学;2017年

2 钟林峰;复杂网络中关键节点的挖掘算法研究[D];电子科技大学;2018年

3 邱实;多光谱卫星遥感影像云及云阴影精准检测算法研究[D];电子科技大学;2018年

4 孙宁;人工免疫优化算法及其应用研究[D];哈尔滨工业大学;2006年

5 陆楠;关联规则的挖掘及其算法的研究[D];吉林大学;2007年

6 胡铟;基于单目视觉的运动目标检测与跟踪算法研究[D];南京理工大学;2008年

7 王珏;生物地理学优化算法的研究及应用[D];哈尔滨工程大学;2013年

8 黄松;面向多应用场景的粒子群优化算法研究[D];江南大学;2017年

9 安琦;信号侦收中的识别与分类理论与算法研究[D];电子科技大学;2017年

10 周瑞红;基于群智能优化理论的聚类改进方法及应用研究[D];吉林大学;2017年

相关硕士学位论文 前10条

1 朱昌龙;面向三维游戏场景的动态寻路算法的研究与应用[D];武汉工程大学;2018年

2 刘晓红;改进的AP-SVM算法研究及其在字母识别的应用[D];厦门大学;2017年

3 何逸凡;基于深度学习的视频动作时空检测算法研究[D];北京邮电大学;2019年

4 林婉莹;图书推荐系统中提升Top-N列表多样性算法研究[D];北京邮电大学;2019年

5 董静;基于主题模型和聚类算法的网络热点话题发现[D];河北大学;2019年

6 李佩茜;一种高效的基于教与学的社区发现算法的研究[D];厦门大学;2018年

7 裴华欣;自适应密度峰划分聚类算法研究及应用[D];浙江工业大学;2018年

8 朱炎亮;基于深度学习的人员异常操作视觉检测算法[D];浙江工业大学;2018年

9 曾辰子;改进差分进化算法及其收敛性分析[D];武汉理工大学;2018年

10 赵斯琦;基于Spark的大规模复杂网络的社区发现算法的研究与改进[D];吉林大学;2018年

本文编号：2641797