基于多边形场景的多智能体寻路系统研究

发布时间：2017-05-28 05:07

  本文关键词：基于多边形场景的多智能体寻路系统研究，，由笔耕文化传播整理发布。

【摘要】：近几年来,由于游戏产品市场的激烈竞争,对游戏新技术的要求越来越高。人工智能,作为能够让构建出的虚拟角色更加聪明,更加智能化的技术,随着游戏产业的发展,越来越受到业界和学界的重视。其中,寻路系统是当今游戏和路径导航系统等领域的基础和重要组成部分。对于游戏中的复杂场景出现的各种实际问题,本文探讨了在连续的二维空间内,以多边形构成的场景中,多智能体角色在不发生相互重叠的前提下的整个寻路系统的构架与实现,主要研究内容包括以下几个方面：(1)在进行场景分析并生成可见点方面,提出了基于形态学膨胀的障碍附近可见点生成算法,具有计算量较小,便于局部修改的特点；并提出了另一种基于圆柱体的可见点生成算法,来生成连通性更好的可见点集合；(2)在寻路过程中的相关算法方面,介绍了一种基于向量乘积的两线段相交判断的方法,并提出了可见性图结构缓存的生成方法和具体阐述了基于该结构的A*寻路算法过程；(3)用智能体中具有旋转不变性的包围圆作为研究对象,来探讨它们的碰撞检测算法,在绕行中避免智能体相互重叠方面,依据两圆之间位置关系与接近和远离的检测,提出了改进的前向预防碰撞检测方法,提升了数值健壮性；在绕行中避免与多边形障碍发生碰撞方面,提出了对场景中的各个多边形以给定的单位半径进行预膨胀的方法,从而可以用点是否在膨胀后多边形内的条件,来判断是否发生碰撞；(4)对于包围圆形式的多智能体的绕行,提出了整个群体下时间复杂度为O(n2)的,对单个智能体、多个智能体的绕行算法,以及对多智能体的提前绕行算法,并能够逐步明显地起到了总体接近目标的效果,同时保证了计算的实时性；(5)在绕行算法与基于可见点的A*寻路算法的结合方面,提出了一种对可见点的范围判断方法,让单位不至于过分接近可见点,从而提升了多个智能体通过可见点的速度,改善了寻路效果,并让单位在碰到场景中的障碍时作另外的寻路。本文的创新之处主要在于提出了两种不同的可见点生成算法,减少了游戏关卡制作者的工作量；以及提出了多种绕行算法,来不断调整智能体单位的阵型,从而可以在保证了性能的前提下,更好地接近目标。此外在其他方面也做出了一些优化和改进。
【关键词】：场景分析 寻路算法 A~* 多智能体 碰撞检测
【学位授予单位】：广东工业大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18
【目录】：

• 摘要4-6
• Abstract6-14
• 第一章 绪论14-18
• 1.1 研究背景和意义14
• 1.2 智能寻路的国内外研究状况14-16
• 1.3 相关研究中存在的局限16
• 1.4 本文的主要工作及贡献16-17
• 1.5 本文的结构安排17-18
• 第二章 寻路系统的场景分析方法18-31
• 2.1 各类型场景的简介18-19
• 2.2 基于形态学膨胀的可见点生成方法19-22
• 2.2.1 凹凸角的形态学膨胀方法19-21
• 2.2.2 多边形的形态学膨胀方法21-22
• 2.3 基于圆柱体的可见点生成方法22-29
• 2.3.1 圆与线段是否有交集的判断23-25
• 2.3.2 障碍之间的几种情况和生成可见点的流程25-29
• 2.4 对障碍内部可见点的剔除29-30
• 2.5 本章小结30-31
• 第三章 基于可见点的A~*寻路算法31-40
• 3.1 基于向量外积的两线段相交判断方法31-32
• 3.2 可见性图结构缓存生成的算法与优化32-35
• 3.3 基于可见性图结构的A~*寻路算法过程35-39
• 3.3.1 起点到终点直线路径上的碰撞检测35-36
• 3.3.2 A~*寻路的准备36
• 3.3.3 A~*寻路算法的循环过程36-37
• 3.3.4 A~*寻路算法的结束循环条件与路径的形成37-39
• 3.4 本章小结39-40
• 第四章 智能体间的碰撞检测算法40-43
• 4.1 包围圆简介40
• 4.2 多智能体之间碰撞检测的算法及改进40-42
• 4.3 本章小结42-43
• 第五章 多智能体间的绕行算法43-50
• 5.1 对单个智能体的绕行算法43-44
• 5.2 对多个智能体的绕行算法44-47
• 5.3 对多个智能体的提前绕行算法与到达目标点效果的优化47-48
• 5.5 结合基于可见点的A~*寻路算法48-49
• 5.6 本章小结49-50
• 第六章 寻路系统的程序设计与实验分析50-64
• 6.1 MinGW与Qt简介50
• 6.2 Qt的消息机制与绘图函数50-52
• 6.3 总体设计52-54
• 6.4 障碍生成模块54-57
• 6.4.1 自绘障碍54-55
• 6.4.2 随机生成障碍55-56
• 6.4.3 界面设计56-57
• 6.5 可见点生成模块57-58
• 6.6 智能体单位模块58-59
• 6.7 实验与分析59-63
• 6.7.1 不含障碍的情形59-61
• 6.7.2 需要绕行固定的多边形障碍的情形61-63
• 6.8 本章小结63-64
• 总结与展望64-66
• 总结64-65
• 展望65-66
• 参考文献66-69
• 攻读学位期间发表的论文69-71
• 致谢71

【参考文献】

中国期刊全文数据库 前7条

1 蒯锐;洪金敏;;自动寻路A*算法的应用及优化设计[J];上海应用技术学院学报(自然科学版);2014年02期

2 余帅;李艳;王熙照;赵鹤玲;;游戏场景中基于势场的交互寻路方法[J];计算机科学;2014年02期

3 徐翔;黄敏;;一种改进的群体智能寻路算法[J];计算机应用与软件;2012年05期

4 黄进;黄宗文;凌子燕;;多智能体寻路系统在计算机游戏上的应用[J];电脑知识与技术;2012年13期

5 邱磊;;基于A~*算法的游戏地图寻路实现及性能比较[J];陕西科技大学学报(自然科学版);2011年06期

6 王培俊;王文静;陈鹏;何丽亚;;基于OBB算法和前向预防的快速碰撞检测[J];西南交通大学学报;2011年06期

7 梁毅;周刚;;基于定位点和路径复用的大型多人在线游戏寻路算法[J];计算机应用;2010年12期

中国硕士学位论文全文数据库 前4条

1 荆东星;人工神经网络在游戏寻路中的应用研究[D];长沙理工大学;2010年

2 杨科选;人工智能寻路算法及其在游戏中的应用研究[D];中南大学;2009年

3 何文雅;3D游戏场景中虚拟角色的智能寻径应用研究[D];华中师范大学;2009年

4 卢s

本文编号：401955