3D角色游戏中AI引擎的设计与实现优秀毕业论文 参考文献 可复制黏贴.pdf

中图分类号： u d c ： 学校代码： 1 0 0 5 5 密级：公开 高越犬淫 硕士学位论文 3 d 角色游戏中赳引擎的设计与实现 t h ed e s i g na n di m p l e m e n to fa i e n g i n ef o r3 d r o l ep l a y g a m e 南开大学研究生院 二o 一一年五月 南开大学学位论文使用授权书 l 一1 呲y 帆2 吣0 0 叭m 2 m 2 刚9 l l 7 嗵 根据南开大学关于研究生学位论文收藏和利用管理办法，我校的博士、硕士学位 获得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范围内的学位论文使用权，即：( 1 ) 学位获得者必须按规定提交学位论文 ( 包括纸质印刷本及电子版) ，学校可以采用影印、缩印或其他复制手段保存研究生学位论 文，并编入南开大学博硕士学位论文全文数据库：( 2 ) 为教学和科研目的，学校可以将 公开的学位论文作为资料在图书馆等场所提供校内师生阅读，在校园网上提供论文目录检 索、文摘以及论文全文浏览、下载等免费信息服务：( 3 ) 根据教育部有关规定，南开大学向 教育部指定单位提交公开的学位论文；( 4 ) 学位论文作者授权学校向中国科技信息研究所和 中国学术期刊( 光盘) 电子出版社提交规定范围的学位论文及其电子版并收入相应学位论文 数据库，通过其相关网站对外进行信息服务。同时本人保留在其他媒体发表论文的权利。 非公开学位论文，保密期限内不向外提交和提供服务，解密后提交和服务同公开论文。 论文电子版提交至校图书馆网站：h t t p ：2 0 2 1 1 3 2 0 1 6 1 ：8 0 0 1 i n d e x h u n 。 本人承诺：本人的学位论文是在南开大学学习期间创作完成的作品，并已通过论文答 辩；提交的学位论文电子版与纸质本论文的内容一致，如因不同造成不良后果由本人自负。 本人同意遵守上述规定。本授权书签署一式两份，由研究生院和图书馆留存。 作者暨授权人签字： 高磊垃 2 0 1 1 i t 年5 月1 9 日i - - 4i，j， 南开大学研究生学位论文作者信息 论文题目 3 d 角色游戏中越引擎的设计与实现 姓名高秀坤学号 2 1 2 0 0 8 0 4 0 7 答辩日期2 0 1 1 年5 月1 9 日 论文类别博士口 学历硕士 硕士专业学位口高校教师口 同等学力硕士口 院系所信息技术与科学学院 专业 计算机应用技术 联系电话1 3 8 2 1 7 6 2 0 3 le m a i l r a k i t t e n y a h o o c n 通信地址( 邮编) ：天津市卫津路9 4 号南开大学西区公寓7 号楼( 3 0 0 0 7 1 ) 备注：是否批准为非公开论文否 注：本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写( 一式两份) 签字后交校图书 馆，非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行研究工作所 取得的研究成果。除文中已经注明引用的内容外，本学位论文的研究成果不包 含任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所 涉及的研究工作做出贡献的其他个人和集体，均己在文中以明确方式标明。本 学位论文原创性声明的法律责任由本人承担。 学位论文作者签名： 非公开学位论文标注说明 2 0 1 1 年5 月1 9 日 根据南开大学有关规定，非公开学位论文须经指导教师同意、作者本人申 请和相关部门批准方能标注。未经批准的均为公开学位论文，公开学位论文本 说明为空白。 论文题目 申请密级 口限制( 2 年)口秘密( 41 0 年)口机密( 2 0 年) 保密期限 2 0 年月日至2 0 年月 日 审批表编号批准日期2 0年月日 限制2 年( 最长2 年，可少于2 年) 秘密1 0 年( 最长5 年，可少于5 年) 机密2 0 年( 最长1 0 年，可少于l o 年) 摘要 摘要 网络游戏是一个生命力和活力都很强的产业。中国的网络游戏产业在日益 繁荣的同时，也面临着产品同质化严重、人才短缺等发展瓶颈。一款游戏想要 从激烈的竞争中脱颖而出，就要兼备挑战性和趣味性。而游戏a i ( a r t i f i c i a l i n t e l l i g e n c e ，人工智能) 对二者具有决定性的影响。本文旨在提供一个通用的 a i 引擎。一方面缩短触的开发时间，降低游戏的生产成本；另一方面使得游戏 开发者有更多的精力和时间设计游戏情节，从而提高游戏的趣味性和挑战性。 根据游戏中n p c ( n o n p l a y c r - c o n t r o l l c x lc h a r a c t e r ，非玩家控制角色) 、p d c ( p l a y e r - d r i v i e dc h a r a c t e r ，玩家驱动的角色) 、p c ( p l a y e rc h a r a c t e r ，玩家控制 的角色) 三种角色的行为特点，本文在a i 引擎中集成了逻辑控制、任务分配、 行为控制、群体行为控制、寻路等功能。其中逻辑控制通过脚本化的f s m ( f i n i t e s t a t em a c h i n e ，有限状态自动机) 实现，l u a 作为脚本语言。 在寻路模块本文提出了五种寻路算法：固定路径的查表法、导航网格的a 幸 算法、导航网格的b 奉算法、障碍物地图的a 枣算法、障碍物地图的b 宰算法等。 障碍物地图是室外场景分析法产生的地图。导航网格是3 d 场景中常用的一种场 景分析方法；而室外场景分析法则是本文提出的一种只记录障碍物数据的分析 方法。 最后本文将a i 引擎与t r i n i g y 游戏引擎结合以便对灿引擎的功能进行测试。 在测试游戏中，n p c 能够自动进行感知、行动；任务分配机制能够选择最合适 的p d c 执行玩家任务；玩家划定群体后，群体内角色能够逐渐聚拢到一起。查 表法和a 幸算法能找到最短路径，而b 幸算法的寻路效率更高。另一方面，寻路实 验的结果表明障碍物地图上的寻路明显快于导航网格上的寻路。 本文提出的a i 引擎很大程度地保证了其功能性和通用性。在脚本中实现游 戏的逻辑控制，使得灿引擎不受游戏情节的限制，同时又减轻了开发程序员的 工作量；寻路算法中查表法适用于固定路径，其它算法适用于无路径限制场景， 使得a l 引擎不受角色活动范围的限制；a 木算法精确，b 幸算法快速，可以满足不 同的寻路需求。 关键词：3 d 游戏人工智能寻路场景分析 a b s t r a c t a b s t r a c t o n l i n eg a m ei sav e r yl i v e l yi n d u s t r y i nc h i n a , t h ed e v e l o p m e n to fg a m e i n d u s t r yi sc u m b e r e df o rs o m er e a s o n s t h ea p p l i a n c eo fa ic o u l dm a k eag a m e m o r ei n t e r e s t i n ga n dc h a l l e n g e a b l e a ne n g i n eo fa ic o u l de a s et h ew o r k l o a do f d e v e l o p e r s t h i sp a p e rd e s i g n sa n di m p l e m e n t sa ne n g i n eo fa i i ti n c l u d e st h ec o n t r o lo f s i n g l er o l eo nl o g i c ，t h es t e e ro fs i n g l er o l ea n dc o l o n ya n dp a t h f i n d e r t h er o l e si n3 dg a m e sc a nb ea s s o r t e dt ot h r e et y p e s ：n p c ，p d ca n dp c t h e f s mi st h em o s tp o p u l a rt o o lt oi m p l e m e n tt h ec o n t r o lo f n p c c o n s i d e r i n gt h e l o g i co fn p ci sd e s i g n e db ys c e n a r i s t sn o tp r o g r a m e r , t h i sp a p e ro n l yp r o v i d e st h e m e c h a n i s mo f n p c ，t h el o g i c a lp a r ti si m p l e m e n t e db yd e v e l o p e r s t h e r ei sam a n a g e rt oa p p o i n tat a s kt oo n eo rs e v e r a lp d c w h e ni tr e c e i v e sa t a s k ，i tw o u l dc h o o s ear o l ew h i c hd i s t a n c ef r o mt h ep o s i t i o no ft a s ki st h el e a s t , t od e a lw i t ht h et a s k i ft h e r ei sn o ta n yf r e er o l e ，t h em a n a g e rw o u l dp u tt h et a s kt oa t a s k sq u e u e w h e nt h e r ei sf r e er o l e ，t h em a n a g e rw o u l dg e tt h ef i r s tt a s ki nt h e q u e u e , a n dc h o o s ear o l ef o r t h et a s k t h es t e e rs y s t e mi nr p gi sd i f f e r e n tf r o mt h es t e e ri nr a c eg a m e ac a rc a n c h a n g ei t ss p e e dc o n t i n u o u s l y , b u tar o l ei nr p g c a l lo n l yc h a n g ei t ss p e e df r o mo n e l e v e lt oa n o t h e rl e v e l s ot h i sp a p e rd e s i g n san e ws t e e rs y s t e mf o ra l lr o l e s t h er o l e i nt h i sa ie n g i n eh a sn e wa l g o r i t h m st os e e lf l e e ，p u r s u i t , e v a d ea n ds oo n t h e a l g o r i t h m so n l yc h a n g et h ed i r e c to f t h er o l et h es t e e rc o n t r o l s t h et r a d i t i o n a lf l o c ka l g o r i t h mi sn o td e s i g n e df o ras p e c i f i cc o l o n y , ai n d i v i d u a l r e g a r d si t sn e i g h b o r i n gu n i t sa n di t s e l fa sac o l o n y i nr p g t h em e m b e r so fac o l o n y i ss p e c i f i e db yt h ep l a y e r i t sn e c e s s a r yt oc h a n g et h ea l g o r i t h mt oc a l c u l a t ea e x p e c t a n tp o s i t i o nf o re v e r yr o l ei nt h ec o l o n y t h ec e n t r a lp a r to ft h i sp a p e ri sp a t h f i n d e rt h a ti n c l u d e ss c e n e - a n a l y s i sa n d p a t h f i n d t h i sp a p e rd e s i g na ne s p e c i a la n a l y s i sa l g o r i t h mf o re x t r a v e n t r i c u l a rs c e n e i nt h et r a d i t i o n a la l g o r i t h m ，t h ep a r tw h a ti sr e s e r v e db yt h ea n a l y s i si sp a s s a b l e b y i i a b s t r a c t c o n t r a r i e s ，i nt h en e wa l g o r i t h m , w eo n l yr e s e r v e st h ei n f o r m a t i o no fb a r r i e r s w e m a k eu s eo ft h ea n a l 如c a lg e o m e t r yt og e n e r a t eab a r r i e r s - m a pf z o mt r i a n g l e s m e s h t h ep a t h - f i n dc o n t a i n sf o u ra l g o r i t h m s t h ef i r s ti st a b l el o o k u pa p p l i e df o r a p t o t i cr o a d s e v e nt h o u g ht h e r em a yb es o m eb a r r i e r sc a nb er e m o v e d ，w ec o u l d u p d a t et h et a b l ea ss o o na sp o s s i b l e t h es e c o n di st h ei m p l e m e n to fb a l g o r i t h mi n n a v i g a t i o nm e s h , t h em a j o rc o n t e n ti st oj u d g ew h e t h e ra 鲥d i sa d j o i n i n gab a r r i o ro r n o t t h en l i r di st h ei m p l e m e n to fb 幸a l g o r i t h mi nb a r r i e r s m a p t h er e s u l to fb 宰 p a t h - f i n da l g o r i t h mi sn o tr e a s o n a b l ea p p a r e n t l y s o ，w ed e s i g na na l g o r i t h mb a s e d o na 木i nb a r r i e r s m a pi nt h ee n d t h em a j o rc o n t e n ti st od e s i g na ni n t e r i ms t r u c t u r e o fc o n n e c t e dg r a p hf r o mb a r r i e r s - m a p i no u re x p e r i m e n t s ，w et e s tc o r r e c t n e s so ft h ec o n t r o lo fs i n g l er o l eo nl o g i c ，a n d t h es t e e ro fs i n g l er o l ea n dc o l o n y c o m p a r i n gt h ea i nn a v i g a t i o nm e s h , t h e e f f i c i e n c yo f b 幸i sm o r eh i g h k e yw o r d s ：3 dg a m e ；a i ；p a t h f i n d i n g ；s c e n e a n a l y s i s i i i 目录 目录 摘要i a b s t r a c t 7 i i 目录 第一章绪论1 第一节研究背景1 1 1 1 网络游戏产业1 1 1 2m 研究热点3 第二节本文的研究内容及意义5 1 2 1 本文研究的内容。5 1 2 2 本文研究的意义。5 第三节本文内容的安排6 第二章相关工作7 第一节常用的逻辑控制方法7 第二节传统的s t e e r 系统9 2 2 1 个体s t e e r 行为9 2 2 2 群体行为1 0 第三节场景分析方法11 第四节经典寻路算法1 2 2 4 1d i j k s t r a 算法1 2 2 4 2a 算法1 3 2 4 3b 幸算法1 4 第三章a i 引擎的设计l5 目录 第一节a i 引擎的结构1 5 3 1 1 游戏角色的控制1 5 3 1 2 a i 引擎结构设计1 6 第二节逻辑和指挥系统17 3 2 1 逻辑控制1 7 3 2 2 行为控制1 9 3 2 3 群体的行为控制1 9 第三节路径规划系统2 0 3 3 1 室外场景分析2 l 3 3 2 场景分析系统结构。2 4 3 3 3 固定路径的寻路2 5 3 3 4 连续环境下的b 算法。2 8 3 3 5 精确寻路：3 l 3 3 6 路径规划系统的设计3 3 第四节本章总结3 3 第四章触引擎的实现。3 4 第一节a i 引擎与游戏引擎的接口一3 4 第二节角色控制的实现3 6 第三节a l 引擎的运行一3 7 第五章趾引擎的应用。3 8 第一节与游戏引擎的结合3 8 第二节a i 引擎的测试3 9 第六章总结及展望4 4 第一节本文总结4 4 第二节未来工作及展望4 5 参考文献4 6 v 致谢。 个人简历 第一章绪论 第一章绪论 第一节研究背景 1 1 1 网络游戏产业 “游戏是劳作后的休息和消遣，本身不带有任何目的性的一种行为活动。 这是古希腊哲学家亚里士多德对游戏的定义。随着生产力的提高，人们在工作 上投入的时间越来越少，使得人们有足够的时间用来休息和消遣；另一方面， 快节奏的生活又在无形中增加了人们的压力。近几年随着全球互联网的发展， 网络游戏因其类型丰富、互动性强而吸引了众多玩家。 根据新闻出版总署公布的( 2 0 0 9 年中国游戏产业报告( 摘要版) 显示，2 0 0 9 年中国互联网用户数达到3 5 3 亿，比2 0 0 8 年增长1 1 3 ；而同年网络游戏用户 数达到6 5 8 7 万，比2 0 0 8 年增加了3 3 4 6 。网络游戏用户增加速度显然高于互 联网用户增加速度。预计2 0 1 4 年中国网络游戏用户数将达到1 2 3 亿。在收入方 面，2 0 0 9 年，中国网络游戏市场实际销售收入为2 5 6 2 亿元人民币，比2 0 0 8 年 增长了3 9 4 。最新的数据显示，2 0 1 0 年，中国网络游戏市场实际销售收入为 3 2 3 7 亿元，比2 0 0 9 年增长了2 6 3 。预计2 0 1 4 年中国网络游戏市场实际销售 收入将达到5 0 8 亿元人民币【1 1 。网络游戏被称为互联网行业中利润最高的产业。 网络游戏按照游戏内容可分为三种类型：大型角色扮演类网络游戏( 如魔 兽世界) 、大中型休闲网络游戏( 如跑跑卡丁车、劲舞团) 、棋牌网络游戏如( 联 众、q q 游戏平台) 。2 0 0 9 年，中国大型角色扮演类网络游戏市场实际销售收入 为1 8 4 3 亿元，比2 0 0 8 年增长了2 2 2 。预计2 0 1 4 年中国大型角色扮演类网络 游戏市场实际销售收入将达到3 4 4 5 亿元人民币。占据了整个网游收入的 7 1 9 。 从画面类型上网络游戏可分为2 d 、2 5 d 、3 d 。本文的研究内容就是针对角 色扮演类3 d 游戏的。 从直观上说，a i ( a r t i f i c i f li n t d l i g e n c e ，人工智能) 就是代替人类思考的计 算机逻辑。比如棋牌类等人机对战游戏中，玩家的对手就是a i ；判断游戏输赢 的也是a i ，这相当于现实游戏中的裁判。 在最早的电子游戏中，玩家只能选择单人模式或双人模式。单人模式下就 】 第一章绪论 要由计算机与玩家对抗。对抗a l 有时直接是玩家的对手，如棋牌、赛车等竞赛 类游戏：有时体现为陷阱或奖励，如超级玛丽等动作游戏；有时隐藏在游戏逻 辑中，如连连看、对对碰等解谜游戏。 裁判a i 是任何电子游戏中不可缺少的，否则游戏就无法结束。如在五子棋 游戏中，舢要时刻判断是否有5 子连成一线。而在其它规则更复杂的棋牌类游 戏中，不仅要判断游戏是否结束，谁输谁赢，还要判断玩家能够移动的棋子以 及棋子能够移动到的位置，或者玩家能出的扑克。在动作游戏中要判断玩家碰 到的物体是陷阱还是奖励，或者玩家的生命是否用完。解谜游戏中如果不存在 可以移动的块，a i 还要将其打乱，使游戏可以进行下去。 可以说a i 几乎等同于游戏逻辑，而游戏逻辑是体现了一款游戏的个性。 原创剧情 l 兰竺兰三 匦 医历赢 回厘 田j 匝 厂翮l 厂丽f 程序 美术 安全防护 各级测试 除错 调试 创意卜一小说、史料、漫画 提案 制作 整合 掣p 兰竺坚竺丁丽 到旷磊磊 兰竺4 厮 竺型霜 兰墨兰鍪il 瓜jl jt n 沿壬卜 磊吾石习一 测试卜一游戏评估报告 著作权证书i( 发布游戏卜一输出海外 一语言翻译 _-_-_一 图1 1 网络游戏制作流程 随着游戏内容的丰富和游戏逻辑的复杂化，游戏的制作流程也越来越繁琐。 如图1 1 所示，游戏程序的开发只占其中很小一部分。而随着网络游戏市场的繁 2 冒露 辛 第一章绪论 荣，大大小小的网游公司也如雨后春笋般成立，导致网游市场竞争加剧。一方 面是程序复杂，要求较长的开发时间，另一方面却是巨大的竞争压力。游戏开 发者只能在保证程序运行的前提下压缩开发时间，忽略了游戏情节的设计和调 整。导致游戏情节雷同，同质化现象严重。 另一方面，开发时间短使得游戏情节不够丰富，游戏发布之后又不能随意 更改或增加游戏情节，很容易使玩家对游戏渐渐厌烦，失去兴趣。如果开发商 不能及时收回成本，不能及时对游戏出现的问题进行维护，游戏也会很快失去 生命力。 在游戏本身缺乏吸引力的情况下恶性竞争时有发生。近两年防沉迷系统上 线，国家又发布了反三俗规定。中国的网络游戏市场正走向更加健康的未来。 而开发周期长、生命周期短是游戏开发者必须攻克的两个难题。游戏引擎的使 用已经非常广泛，在一定程度上缩短了游戏开发时间。目前游戏引擎只提供渲 染、物理、g u i 方面的功能。对于游戏逻辑部分，不同的游戏其逻辑完全不同， 很难从全部游戏中提炼出a i 的共性来。目前还没有能够广泛应用的a i 引擎， 以及被广泛认可的灿引擎的标准定义。 1 1 2a l 研究热点 随着网络游戏的繁荣，游戏相关的计算机技术也在同步发展。在a i 方面， 已经形成了路径规划、f s m ( f i n i t es t a t em a c h i n e ，有限状态自动机) 等成形的 技术。 目前游戏中a i 的研究主要有以下几个方面： 1 高性能的路径规划系统 在路径规划方面已经有比较成形的技术，主要分为两方面：寻路算法和场 景分析。场景分析是对连续的空间进行分析，形成寻路的搜索空间。寻路算法 的研究集中在缩小搜索范围和提高底层数据的读取速度上。v i s h a lv e r m a 等人利 用减少寻路时额外存储空间的方法从侧面提高寻路效率【2 】。在网络游戏中，多 个玩家可以在同一场游戏中角逐，游戏中存在多个角色。多个角色的寻路请求 势必会影响程序的正常运行，一个角色也作为其他角色的障碍物而存在。着眼 于多角色系统d a v i ds i l v e r 提出了使用抽象层次信息的h i e r a r c h i c a lc o o p e r a t i v e a 宰( h c a ) 算法来提高传统a 幸算法的性能【3 】。r e n e ej a n s e n 等人通过记录方 向地图总结角色经过地图上各点的方向特点【4 】，减少了角色间碰撞的概率，从而 3 第一章绪论 减少了系统寻路的次数，提高了程序运行效率【5 1 。 蚁群算法在寻路方面的研究也很广泛。m a r c od o r i g o 等人首次提出了蚁群仿 生系统，并将其应用于求解t s p ( t r a v e l i n gs a l e s m a np r o b l e m ，旅行商问题) 【6 1 。 t h o m a s t u z l e 等人提出了最大最小系统，在解决t p s 问题时结果要优于一般的蚁 群算法【7 1 。蚁群算法的实际应用始终受到收敛性、停滞的影响。在游戏中，系统 对a i 性能的要求是很苛刻的，蚁群算法不适合在游戏中实现【8 】。 在场景分析方面，史红兵利用空间八叉树对3 d 场景进行分割，并根据空间 之间的连通性对场景进行通过性分析【9 】。k h a t i b 在研究自动机器人的工作中提出 了运用虚拟场的方法来使智能实体在向目标前进的同时动态地躲避障碍物【1 0 】。 n o s e r 等人在智能实体上使用合成视觉作为信息通道来对虚拟环境进行探测【1 1 】。 2 前沿a i 理论应用到游戏中 神经网络是一个模拟大脑功能的数学模型，核心思想是模拟动物神经系统 功能的学习方法，并可以做出最优或近似最优的反应【1 2 】。神经网络不需要考虑 问题的解决方法，它只关心系统的输入与输出之间的关系。但是，神经网络并 没有在游戏中得到普遍应用，主要因为：选择合适的输入输出比较困难，只能 凭感觉和经验：学习过程缓慢，需要大量时间不断调整；可能出现不理智、不 科学的行为【1 3 】。在一些特殊的游戏中，比如学习游戏和严肃游戏【1 4 1 ，在硬件有 余力的情况下，开始引入机器学习这类的方法，希望提升a i 的智能性【1 5 】。 3 针对系统的触技术 n a r e y e ka 在新加坡国立大学的研究小组则正在从事a u t o m a t e dc o n t e n t g e n e r a t i o n ( 自动场景生成) 、a u t o m a t e ds t o r y t e l l i n g ( 自动编剧) 、a d a p t i n gt ot h e p l a y e r ( 玩家自适应) 等方向的研究，这些研究从提升游戏开发的智能入手，提 高开发效率【l6 。 4 a i 引擎 在几种主流a i 技术逐渐成熟的同时，目前却还没有一个被普遍认可的a i 引擎出现，这就造成了游戏开发过程中，开发人员仍然需要从事最底层的算法 实现【1 7 1 。 4 第一章绪论 第二节本文的研究内容及意义 1 2 1 本文研究的内容 本文针对3 d 角色扮演游戏，设计并实现了一个通用的触引擎。主要包括： 1 对游戏中不同的角色进行分类，分析a i 功能的共性，整理出a i 引擎的 功能。设计a i 引擎的结构。 2 设计了角色逻辑的控制机制，实现了其脚本化方法。 3 实现了角色常见行为以及群体协作。 4 设计了功能全面的路径规划系统，实现了常用的a 幸算法，高效的b 奉算 法。提出了室外场景分析法及其适用寻路算法。适用于固定路径的查表寻路法。 5 实现了触引擎，并将其与t r i n i g y 游戏引擎结合进行了测试。 1 2 2 本文研究的意义 a i 含义里不仅有智能化，还有人性化。好的游戏通常由易而难分成若干个 级别。便于玩家入门；如果游戏总是特别容易就过关，势必会消磨玩家的兴趣； 反之，如果游戏总是超过玩家的能力，如棋牌游戏中电脑一方过于聪明，也会 让玩家知难而退，对游戏望而生畏。 对游戏的难度进行控制并不是一件容易的事，尤其是同一难度下还要进行 变化多样的布局。可以通过给玩家提示的方式降低难度。适当的帮助会给玩家 带来信心和勇气，从而使玩家继续将游戏玩下去。虽然本文的研究内容是针对 3 d 角色扮演游戏的，但是大多数网络游戏都是由单机游戏衍变而来，游戏中m 的基本思想没有过时。灿既要对抗玩家又要帮助玩家，目的是提高游戏的挑战 性和趣味性。 a i 对游戏的影响是很大的，灿通常由游戏策划者进行设计，软件开发人员 实现。一个通用的a i 引擎可以有效减少开发人员的工作量，通过脚本化的方式 让策划者参与到部分实现中，继而提高游戏中a i 的开发效率。也使得游戏发布 后的修改成为可能，继而增加游戏的挑战性和趣味性，延长游戏的生命周期。 目前国内还没有一个能广泛应用的m 引擎，因此，本文的研究内容对a i 引擎技术的发展具有一定的意义与价值。如果能广泛应用，将进一步促进国内 网游市场的发展以及游戏产品质量的提高。 5 第一章绪论 第三节本文内容的安排 本文的组织结构如下： 第1 章绪论：介绍灿引擎研究的背景，分析存在的问题，说明本文研究 的意义及内容，并对论文安排作了简要说明。 第2 章相关工作：介绍了相关工作，即本文的研究时采用的已存在的理论 和算法。并简要介绍了其原理。 第3 章a i 引擎的设计：分析游戏中常见角色的共性，据此提出趾引擎的 模块及结构。着重分析阐述了路径规划系统的设计，寻路算法的基本步骤及分 析。 第4 章a i 引擎的实现：本章对前文所设计的a i 引擎进行实现上，提供各 个模块的类图和主要流程图，以及与游戏引擎的接口设计。 第5 章a i 引擎的应用：与游戏引擎结合，展示部分实验结果，分析a i 引 擎的性能。 第6 章总结及展望：本章是论文的最后一部分，总结了全文的工作，并提 出进一步的工作方向。 6 第二章相关工作 第二章相关工作 第一节常用的逻辑控制方法 f s m 在游戏中被广泛用来控制n p c ( n o n p l a y e r - c o n t r o l l e dc h a r a c t e r ，非玩 家控制角色) 。在经典游戏“吃豆人中，玩家的任务是控制自己的角色避开所 有n p c 小鬼吃完屏幕上的小豆子过关。吃了大豆子可以反过来吃小鬼1 8 】。如图 2 1 所示，n p c 共有五种状态，状态之间的转换通过f s m 很直观的表现出来。 眼睛返回 h 重生3厂一叫黜j 0千 g h o s t 从中央屑间出来 追逐玩家 j玩家簪亡 中央房间 。p u r s u i t )； 玩家吃芊能量球 _ f 死亡j 糙p 【逃( e 志v a d e 家) j 图2 1 吃豆人游戏中n p c 的f s m f s m 最初是数学家用来解读问题的形式化工具，著名的图灵机就是一个代 表。f s m 原理在计算机领域的应用非常普遍，如编译器等等。这就使得f s m 技 术日渐成熟，设计模式【1 9 】一书中就提出了一种状态机的可复用面向对象模式； 另一方面，f s m 的广泛使用也使得程序开发者都非常熟悉f s m 的原理和使用。 使用f s m 是一种简单又可靠的方式。 将f s m 逻辑放在脚本中实现就可以将游戏逻辑和游戏程序的编译剥离开 来，在程序完成之后，仍然可以通过修改脚本来修改a i 逻辑，而不需要重新修 改代码。在著名游戏魔兽世界中就使用了l 岫作为辅助脚本。 l u a 从一开始就是作为一门方便嵌入其它应用程序并可扩展的轻量级脚本 语言来设计的，因此它一直遵从着简单、小巧、可移植、快速的原则，官方实 现完全采用a n s ic 编写，能以c 程序库的形式嵌入到宿主程序中【2 0 1 。宿主程 7 第二章相关工作 序可以调用l 眦中的函数，可以在l u a 脚本定义m 的主要逻辑函数，在宿主程 序中调用这些函数。以f s m 为例，在a i 引擎中只提供f s m 的接口，而各个状 态及状态转换等逻辑需要在游戏开发时在程序中或者脚本中来定义。 将逻辑放在脚本中实现就可以将游戏逻辑和游戏程序的编译剥离开来，在 程序完成之后，仍然可以通过修改脚本来修改触逻辑，而不需要重新修改代码。 图2 2 提供了一种l m 与c + + 配合实现f s m 机制的方法。f s m 中的状态通常会 有两个主要的内容：状态迁移条件( 假定为t r a s i t i o n f u n c o 函数) 和当前状态下 的行为( 假定为d o s o m e t h i n g ( ) 函数) 2 1 】。将这两个函数的实现放在脚本中，每 个状态的函数实现放在不同的脚本文件中。在c + + 程序中定义唯一的状态类的 结构，类中有一个字符串变量成员f i l e n a m e ，用来存放脚本文件名。在类中同样 定义t r a s i t i o n f u n c o 和d o s o m e t h i n g o 两个函数，但函数中不定义状态逻辑，而是 调用f i l e n a m e 脚本文件中的函数。在定义类的对象时，根据文件名的不同区分 不同的状态。 图2 2 脚本化的f s m 如图2 3 所示为f s m 的实现机制。其中f s m 类中的函数也是放在脚本 文件中实现的。在创建一个f s m 对象时，初始化函数从脚本文件中读取该f s m 中所有状态的脚本文件名，并为每一种状态定义一个对象，并把脚本文件中定 义的f s m 初始状态的对象指针赋值给m _ p c u r r e n t s t a t e 。本文的f s m 机制正是 基于此实现的，并根据实际需要修改了f s m 、s t a t e 中的函数。 8 第二章相关工作 g f s m s h t e g 队姥f s m mn s t a t e l d - m s t a t e s j l- ms t r t r a n s i t i o n m _ p c u r m n t s t a t c1 r - m _ s t r u p d a ( e + l n i t s t a t e ( )l + u p d a t e ( ) + t r a n s i t i o n ( ) + u d d a t d l 图2 3 脚本化f s m 的实现 第二节传统的s t e e r 系统 2 2 1 个体s t e e r 行为 s t e e r 又称为操控系统，是通用性非常高的一个模块。常用的s t e e r 行为有： s e e k f l e e ( 靠近离开) 、a r r i v e ( 到达) 、w a n d e r ( 徘徊) 、p u r s u i t e v a d e ( 追逐 逃避) 、o f f s e tp u r s u i t ( 固定偏移追逐) 、p a t hf o l l o w i n g ( 路径跟随) 、i n t e r p o s e ( 插入) 、h i d e ( 隐藏) 、w 甜la v o i d a n c e ( 避开墙) 、o b s t a c l e a v o i d a n c e ( 避开障 碍) 【2 2 1 。 s e e k 是靠近某一固定物体的行为，式2 1 2 3 说明了加速度的计算过程。f l e e 正相反，如式2 4 所示，但f l e e 通常离开该物体一定距离后就会停下来，不再考 虑该物体的影响。a r r i v e 与s e e k 行为类似，只是在到达目的物体时速度为零， 加速度如式2 5 所示。 d ( 1 ，如押) = d ( 哪d k ) 妇= 1 1 ，一i d ( k ) d ( q 献) = d ( 妇一) d ( 1 ，酗妇) = d ( 一c 醒d ) 口一2 昔2 币i v 6 - 1 a - r 夏e n 丁 ( 2 1 ) ( 2 2 ) ( 2 3 ) ( 2 4 ) ( 2 5 ) w a n d e r 就是角色无目的的随机移动，在连续环境下的解决方案是在角色前 方设置一个虚拟的圆，将角色的目标始终限制在该圆上。每次随机生成一个随 机的目标位置，并投影回圆周上。通过改变圆半径、圆到角色的距离，这个方 法产生的目标位置可以覆盖场景内所有范围。 9 第二章相关工作 当初次开始w a n d e r 行为时，需要计算当前的目标点： 啦d = + ( s 眦一尺砌) d ( 1 ，) 之后，每次计算需要计算新的目标位置： q 啦硝= + s 岫d ( 1 ，删) 一，哪甜= c 雄甜 只啦爿= d 腑+ 尺岫i ( 蜊+ j 赫) 一。岫l ( 2 6 ) ( 2 7 ) ( 2 8 ) ( 2 9 ) 计算出目标位置后再调用s e e k 行为，就是完整的w a n d e r 行为了。 p u r s u i t e v a d e 是对一个正在移动的物体进行s e e k f l e e ，这两个行为也是通 过预测和目标物体的相遇点，再对相遇点进行s e e k f l e e 实现的。式2 1 2 是e v a d e 行为的目标位置计算公式。 s 址删2 瓦= 而 ( 2 1 0 ) 只弼甜= k + 。垃脚 ( 2 1 1 ) c 啦d = + v 删。& 脾 ( 2 1 2 ) o f f s e tp u r s u i t 也可以成为跟随行为，追逐某一移动物体但保持距离，常用于 实现群体的行为。只需在预测目标点位置上加偏移量即可，得到最终的目标位 置，再进行s e e k 行为。 路径跟随本质上是对路径节点依次进行s e e k 行为，如果路径是封闭的，角 色到达终点后需要继续向起点移动。 i n t e r p o s e 行为是将角色插入两个移动物体之间，常用于足球运动员的截球。 该行为的目标点是角色到达两个物体连线的中点时的位置，求得目标位置后再 进行s e e k 行为。 而h i d e 行为的目标点是追逐者与障碍物连线的延长线上，到角色距离最短 的那一点。 w a l la v o i d a n c e 和o b s t a c l ea v o i d a n c e 行为都是通过在角色前面加一个虚拟 的触须实现的，