【硕士论文】三维游戏技术的研究与实现.pdf

哈尔滨工程大学硕十学位论文摘要三维游戏技术目前已经广泛应用于各种研究领域，如虚拟现实系统、汽车模拟训练系统及军事仿真系统等它推动诸多领域的发展，并已经成为当今的研究热点基于三维游戏技术的重大意义，本文将主要对三维游戏中的碰撞检测技术和路径搜索算法进行深入详细的研究首先，提出三维游戏系统的设计思想，设计三维游戏引擎的总体框架其次，通过对碰撞检测技术的深入研究，针对轴对齐包围盒碰撞检测算法中的包围盒不紧密，检测不灵敏等缺点，对该方法进行了改进，改进后的碰撞检测方法能有效地减少运算时间，提高游戏的运行速度此外，论文详细研究了游戏中的人工智能技术，主要针对人工智能技术中的有限状态机技术和路径搜索算法迸行研究与分析，根据系统需求对A ‘路径搜索算法进行改进与优化，通过分级路径搜索、约束A ’算法搜索范围以及加权启发式函数来达到快速、有效、真实地智能化路径搜索最后，实现三维游戏系统，该系统渲染流畅、真实性好、易操作、实用价值较高关键字：三维游戏；三维游戏引擎；碰撞检测；路径搜索哈尔滨T 程大学硕十学位论文1 ．1 选题意义与背景第1 章绪论随着经济和社会的发展，三维游戏开发已经成为社会各界的重要研究领域。

由于计算机软件和硬件的迅速发展及对游戏技术的深入研究，人们对游戏的真实性和趣味性要求越来越高游戏中的碰撞检测技术可以真实地反应物体的作用；人工智能是模拟物体的智能性，不仅可以提高游戏的真实性，也可以增加游戏的趣味性于是，碰撞检测技术和游戏中的人工智能技术已经成为目前游戏研究领域的热点问题目前，各界对碰撞检测技术及人工智能技术有一定的研究，但对应用于游戏中的碰撞检测和人工智能研究较少，尤其是高校对三维游戏技术的研究尚未普及虽然有很多优秀的碰撞检测算法和人工智能技术，但是在游戏开发中，不同的应用场合，对物体碰撞的实时性和精确性及游戏角色的智能性的要求不尽相同而大部分碰撞检测算法都是针对具体的应用场合设计的，主要集中于在静态环境下两包围盒树之间的碰撞检测研究，对于动态虚拟场景中多虚拟对象之间的高效碰撞检测算法还不多图形技术渲染出漂亮的游戏场景是不能够满足人们的需求，必须有合理的人工智能技术来保证游戏的智能化和趣味性，这对人工智能技术提出了新的挑战在游戏中，寻路已经成为游戏中的一个核心部分，是人们研究的热点问题游戏中的精灵通常需要从一点移动到另外一点，这就要求能够找到一条最佳路径，并合理地躲过障碍物，这种问题的解决就要用到人工智能的路径搜索技术。

搜索技术渗透在各种人工智能系统中，如专家系统、自然语言理解、自动程序设计、模式识别、机器人学习、博弈都应用了搜索技术游戏中的路径搜索算法通常都是两个静态点之间的寻路，搜索的路径不自然，搜索速度慢，算法效率低，还没有研究出～种适合游戏的高效，快速的路径搜索算法碰撞检测技术和人工智能技术不仅可以用于游戏开发，还广泛应用于教育、虚拟现实、文物保护、地理信息系统、军事训练、科研、娱乐和商业等 稃大学硕十学位论文领域因此，加强三维游戏技术的研究具有重大的实际意义如果成功研究出适用于三维游戏的碰撞检测技术和人工智能技术将具有巨大的理论意义、实用意义及广阔的应用前景本课题以三维游戏开发为依托平台，深入地研究游戏中的碰撞检测算法和人工智能技术，针对碰撞检测算法中的计算量大，计算速度慢及碰撞检测不精确的问题，通过分类包围盒、分段检测的方式与空间剖分方法相结合的方法改进游戏中的碰撞检测，该改进方法可有效地提高碰撞检测算法的精度和速度此外，通过改进A ‘算法的路径搜索方式，约束搜索范围及加重启发函数权值的方法来完善游戏中的路径搜索算法，改进A ’路径搜索算法中的搜索时间长，搜索速度慢等问题1 ．2 研究现状2 0 世纪9 0 年代以来，随着软件技术的进步，硬件产品性能的提高，三维游戏的真实性和趣味性越来越受到关注，游戏中的碰撞检测技术和人工智能技术成为了各界的研究热点。

1 ．2 ．1 碰撞检测算法的研究现状碰撞检测问题的研究起源于2 0 世纪7 0 年代，至今，已经在碰撞检测领域做出了很多成果，已有了一些比较成熟的碰撞检测技术早期开始研究的是静态碰撞检测技术，D o b k i n 、A g a r w a l 、C h a x e l l e 等在这方面做了研究静态碰撞检测主要是检测静止状态中各物体之间是否发生碰撞的算法，这在计算几何中得到了广泛应用，这类算法对算法精度要求较高而对实时性的不作要求由于碰撞检测准确性要求的提高，C a m e r o n 、C a n n y 和R e d o n 在连续碰撞检测算法进行了研究，但连续碰撞检测算法涉及到四维结构和时间的问题，算法虽然精确，但计算复杂高，计算速度慢，在大规模场景中无法实时进行碰撞检测王兆其、王志强、L i n 及J i m e n e z 等一直致力于基于物体空间的碰撞检测算法，该算法是把层次表示法、几何推理、代数范式、空间划分、解析方2 i n 还提出了“最邻近特征算法“ 并按照物体的特征进行区间划分H o f f 和K i m 等将图像空间碰撞检测和物体空间碰撞检测算法结合起来，利用二者优点增强算法的功能，同时通过一定的负载平衡策略在C P U 与G P U之间进行调配来保证算法的整体效率。

S m i t h e r a l 提出了一种基于A A B B 包围盒的角色变形体对象的方法，该方法在每一步都重新计算对象的包围盒，其缺点是当模型复杂时不能得到实时计算V a n d e nB e r g e n 提出了一种基于S O L I D 库的方法，并时刻由叶子节点开始完成自底向上的更新，缺点是发生大尺度的变形时，A A B B 包围盒的紧密性就比较差并且包围盒之间有很大的重叠区域Y a s h i f u m iK i t a m u r a 等人提出了一种用于解决复杂场景下的变形体的碰撞检测算法，这种算法的本质是包围盒方法与空间分解法的结合，该方法的缺点是采用八叉树的数据结果复杂J ．M e z g e r 等人在模仿布料仿真时对层次包围盒结构做出了很多优化，它采用的包围盒类型是k - D o p s ，由于k - D o p s 在最坏情况下只需k ／2 次相交测试，因此J ．M e z g e r 等人采用的是四叉树方法的优点是减少相交测试时递归调用尝试，一定程度上减少了内存消耗，此外它采用“向量圆锥’’解决自相交的问题M a t t h i a sT e s c h n e r 等人提出了一种优化的哈希表来解决变形体以及自相交问题。

国防科学技术大学的魏迎海等人提出了一种基于固定方面凸包F D H 包围盒层次的碰撞检测方法，该方法用于虚拟手术仿真，解决了复杂环境中的碰撞检测问题浙江大学的范昭炜等人对实时碰撞检测技术进行了研究，利用图形硬件的高计算性能、可编程性及多处理机的并行计算能力来加速碰撞检测过程1 ．2 2 人工智能技术的研究现状2 0 世纪7 0 年代游戏中的人工智能领域才开始引起注意在最近几年中， 程人学硕十学何论文智能游戏得到了长足的进步，从而使当今的智能游戏比以前的游戏更加有趣人工智能已经成为决定每个游戏成功的重要因素游戏只靠图形技术渲染出真实的场景是不够的，必须依赖合理的人工智能技术来保证游戏的真实性和趣味性比较有代表性的是M i c r o P r o s e 公司的“文明”系列，它们采用了欺骗的手段使虚拟人物来应对复杂场面1 9 9 8 年，人工智能在三维游戏中的应用开始被重视L o o k i n gG l a s s 工作室开始在游戏中加入脚本序列技术并对人工智能引擎进行改进，L o o k i n gG l a s s 工作室自行开发的D a r k 引擎，游戏中的敌人可以根据声音辨认对物的方位，并且能分辨出不同的地面上的脚步声，在不同的光照环境下有不同的视力等等一系列比较高端的人工智能技术。

近来，美国B l i z z a r d 娱乐公司的“魔兽争霸Ⅱ“ 采用了强大而有趣的策略智能技术，M i c r o s o f t 公司的E n s e m b l e 工作室制作的“帝国时代”则具有至今为止最强大的策略智能V a l v eS o f t w a r e 公司的“半条命“ 也应用了高水平的战术智能，而E p i cG a m e s 公司开发的“虚幻竞技场“ 则因为其可扩展性和高超策略而闻名在模拟类游戏中，美国E A 公司久负盛名的“模拟人生“及“模式城市”最早成功采用了人工生命技术其中，游戏T h eS i m s 采用了许多极具个性的智能体，证明了有限状态机和人工生命技术的巨大潜力麻省理工学院( M I T ) 主要研究三维引擎技术中的人工智能、机器人和计算机图形学以及动画技术，并在人工智能技术方面做了很多成果1 ．3 存在问题纵观国内外的相关资料，三维游戏技术的研究已经取得了很多成果，涌现了很多的优秀的碰撞检测算法和人工智能技术，但是在不同的三维游戏中，对碰撞检测实时性和精确性及人工智能技术的智能性和趣味性的要求都不相同最原始的碰撞检测方法是一种费时的计算方法，对两个几何模型中的所有基本几何元素进行两两相交测试，尽管这种方法可以得到正确的结果，但当模型的复杂度增高时，o ( n 2 ) 次的相交测试是我们不能接受的。

目前大部分碰撞检测算法都是针对具体的应用设计的，主要集中于静态环境下的包围盒4 ’算法是典型的启发式搜索算法，在复杂地图的情况下，标准A ’算法的搜索速度慢，并且每个节点的相邻八个节点都要进行搜索，造成存储空间浪费显然，路径搜索算法存在着搜索节点多、计算时间长，路径不平滑等问题1 ．4 本文的研究内容和所做的工作本课题以三维游戏开发为依托，深入研究三维游戏技术，特别是碰撞检测算法和人工智能技术中的路径搜索技术主要研究工作包括：( 1 ) 游戏技术研究现状介绍国内外三维游戏技术的研究现状和发展趋向以及本课题的研究意义，得出对三维游戏技术研究的重要性及游戏技术中尚存的问题，最后给出本论文的主要研究内容和组织结构( 2 ) 三维游戏系统结构设计通过对三维游戏引擎结构、场景模型、碰撞检测技术及人工智能技术的研究，提出了三维游戏系统总体框架设计 3 ) 碰撞检测技术的研究碰撞检测技术是实现三维游戏真实性的关键技术本文通过对基于空间剖分结构的碰撞检测算法、轴平行包围盒( A l i g n e dA x i sB o u n d i n gB o xA A B B )碰撞检测算法、有向包围盒碰撞检测算法离散和有向多面体碰撞检测算法的研究。

针对轴平行包围盒碰撞检测算法计算量大、包围盒不精确的缺点进行5 丁稃大学硕十学位论文改进 4 ) 游戏中的人工智能技术研究游戏中的人工智能技术体现了游戏角色的智能，是三维游戏技。