（计算机应用技术专业论文）游戏地图寻径及地图编辑器的研究.pdf

摘要 | ! _ ，i ，i 一i i i i ii 量 摘要 长期以来，搜索算法一直是人工智能研究的一个活跃方向。在5 0 多年的研 究中，搜索算法不断发展，形成了成熟的理论体系。在搜索算法的各种应用中， 游戏地图寻径问题一直是研究的热点。 首先，本文从人工智能的角度扼要介绍了目前在游戏地图寻径中使用最多 的启发式搜索算法- a 木算法的思想、实用性及实现方法，以及与地图寻径紧密 相关的游戏地图制作工具一地图编辑器的基本概念和相关术语。 其次，本文在详细分析了地图编辑器实用性的基础上，对其进行了优化设 计，提出把地图编辑器从功能上分为编辑地图和编辑资源两个部分来实现及对 地图中的孤岛区域进行预处理的思想。 接着，本文深入研究了传统a 幸算法在游戏地图寻径中影响速度的原因，并 结合优化后的地图编辑器，从节点的数据结构、开启列表的遍历算法、路径的 平滑处理三个方面对算法进行了改进，设计并实现了一种基于a 的智能化的地 图寻径新算法，而且对新算法进行了理论分析。 最后，本文结合项目的具体情况，对改进前后的算法进行了对比分析。对 比结果表明，基于a 宰地图寻径的新算法大大提高了地图寻径的速度，切实、可 行。 关键词：a 水算法；评价函数；地图编辑器 a b s t r a c t f o ral o n gt i m e ，s e a r c ha l g o r i t h mh a sb e e nav e r yi m p o r t a n tf i e l do fa r t i f i c i a l i n t e l l i g e n c e i nm o r et h a n5 0y e a r sr e s e a r c h ，s e a r c ha l g o r i t h mh a sd e v e l o p e di n t o a m a t u r et h e o r ys y s t e m i na l lt h ea p p l i c a t i o n so fs e a r c ha l g o r i t h m ，p e o p l ea l w a y sf o c u s o nt h em a pp a t h f i n d i n g f i r s t l y ，t h i sp a p e ri n t r o d u c e st h em o s tp o p u l a rm e t h o do fs e a r c hp r o c e s so ft h e m a pp a t h f i n d i n ga l g o r i t h m - - t h et h i n k i n go fa 奉a l g o r i t h ma n d i t sc h a r a c t e r i s t i ca n d m e t h o do fr e a l i z a t i o n ，a n dt h ec o m m o nc o n c e p t sa n dr e l a t i o n a lt e r m i n o l o g yo ft h e t o o lo fd r a w i n gg a m em a p - - - - m a pe d i t i n gp r o g r a m m e r , t h a ti si n s e p a r a b l ew i t ht h e m a pp a t h - f i n d i n g s e c o n d l y ，t h i sp a p e rm a k e ss o m ei m p r o v e m e n t st ot h ee d i t i n gp r o g r a m m e ro f m a po nt h eb a s eo fi sa n a l y z i n gi t a n dp u r p o s et os o m en e wt h i n k i n g o n ei s t h a t d u r i n ge d i t i n gm a p ，t h ep r o g r a m m e r i sd i v i d e di n t ot w of u n c t i o n s - - - m a pe d i t i n ga n d r e s o u r c ee d i t i n g ；t h eo t h e ri sp r e c o n d i t i o n e dt h ei s o l a t ea r e ai nt h eg a m e sm a p t h e n ，t h i sp a p e r s t u d i e st h er e a s o n st h a tm a k et h el o wr a t ei ng a m e p a t h - f i n d i n g ，b yu s i n ga a l g o r i t h m ，a n d i tm a k e sa ni m p r o v e m e n ti nn o d e d a t as t r u c t u r e ，t h em a i n t e n a n c eo fo p e n sq u e u ea n ds m o o t h i n gt h ep a t ho nt h eb a s ei s o fa a l g o r i t h ma c c o r d i n gt ot h em a ps t r u c t u r e ，a n dr e a l i z e sak i n do fm a p p a t h f i n d i n gb a s e do na 牛a l g o r i t h m t h en e wa l g o r i t h mw a sa n a l y z e do nt h et h e o r y l e v e l f i n a l l y ，a c c o r d i n gt o t h er e a l i s t i cp r o j e c t ，t a k et h et e s t i n gb e t w e e nt h en e w a l g o r i t h ma n dt h eo l d t h er e s u l ts h o w st h a tt h en e wm a pp a t h f i n d i n ga l g o r i t h m b a s e do na | ia l g o r i t h mi n c r e a s e st h er a t eo fm a pp a t h - f i n d i n g ，a n dt h i sa l g o r i t h mi s p r a c t i c a l k e yw o r d s ：a a l g o r i t h m ；e v a l u a t i o nf u n c t i o n ；m a pe d i t i n gp r o g r a m m e r i l - 论文原创性声明 本人声明，所呈交的学位论文系在导师指导下本人独立完成的研究成果。 文中依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法 律意义上已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申 请的论文或成果。 本人如违反上述声明，愿意承担以下责任和后果： 1 交回学校授予的学位证书； 2 学校可在相关媒体上对作者本人的行为进行通报； 3 本人按照学校规定的方式，对因不当取得学位给学校造成的名誉损害， 进行公开道歉； 4 本人负责因论文成果不实产生的法律纠纷。 论文作者签名： 劳炙寿、 论文知识产权权属声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属东北电 力大学。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权 利。本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成果时， 署名单位仍然为东北电力大学。 论文作者签名： 导师签名： 日期：兰：! 年旦月丑日 日期：2 虹年上一月巫日 第1 章绪 论 暑量曼鼍皇寰鲁量曼量量皇皇曼曼曼曼曼曼皇曼舅量量量曼量曼皇皇量曼曼量曼量量曼曼皇曼量量曼皇曼量曼曼曼曼鼍i i 亏；一一曼i i 第1 章绪论 1 1 课题背景 长期以来，搜索算法一直是人工智能研究的一个活跃方向。在搜索算法的 各种应用中，游戏地图寻径问题一直是人们关注的热点1 1 j 。游戏地图寻径的目的 是设法从地图中寻找一条从起点( 筋到目标点( 句的最优通路，需要解决的最基 本问题是如何避开障碍物。国内外针对地图寻径算法有很多种，常用的算法有 状态空间搜索和启发式搜索 2 j 。在游戏中，地图寻径与游戏地图紧密相关，游戏 地图的制作通过地图编辑器来实现。一个好的地图编辑器不但决定着一款游戏 的好坏，更与地图寻径的速度密不可分。在地图编辑器中，地图是由很多被称 为瓷砖的小图素拼接而成。游戏地图的文件结构、瓷砖是否可通以及目标点所 在的瓷砖是否可通等是地图寻径必须考虑的多方面因素。简单地说，从计算碰 撞、物理系统和物体的相对位置，到接受玩家的输入，以及声音的输出等等功 能都是游戏需要完美处理的事情，需要采取相关手段把游戏中的所有元素捆绑 在一起，在后台指挥它们有序地工作。因此，无论是2 d 游戏还是3 d 游戏，无 论是角色扮演游戏、即时策略游戏、冒险解谜游戏或是动作射击游戏，哪怕是 一个只有l 兆的小游戏，都有耗费开发者大量的心血。经过不断的进化，如今 的游戏从建模、动画到光影、粒子特效，从物理系统、碰撞检测到文件管理、 网络特性，专业的编辑工具和插件、卡设计师、建模师、动画师几乎涵盖了开 发过程中的所有重要环节。但因为游戏的开发相当耗时耗财，所以基于节约成 本、缩短周期和降低风险这三方面的考虑，越来越多的开发者倾向于使用第三 方的现成引擎制作自己的游戏。 国产游戏产品研发一直比较落后，而游戏的研发前期投入高、风险大则更 加无人问津。所以相比国外十数年的游戏发展历史，国内的可以说尚处于幼年 阶段。 东北电力大学硕士学位论丈 m i 近几年，虽然国内的游戏有了一定的发展，但相对于国外来说，差距还是 非常大! 尤其体现在对先进技术的运用上以及市场推广上。由于中国游戏开发 的落后现状，所以，不少计划进入自主游戏研发领域的中国公司纷纷做出了从 国外购买游戏的决策，这其中不乏u n r e a l 等价格昂贵的知名大作。然而，购买 国外游戏的硬伤同时也令本土厂家痛苦不堪。第一：成本昂贵，价格是大多数 中小型游戏开发商无法承受之重；第二：国外厂商对国内市场重视程度不够， 很难保证良好的售后服务：第三：人员的沟通不便，出现技术问题不能得到及 时的解决。种种现象表明国内游戏的发展之路还任重而道远。 1 1 1 国内外发展状况 国外的网络游戏主要分为两大类。一方面，以韩国为主的东南亚开发的游 戏，其特点是以光纤靓丽的画面( 符合东方人的审美观) ，紧张刺激的p k 系统。 来吸引玩家的眼球。但是长期玩以后，其游戏性差的弊端：模式单一，一味打 怪升级等都显现出来了。另一方面，以欧美游戏为主，其特点是充分照顾玩家 的胃口，多种多样的游戏模式，让玩家充分享受游戏的乐趣性。他强调的是游 戏的过程，这和韩国游戏有本质的区别，但他的图画风格更适合欧美人的审美 观，对于中国人不是很能接受( 特别是任务的刻画) ，还有就是他到中国文字 的汉化问题，以及文化差异，高额的游戏费用。一直是阻碍他在中国发展的一 些原因。 目前，在游戏研发、运营、管理等诸方面，与日韩、欧美等国相比，我国 还存在较大差距。我国的游戏大多是引进的韩国、日本的游戏引擎，而国外游 戏引擎的核心代码是不公开的，因此研究游戏中的关键技术是次有意义的尝试， 现在一些高校和研究所加入了研究游戏的行列，这无疑将对我国游戏引擎方面 的进步起到积极的作用。国内游戏软件尴尬的现状及国外游戏软件成果的事实 无不表明，没有游戏通用引擎，就无法从根本上赶超国际水平，就无法抵抗大 量国外游戏地冲击，更无法占领网络经济下大众娱乐的精神文明阵地。因此， 研制中国自己的游戏通用引擎是一项需求牵引力地发展方向，具有重大的战略 意义和明显的现实意义。 第1 章绪论 量曼曼量曼量量舅曼曼寡曼曼曼量曼鼍曼舅皇皇曼曼曼曼鲁曼寡曼舅曼曼曼曼量曼量曼皇曼皇曼皇量曼量曼i m 一一一i 目前，国内外游戏地图寻径算法主要有a 木算法，单个物体寻径算法，分等 级寻路算法和路径再计算算法等，它们各有优缺点。 a 术算法是当前国内外在游戏地图寻径中使用最多、最先进的算法p j 。它是一 种动态规划的启发式搜索算法，以评价函数作为搜索约束条件，通过不断逼近 目的节点来寻找最优路径。a 木算法在比较简单的地图上，寻径速度非常快，能 很快找到最短路径( 确切说是时间代价最小路径) ，而且可以很方便地控制搜索规 模以防止程序堵塞；但是在地图很大的情况下，标准的a 木算法的速度会明显变 慢，同时a 木算法搜索每个节点周围的八个节点，有很大可能性会返回一条不可 能的路径，并且标准的a 木算法所提供的寻找有效路径的方法在现实情况下经常 发生失败，很难实现游戏移动的实时性。 单个物体寻径算法是从起点到终点拉一条直线a ，沿着直线a 朝终点行进， 一遇到障碍物便按顺时针方向绕着障碍物行走，直至碰到直线a ，重复上述步骤， 便一定能到达目的地。该算法计算出来的路径并不是最短，但速度很快。 分等级寻路算法是把到达目标点的路径分成若干个中间点，每个中间点可 以作为一个子目标点，但这种方法存在一种可能性，就是中间点处在一个不可 能到达的区域，如果把这种中间点作为子目标点，就会导致不能找到一条有效 的路径。 路径再计算算法是先用a 牢算法搜索一遍，沿着计算好的路径寻路，确定每 步从一个关键点到下一个关键点都是有效，如果发现碰撞，就标志这一步无效， 然后重新用a 木算法再搜索一遍。为了做到这个，需要对每个图片元素存储一个 字节，每一位对应当前图片元素的周围八个相邻的图片元素，表示这个相邻图 片元素是否可以通过，然后用舻算法使得在确认下一步之前都要检查这一步是 否有效。这个方法的主要问题是如果淘汰路径中的某步，那么其它有效的从不 同方向通向这个图片元素的路径可能会无法找到。同样，在最坏的情况下，这 个方法可能需要重新计算这条路径多次。 地图编辑器按功能可以分为两部分：编辑地图和编辑资源。编辑地图主要 包括铺设地表，放置物体，设置地图上地表的属性，设置地图上物体的属性等。 编辑地图的所有操作都是围绕着上面这些功能而展开的；编辑资源包括编辑地 表元素，编辑物体元素及其属性，编辑地表之间的过渡关系。由于资源是独立 东北电力大学硕士学位论文 ! ! i ，一 i m 于地图的，可以单独编辑，也可以重复使用，不同的地图可以使用相同的资源 文件。目前地图编辑器没有对地图中的孤岛区域进行预处理，当寻找通往孤岛 区域的路径时，它会搜索整个地图中所有节点，这会浪费大量的c p u 时间。 总之，地图寻径算法和地图编辑器在国内外研究中仍然是一个热点问题， 没有一个完美的解决方案，而本文的研究对此作出了有益的探索。 1 1 2 地图寻径和地图编辑器的发展预测 在5 0 多年的研究中，地图寻径算法和地图编辑器不断发展，已形成了成熟 的理论体系【4 】。在技术上，地图寻径算法需要考虑许多方面的知识，如即时战略 游戏中实时路径的计算，第一人称视角变换，碰撞检测技术等。在实际的即时 战略游戏中，经常是一群坦克在一个动态的地图上纵横驰骋，不同的坦克在行 走过程中相遇时互为障碍物，而且是可移动的障碍物，这就需要在编辑地图时， 对地图中的孤岛区域和障碍物提供强大的处理功能。最直观的解决办法是预先 为每一个行走物体分配一个优先级，当碰到可移动的障碍物，立刻重新计算行 走路径，该方法的缺点是重复计算路径，耗时太多。其实，当某个物体碰撞到 一个处于运动状态的可移动障碍物时，可以先等待一段时间，接着若发现可移 动障碍物已离开，就可以按原来的行走路径继续前进，从而节省了重复计算路 径的时间；反之，若发现可移动障碍物仍在原地，就比较两者的优先级，优先 级较低则继续等待，优先级高者立刻重新计算行走路径避开可移动的障碍物。 显然，运用该方法可以减少很多重复计算，加快了执行速度。 1 2 本文所做的工作 1 2 1 课题来源及意义 随着网络技术和软件技术的飞速发展，特别是i n t e r n e t 和i n t r a n e t 技术的 发展以及人们生活水平的提高，使得游戏在全球出现了前所未有的高潮。而在 网络游戏中，游戏地图和地图寻径已经成为游戏中的核心组成部分，也是人们 研究的热点问题之一。作者参加了吉林省电业局游戏项目的开发，本文的一部 第1 章绪论 !,p,el i i , i l l ! 分内容直接来自于此项目。在游戏中，通常精灵按照某种指定方式从起点移动 到目标点，这就要求程序必须能够找到一条从起点( 局到目标点( 功的最佳路径， 这条路径应该是绕过障碍物并且是到达目标点的最短路径，这类问题通常用人 工智能的搜索算法来解决，人工智能的搜索算法通常分为盲目搜索和启发式搜 索。 盲目搜索是传统的搜索技术，典型的盲目搜索方法包括深度优先搜索、宽 度优先搜索( 亦称广度优先搜索) 和等代价搜索等。在应用盲目搜索进行求解过程 中，一般是盲目地穷举，即不利用问题的有关信息，而根据事先确定好的某种 固定的搜索方法进行搜索。盲目搜索的效率很低，一般只适用于求解比较简单 的问题，对于复杂的问题，一般要占用很多的计算空间与时间，这种结果是组 合爆炸的一种表现形式。 启发式搜索是把求解问题领域的具体知识加进搜索算法中，控制搜索过程， 以提高算法效率的搜索方法。启发式搜索有很多种算法：局部择优搜索法、最 好优先搜索法和舻算法等。这些算法都使用了评价函数，只是在具体的选取最 佳搜索节点时策略不同。像局部择优搜索法，就是在搜索的过程中选取最佳节 点后舍弃其它的兄弟节点和父亲节点，而一直搜索下去。这种搜索的不足之处 是由于舍弃了其它的节点，可能把最好的节点舍弃了，因为求解的最佳节点只 是在该阶段的最佳并不一定是全局的最佳。最优搜索算法在搜索过程中没有舍 弃节点( 除非该节点是死节点) ，在每一步的估价中都把当前节点和以前节点的估 价值比较得到一个最佳的节点，这样可以有效的防止最佳节点丢失，但由于保 存节点的数目过多，需要较大的存储空间。a 术算法是以评价函数作为搜索约束 条件，由该函数可获得各点的代价，求解出状态空间搜索的最短路径，但在地 图很大的情况下，标准的a 木算法的速度会明显变慢，很难实现网络游戏移动的 实时性。 显而易见，上述搜索技术都有不足之处。因此，本文研究就是为了解决长 期以来一直未能有效解决的地图寻径问题，旨在通过分析地图文件结构，构造 地图文件和对a 木算法进行加速、平滑处理等改进，实现智能化的地图寻径。改 进后的a 木算法，将对地图寻径问题的解决方案具有非常实际的价值。 东北电力大学硕士学位论文 1 2 2 本文所做的工作 本文首先扼要地介绍了启发式搜索技术和地图编辑器的相关知识，接着 详细分析研究了启发式搜索技术中的a 木算法和地图编辑器，重点实现了地图文 件的编辑、生成和地图寻径算法的优化；最后结合具体项目对改进后的寻路算 法进行了进一步优化，设计并实现了智能化的地图寻径。地图编辑器和如何实 现智能化的地图寻径是本文的研究技术难点。课题主要研究内容包括： 1 对各种经典的搜索算法进行分析归纳，特别是通过对节点结构的优化、开 启列表和关闭列表遍历算法的改进，提高a 术算法的寻径速度。 2 引入平滑算法对a 算法找到后的路径进行平滑处理。 3 考虑到地图资源是独立于地图的，可以单独编辑，也可以重复使用，不同 的地图可以使用相同的资源文件，提出把地图编辑器从功能上分为两个部分来 实现，即编辑地图和编辑资源，从而给出了一个可以重复利用地图资源，对地 图和地图资源单独进行编辑的新思路。 4 考虑到游戏地图寻径的下限是当寻找通往孤岛区域的路径时，会搜索整个 地图，直到所有可到达的节点都被通过计算，这会浪费大量的c p u 时间，提出 通过地图编辑器对地图不可到达的孤岛区域进行预处理的思想，用数组记录这 些孤岛信息，在开始寻路前检查它，进一步提高了寻径速度。 5 在以上相关工作的基础，利用j a v a 技术，在吉林省电业局项目电力系 统安全规程培训平台( 游戏版) 中，设计并实现了智能化的地图寻径。 1 3 本文的组织结构 论文的组织结构如下： 第l 章首先介绍了论文的选题背景，然后阐述了本文所做的主要工作，最 后介绍了本文的研究内容和结构安排。 第2 章介绍了地图寻径中的启发式搜索算法和地图编辑器的基本理论，包 括启发式搜索算法的必要性、评价函数、有序搜索算法、a 木算法和地图编辑器 的相关概念。 第1 章绪 论 第3 章实现了游戏地图编辑器的优化设计，主要包括地图文件的数据结构 及优化、详细设计和地图的生成。 第4 章给出了基于舻算法的游戏地图寻径新算法。主要包括对a 木算法节 点结构的优化、开启列表和关闭列表遍历算法的改进和路径的平滑处理。 第5 章结合吉林省电业局项目电力系统安全规程培训平台( 游戏版) 的 具体情况，对改进后的新算法进行了进一步改进，实现了智能化的地图寻径。 东北电力大学硕士学位论文 第2 章启发式地图寻径算法及地图编辑器简介 路径搜索是游戏中一个很基础也很关键的部分，而且这也是个很有挑战性 的难题，因为游戏路径搜索过程中，c p u 计算负担很重的任务，并且存储路径 搜索相关信息又需要较大的存储空间，而赋予一个角色在游戏世界中比较智能 的移动能力需要很多的技巧。目前，游戏地图寻径的搜索算法主要包括传统搜 索算法和启发式搜索算法【5 1 。典型的传统搜索方法是宽度优先搜索( 亦称广度优 先搜索) 和深度优先搜索，它们都没有用到本身的信息，搜索完全是盲目的按照 固定顺序进行，效率低，耗费过多的计算空间与时间。启发式搜索则是在控制 性知识中增加关于被求解问题和相应任务的某些特性，利用启发性信息来确定 节点的生成、扩展和搜索顺序，指导搜索朝着目标方向前进。 2 1 传统搜索技术 传统搜索技术是利用计算机的高性能来有目的的穷举一个问题的部分或所 有的可能情况，从而求出问题的解的一种方法【6 】。搜索过程实际上是根据初始条 件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。 所有的搜索算法从其最终的算法实现上来看，都可以划分成两个部分一控 制结构和产生系统，而所有的算法的优化和改进主要都是通过修改其控制结构 来完成的 7 1 。 传统搜索技术是不利用问题的有关信息，而根据事先确定好的某种固定的 搜索方法进行搜索。典型的传统搜索方法是宽度优先搜索( 亦称广度优先搜索) 和深度优先搜索，这是两种基本搜索方法。这里先介绍回溯策略的一般策略， 然后再介绍宽度优先搜索和深度优先搜索。 2 1 1 回溯策略( ( b a c k t r a c kin gs t r a t e g ie s ) 回溯算法是所有搜索算法中最为基本的一种算法，所谓回溯法是一种优先 搜索法【8 】。按条件向前搜索以达到目的，但当搜索到某一步时，发现原先选择并 第2 章启发式地图寻径算法及地图编辑器简介 不是最优或达不到目标，就退回上一步重新选择，这种走不通退回再走的技术 称为回溯法。其采用了一种“走不通就掉头 思想作为其控制结构，其相当于 采用了先根遍历的方法来构造解答树，可用于找解或所有解以及最优解。 回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法不 是按某种固定的计算方法来设计算法，而是通过尝试和纠正错误来寻找答案。 用回溯算法解决问题的一般步骤为： 1 定义一个解空间，它包含问题的解。 2 利用适于搜索的方法组织解空间。 3 利用深度优先法搜索解空间。 4 利用限界函数避免移动到不可能产生解的子空间。 回溯算法的一个重要特性是问题的解空间在搜索问题解的过程中动态产 生。它对空间的消耗较少，当其与分枝定界法一起使用时，对于所求解在解答 树中层次较深的问题有较好的效果，但应避免在后继节点可能与前继节点相同 的问题中使用，以免产生死循环 9 1 。 2 1 2 宽度优先搜索( b f s ) 宽度优先搜索算法是最简便的图的搜索算法之一，这一算法也是很多重要 的图的算法的原型。d i j k s t r a 单源最短路径算法和p r i m 最小生成树算法都采用了 和宽度优先搜索类似的思想【l o 】。 如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索算法就 叫做宽度优先搜索( b r e a d t h f i r s ts e a r c h ) ，如图2 1 所示【2 7 1 。从图可见，这种搜索 是逐层进行的：在对下一层的任一节点进行搜索之前，必须搜索完本层的所有 节点。 己知图g - ( k 助和一个源顶点s ，宽度优先搜索以一种系统的方式探寻g 的 边，从而发现s 所能到达的所有顶点，并计算j 到所有这些顶点的距离( 最少边 数) ，该算法同时能生成一棵根为s 且包括所有可达顶点的宽度优先树。对从s 可达的任意顶点v ，宽度优先树中从s 到v 的路径对应于图g 中从s 到，的最短 路径，即包含最小边数的路径。该算法对有向图和无向图同样适用。 之所以称之为宽度优先算法，是因为算法自始至终一直通过已找到和未找 东北电力大学硕士学位论文 到顶点之间的边界向外扩展，也就是说算法首先搜索和s 距离为k 的所有顶点， 然后再去搜索和s 距离为抖1 的其他顶点。 图2 1 宽度优先搜索示意图 宽度优先搜索算法如下： 1 把起始节点放到未扩展节点表( o p e n 表) 中( 如果该起始节点为目标节点， 则求得一个解答) 。 2 如果o p e n 是个空表，则没有解，失败退出；否则继续。 3 把第一个节点( 节点n ) 从o p e n 表移出，并把它放入己扩展节点表 ( c o 她d 表) 中。 4 扩展节点刀，如果没有后继节点，则转向上述第2 步。 5 把1 1 的所有后继节点放到删表的末端，并提供从此后继节点回到玎的 指针。 6 如果n 的一个后继节点是个目标节点，则找到一个解答，成功退出；否则 转向第2 步。 这一算法假定起始节点本身不是目标节点，如果要检索起始节点是目标节 点的可能性，只要在第1 步的末尾加上一句“如果起始节点为目标节点，则求 得一个解答”即可做到，正如第l 步括号内所写的。这个搜索过程产生的节点 和指针构成一棵隐式定义的状态空间树的子树，称之为搜索树。 显而易见，宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点 第2 章启发式地图寻径算法及地图编辑器简介 的最短路径；这棵搜索树提供了所有存在的路径，如果没有路径存在，那么对 有限图来说就失败退出；对于无限图来说，则永远不会终止。 2 1 3 深度优先搜索( d f s ) 深度优先搜索( d e p t h - f i r s ts e a r c h ) 是另外一种盲目( 无信息) 搜索算法【1 1 1 ，正如 算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深 的搜索图1 2 列。 在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到 的边，就沿此边继续探下去。当结点1 ，的所有边都己被探寻过，搜索将回溯到发 现结点v 有那条边的始结点，这一过程一直进行到已发现从源结点可达的所有结 点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以下 过程，整个进程反复进行直到所有结点都被发现为止。 在深度优先搜索中，首先扩展最新产生的( 即最深的) 节点，如图2 2 所示。 深度相等的节点可以任意排列。定义节点的深度如下： 1 起始节点( 即根节点) 的深度为0 。 2 任何其它节点的深度等于其父辈节点深度加1 。 首先，扩展最深节点的结果使得搜索沿着状态空间某条单一的路径从起始 图2 - 2 深度优先搜索示意图 节点向下进行下去，只有当搜索到一个没有后继的状态时，它才考虑另一条替 代的路径。替代路径与前面已经试过的路径不同之处仅仅在于改变最后拧步， 东北电力大学硕士学位论文 皇曼量曼曼曼曼曼曼量曼曼曼皇量曼曼曼曼曼詈舅曼曼鼍i 量皇皇曼皇曼鼍曼鼍皇皇曼皇曼曼曼皇皇曼曼皇笪曼曼量曼曼曼曼鼍曼曼皇 而且保持i 尽可能小。 对于许多问题，其状态空间搜索树的深度可能为无限深，或者可能至少要 比某个可接受的解答序列的已知深度的上限深度还要深。为了避免考虑太长的 路径( 防止搜索过程沿着无益的路径扩展下去) ，往往给出一个节点扩展的最大深 度一深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继 节点处理。值得说明的是，即使应用了深度界限的规定，所求得的解答路径并 不一定就是最短路径。 2 1 4 等代价搜索( u n if o r m - c o s ts e a r c h ) 有些问题并不要求路径节点最少的解，而是要求具有某些特性的解【2 n 。搜 索树中每条连接弧线上的有关代价以及随之而求得的具有最小代价的解答路 径，与许多这样的广义准则相符合。宽度优先搜索可能被推广用来解决这种寻 找从起始状态至目标状态的具有最小代价的路径问题，这种推广了的宽度优先 搜索算法叫做等代价搜索算法【1 2 】。如果所有的连接弧线具有相等的代价，那么 等代价算法就简化为宽度优先搜索算法。在等代价搜索算法中，不是描述沿着 等长度路径断层进行的扩展，而是描述沿着等代价路径断层进行的扩展。 在等代价搜索算法中，把从节点i n 它的后继节点，的连接弧线代价记为c ( f ， 力，把从起始节点s 到任意节点f 的路径代价记为g ( o 。在搜索树上，假设g ( o 也是从起始节点s 到任意节点f 的最少代价路径上的代价，因为它是唯一的路径。 等代价搜索方法以删的递增顺序扩展其节点，其算法如下： 1 把起始节点s 放到未扩展节点表( o p e n 表) 中。如果此起始节点为目标节 点，则求得一个解，否则令g ( 5 ) = 0 。 2 如果o 删是个空表，则没有解而失败退出。 3 从o p e n 表中选择一个节点j ，使其( d 为最小。如果有几个节点都合适， 那么就要选择一个目标节点作为节点f ( 有目标节点的话) ：否则就从中选一个作 为节点j ，把节点j 从o p e n 表移至已扩展节点表( 位粥劬表) 中。 4 如果节点j 为目标节点，则求得一个解。 5 扩展节点j ，如果没有后继节点，则转向第2 步。 6 对于节点j 的每个后继节点计算分( 力= g ( d + c ( 力，并把所有后继节 第2 章启发式地图寻径算法及地图编辑器简介 皇皇量量曼曼曼量璺量蔓in = i 鼍罾鼍寡皇曼葛 点。，放进o p e n 表，提供回到节点j 的指针。 7 转向第2 步。 2 2 启发式搜索的必要性 从理论上说，如果计算机可以使用的时间和空间是无限的，那么仅仅有盲 目搜索算法也许就己经足够了，但实际情况并不是这样，更何况还有搜索速度 问题【2 7 】。现在已经发现了许多计算复杂性很高的问题，如旅行推销员问题，布 尔表达式的化简问题等等，这些问题的现有算法都是具有指数复杂性的f 1 3 1 。 现实的困难迫使人们转而求援于启发式算法。这种算法的本质是部分地放 弃算法一般化、通用化的概念，把所要求解问题的具体领域的知识加进算法中 去，以提高算法的效率。如宽度优先算法几乎可以用于求解一切搜索问题，比 如九宫图( 八数码难题) ，河内塔( 焚塔问题) ，旅行推销员，华容道，以及魔方等， 但是实际使用时，效率也许低得惊人，甚至根本解不出来，但如果为每类问题 找出一些特殊规则和宽度优先法配合起来使用，那结果就可能完全不一样。 根据启发信息，在生成各种搜索树时可以考虑种种可能的选择，如： 1 下一步展开哪个节点 2 是部分展开还是完全展开 3 使用哪个规则( 或算子) 4 怎样决定舍弃还是保留新生成的节点 5 怎样决定停止或继续搜索 6 如何定义评价函数 7 如何决定搜索方向 由于这些选择的不同，就得到了不同的启发式搜索算法。启发式搜索是利 用问题拥有的启发信息来引导搜索，达到减少搜索范围，降低问题复杂度的目 的。在研究启发式搜索方法时，先说明一下启发信息应用，启发能力度量及如 何获得启发信息这几个问题，然后再来讨论具体算法及一些理论问题。 一般来说启发信息过弱，在找到一条路径前将扩展过多的节点，即求得解 路径所需搜索的耗散值( 搜索花费的工作量) 较大；相反引入强的启发信息，有可 能大大降低搜索工作量，但不能保证找到最小耗散值的解路径( 最佳路径) 。因此 东北电力大学硕士学位论文 i i 实际应用中，希望最好能引入降低搜索工作量的启发信息而不牺牲找到最佳路 径的保证。这是一个重要而又困难的问题，从理论上要研究启发信息和最佳路 径的关系，从实际上则要解决获得启发信息方法的问题 1 4 1 。 在启发式搜索过程中，要对o p e n 表进行排序，这就需要有一种方法来计 算待扩展节点通向目标节点的不同程度，从而尽可能找到最有希望通向目标节 点的待扩展节点优先扩展。一种最常用法是定义一个评价函数六对各个节点进 行计算，其目的就是用来估算出有希望的节点来。如何定义一个评价函数昵? 通常参考的原则有：一个是节点处在最佳路径上的概率，求出任意一个节点与 目标节点集之间的距离度量或差异度量；另一个是根据格局( 博弈问题) 或状态的 特点来打分，根据问题的启发信息，从概率角度、差异角度或记分法给出计算 评价函数的方法。 2 3 评价函数 评价函数的任务就是估计待搜索结点的重要程度，给它们排定次序f l5 1 。评价 函数厂可以是任意一种函数，如定义它是结点x 处于最佳路径上的概率，或是 x 结点和目标结点之间的距离，或是x 格局的得分等等。一般来说，评价一个结 点的价值，必须综合考虑两方面的因素：已付出的代价和将要付出的代价。在 此，把评价函数厂( ，z ) 定义为从初始结点经过n 结点到达目标结点的最小代价路径 的代价估计值。它的一般形式是： 厂( 刀) = ：g ( 丹) + 办( ，2 ) 其中甙聆) 是从初始结点到n 结点的实际代价，办( 玎) 是从n 结点到目标结点的 最佳路径的估计代价，办( 刀) 主要体现了搜索的启发信息。因为实际代价甙 ) 可以 根据生成的搜索树实际计算出来，而估计代价办( 玎) 却依赖于某种经验估计，它来 源于对问题解的某些特性的认识，这些特性可以帮助更快地找到问题的解。 2 4a 球算法 a 木算法是当前国内外在游戏地图寻径中使用最多、最先进的算法。它是一 种动态规划的启发式搜索算法，以评价函数作为搜索约束条件，通过不断逼近 目的节点来寻找最优路径。a 木算法在比较简单的地图上，寻径速度非常快，能 第2 章启发式地图寻径算法及地图编辑器简介 寰曼曼曼曼詈曼曼曼寰量量量量曼曼皇曼皇曼曼曼曼曼曼曼量皇曼皇曼量曼曼曼曼宝曼鼍曼曼曼皇曼曼曼鼍i i i !i 很快找到最短路径( 确切说是时间代价最小路径) ，而且可以很方便地控制搜索规 模以防止程序堵塞；但是在地图很大的情况下，标准的a 术算法的速度会明显变 慢，同时a 木算法搜索每个节点周围的八个节点，有很大可能性会返回一条不可 能的路径，并且标准的a 术算法所提供的寻找有效路径的方法在现实情况下经常 发生失败，很难实现游戏移动的实时性。 2 4 1a ，t c 算法的基本原理 a 木算法是一种具有约束条件的最好优先搜索算法【1 6 】，具体实现主要依靠两 个列表：开启列表o p e n 和关闭列表c l o s e 。首先精灵从一点开始探走几个相邻的 节点，如果可以移动且当前移动为起点到那个节点的历史最佳方法，则把那个 节点按照估价值从小到大插入到开启列表。所谓最佳方法是指移动耗费总和f 最低( f = g + h ，其中g 为从起点彳沿着产生的路径移动到当前点s 的移动 耗费。日为从s 移动到目标点五的预估移动耗费) ；其次对几个方向试探结束后， 取出估价值最小的节点放入关闭列表，重复上述过程直到到达目标节点；最后 从目标节点开始，沿着每一节点的父节点逆向回溯到起始节点，从而得到搜索 的最短路径。 当前节点放入开启列表需要满足三个条件： 1 这步在地图上面是可以移动的。 2 这步所在节点在开启列表里面并不存在。 3 从起点到这步的实际距离比这点的历史最小距离还短。 2 4 2 标准a 算法的描述 a 幸算法内容如下： 1 生成一个只包含开始结点n d 的搜索图g ，把n o 放在o p e n 列表上； 2 生成一个c l o s e 列表，它的初始值为空； 3 若o p e n 为空，则失败退出； 4 选择o p e n 的第一个结点，把它从o p e n 表移入c l o s e 表，称该结点为以； 5 若n 是目标结点，顺着g 中从n 到n d 的指针找到一条路径，获得解决方 案，成功退出( 该指针定义了一个搜索树，在第7 步建立) ； 东北电力大学硕七学位论文 6 扩展结点n ，生成其后继结点集m ，n 的祖先不能在m 中，在g 中安置m 的成员，使它们成为n 的后继； 7 为m 的每一个不在g 中的成员建立一个指向n 的指针。把m 的这些成员 加入到o p e n 表中。对m 中的每一个已在o p e n 表或c l o s e 表中的成员m ，若到目 前为止找到的到达m 的最好路径通过n ，就把它的指针指向玎；对已在c l o s e 表 中的m 的每一个成员，重定向它在g 中的每一个后继，以使它们顺着到目标发 现的最好路径指向它们的祖先；按定义的函数值从小到大的顺序重排o p e n 表； 8 返回第3 步。 从a 木算法的基本思想上可以看出，如果搜索过程发现一条路径到达一个节 点的代价比现存的路径代价低，就要重定向指向该节点的指针，己经在c l o s e 表 中的节点子孙的重定向保存了后面的搜索结果，但是可能需要指数级的计算代 价，因此，第7 步常常不会实现，随着搜索的向前推进，其中有些指针最终将 会被重定向。 2 4 3a 木算法的估价函数 a 木算法目的是能够求解出状态空间中的最短路径，也就是用最快的方法求 解问题。如果一个估价函数可以找出最短的路径，称之为可接纳【1 7 】。a 枣算法是 一个可接纳的最好优先算法。a 宰算法的估价函数可表示为： k 甩) = g ，( 玎) + 办，( 玎) 这里，八刀) 是估价函数，g 研) 是起点到终点的最短路径值，厅，( 刀) 是n 到目标 点的最短路径的启发值。由于这个八门) 其实是无法预先知道的，所以用估价函数 苁功做近似，当甙，z ) 习时( 大多数情况下都是满足的，可以不用考虑) ，用 双玎) 代替g ，( 门) ，当乃( 玎) 勘，( 玎) 时( 这一点特别的重要) ，用 ( 玎) 代替乃切) ，可以 证明应用这样的估价函数是可以找到最短路径的，也就是可接纳的。 与估价函数性能密切相关的是办( n ) 启发函数的信息性。j l z 0 ) 的信息性通俗点 说其实就是在估计一个节点值时的约束条件，如果信息越多或约束条件越多则 排除的节点就越多，估价函数越好或说这个算法越好，但在游戏开发中由于实 时性的问题，办( 刀) 的信息越多，它的计算量就越大，耗费的时间就越多，就应该 适当的减小 ( 玎) 的信息，即减小约束条件，但算法的准确性就差了，这里需要两 第2 章启发式地图寻径算法及地图编辑器简介 者相对平衡。 2 4 4a 木算法的可接纳性 对办m 施加三个条件可以保证a 算法总能找到最小代价路径【l 引。条件分别 是： 1 每个节点如果有后继节点，且个数是有限的。 2 所有节点代价都大于某个正数。 3 对搜索中的所有节点刀，办( 以) 决不会超过实际值的估计，这样的厅( 胛) 函数 被称为优化概算机。 用这三个约束条件，只要存在到达目标的路径，a 算法就可以保证找到一 条到达目标的最佳路径【1 9 j 。 如果a 算法的两个版本a 。和a 。，其差别在于对所有的非目标节点h 1 h 2 ， 那么就说前者比后者更灵通。当对所有的节点办( 玎) = d 时，得到的是相同代价算 法( 搜索顺着相同代价的边沿向外扩展) ，顺着相同深度的边沿向外扩展，宽度 优先算法也是”算法( h = o ) 的一种特殊情况，故也是可接纳的。 2 4 5a 冰算法的一致性( 或单调) 条件 考虑一对节点( r l ，n j ) ，n j 是珞的一个后继，如果在搜索图中所有的这种节 点对都满足下述条件：h ( n 3 一向( 砌 3 2 3t i l e 存储格式 t i l e d 保存的地图格式是一个x m l 文件。x m l 是一种可以创建自己的标记 的标记语言，即“可扩展标记语言 。x m l 简单易懂，是- v j 既无标签集也无语 法的新一代标记语言。x m l 支持世界上几乎所有的主要语言，所有这一切使 x m l 成为数据表示的一个开放标准，这种数据表示独立于机器平台、供应商以 及编程语言。x m l 是被设计用来存储数据、携带数据和交换数据的。x m l 是与 软件、硬件和应用程序无关的，所以使数据可以被更多的用户、更多的设备所 利用。x m l 具有如下的特性： 1 可扩展性x m l 允许使用者创建和使用自己的标记而不是h t m l 的有 限词汇表，用户可以用x m l 为项目定义自己的标记语言，甚至定义特殊标记语 言作为该领域信息共享与数据交换的基础。 2 灵活性x m l 提供了一种结构化的数据表示方式，使得用户界面独离于 结构化数据。 3 自描述性x m l 文档通常包含一个文档类型声明，因而x m l 文档是自 描述