（计算机软件与理论专业论文）基于改进a算法的游戏地图寻径的研究.pdf

心。 l 乞 j 目录 摘 要i a b s t r a c t i i i 第1 章绪论l 1 1 引言一1 1 2 研究背景和意义2 1 3 游戏中路径搜索研究现状3 1 4 本文研究工作和组织结构6 1 4 1 本文研究工作6 1 4 2 本文组织结构6 第2 章搜索技术理论研究9 2 1 图搜索1o 2 1 1 图的相关概念1 0 2 1 2 图的搜索过程1 2 2 2 盲目搜索算法1 3 2 2 1 宽度优先搜索1 3 2 2 2 深度优先搜索1 4 2 3 启发式搜索算法。1 6 2 3 1 启发信息1 6 2 - 3 2 估价函数16 2 3 3 启发式搜索算法1 7 2 4 传统的最短路径算法18 2 4 1f l o y d 算法l8 2 4 2d i j k s t r a 算法l 9 2 5a 术算法。1 9 2 5 1a 宰算法原理1 9 2 5 2a 木算法的性质2 2 2 6 本章小结2 4 第3 章a 幸算法的改进和优化2 5 3 1a 木算法存在的不足一2 5 3 2 估价函数的选取2 6 3 2 1 曼哈顿距离一2 6 3 2 2 对角线距离2 7 3 2 3 欧几里得距离2 8 3 3 优化o p e n 表查找速度2 8 3 3 1 二叉堆的定义3 0 3 3 2 插入节点31 3 3 3 删除节点3 2 3 4 分级路径搜索3 3 3 4 1 分级路径搜索思想3 3 。3 4 2 分级路径搜索步骤3 4 3 5 分层寻路3 5 3 6 本章小结3 6 第4 章仿真实验与结论分析。3 9 4 1 基于改进a 木算法的仿真实验步骤3 9 4 2 标准a 枣算法路径搜索及实验数据分析4 1 4 3 采用二叉堆存储o p e n 表节点的a 木算法对比实验4 2 4 4 采用分级路径搜索算法对比实验4 3 4 5 综合改进a 母算法对比实验4 4 第5 章总结和展望4 7 5 1 论文主要结论4 7 5 2 展望4 7 参考文献4 9 致 射51 攻读硕士学位期间发表的论文5 3 t f 1 0 l i n 摘要 基于改进a 术算法的游戏地图寻径的研究 计算机软件与理论专业硕士研究生周小镜 指导教师陈宏刚教授 摘要 随着计算机硬件性能的不断提升和软件技术的飞速发展，游戏行业也相应得到发展。近 几年来，游戏里面的声音和视觉效果方面都得到了极大的提高和改善。但是，游戏中的人工 智能技术的研究和应用还相对比较落后，所以游戏中虚拟角色的行为表现就显得比较单调和 笨拙，只能重复做几个简单的动作，行走看起来非常机械，严重影响到了游戏的品质。然而， 人工智能技术能够使虚拟角色看起来更加聪明更加智能化，因此，近几年来人工智能方面的 技术就成为了改善和提高游戏品质的热门研究课题。在游戏软件中，人工智能是一个既重要 又复杂的模块，而寻路算法又是人工智能运用予游戏中的最基本和最重要的问题之一。 a 木算法是目前被游戏开发人员最广泛使用的人工智能寻路算法。a 木算法是一种启发式搜 索算法，它采用的估价函数是：f ( n ) = g ( n ) + h ( n ) ，g ( n ) 表示起始节点到当前节点实际走 的距离，h ( n ) 表示当前节点到目标节点的距离的估价值。利用这个函数计算出下一步将要搜 索的所有节点的估价值，通过比较选择估价值最小的节点，作为下一步要走的节点，因此找 到的是最优路径。本文首先优化o p e n 表中节点的查找速度，然后运用将单个物体路径搜索和 a 木算法相结合的分级路径搜索方法来搜索路径。运用c + + 语言实现标准的胁算法和改进后的 算法进行路径搜索，然后根据统计它们搜索的节点数和搜索路径所花费的时间，来验证改进 后的算法的可行性和有效性。 本文采用3 2 * 3 2 的矩形方格来模拟游戏地图，黑色的方格代表障碍物，也即是代表游戏 中的建筑物、墙、河流等无法通过的区域。具体的研究方法和步骤如下： 第一，经过分析，我们可知a + 算法最耗费时间的部分是：在o p e n 表中查找f 值最小的 节点。本文采用二叉堆的方法，通过对o p e n 表中的节点进行排序。采用二叉堆的方法比一 般的排序方法更加高效，极大的优化了o p e n 表内查找、增加和删除节点的速度。通过对比 实验验证了采用二叉堆的方式来优化o p e n 表中节点的查找速度的a 奉算法比标准的a 幸算法 的搜索效率提高了5 。 第二，在大型的游戏地图中，a 算法需要搜索的节点数量仍然非常巨大。通过分析我们 发现，在没有障碍物的情况下，起始节点和目标节点之间就是一条直线路径。所以本文采用 i i ， j ： l 1 蕾 a b s t r a c t r e s e a r c ho f r o u t i n gi nt h eg a m em a p b a s e d o ni m p r o v e d a 六a l g o r i t h m m a j o r ：c o m p u t e r s o f t w a r ea n dt h e o r ya u t h o r ：x i a o j i n gz h o u s u p e r v i s o r ：p r o f e s s o rh o n g g a n g c h e n a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rh a r d w a r ea n ds o f t w a r et e c h n o l o g y , t h eg a m ei n d u s t r yh a s a l s ob e e nd e v e l o p e d i nr e c e n ty e a r s ，t h es o u n da n dv i s u a le f f e c t si nt h eg a m eh a v eb e e ne n h a n c e d a n di m p r o v e dg r e a t l y h o w e v e r ，t h er e s e a r c ha n da p p l i c a t i o no fa r t i f i c i a li n t e l l i g e n c et e c h n o l o g yi n t h eg a m ea r er e l a t i v e l yb a c k w a r d ，s ot h ev i r t u a lc h a r a c t e r sb e h a v i o ri nt h eg a m eb e c o m e s m o n o t o n o u sa n ds t u p i d i tc a no n l yr e p e a taf e ws i m p l em o v e s ；t h i sa f f e c t e dt h eq u a l i t yo ft h eg a m e s e r i o u s l y h o w e v e r ，u s i n ga r t i f i c i a li n t e l l i g e n c et e c h n o l o g ym a d et h ev i r t u a l c h a r a c t e rl o o k m o r ei n t e l l i g e n t s o ，i nr e c e n ty e a r sa r t i f i c i a li n t e l l i g e n c et e c h n o l o g yb e c a m eah o tr e s e a r c ht o p i ci n i m p r o v i n ga n de n h a n c i n gt h eq u a l i t yo ft h eg a m e i nt h es o f t w a r eo fg a m e ，a r t i f i c i a li n t e l l i g e n c ei s a ni m p o r t a n ta n dc o m p l e xm o d u l e ，a n dp a t h - f i n d i n ga l g o r i t h mi st h em o s ti m p o r t a n ti s s u e si n a r t i f i c i a li n t e l l i g e n c e a a l g o r i t h mi st h em o s tw i d e l yu s e da r t i f i c i a li n t e l l i g e n c ep a t h - f i n d i n ga l g o r i t h m si nt h eg a m e d e v e l o p i n gc u r r e n t l y i ti sah e u r i s t i cs e a r c ha l g o r i t h m ，t h ee v a l u a t i o nf u n c t i o ni s ：f ( n ) = _ g ( n ) + h ( n ) ， g ( n ) i st h ea c t u a ld i s t a n c ef r o mt h es t a r tn o d et ot h ec u r r e n tn o d e ，h ( n ) i st h ev a l u a t i o nd i s t a n c e f r o mt h ec u r r e n tn o d et ot h et a r g e tn o d e u s i n gt h i sf u n c t i o nc a nc a l c u l a t et h ev a l u a t i o no fa l lt h e n o d e s ，w h i c hc a ns e a r c hi nt h en e x ts t e p t h e nc h o o s et h em i n i m u mt ob et h en e x tn o d e s ot h i sp a t h i st h eo p t i m a lp a t h i ts e e m st h a tt h ee v a l u a t i o nf u n c t i o ni st h em o s ti m p o r t a n ti na a l g o r i t h m i t d e s i g n e da p p r o p r i a t e l yc a ng r e a t l yi m p r o v et h ee f f i c i e n c yo ft h es e a r c ha l g o r i t h m i nt h i sp a p e r , f i r s t l y , i m p r o v et h ee v a l u a t i o nf u n c t i o n ，s e c o n d l y , o p t i m i z et h es e a r c h i n gs p e e di no p e nt a b l e ， t h i r d l y , c o m b i n i n gt h ea l g o r i t h mo f as i n g l eo b j e c ta n da a l g o r i t h m f i n a l l y , r e a l i z et h es t a n d a r da a l g o r i t h ma n dt h ei m p r o v e da l g o r i t h mu s i n gc + + l a n g u a g e t h e na c c o r d i n gt ot h en o d e sa n dt h e t i m e ，w h i c hs p e n tt os e a r c ht h ep a t h 1 1 1 e yc a l lv e r i f yt h ei m p r o v e da l g o r i t h m sf e a s i b i l i t ya n d a f f e c t i v i t y i 两南大学硕十学伊论文 i nt h i sp a p e r , u s e3 2 幸3 2r e c t a n g u l a rg r i d st os i m u l a t et h eg a m em a p t h eb l a c kb o x e s r e p r e s e n tt h eo b s t a c l e si nt h eg a m e s u c ha sb u i l d i n g s ，w a l l s ，r i v e r s ，o t h e rh a r m l e s st h r o u g h a r e a s s p e c i f i cr e s e a r c hm e t h o d sa n ds t e p sa r ea sf o l l o w s ： f i r s t l y , t h r o u g ha n a l y s i s ，w ek n o wt h a tt h em o s tt i m ec o n s u m i n gp a r ti na a l g o r i t h mi s ： f i n d i n gt h es m a l l e s tfv a l u en o d ei nt h eo p e nt a b l e i nt h i sp a p e r , iu s et h eb i n a r yh e a pm e t h o dt o s o r tt h en o d e si nt h eo p e nt a b l e b i n a r yh e a pm e t h o di sm o r ee f f i c i e n t , g r e a t l yo p t i m i z e dt h e f i n d i n g ，a d d i n ga n dr e m o v i n gn o d e s s p e e d b yc o m p a r i n gt h ee x p e r i m e n t a l ，v e r i f i c a t i o nt h es e a r c h e f f i c i e n c yo fi m p r o v e da l g o r i t h mt h a nt h es t a n d a r da 宰a l g o r i t h mi n c r e a s e d5 s e c o n d l y , t h r o u g hi m p r o v et h ev a l u a t i o nf u n c t i o n ，r e d u c i n gt h en u m b e ro fn o d e s h o w e v e r , t h e g a m em a p i sh u g e t h en u m b e ro fn o d e si ss t i l lv e r yl a r g e t h r o u g ha n a l y s i s ，w ef o u n dt h a tf r o mt h e s t a r t i n gn o d et ot h et a r g e ti sas t r a i g h tl i n ew h e nt h e r ed on o th a v eo b s t a c l e s s oic o m b i n et h e a l g o r i t h mo fas i n g l eo b j e c ta n da a l g o r i t h m ，i no r d e rt of u r t h e ri m p r o v et h es p e e d b yc o m p a r i n g t h ee x p e r i m e n t a l ，v e r i f i c a t i o nt h es e a r c he f f i c i e n c yo fi m p r o v e da l g o r i t h mt h a nt h es t a n d a r da a l g o r i t h mi n c r e a s e d1 1 5 f i n a l l y , ic o m b i n et h et w om e t h o d s t h e n ，u s ei tt of i n dp a t hi ng a m em a p b yc o m p a r i n gt h e e x p e r i m e n t a l v e r i f i c a t i o nt h es e a r c he f f i c i e n c yo fi m p r o v e da l g o r i t h mt h a nt h es t a n d a r da 事 a l g o r i t h mi n c r e a s e dl4 7 k e y w o r d s ：a r t i f i c i a li n t e l l i g e n c e ；p a t h f i n d i n ga l g o r i t h m ；a 女a l g o r i t h m ； b i n a r yh e a p j j 鼻 j i 第1 章绪论 第1 章绪论 1 1 引言 近十年来，随着我国经济的飞速发展和科学技术的不断进步，国际之间的文 化交流也不断增多，比如，我们在不断的学习英文，而其他国家的人们也在努力 的学习中文。再加之随着互联网的迅速普及，网络文化更是突飞猛进的发展，紧 接着用于上网的营业场比如网吧等场所遍布全国所有大中小城市，为网络游戏的 发展创造了得天独厚的条件。随着宽带普及到家庭，互联网用户越来越多，同时 也出现了大量的网络游戏开发企业和运营企业，于此同时市场上就出现了大量的 网络游戏产品，我国网络游戏市场发展迅速。因为网络游戏丰富了社会大众的文 化娱乐生活，所以深受人们尤其是年轻一代的喜爱。最近几年，我国网络游戏产 业不仅创造了较大的产值，而且还带动了相关行业的发展。游戏业成为了娱乐业 和网络经济的重要支柱，甚至还成为了文化产业里面一个非常有潜力的增长点。 正因为现在网络技术如此的发达，所以网络上的游戏也就越来越多。因此，要想 让一款游戏在市场上有竞争力就必须提高游戏的品质，而游戏的真实感决定了一 款游戏的品质。 那么什么是游戏的真实感呢? 一般来说，游戏的真实感就是说尽量使得游戏 里面虚拟角色的行为更接近现实生活里面人们或者动物的行为，这样让人们在玩 游戏的时候有种身临其境的感觉，即是指游戏中虚拟角色的智能性和游戏的沉浸 感。为了增强游戏的真实感，现在市面上大多数的计算机游戏都是综合采用了物 理技术、图形图像技术和人工智能技术。在过去的几年里，游戏中的物理方面的 技术和图形图像技术都取得了很大的进展。例如，d i r e c t x ( d i r e c t e x t e n s i o n ，简 称d x ) 是由微软公司创建的多媒体编程接口1 和o p e n g l ( 全写 o p e ng r a p h i c sl i b r a r y ) 一个功能强大并且调用方便的底层图形库，也是一个专业 的图形程序接口2 1 。h a v o k 游戏动力开发工具包( h a v o kg a m ed y n a m i c ss d k ) ， 简称为h a v o k ，专门为电子游戏设计的，是一个用于物理方面的游戏引擎，注重在 游戏中对真实世界的模拟3 1 。但是，对物理特征模拟技术和图形图像技术的应用 已经不足以使一个游戏具有独特性了，于此同时也不能满足游戏玩家对游戏品质 的高要求。因此，游戏开发人员需要从别的方面来增强游戏的真实体验感。所以， 人工智能技术在游戏里面的应用就逐渐得到了重视，而路径搜索又是人工智能领 域里面最热门的一个研究内容，所以国内外大量的学者都在进行路径搜索技术的 研究。 两南大学硕十学位论文 1 2 研究背景和意义 在中国，游戏产业是一个新兴的产业。现在中国的游戏产业正处于成长期， 并且将快速走向成熟期的阶段。前几年，在世界金融危机的时候，整个世界经济 都受到了打击，但是游戏产业却没有受到金融危机的影响，反而成为了整个经济 发展的领头羊，得到了迅猛的发展。 2 0 0 6 年，中国网络游戏用户数为4 3 0 0 万。其中，付费的用户为2 4 0 0 万，占 全部用户数的5 6 。网络游戏收入达到5 9 亿元，比2 0 0 5 年增长了6 2 。同时， 中国的网络游戏玩家群也发生了较大的变化，从1 6 岁到2 5 岁的青少年玩家，逐 步向1 6 岁到3 5 岁的成人玩家发展。 2 0 0 7 年，游戏玩家数量不断增加，这部分增加的玩家一方面来自于休闲游戏 的玩家；另外一方面来自于游戏运营商对中小城市里面的潜在的游戏玩家的挖掘。 至此，游戏用户数则达到了4 8 5 0 多万，比2 0 0 6 年增长了1 7 。网络游戏收入达 到1 3 0 亿元，比2 0 0 6 年增长6 7 。预计在未来的几年之内，游戏带来的收入还将 继续保持2 0 以上的增幅。 网络游戏的快速发展一方面得益于中国庞大的网络用户基数，另一方面得益 于游戏运营商对潜在游戏用户的挖掘“1 。于此同时，政府也在大力扶持我国国内 的游戏开发公司。比如说，政府加强了对外国游戏开发公司的管制力度，也就是 对本国游戏开发公司的保护政策，尽量保护我国国内的游戏开发公司。在贯彻落 实国务院颁布的多个支持软件行业的政策的基础之上，因为游戏产品属于软件产 品中的一种，所以对于游戏开发者和开发企业，给予高新技术企业税收优惠和资 金支持的优惠政策。同时，对于参与游戏开发的国内公司，可以享受政府的税收 优惠和资金支持。游戏产业是软件产业中的一个重要组成部分，所以用于电子信 息产业发展的基金，应该有一部分用于游戏产业。这样游戏产业就可以依靠这一 部分资金，重点投资开发游戏开发过程所涉及的核心技术。另一方面，对有益于 未成年人健康成长的游戏软件产品，政府更加的鼓励和支持。按照规定参照国家 财政部和国家税务总局联合发布的政策财税1 2 0 0 4b 9 号文件中的优惠政策实行，这 样使他们能够享受到教育领域相应的优惠政策“1 。同时，在国家设立的支持文化 产品出口的政策里面，同样也体现出了对国内游戏软件产品出口的扶持。国家颁 布了许多诸如以上的优惠政策用以扶持游戏产业的发展。 2 1 世纪最重要的是人才，所以政府不仅在政策上给予了优惠和支持，还大力 培养和引进游戏相关技术人员，包括游戏策划人员、游戏美工人员和游戏程序开 发人员。国家鼓励大学在软件专业和美术专业的学科必修课程中，开设涉及到游 戏相关技术的课程。同时还鼓励一些条件比较好的科研机构和学校，开设专门的 2 第1 章绪论 游戏专业。除此之外，政府还大力支持游戏公司独立办学，或者和高校联合办学， 希望能够培养更多的游戏行业相关的人才，让更多的人参与到游戏的策划和开发 中来。 除了在政策上和人才培养方面得到了政府的大力支持之外，我国还开展了许 多游戏行业的会议和交流活动。比如，2 0 0 7 年，在上海举办的游戏开发者大会， 是技术性很强而且非常专业的一个游戏行业的会议，这是一个游戏开发者的交流 盛会“1 。除此之外，还有c h i n a j o y ，这是一个综合性的游戏会议。在这个会议上 有多款游戏参加展出，各大游戏公司凭借这个会议对自己公司的游戏进行宣传； 很多游戏爱好者也前去参观，尽情享受游戏的乐趣，它是游戏开发者和游戏爱好 者一年一度共同的盛会。通过这个会议，游戏公司不仅可以宣传自己的游戏，同 时还可以了解游戏玩家更倾向于喜欢哪种类型的游戏，也就是了解了市场需求， 之后才能开发出更畅销的游戏来。这些会议虽然在规模和影响力方面还不够，目 前还不能和美国召开的游戏相关的会议相比拟，但是它至少表明我国的游戏产业 已经开始走向成熟。 游戏行业的发展趋势：随着游戏行业的飞速发展，游戏玩家对游戏品质的要 求也越来越高。要想游戏在市场上有竞争力，就必须得提高游戏画面的精美程度、 娱乐性和挑战性，还有提高游戏的速度。除此之外，更重要的是要增强游戏玩家 的真实体验感，只有这样游戏才能得到玩家的认可和亲耐，否则，这款游戏就不 能在市场上生存，就会被淘汰。在各种类型的游戏中，特别是在r p g ( r o l e p l a y i n g g a m e ) 角色扮演游戏中虚拟角色的最基本的任务，就是要求在最 短的时间找到最合适的路径，也就是必须有效地找出一条路径，使其能够在游戏 里面按照既定的路径行动。这样就会使用到人工智能领域里面的路径搜索相关的 知识，游戏开发人员应根据游戏的具体需要对人工智能里面的寻路算法进行改进 和优化，使人工智能为游戏开发带来更大的发展空间，让虚拟角色在游戏地图里 面的行走看起来更加智能化。 1 3 游戏中路径搜索研究现状 游戏地图中的路径搜索是人工智能理论在游戏中的一个实际应用，游戏地图 的寻路是虚拟角色( 游戏里面的人物) 应该具备的最基本的能力之一7 1 。从虚拟 角色的行走可以看出该款游戏的品质，因此寻路成为游戏开发中的重要内容之一。 再加上现在的游戏玩家对游戏品质要求越来越高，要求游戏更加真实和逼真，这 样对寻径算法就提出了更高的要求。寻路就是虚拟角色花费最少的时间以最佳的 方式走到指定的地点。然而，在游戏地图中寻找路径的问题并不仅仅是图论中寻 找一条从起点到目标点的通路那么简单。在游戏中还需要考虑很多方面的因素， 两南大学硕十学何论文 比如，游戏地图数据量非常巨大，需要很大的存储空间；游戏地图非常复杂，包 含了很多的建筑物、草地和河流等。虽然路径搜索算法作为人工智能领域里面一 个最热门的方向，经过多年的研究不断发展，已经形成了比较成熟的理论体系。 但是，由于游戏地图的复杂性，以及游戏玩家对游戏真实感等方面的要求。把人 工智能里面的路径搜索算法直接运用到游戏中，还存在很多问题。因此，游戏地 图中寻找路径的方法对于游戏开发人员来说也还是一个技术难点。 在游戏中，为了使得虚拟角色能够按照搜索出的路径行走，游戏地图的路径 搜索通常是要求利用路径搜索算法能够尽快找到可靠的而又最优的路径。也即是 用于搜索路径的算法最好能满足下面三个条件： 可靠性：游戏里面的虚拟角色在游戏中会遇到各种各样的场景和地形等。比 如，有高低起伏的山路、草地、迷宫和墙等障碍物。只要起点和目标点之间存在 路径，路径搜索的程序模块就必须保证：一定能够找到这个路径。我们就说这个 搜索算法具有可靠性。 高效性：只要虚拟角色在游戏里面移动，就会涉及到地图的路径搜索，就会 反复调用这个路径搜索算法，才能搜索出路径。这样就会导致游戏运行的时候速 度就比较缓慢，让游戏玩家感觉游戏很卡，这是很多玩家都不能接受的。这就要 求该用于路径搜索的算法必须高效，否则就会占用大量的处理器资源。 逼真性：游戏世界其实就是人们真实生活的一种模拟，再加上一部分虚构的 东西。所以应该让虚拟角色的行走和现实世界里面的人或者动物的行走相似。这 样游戏看起来才更加逼真，让游戏玩家有一种身临其境的感觉。所以，这就要求 寻路算法要足够精确，能够找到最优的路径。 在大多数时候，在游戏的设计和实现过程中，这几个条件是相互冲突的，不 能够同时满足。要使得这个寻路算法能够尽量满足以上三个条件，就导致游戏地 图的寻路变得更加困难。如果要求游戏里面的虚拟角色在寻路过程中尽可能做到 逼真，就要考虑角色面对各种可能出现的问题时能够做出合适的反应，同时还需 要对游戏虚拟角色以及场景中的各种物件等的建模更加复杂。这样就会存储大量 的信息，数据量就非常庞大。进而肯定就会影响到游戏运行的时间，大大的降低 了游戏的执行效率。所以，在实际游戏开发中，需要根据游戏的实际需求进行权 衡。首先要确定不同条件的优先级，不同的类型的游戏对各个条件的需求不同， 然后做出取舍，选择适合该款游戏特点的寻径算法。 国内外用于路径搜索的算法有很多种，但是现在游戏中经常采用的算法比较 少，只有如下一些算法：分等级寻路算法、单个物体寻路算法和a 木算法，其中， 最常用的是a 幸算法。下面对各个算法做一个简单的介绍： 分等级寻路算法的原理是：首先第一步需要把地图分成很多个区域，也就是 4 第1 审绪论 对游戏地图进行预处理。确定几个或者多个子目标节点，把寻找目标节点的步骤 分成几步。然后再开始搜索，首先搜索到子目标节点，然后通过搜索子目标节点 一步一步的前进，最后到达目标节点。这种算法存在的一个明显的不足是：子目 标节点有可能处在一个不可能到达的区域中，这样就无法找到这个点，就导致寻 路失败。所以，这种算法不具有可靠性。 单个物体寻路算法的原理是：首先根据起始节点s 和目标节点d 这两点确定 一条直线l 。然后从起始节点开始沿着直线l 朝目标节点前进，在这个过程中，如 果没有障碍物，则起始节点s 到目标节点d 之间的路径就是这条直线l ；如果遇到 障碍物就按照顺时针方向( 或者逆时针方向) 绕开障碍物行走，直到碰到直线l 为止，然后再接着沿着l 行走，这样一直循环下去。只要目标节点可达就可以到 达目标节点。 单个物体寻路算法的具体步骤如下： ( 1 ) 根据起始节点s 和目标节点d ，这两点确定一条直线l 。 ( 2 ) 从起始节点s 开始，沿着直线l 朝目标节点d 移动。 当遇到障碍物的时候，就按照顺时针方向( 或者逆时针方向) 绕开障碍物行 走，直到碰到直线l 为止。 ( 3 ) 重复步骤( 2 ) ，直到到达目标节点d 为止。 由此可知，这样的算法虽然比较简单，但是效率非常高，而且很明显存在一 个缺陷，就是按照这个算法找到的路径不是最短的路径，恰恰相反，找到的路径 是比最优的路径长好几倍的路径，这让游戏玩家无法接受。这种寻路算法就不具 有逼真性。 在1 9 6 8 年h a r t 教授等专家提出了一种比较高效的用于路径搜索的启发式搜索 算法a 宰算法8 1 。它最大的特点在于：在选择下一步将要走的节点时，引入了 已知的信息，特别是有关于目标节点的信息。对当前节点到目标节点的距离进行 评估，然后根据这个评估值来判断该节点是不是最有可能是最优路径上的节点。 这样就可以优先搜索最可能是最优路径上的节点，就能更快的找到目标节点，提 高搜索的效率。但是由于a 木算法要从当前节点的所有子节点中找出到达目标节点 代价最小的节点，要搜索的节点就比较多，在游戏地图较大较复杂的情况下，所 以搜索速度仍然会比较慢。因为游戏地图的复杂性，游戏地图中的寻径算法的研 究仍然是人工智能领域中的一个热点问题，而且也是游戏开发过程中的一个难点 问题，本论文的研究将对此做出探索，通过对a 幸算法进行改进和优化，达到提高 路径搜索效率的目的。 游戏地图中的路径搜索是一个比较复杂的问题。很多数时候都需要结合多种 解决方法，然后再根据实际的游戏开发需求，最后得到一个比较好的适合该款游 两南大学硕十学何论文 戏的解决方案。本论文围绕游戏地图的路径搜索展开研究，通过对常见的寻径算 法的优缺点进行分析，重点介绍了a 幸算法，详细分析了它的优缺点，从几个方面 对其进行改进和优化。 1 4 本文研究工作和组织结构 1 4 1 本文研究工作 本文的目的是通过对已有的寻路算法进行改进和优化，尽量使得改进的算法 在最短的时间之内找到最优的路径。本文首先对路径搜索的相关理论技术，包括 图搜索、盲目搜索算法和启发式搜索算法等进行了全面的分析。由于a 木算法是现 在游戏中最广泛采用的寻路算法，所以本文以a 宰算法为主要研究内容。然后，在 分析a 木算法的缺点的基础上，从几个方面提出了基于a 木算法的改进和优化的寻 路算法。最后本文设计了一个仿真实验，将本文所提的改进的寻路算法和标准的 a 幸算法进行了对比，验证本文所提出的改进方法的有效性和可行性。 本文主要研究内容如下： 分析比较目前常用的路径搜索方法，详细分析了a 宰算法，分析出它的不足之 处。经过分析发现它主要有以下不足：估价函数对a 宰算法的搜索起到关键性作用， 但是受到主观因素等的限制，因而估价函数的选取是一个比较复杂的问题； a 幸 算法中最耗费搜索时间的就是搜索o p e n 表中的f 值最小的节点，如何提高在 o p e n 表中查找节点的速度成为了一个难点。 针对以上a 木算法存在的不足，本文基于a 唯算法从几个方面来改进和优化算 法。首先利用二叉堆的方式来优化o p e n 表的查找速度。第二采用分级路径搜索。 最后将前面两个方面综合在一起。通过这些改进方法，来提高路径搜索的速度。 由于游戏地图的编辑非常复杂，需要专门的地图编辑器和大量的美术资源， 所以，本文采用一个3 2 * 3 2 的矩形方格图来仿真游戏地图，分别在这个地图上用 标准的a 母算法和改进后的a 木算法进行对比实验，通过统计它们寻路所花费的时 间和搜索的节点数，来评估它们的优劣。通过这些对比实验，来验证改进的算法 的有效性和可行性。 1 4 2 本文组织结构 论文共分为五个章节，论文的组织结构如下： 第1 章绪论 本章首先介绍了游戏地图中路径搜索的研究背景和意义，然后介绍了游戏中 路径搜索的研究现状，最后简述了本文的研究工作和组织结构。 第2 章搜索技术理论研究 本章介绍搜索算法相关的理论和技术，首先介绍了图论的相关知识，然后分 6 第1 罩绪论 两个大的方面对搜索算法进行介绍：一方面是盲目搜索算法，主要是深度优先搜 索和广度优先搜索，分析了各个算法的思想和优缺点；另一方面是启发式搜索算 法，主要介绍了启发式搜索的原理，启发信息和估价函数等内容。接着分析了传 统的最短路径算法，即f l o y d 算法和d i j k s t r a 算法。最后介绍了目前在游戏中常用 的a 幸算法。 第3 章a 木算法的改进和优化 本章首先分析了a 木算法存在的不足，然后针对它的不足之处，从几个方面对 其进行改进和优化。本文首先采用二叉堆的方式来优化o p e n 表的查找速度，然 后再采用分级寻路算法，大大提高了寻路的速度。除此之外，还分析了分层寻路， 针对跨地图的情况和同一地图的情况，分别采用低密度路点寻路和高密度路点寻 路。 第4 章仿真实验与结论分析 本文利用c + + 实现了标准的a 母算法寻路和改进后的a 木算法。再通过将标准 的a 木算法分别与采用二叉堆存储o p e n 表节点的a 木算法和分级路径搜索算法进 行对比实验。最后再将综合改进的a 木算法和标准的a 木算法进行对比。通过实验 数据来验证本文提出的改进算法的可行性和有效性。 第5 章总结和展望 主要对论文所做的工作做个总结，并对以后进一步研究方向进行了展望。 7 4 ， 物和森林等等，地图就是模拟的现实世界。一般来说，地图是用来表示游戏世界 里面的环境的图形。我们一般使用一定比例的方格图来表示整个游戏地图，其中 方格表示的每个节点对应游戏地图中的一个点，在仿真系统中，采用黑色方格表 示游戏里面的障碍物，障碍物即是建筑物和河流等等。在方格图系统中，路径搜 索的本质就是使用一种搜索算法寻找当前节点到目标节点的最短路径。这就需要 在考虑游戏地图的特点的基础之上，对人工智能里面的路径搜索算法进行改进和 优化，然后运用于游戏中地图的寻路。所以，研究寻路算法就是研究如何找到一 种更加有效的算法在游戏地图中找出最短路径。 人工智能( a r t i f i c i a li n t e l l i g e n c e ，简称a i ) 是近几年来游戏行业里面非常热 门的研究领域。特别是在第一人称射击f p s ( f i r s t p e r s o ns h o o t e r ) 和即时策略 r t s ( r e a l t i m es t r a t e g y ) 这两种类型的游戏出现之后，甜技术才被应用到游戏领 域中。因为在这两种类型的游戏中，有比较复杂的任务系统，以前的方法根本无 法达到这个复杂任务系统的要求，所以需要运用人工智能里面的技术，从此之后， 触技术在游戏里面就越来越受到重视。例如，现在大多数的游戏中，虚拟角色可 以进行自动寻路，当我们使用鼠标点击了目的地之后，不需要控制每一步，游戏 里面的自动寻路系统就开始运行，虚拟角色自动的就走到了目的地。这样节省了 玩家大量的操作，让游戏操作更加简洁化，让虚拟角色更加智能化。其实，这个 原理就是虚拟角色按照游戏系统里面采用的路径搜索算法找到的路径行走。这就 是游戏地图的寻径问题，即人工智能中的图搜索问题。 所谓图搜索问题，就是在地图上寻找一条从起始点a 到目标点b 的路径。但 是，在大多数情况之下，a 和b 之间可能存在很多条路径，有的路径比较短，有 的路径非常长，我们的研究目的就是用最短的时间找到最佳的路径。由于图搜索 过程中，每搜索一个节点，都要考虑下一步应该走哪一个与之相连的节点，但是 与之相连的节点有很多个，这样就需要依据一定的搜索策略，才能确定下一步走 的节点。由此可知，搜索策略至关重要。但是，如何判断搜索策略的好坏，可以 通过下面四个标准来评价： 完备性：如果起始点a 和目标点b 之间有通路，运用该搜索策略能否保证找 到通路。也就是说只要求解的这个问题有解，运用此搜索策略，就一定能得到这 些解，则该搜索策略就具有完备性。 时间复杂性：运用该搜索策略需要多长时间可以找到通路。也就说要明确搜 索的目的，对于那些无用的节点，要尽量避免对其的考察和搜索，尽量只搜索有 9 两南大学硕十学何论文 用的节点。因此达到提高搜索效率的目的。 空间复杂性：执行该搜索策略需要多少存储空间。也就是说在搜索过程中， 需要记录大量的节点信息，用来保存节点信息的空间要尽可能的小。 最优性：如果起始点a 和目标点b 之间存在多条通路，运用该搜索策略能够 找到最优的那条路径，则这个搜索策略才具有最优性。 但是，在大多数情况下很难满足各个条件。在这些条件之间，我们要结合实 际游戏需求综合起来考虑，如果能使总的搜索策略的综合性能比较好就行了。常 用的搜索方法分为盲目搜索和启发式搜索两大类。 2 1 图搜索 游戏中虚拟角色的寻路过程本质上就是遍历游戏地图中人为预先设置的含有 大量路点的地图，然后从中找出当前节点至目标节点的最短路径的过程。所以， 下面对图的相关知识包括图的相关概念以及图的搜索过程做个简单的介绍。 2 1 1 图的相关概念 一个图( g r a p h ) 是由一些节点和连接节点之间的连线所组成的阳1 。正规的定 义是：图g ( v ，e ) 是一个v 和e 组成的有限集合，其中，e 称为边( e d g e 也叫连 线) 的集合，v 称为顶点( v e r t i c e s 也叫节点) 的集合，而且e 集合中的每一条 边连接v 集合中两个节点，比如，i 和j 是这条连线所连接的两个节点，则可以用 ( i ，j