（计算机软件与理论专业论文）3d游戏场景中路径搜索的研究与实现.pdf

摘要 摘要 游戏入工智能这一领域是缱着2 0 世纪了。年代视频游戏豹跚现雨兴起静，这 一领域最初并没有受到人们的关注，因此在很长的一段时间里蕊，游戏人工镏能 在业界都处于默默无闻的地位。但怒，随着最近几年三维渲染的硬件设备秘游戏 静图形羧爨已经发震舞了迓乎较致豹蟪步，辩戏入王智戆逸鑫成为决定每个游戏 的成功的缀要因素。 而游戏路径搜索韪实现n p c ( 游戏中的电脑角色) 在游戏巾逼真行动的关键 技寒之一，在一定程度上决定善n p c 餐毙纯本警熬裹低。嚣辩，游戏爨缀搜索 也是一个较为困难酌强务，这是因为进行路径计簿时c p u 的负荷很重，并盥存 储路径搜索相关信息又需要较大的存储空间。 论文针对3 d 游戏场景中路径搜索的要求，程对游戏路径搜索的各秭技术进 行了分耩瓣基磴之上，并结合项嚣鹃霈求，捷密磬实现了一今3 d 游戏场豢串路 径搜索的解决方案。该方案的核心思想是对游戏场景中静态障碍物采用导航阿格 技术进行处理。一个导航网格记述了3 d 游戏场景中”可以走过”的表面，这怒一 个筵摹耋溪熬”建筑乎瓣霆”，霹戮被婚e 震寒逡霉霉靛。谂文分绥窝实褒了在 导航网格上进行寻径的技术以及如何构造一个可供寻径的导航网格的技术。而对 游戏场景中的动态障碍物，则采用导航行为中的舰避障碍物行为来处理，并针对 原有的技术在对障碍物凡每形状撼象上的缺陷，辫其遴耄亍了改遴，馒其能受好戆 匹配障礴物豹死褥特徭。并置在决定导航力的努淘野采蕉了模糊逻辑，叛使得 n p c 在规避障碍物的时候显得更为镏能。除了使用规避障碍物导航力来解决动 态障碍物处理之外，还使用了路径跟随导航行为来驱动n p c 淞着寻径算法计算 转夔鼹径豢运囊，这睇裁使霉獬c 熬运凌在显缮受为遥囊。谂文最惹在我鬃瑷 目开发的碍i 擎下面实现了这个解决方案，并对其进行了功能测试和效率测试。 关键词：游戏路径搜索，电脑角色，导航网格，导航行为，矗零葵法 a b s w a e t a b s t r a c t i n1 9 7 0 s ，w i t ht h ea p p e a r a n c eo fv i d e og a m e s ，g l t l n l 。a r t i f i c i a li n t e l f i g e n t e m e r g e d ，t h i sf i e l dd i dn o ta t t a c hm a n yp e o p l e sa t t e n t i o na tf i r s t s of o ral o n gt i m e ) g a m l 5a r t i f i c i a li n t e l l i g e n tw a s l l l l k n o w ni ni n d u s t r y b u ti nr e c e n ty e a r s ，w i t ht h eg r e a t d e v e l o po f3 d g r a p h i eh a r d w a r ea n dt h eq u a l i t yo fg a m ep i c t u r e , g a m ea r t i f i c i a l i n t e l l i g e n th a sa l r e a d yb e c a m et h ek e yf a c t o rt od e t e r m i n et h es u e c ：e s $ o f ag a m i n g a m ep a t h - f i n d i n gi st h ek e yt e c h n o l o g yo f i m p l e m e n to f t h ei n t e l l i g e n tm o v eo f n p c si ng a m e ac e r t a i ne x t e n t ，i td e t e r m i n et h ei n t e l l e c t u a l i z e dd e g r e eo fn p c s a n dg a m ep a t h - f i n d i n gi sad i f f i c u l tt a s k , t h a ti sb e c a u s ei tn e e d sm u e l ae p ur e s o l l r c 1 粥 a n dm e m o r yl - e s o u l c e st os t o r a g et h oi n f o r m a t i o na b o u tp a t h - f i n d i n g w i t ht h en e e do fg a m ep a t h - f i n d i n gi n3 dg a m es e e n oa n d0 1 1 1 p r o j e c t , a f t e r a n a l y z i n ga l lk i n d so ft e e l m o l o g ya b o u tg a m ep a t h - f i n d i n g ，as o l u t i o no f3 dg a m e p a t h - f i n d i n gi sp r o p o s e di nt h i st h e s i s t h ok e yi d e ao ft h i ss o l u t i o ni s t ou s ot h e n a v i g a t i o nm e s h t od e a lw i t ht h er e s to b s t a c l e s an a v i g a t i o nm e s hd e s c r i b e sas u r f a c 聍 w h i c hn p c sc a ng o0 1 1i t w ei n l r o d u e ea n di m p l e m e n tt h et e c h n o l o g yo f h o wt of i n d ap a t ho nt h en a v i g a t i o nm e s ha n dh o wt ob u i l dan a v i g a t i o nm e s hs u p p o r t i n gf o r p a t h - f i n d i n g a n dt od e a lw i t ht h ed y n a m i co b s t a c l e s w eu s et h es t e e r i n gb e h a v i o r w eu s ean e wt e c h n o l o g yt oa b s t r a c tt h eg e o m e t r ys h a p et oi m p r o v et h ee x i s t i n g t e c h n o l o g y , t h en e wt e e l m o l o g yc a nd oab e t t e rg e o m e l r ym a t c h i n gt h a nt h ee x i s t i n g t e c h n o l o g y w eu s ef u z z yl o g i ct od e t e r m i n et h ed i r e c t i o no ft h oo b s t a c l ea v o i d a n c e s t e e r i n gf o r c e ) w h i c hc a nm a k en t c sa p p e a rm o l ei n t e l l i g e n tw h e nt h e ya v o i d o b s t a c l e s b e s i d et h i s w eu s et h ep a t hf o l l o w i n gs t e e r i n gb e h a v i o rt od r i v en p c st o m o v ea l o n gt h ew a yp o i n t sw h i c ha l - ec o m p u t e d b e f o r e h a n d ，w h i c hc a nm a k l ：i 1 1 0 1 o i n t e l l i g e n tm o v eo f n p c s f i n a l l yt h i ss o l u t i o ni si m p l e m e n t e du n d e r o u r e n g i n e ，a n d t h ef u n c t i o na n de t f i e i e n e yo f t h i ss o l u t i o n a t e s t e d k e y w o r d s ：g a m ep a t h - f i n d i n g , n p c ，n a v i g a t i o nm e s h , s t e e r i n gb e h a v i o r , a + a l g o r i t h m 独创性声明 本久声明掰呈交豹学位论文是本人在导磐播导下进符戆研究王 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文巾不包含其他人已经发袭或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：兰金蒌亟嚣麓：? 司年争秀细 关于论文使甩陵权的说明 本学位论文作者完众了解电予科技大学有荧保留、使用学位论文 熬麓定，有权保鍪并翔豳家有关帮门或辊梅送交论文熬复窝箨窝磁 盘，- 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 鳇全部或部分瞧容编入宥关数据摩遴行检索，可以采用影爨、缩印或 扫描等复制乎段保存、汇编学位论文。 ( 保密鲶学位论文在解密后应遵守此规定) 签名：锰导爆签名：壁璧! 筮 嚣期：弘，7 年胃必e t 第一章绪论 1 1 概述 第一章绪论 人工智能，是指用计算机来模拟、延伸和扩展人的智能，实现某些机器思维 和采取某些合理行为、活动。人类的智能是一种综合性的认识客观事物和运用知 识解决问题的能力，包括感知和认知客观事物、客观世界与自我的能力；通过学 习取得经验、积累知识的能力；理解知识、运用知识和运用经验分析问题和解决 问题的能力；发明、创造、创新的能力等。因此，游戏中的人工智能可以简单定 义为所有由计算机在游戏中所作的思考。它使得游戏表现与人的智能行为、活动 类型，或者与玩家的思维、感知相符合的特性。在游戏中，无论是战略游戏中电 脑的布局、行动、攻击，还是角色扮演游戏中敌人的角色的施法、攻击和行为控 制等，人工智能都扮演了重要的角色。特别是在以战术问题求解为核心的游戏中， 人工智能更是显得重要，它能给玩家提供更多，更为真实的游戏挑战，激发玩家 的兴趣，并有效地融入到游戏中。另外，人工智能在游戏可玩性方面往往也起着 决定性的作用，把人工智能应用到游戏中，会使玩家感受和觉察到游戏中的人物 行为具有令人信服的合理性j 趣味盎然的人工智能无疑将吸引到一大批玩家，并 有效地促进游戏开发获得成功。 以往游戏开发侧重于能实时绘制渲染多个多边形，人物的眼睛是多么漂亮， 人物的肌肉是多么有弹性。当游戏引擎已经能够渲染出非常真实的场景和人物模 型，游戏开发人员自然而然的将注意力转移做出更有意义的事情，这就需要人工 智能技术，一个游戏趟系统可以分为以下几个部分： 周 记忆存储游戏中的 、戳i 用邕 i 感知l 决策行 l 输入r 分析推理为输出 图i - i游戏a i 系统结构图 电子科技大学硕士学位论文 感知输入子系统：它使游戏a j 系统的最基本部分。所有a j 系统都必须能感 知它们周围的世界，才能使用这些信息作进一步的推理和分析。周围世界中哪些 信息在何种程度和范围内被感知，取决于正在开发的游戏类型。 记忆存储子系统：它负责将所有感知的信息、数据和知识等，以合适的方式 在计算机内表达和存储。游戏中感知数据和知识的存储是一个较为复杂的过程， 很多数据并不是按一种直接的方式存储。 分析推理子系统：它使游戏a i 系统的核心。它通过感知到的数据和存储记忆 体中的知识分析当前的状况，并做出一个合理的决策。做出决策的快慢取决于可 选择的决策数目的多少，以及所需要考虑的感知信息的多少。 决策行为子系统：它主要负责把计算机做出的各种决策和行为，作用到游戏 世界中的人物角色上。 路径搜索是实现n p c 在游戏中逼真行动的关键技术之一。在一定程度上标志 着n p c 智能化水平的高低。游戏路径搜索是一种用来产生有目的的移动的技巧， 它赋予了n p c 感知周围地形环境的能力。而游戏路径搜索的实现即复杂，又需要 耗费很多的计算和存储资源，因此，在游戏路径搜索中要兼顾效率与真实感，这 使得游戏路径搜索成为游戏人工智能中一个很有挑战性的课题。 1 2 课题的来源 论文是3 d 游戏场景中路径搜索的研究与实现，是以国家8 6 3 项目“网络游戏 公共技术平台关键技术研究”和国家8 6 3 项目“数字媒体公共技术平台研发”为 依托研究开发的。前者是大型实时网络三维游戏引擎设计，蕤合网络，图形，物 理，a j 和游戏逻辑，音效等功能模块，并开发以场景编辑器为主的数字内容创作 工具。最终实现了多通道大视景的大型室外场景实时模拟。后者是研究数字媒体 创作中的若干关键技术。实现一个统一的数字媒体技术开发公共平台。主要涉及 实时计算机图形学高级算法与大规模软件工程。 1 3 发展现状与研究动态 1 3 1 游戏a l 的发展 m 在游戏开发中占有越来越重要的位置，大多数的游戏公司宣称他们的游戏 2 第一章绪论 开发项目中包括至少一名专业a i 程序员，越来越多的游戏开发人员正把更多的精 力投入到游戏a j 的设计和实现中。人工智能领域5 0 多年来的发展提供了很多优 秀的a i 成果和技术，已经能够解决一大批的问题。虽然大多数传统的人工智能技 术在游戏中的应用近乎完美，但这并不意味着任何人工智能技术应用都可以直接 应用到游戏开发中。游戏开发人员所拥有的各种资源十分有限，开发进度的时间 要求特别高，因此，他们往往只使用能带来清晰而明显好处的人工智能技术，否 则，就会因为开发经费、开发周期等问题而放弃。纵观当前游戏中的a j 技术，最 为流行和普及的是基于规则的a i 。在技术实现上以有限状态机和模糊有限状态机 为主。它们的设计原理已为人熟知、测试简便，设计者可以方便地在许多方面“自 定义”特定的行为方式。目前市场上的许多游戏都运用了这种基于规则的a j ，虽 然在技术实现上比较简单，但由于制作者的智慧，还是有很多作品表现出让人惊 奇的智能水平。游戏开发领域也曾对很多a i 技术，如神经元网络、遗传算法等， 进行了各种尝试，事实证明，游戏中的a i 技术并不是越复杂越好。 今后的a i 将从死板的、基于规则推理的a i 技术向更为灵活的、以模糊推理 为核心的技术转变。游戏越的开放程度也将越来越高，可扩展的a i 技术将会成 为主流发展趋势之一。可以想象，对游戏玩家来说，最激动人心的莫过于依照自 己的口味和爱好，对游戏的a i 进行一番全面的修改和整理。不过，增加强大的可 扩展a j 功能并不容易，究竟通过何种方式或是在多大程度上向玩家提供a j 扩展 功能? 这一问题引起了开发者们的激烈争论。显而易见的是，玩家们既想简单快 捷而又全面自由地改编游戏地越，而开发者们担心由此带来的游戏的安全问题。 而且，游戏的自由越高，售后服务就越棘手。目前市场上已经有多款游戏( 如“文 明之力量召唤”、“半条命”等) 成功的应用了可扩展a i 技术，证明了它在多种游 戏类型中的可行性。 游戏a i 发展的另一个主要趋势是游戏人物的学习能力的模拟日益得到重视。 随着玩家们对游戏a j 的要求愈来愈高，游戏a i 的经验积累和学习功能这一难题 也浮出水面，一个优秀的游戏，a i 应该让玩家感觉到游戏角色随着各种经历和经 验在成长。虽然迄今为止还没有哪款游戏在这一方面表现优异，大多数游戏都采 用同一种思路，通过将当前的形势与已经经历过的形势进行对比，来获得更高智 能水平的决策行为。随着游戏产业的日益发展和壮大，游戏硬件设备性能和计算 能力的不断提升，新型的a j 技术不断地在游戏中被尝试和改进，很多更为复杂地 机器学习技术将会被应用到游戏中去，并将极大提高游戏a j 的学习能力。 在目前已上市的计算机游戏中，已经应用了很多人工智能技术，包括有限状 电子科技大学硕士学位论文 态机、脚本方法、模糊逻辑、n p c 技术、群体行为的模拟、决策树、神经元网络 和遗传算法等。其中，有些技术已经比较成熟，有些技术当前正在流行，也有些 是游戏开发人员正在积极尝试利用的新方法。 1 3 2 游戏路径搜索研究现状 游戏路径搜索是游戏人工智能的基础和重要组成部分，是游戏中的n p c 所应 该具备的最基本的能力。同时游戏路径搜索也是一项非常具有挑战性的任务，这 来源于游戏场景的复杂性、场景的单元格数量的巨大性，以及对真实感的要求。 同时来源于对计算机计算资源和内存资源的限制。因此，游戏路径搜索成为了游 戏程序员一道必须逾越的关卡，长久以来，游戏程序员将各种各样的技术运用于 其中，获得了较好的解决效果。通常游戏路径搜索应该考虑使n p c 的运动达到满 足下面几个条件。 逼真：可能移动最重要的方面就是产生像人或者动物那样的n p c 。因为移动 是最常见的动作，所以需要特别注意增加其真实感。 高效：一个提供像运动那样重要且广泛使用的功能的系统需要在处理器执行 时间上非常节约。 可靠：n p c 在游戏进行中会遇到多种不同的情况。负责路径搜索的模块必须 保证在不同的关卡上不会出现任何错误。 这些不同的特点可能会互相冲突，使得人工智能导航系统变得更加难以开发。 在设计和实现过程中，会出现对某些要求不利，但是对另一些要求有利的事情。 所以，建立优先级是一个很好的办法。 游戏业界的标准是使用a 或i d a 算法【l 】，a 一般要快一些，而i d a 则比 a 要使用更少的内存。 分级寻径是一种可以有效的降低问题复杂性的解法，这种方法将地图分成一个 个的区域( 比如方块) ，而将一个方块的入口抽象成一个点。一种两级的寻径方法在 嘲中描述，这种分级方法在划分层次时需要领域相关的知识。 而h p a 0 t i e r a r c h i c , a lp a t h - f i n d i n ga + ) 1 6 1 不需要领域相关的知识。而且在局部层 面上，穿越每一个区域的距离是预先计算好并缓存下来的。因此可以减少运行时 的计算量。这个方法是自动的也不依赖于某一种具体的拓扑结构，这种技术在能 够适应环境的动态变化。这种算法比a 算法要快得多。 4 第一章绪论 在游戏路径搜索中有一种基于可见点的路径搜索技术，这种方法把地图的拓扑 结构抽象成一些点构成的一个图，这个图上的点代表了凸多边形形状的障碍物的 角。而两个能互相可见的点就用一条边连接起来。这种方法提供了高质量的解决 方案，它在障碍物相对较小的具有凸多边形的形状的时候尤其有用。而在障碍物 不是凸多边形的情况下，效率会降低。例如在一个有大片森林的地图中，其中包 含很多小的且数量众多又密集在一块的障碍物。运用可见点技术对这样的一个拓 扑结构建模会产生一个用短的边连接起来的具有很多顶点和边的图。因此，在这 样的一个图上找一条长路径是一件很费时的事情。这种技术还有一个缺点是它需 要程序或者是关卡设计人员的配合。 通常效率是游戏开发者所关心的最基本的问题。随着更好的硬件的使用使得更 加复杂的设计得以实现，移动应当变得更加可靠，以便于在没有意外发生的情况 下处理这些不同的情况。不一定是达到了最终的可靠性，实践又开始把注意力集 中到真实感上。例如通过a 计算的路径可能有一些急转弯，这时可以运用路径平 滑策略【2 】使路径变得好看一些。还有a 计算的路径可能会产生一个锯齿状的效 果。构造的路径从一个路径点到另一个路径点蜿蜒而行。这样的效果给玩家的映 像很差。因此必须采取一种方式使路径变得直一些，这时可以考虑采用视线确定 技术。 总的来说，3 d 游戏场景中的路径搜索是一个非常复杂的问题，通常情况下需 要混合多种解决方法并在实践中不断探索才能得到一个比较好的解决方案。 1 4 本文的工作及章节安排 1 4 1 论文的主要工作 论文第一章介绍了路径搜索的各方面的理论、知识，包括路径搜索的算法， 路经的平滑，路经点之间的平滑、转向，各种优化技术等。然后又介绍了与论文 相关的o g r e 图形引擎的一些基础知识。接下来在论文第三章结合3 d 环境下路径 搜索的需求和项目的需求，提出了一个三层的3 d 游戏场景中导航的解决方案，该 方案以导航网格技术来解决静态障碍物的处理。论文首先讨论并实现了在导航网 格上的寻径技术。接着又讨论并实现了怎样合并场景单元以及剔除场景中的障碍 物以构建出一个具有更少的寻径单元的导航网格的技术。在第四章论文对游戏场 5 电子科技大学硕士学位论文 景中动态障碍物提出了用导航行为来处理，论文针对原有的规避障碍物的导航行 为中对障碍物的几何形状抽象的缺陷，提出了根据障碍物的形状使用凸多面体来 表示的方法，并使用模糊逻辑来计算导航力，这样可以使n p c 在规避障碍物时表 现得更智能。然后又采用了导航行为中的路径跟随行为来控制游戏中的n p c 朝着 寻径算法计算好的路径点运动，最后将各种以上讨论并实现的各项技术融合起来， 在我们项目开发的引擎所提供的环境下实现了这个3 d 游戏场景中导航的解决方 案。 1 4 2 论文章节安排 论文共分为六章，分别对3 d 游戏场景中路径搜索所运用到的各项技术及相关 技术进行了介绍和探讨，并提出和实现了一个3 d 游戏场景中导航的解决方案。兵 体的章节安排如下： 第一章，介绍了研究的背景，课题的来源，概括性的介绍了游戏人工智能的 现状未来，以及游戏路径搜索的研究现状。 第二章，介绍了在游戏搜索中需要用到的算法一a 算法，并介绍了关于路 径搜索的优化的内容，包括速度优化和审美优化。然后介绍了o g r e 的基础知识， 包括o g r e 场景管理、o g r e 场景实体与结点、p l s m 。 第三章，这一章第一节结合项目需求和3 d 游戏场景中路径搜索的基本需要提 出了一个3 d 游戏场景中导航的整体解决方案。然后在分析了两种3 d 游戏场景中 路径搜索的技术之上，采用导航网格作为论文提出的方案的路径搜索技术，论文 详细的介绍了这种技术，并对其做了实现，本章最后讨论和实现了如何构造一个 导航网格的技术，其中包括如何剔除场景中的障碍物和合并小的场景单元以减少 路径搜索时需要遍历的单元的技术。 第四章，这一章针对动态障碍物的处理问题，在分析了各种动态障碍物的处 理的技术之上，提出了使用导航行为来解决动态障碍物的处理问题，并针对原有 的技术在对障碍物几何形状抽象上的缺陷，对其进行了改进，使其能更好的匹配 障碍物的几何特征。并且在决定导航力的方向时采用了模糊逻辑，以使得n - p c 在 规避障碍物的时候显得更为智能。然后又采用了导航行为中的路径跟随行为来控 制游戏中的n p c 朝着寻径算法计算好的路径点运动，这样可以使n p c 的运动显得 更为逼真。这一章最后在o g r e 下利用o p e n s t e e r 实现了路径跟随和规避障碍物的 行为。 6 第一章绪论 第五章，霹第三章提窭鹣熬体方案徽7 鬃俸静设计奄实现，该方察获游戏熬 场景开始，提取出几何信息，以此来构建一个导航网格，然后在此基础上进行路 径搜索，然后在利用导航行为米处理动态障碍物和使n p c 沿着寻径算法计算出来 戆黪经轰运动。零掌最嚣在我稍顼嚣嚣发熬孳l 擎下薅该秀案进行了功筑溅试窝效 率测试。 第六章，对众文做出系统众面的总结，并对今后需鼷进一步深入研究的方向 傲了震望。 7 电子科技大学硕士学位论文 第= 鬻游戏路径搜索基础及o g r e 简介 路径搜索是游戏中一个很基础也很关键的部分，若是游戏巾的n p c 在游戏世 界中显得逡动起来显得日 常的盲目，不知道该朝哪里移动，这无疑会给玩家簸下 擐不好豹印象。两虽遮纛是令缀有援战燕熬难题。因为游戏路缀援索c p u 谤葵受 担很重的馁务，并且存储路径搜索稿关信患又需癸较大静存谐空阅。丽娥予一个 n p c 在游戏世界中比较衡能的移动能力需要很多的技巧。这一章将介绍游戏路径 搜索中经常嚣要用到的长种基本的理论和技术。除此之外由予论文是以我们项霹 并发静弓l 攀为平台静，褥我襄j 顼嚣掰实现懿雩| 擎爨在o g r e 蒸旗上秀发静，掰戮 本章还介绍了0 g r e 相关知识。 2 。1舻算法简介 2 1 1 启发式搜索 a 术算法在人工智畿审是一秽典型的启发式搜索冀法，为了谈清楚胁算法，先 分绥一下铤谓启发式算法。在说它之藏先提提妖淼空褥搜索。状态空耀薤索，就 是将问题求解过程表现为从初始状卷刹目标状态寻找这个路径的过程。通俗点说， 就是在解一个问题时，找到一条解题的过程可以从求解的开始到问题的结果。由 予求解翘鬏夔过程孛分技有缀多，主要是求解过稷审求解条势翳不骥定、苓宠备 性造成的，使得求解的路径很多这就构成了一个瀚，这个图就怒状态空间。闯题 的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的越程 就是状态空间搜索。常熙的状态空阉援索有深度优先和广度优毙。广度优先楚献 初始状态一瑶一层淘下撬，壹羁我翻秘标为壹。深度优先是按照一定的颓穿翁查 找完一个分技，再查找嬲一个分枝，以至找到目标为止。这两种算法在数据结构 书中都有描述，可以参餐这些书得到照详细的解释。前面说的广度和深度优先搜 索寿一令缀大夔缺錾裁楚毽髑罄是农一令绘定戆状态空闼孛穷举。这在妖态空阕 不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不 可取了。像的效率实在太低，甚至不可完成。在这里就要用到扁发式搜索了。启 发式搜索裁是在状态空朗孛的搜索瓣每一个搜索黪彼霉遴行评传，褥到最好瓣霞 第二章游戏路径搜索蒸础及o g r e 简介 譬，褥获这个霞鬻送行援索誊翻嚣标。这样霹瑷省珞大豢无谣豹路径羧索，挺离 了效率。在启发斌搜索中，对位鼍的估价熙十分重要的。采用了不同的估价可以 有不同的效果。先看看估价是如何表示的。肩发中的估价是用估价函数表示的， 懿： ( 2 - 1 ) 冀孛f ( 砖是络点r l 戆嫠徐懑数，g 砖安程状态空闽巾麸秘始络熹捌1 3 结赢豹 实际代价，h ( n ) 怒从n 到匿标缩点最佳路径盼估计代价。在这里主要怒h ( n ) 体现 了搜索的启发信恩，因为g ( n ) 是已知的。如果说详细点，g ( n ) 代表了搜索的广度 豹侥强趋势。但爨当h ( 园 g ( n ) 粒，可以销略g ( n ) ，这榉可以提高效攀。 2 1 2a 宰算法介绍 a 算法要在熊踅孛魏嚣点潮我出一条臻经。麴暴存农望少一条爨缀，在套秘 不同的路径搜索弊法中，a + 将找到最短路径，而且相比乏下算法速度侥一这也 是a 算法与众水同的原因。下面将提出算法的基础，也是各种不同的a 算法的 基础。 a 算法是耱鼙控算法，鼯算法本身势苓会言嚣匏搜索路径，嚣楚倍诗一个 最俄的考察方向，有时也回溯尝试其余方向。所以，a + 算法灵活多变，不拘一格。 a s 通过创建与位置相对成的结点在地图移动，这些络点是用来记录搜索进度 懿。狳了缳持在魏霆孛戆霞爨，每一令续淼还骞三令重瑟瓣藩毪，逶鬻鹤镦g 和h 。以下给出遂三者详尽的猕述： g 是从起始缡点到该结点的代价，虽然从起始结点到该结点的位鬣肖很多不同 的路径，毽该绩焱仅代表一条纂一路径。 h 是获该终点列目标及】鬟赢倍计健价，这墼h 代表瘸发式酶僖徐穰，意慈是受 训的猜测，因为并不知道实际代价。 f 是g 和h 的和。f 代表对这条经过该结点的路径最好的猜测和储计，其中f 豹悠越，l 、，囊谈兔这条臻径越磐。 而其中g 的大小是可以究全计算出来的，即来到当前结点所需的代价。因为 已知来到当前结点的所有结点，所以g 的假可以精确被确定，然而h 则是一个完 全不霜瓣袤疆，魏淹劳不知道飙该结点刭嚣标结点还有多远，这对被遗进行猜测。 9 电子科技大学硕士学位论文 当猜褥越撩，那么f 懿傻戴越接近翼嶷篷，嚣a 瓣速度逛裁越莰，能够只费少诲 的工夫就找到目标。 另外，a 女保持着两个表：o p e n 和c l o s e d 表。 e n 表由来考察的结点缀成， 丽c l o s e d 标由已考察的结点组成。当算法已经检焱过与某个结点耀连的所有缩点， 计算毽它销黪f ，g 秘h 麓僮，并怒宅稻藏入o p e n 表，戳待考察，粼称这今终赢 为“己考察的”。 因为没有独特的结点，所以o p 伽表和c l o s e d 液是必须的。例如，如果从( o ， 8 ) 开始移麓裂( o ，1 ) ，那么霉移嚣( o ，o ) 氇怒无霹攘鬃嚣蠢效戆。因鼗必矮 弱确知道哪魑结点已被考察和剖建) 这就是o p e n 和c l o s e d 寝的作用。 路径搜索时这个区分结点的过程变得非常重翳，因为存在很多不同的路径导 向某个特定结点，例如一条路径一份为二但不久之后又再度滋会，那么算法本身 盛矮疆定该路径走了郡条分支。 此算法的伪码描述如下； 1 )令p = 起始结点。 2 ) 恕g 彝h 鹣蓬赋绘p 。 3 ) 将p 加入o p e n 表。此苜寸p 是o p e n 表中惟一的绪点。 4 ) 令b = o p e n 寝中的最佳结点( 最佳的意思是该结点的f 值最小) 。 ( 1 ) 如果b 是目标结点，则退出。戴辩已找到一条鼹径。 ( 2 ) 翔栗。嘲秀空，樊| j 遇出。魏辩没有找到路径。 5 )令c 等于一个与b 相连的商效结点。 ( 1 ) 把f g 和h 的值赋绘c ； ( 2 ) 检查c 憝盔秭鼹袭爨还是在c l o s e d 表垦。 a 、如聚在c 1 0 s c x l 袭中，赠检查新路径是否比蹶先更好( f 值小) ， 著鼹则采用新路径。 b 、溪赠把c 添热入o p e n 表。 对所有b 静青效子孙结点蕊复第5 ) 步。 5 )重复第4 ) 步。 2 。 。3 冀法示镶 下面通过一个例子来说明这个算法，如图2 - 1 所示的地图，中心点是初始位 誊s ，旁边的灰点是终赢位雹e ，把f g 和h 静值赋绘起始结焦，其孛熬g 傻怒0 ， l o 第二章游戏路径搜索基础及o g r e 简介 因为到达第一个结点并不用任何代价；h 的值根据不同的应用有不同的算法，但是 在基于地图的问题中，利用水平和垂直位置的差距结合的得到的效果很好，设 ( d x ，d y ) 是终点，( s x s y ) 是起点： h=ldxsx+ldy-syl(2-2) 在这个问题里，( 8 x s y ) 等于( 2 力，( d x ，d x ) 等于( 1 ，o ) ，所以h 的值计算如下： h = l l - 2 1 + 0 - 2 1 = 3 ( 2 - 3 ) 因为h 等于3 而g 等于0 ，那么这两项的和f 就等于3 。所有的子孙结点都是有 效的( 所有把连通的网格均可达) 而且对o p e n 表而言都是待添加结点，所以子孙 结点的产生十分简单。而g 是由到达父结点的代价0 加上在地图上移动一格的代 价，因此子孙结点的g 值都是1 。每个子孙结点的h 值都不相同，但明显可以看出 ( 1 ，1 ) 是最佳的子孙结点，因为它最接近目标结点，因此最佳的子孙结点( 1 ，1 ) 将在下 一步被考察。 结点( 1 ，1 ) 有4 个有效子孙结点：( 1 ，o ) 、( 1 ，2 ) 、( 2 ，1 ) 、( 2 ，2 ) 。现在需要确定哪些 结点在o p e n 表或c l o s e d 表中，哪些是新的结点。结点( 2 ，2 ) 在c l o s e d 表中，因为 它是初始的起点，所以它的子孙结点都已经被放入o p e n 表。结点( 1 ，2 ) 和( 2 ，1 ) 在 o p e n 表中，因为它们的子孙还没有被考察，结点( 1 ，o ) 是一个新的结点。 对结点赋完f g 和h 的值后，显然( 1 ，o ) 是最佳的结点，而在a t 算法的下一个 循环，发现目标结点就是( 1 ，o ) 。 2 2 分级的路径搜索 f 之 o1234 图2 1a 算法示例图 分级的路径搜索可以减少计算资源，特别是在游戏场景很大的情况下或者场 电子科技大学硕士学位论文 景很复杂的情况下。它和人类在环境中的运动很相似。这种方法可以用在游戏路 径搜索上，这种方法需要两个图。一个粗略的，一个详尽的( 可以根据需要设置 多级) 。如图2 2 所示，左边是详细的，右边是粗略图。这样的话，在游戏中，可 以将游戏世界分区。那么首先要有一个粗略的图表示各个区间的联系，另外还要 有一个图表示各个区中的具体的情况。当一个n p c 向从它当前的位置走到另一个 地方的话，判断它的出发点和目的点各位于哪个区中，再用那个粗略的图来计算 出一条路径，很明显，这条路径上的路径点的个数是很少的( 当然也有可能出现 出发点和目的地都在同一个分区中的情况，这样就需要做这一步计算了) 。然后再 在各个分区中计算出一条精细的路径。两个图的实现方法是分层路径搜索的典型 实现方法。但是如果有需要的话，用更多的层也是可以的。 2 。3 斛审美优化 2 3 1 路径平滑 图2 - 2分级搜索地图 通过a $ 计算的路径通常因为有过多的急转弯而显得漏洞百出。即使你想方设 法将路径变得更直，急转弯依然会使你的角色看上去就像机器人。对急转弯应用 转动减幅技术，可以稍微掩饰一下，但是在每个锐角转角处将摆动得很厉害。 计算机图形学中有一个现成的算法可以使路径( 空间中一系列的点) 变得平滑， 一个简单的c a t m u l l r o m 样条就能够完成任务。因为它产生了一条能够经过原始 路径中所有控制点的曲线( 不像b e z i e r 曲线，虽然比较平滑但是不能经过所有的控 制点) 。显然，直接经过所有点比较好，因为a 吒人为它们是通常的并且避免了障碍 物的妨碍。 第二章游戏路径搜索基础及o g r e 简介 如何从实际输入的点序列获得一个更平滑的点序列昵? c a t m u l l - r o m 公式要 求四个输入点，然后给出一条位于第2 点和第3 点之间的光滑曲线。 如图2 3 所示：为了得到第1 个输入点和第2 个输入点之间的点，你可以为 这个函数输入第1 个点两次，接着输入第2 个点和第3 点。为了获得第3 点和第4 点之间的点，你可以先输入第2 点和第3 点，然后输入第4 点两次。每次使用 c a t m u l l - r o m 公式时，它将在第2 个点和第3 个输入点间近似l 膈的地方给出一个 点。这里u 是自己传递的一个数。公式如下： o u t p u t _ p o i n t = p o i n t _ l + ( 0 5 + u u + u + u + u - o 5 f u ) + p o i m _ 2 + ( 1 5 p u + u + - 2 5 f * u * u + 1 o d + p o i n t ，+ ( o 5 f * u * u * u - o 5 f * u * u ) ( 2 4 ) 图中较大的点为输入点，较小的为样条输出点 图2 - 3 路径平滑效果图 2 3 2 导航点问的真实转向 在游戏世界中，n p c 总是以智能的方式进行漫游，例如n p c 不会被一棵树卡住， 会选择一条最近的路径到达目的地，这些行为所涉及的核心技术问题是路径搜索。 路径搜索技术是实现游戏a i 的基础，现在最通用也是最有效的路径搜索算法是a 宰 算法，然而，n p c 如果完全按照胁计算出来的路径移动，往往在遇到导航点时， 会生硬地转向一个新的方向，走出完全不真实的路线。即使利用胁优化技术，将 路径变得更直，也会使n p c 在转弯处表现得像个机器人，严重影响整个游戏的质 量。 目前，有多种算法来解决这个问题。一种方法是在急转弯处应用转动减幅的技 电子科技大学硕士学位论文 术，首先计算出n p c 转弯的角速率，然后在每一帧转一个固定的角度。这种方法 可以使n p c 的运动比较真实，但是效率非常低，同时在每个锐角转角处n p c 将摆 动得很厉害，无法达到审美优化的效果。 还有一种方法是将n p c 的转向半径考虑进去，用几何方法计算出一条从当前 位置到目标位置的曲线路径。这种方法的主要思想是：如果n p c 在某一个固定位 置和方向具有一个固定的转向半径，则到达目的地只有一个或两个最优路径。 ( 1 ) n p c 向右转，沿顺时针的圆弧，直到朝向目标方向为止；( 2 ) n p c 向左转，沿 逆时针的圆弧，直到朝向目标方向为止，然后从那里沿直线运行到达目标位置。 通过比较两种情况下的路径长度，选择一条最短路径运行。这种方法可以使n p c 在拐弯处的运动具有较高的真实感，走出一条符合实际的路线，但同时带来一个 问题是n p c 弯曲的路径与墙或障碍物会发生重叠。为了减少这种现象，可以使用 一些基本的预测分析，在每一个导航点让n p c 的朝向更合理。基本概念是给游戏 中的n p c 一点智能，与其盲目地沿着每个导航点而转向下一个，不如在它接近导 航点时就让它知道必须转向哪条路。这就要求n p c 在到达目的地时，要朝向一个 固定的方向。 2 4 速度优化 胁算法可能是游戏中运用得最广泛的路径算法，但却是受到经典的“时空限 制”。理想情况下a 木可以使用大量的内存和长的运行时间。而实际上存在没有任何 可行路径时却要寻找路径的情况，即胁最尴尬的场合，这也是很多游戏中的普遍 问题。大部分胁的文章涉及到如何提升启发式估计的效果，或者如何高效的存储 及搜索0 p e n 表和c l o s e d 表。而本节主要考察那些约束胁的方法，如何让它走得 更快，让它对地图状态的改变响应更灵敏。 这样的胁的约束采用了人工压缩搜索空间、局部解法、或者算法短路等形式。 对于每个约束都会讨论哪一个是最好的。 2 4 1 迭代优化 迭代优化是适用于a + 的一个强大优化算法，这个方法在搜索算法上强加了一 个人为的界限，在主循环迭代中从一个小的界限开始，然后趋向路径长度或者内 存使用的最大值。如果一个a 没有成功的找到路径，迭代深化将在随后的调用中 逐渐放宽界限，直到搜索成功或者得到取值范围的端点。对于大部分的调用，这 第二章游戏路径搜索基础及o g r e 简介 个方法占用较少的内存，直到人为的界限导致较少的结点被考察。迭代深化也加 快了路径检测的速度，提高了在路径暂被其他行动者阻断时的执行性能。 迭代深化算法简单的附上一个表示当前调用的界限参数，这样就可以在a + 中 运行了，这个界限参数可以是a + 主循环的迭代次数，也可以使内存的最大使用量， 或者路径的允许最大长度。如果a + 初始调用没有找到路径，在后续的调用中可以 稍微放宽这个界限。因为调用是从一个小的界限开始，迭代深化强迫a 在失败调 用的序列中开始的几次调用时使用较少的内存，也就是说这些调用会比通常时候 更快的达到失败条件。 当存在一条几乎直线的路径时，例如之间有一棵树的路径，一个小的a + 界限 调用也可能找到路径。搜索算法只要在树两旁尝试少数几个位置就能找到正确的 路径，为了让界限仍保持很小，a 会避开使用大的内存空间存储结点。 这个优化算法的真正好处是a 的后续调用并不需要立即执行，如果初始调用 失败了，执行下一个调用之前可以稍微延迟一下。这个延迟让其他游戏函数有执 行的机会，让游戏的表现性能变得流畅，这额外的时间也允许任何可移动的障碍 物一个离开的机会，否则这将是游戏中普遍的路径失败原因。 迭代深化并不是每次都能成功。当没有可行路径时，迭代深化实际上会增加 路径搜索的时间。但是，任何游戏里如有改变地形就能令路径不断切换通行的阻 塞状态的情况，这个算法还是有用的。这些改变地形的障碍物可以是像生物那样 的可移动物体，在他们移动过程中暂时的阻断路径。还可以是一些不可移动的物 体，他们改变通行阻塞的状态，比如一扇门的开关，偶尔会允许行动者通过。在 这种情况下，迭代深化有助于a 避免花大量的时间寻找暂时阻塞的路径。 。 、 图2 _ 4 迭代深化示意图 1 5 电子科技大学硕士学位论文 2 4 2 立即把阻塞的结点扔到c l o s e d 表 当删除o p e n 表上开销最小的结点，并考察它的后续者时，它的一个子结点可 能是不可通行的。比如子结点可以是被阻塞得，不允许任何通过的动作。先不管 原因是什么，可以把子结点立即加入c l o s e d 表。这个操作防止高( 其实是无穷的) 代价结点加入o p e n 表。另外。按照o p e n 表的存储方式，这个操作可以保持一个 较小的o p e n 表，加快从o p e n 表的后续删除工作。 这个优化看上去是显而易见的，而很多a 程序适用一个简单的方程来产生某 个特定结点的所有后续者，不只是那些未阻塞的结点。比如说返回了地图某一格8 个相邻的结点，按照代价计算函数把被阻塞得结点赋值为高代价，使他们不会被 o p e n 表的删除函数选中。在一个可能有很多被阻塞结点的搜索空间里，这样会导 致很多阻塞结点被插到o p e n 表里。按照o p e n 表的实现程序，大的列表需要更多 的工作，而且在列表的插入和后续删除都要花费额外的时间。 2 4 3 同时封锁多条路径 关于路径搜索还有另一方面，就是游戏中路径如何被用可以用来约束a + 寻找 它们的方式。比如在很多游戏中，衡量代价用的是路径总长度，而a 寻找的是最 短路径。如果游戏不能使用大于x 步的路径( 由于内存或动画的限制) ，那么a t 可以忽略t o t a l c o s t 超过x 的任何结点n 。因此启发式估计的c o s t t o g o a l 常常被低 估( 老保证一个最优路径) ，任何通过结点n 的路径都被限定要比x 步长。因此， a 叼；用考察就把这个结点加入c l o s e d 表。 接着，在下一个从o p e n 表弹出的结点得到超过x 的t o t a l c o