（计算机软件与理论专业论文）游戏软件中自主角色的设计和实现.pdf

目录 摘要 具有学习能力和动态适应环境变化的自主角色已经成为商业游戏的一个研究热点，采 用传统的基于规则的方法往往无法实现复杂的自主角色的行为，基于此，采用非确定性的 神经网络和遗传算法来实现自主角色已经成为当前游戏的一个热点，本文首先分析了游戏 自主角色的特点，接着通过认知建模来指导简单的非玩家控制角色的自主行为，最后利用 遗传算法优化b p 神经网络的方法设计和实现了一个游戏自主角色模型，并通过实验进行了 验证。本文工作对角色扮演类型游戏的开发具有参考价值。 本文共分为五章。第一章主要介绍本文的研究背景、主要研究内容及技术路线：第二 章主要是通过认知建模构建一个游戏角色的自主性模型；第三章讨论了神经网络和遗传算 法在自主角色实现中的方法；第四章描述了一个具有自主角色性的游戏原型系统，第五章 总结本文所做的研究工作，指出尚未解决和有待改进之处。 本文的主要成果是利用认知模型来指导非玩家控制角色的简单行为，利用动鼍改进b p 算法( 简称m b p 算法) 和遗传算法相结合来训练角色扮演类型游戏中非玩家控制角色对复杂 行为的学习，最终实现非玩家控制角色的自主行为。 关键词：自主角色认知模型人工神经网络遗传算法b p 算法 东南太学硕士学位论文 a b s t r a c t r e s e a r c h e s0 1 1t h et e c h n i q u e sf o rl e a r n i n ge n dr e a c t i n gt oc h a r a c t e rb e h a v i o ra r cc u r v e tr e s e a r c h c o n c e r o s a l t h o u g hm o s tg a m e ss t i l l u $ et r a n d i t i o n s lm e t h o d st os o l v eg a m ep r o b l e m , n o n - d e t e r m i n i s t i cm e t h o d sc a nf a c i l i t a t el e a r n i n ga n du n p r e d i c t a b l eg a m e p l a y , s ot h i s p a p e r # a c e sf o c u so nn o n - d e t e r m i n i s t i cm e t h o d st oc o n s t r u c tag a m ef r a m e w o r kb a s e do na l l t o n o n l o n s c h a r a c t e r f i r s t l y , t h ec u r r e n tr e s e a r c hd e v e l o p m e n to fs e l f - a u t o n o m o n si nv i d e og a m e sa n di t sm a i n c h a r a c t e r i s t i c sa r ea n a l y z e d s e c o n d l y ，b u s e do i lt h ea n a l y s i so fc o g n i t i v em o d e l ，a l lr e s o l v e n tf o r s i m p l es e l f - a u t o n o m o u si sp r o p o s e d t h i r d l y , b a s e do nm b p ( m o m e n t u mb a c kp r o p a g a t i o nn e u r a l n e t w o r ka l g o r i t h m ) e n dg a ( g e n c f i ca l g o r i t h m ) ，af r a m e w o r ko fs e l f - a u t o n o m o u ss y s t e mi s d e s i g n e da n di m p l e m e n t e d ，t h ef i a m e w o r kh a sb e e nv a l i d a t e dt h r o u g he x p e r i m e n t , m e a n w h i l e , i t i sh e l p f u lt od e v e l o pn o n e - p l a y e r - c h a r a c t e rg a m e t h i sp a p e rf a l l si n t o5c h a p t e r s t h ef i r s t c h a p t e r , a sa ni n t r o d u c t i o n ，m a i n l yi n t r o d u c e st h e r e s e a r c hb a c k g r o u n d ，s i g n i f i c a n c e , a sw e l la st e c h n o l o g i c a lm e t h o d s t h es e c o n dc h a p t e rm a i n l y i n t r o d u c e sc o g n i t i v em o d e l ，a n dm a k e sa r ta n a l y s i so ft h e o r i e so fc o g n i t i v em n d e l t h et h i r d c h a p t e rp r o p o s ead e s i g nm e t h o db a s e d0 1 1n e u r a ln e t w o r ka n dg e n e t i ca l g o r i t h mf o ra u t o n o m o u s c h a r a c t e r t h ef o u r t hc h a p t e rd e s i g n sa n di m p l e m e n t st h ef r a m e w o r ko fg a m ee n g n e e rb a s e do n a u t o n o m o u sc h a r a c t e r , t h el u s t c h a p t e r , a sac o n c l u s i o n 翻h n su pt h er e s e a r c hw o r kd o n e t h r o u g h o u tt h i sp a p e r , e n dm e n t i o n ss o m ea s p - t sr e m a i n i n gu n s o l v e do rr e q u i r i n gf u r t h e r i m p r o v e m e n t t h em a i nr e s e a r c h e sc o n t r i b u t e di nt h i sp a p e ri n c l u d et h ea n a l y s i so fs i m p l es e l f - a u t o n o m o u s b a s e do nt h e o r i e so fc o g n i t i v em o d e l ；t h ed e s i g ne n di m p l e m e n t a t i o no ft h ef r a m e w o r ko f c o m p l e xs e l f - a u t o n o m o u sb a s e d0 1 1m b p g aa r i t h m e t i c k e yw o r d s ： s e l f - a u t o n o m o n sr o l e , c o g n i t i v em o d e l ，a r t i f i c i a ln e u r a ln e t w o r k , g e n e t i ca l g o r i t h m , b a c k - p r o p a g a t i o na l g o r i t h m 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我 所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同 志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和 电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内 容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的 全部或部分内容。论文的公靠( 包括刊登) 授权东南大学研究尘院办理。 研究生签名：蓥壹 导师签名： 牲日期：甲；i 第一章绪论 第一章绪论 具有学习能力和动态适应环境变化的自主角色1 1 已经成为游戏软件的一个研究热点，采 用传统的基丁规则的方法往往无法实现复杂的自主角色的行为，基于此，本文采_ f j 非确定 性的神经网络和遗传算法相结合来尝试实现非玩家角色( n o n e - p l a y e ra m a c 慨简称n p c ) 的 自主性 1 1 研究背景及其意义 随着计算机图形学 2 1 和硬件技术的高速发展，计算机游戏近十几年也取得了很大的发 展，游戏软件已成为软件产业中非常重要的内容。游戏的类型主要包括f p s ( 第一人称射击， f i r s t p e r s o ns h o o t e r ) 、r p g ( 角色扮演类型，r o l e p l a y i n g g a m e ) 和r t s ( 即时战略游戏， r u n t i m es t r a t a g y ) 等几种类型p j ，这些不同类型的游戏都要求n p c 与玩家控制的角色要有行 为的交互，交互的方式直接影响玩家对游戏的兴趣度。因此，x c n p c 与玩家之间的角色交 互行为方式的研究已经成为游戏软件中的一个非常重要的研究课题。 目前大多数游戏中的角色行为的交互方式采用的是确定型的交互行为，其特征主要表 现在角色的行为都是预先确定的，这种类型的行为实现起来较为简单，也是目前大多数游 戏所采用的交互方式。象这种确定性的行为往往体现不出角色的自主性，而且还会导致角 色行动单调乏味，其行动很容易被玩家所预测，降低游戏的可玩性。为此，我们需要在游 戏软件中设计和实现这样的n p c 角色，它能够根据当前环境的变化以及以往的经验知识来 动态地改变对玩家的行为。具有这种能力的角色，我们称之为自主角色也称为自适戍角色 h 。具有自主特点的角色可具有推理能力和自适应能力，在游戏环境下可以提高游戏的可玩 性。 1 2 研究现状及分析 所谓自主角色是指具有学习能力和推理能力，能够根据环境的变化而动态改变自己行 为的角色，一个具有自主角色的游戏能够牢牢地吸引玩家的注意力，从而延长这个游戏的 生命周期，因此促使游戏开发人员花更多的时间来研究自主角色的实现。 关于游戏中自主角色的研究可以追溯到上世纪9 0 年代，对于自主角色的研究最早是应 用于r t s ( 即时战略游戏) 类璋! 的游戏”1 ，比如w a r c r a r 游戏首先引用了自主角色的设计， n p c 在该游戏中已经具备了选择多种行为的能力，但n p c 的预测能力较差”，在f p s ( 第一人 称射击游戏) 中，v a l v es o f t w a r e 公司的h a l f - l i f e 以它卓越的自主角色的实现而倍受好评， 但n p c 的学习效率不高。在r p g ( 角色扮演类型) 游戏中，s i e r r a 工作室的s w a t3 ：c l o s e q m _ r t e r sb a t t l e 游戏极好地表现了拟人的动作和交互方式，并且采用随机化的智能行为技术， 使得玩家在每次游戏中都得到新的体会；l i o n h e a ds t u d i o 开发的游戏b l a c k & w h i t e 采用了至 今为止最为先进的智能游戏技术来实现自主角色，尽管这款游戏并不是最早采用机器学习 技术的范例，但它无疑是最早成功运用智能技术的典范。也有的象著名的游戏c o l i nm c r a e r a l l y 2 则采用了学习系统和神经网络来实现角色的自主性。上述几款游戏都不同程度的实现 了n p c 的自主性，但e n p c 的预测能力以及学习能力上由于受到单一算法的限制( 这几种 游戏都是单独采用的神经网络算法) 而受到一些影响。 同国外游戏相比，国内自主研发的游戏在自主角色的实现上还处在起步阶段，相关工 东南大学硕士学位论文 作较少。 有关自主角色行为已经有很多做出了卓有成效的成绩，如在“1 中，对自主角色的群体行 为进行了描述。b l u m b e r g f l g a l y e a n 。1 中引入更多的行为控制机制，并考虑了行为学习这样 一个令人感兴趣的问题。对于自主角色的更高层次的认知能力方面，j o h n d a v i d f u n g 1 中 指出，认知模型是用丁二创建虚拟世界的模型“金字塔”的顶层，低层的行为模璋 作为认知 模型和物理学模型之间的缓冲区，并将情景演算( s i t u a t i o nc a l c u l u s ) “用于高度动态的虚拟 世界。 因此本文在原有的针对n p c 自主性的研究基础上，重点引入了神经网络和遗传算法相结 合来对n p c 自主角色进行深入的研究。 1 3 研究目标及内容 本文在研究n p c 的高级行为规划基础上研究游戏中n p c 的自主行为，目标就是使游戏 中的n p c 角色成为一个具有学习能力和自适应能力、可以自己的方式独立地对其所处的环 境作出动作和反应的自主角色。 研究的主要内容包括： ( 1 ) 利用认知建模方法，建立n p c 的认知模型，提高n p c 的自适应能力，实现具有认知能力 的n p c 的高级行为规划。n p c 的行为控制可以由两层完成：控制层和行动层，控制层的功 能由意图产生器实现根据当前周围环境条件和n p c 自身的精神状态产生n p c 的行动意 图而行动层则根据行动意图在行动指令集中选择合适的行动，从而使n p c 能够自主的实现 其行为活动。为了进一步提高n p c 的自主性，拟在n p c 现有的控制方案的顶层，利用认知 建模的方法增加基于n f c 逻辑的具有认知能力的高级行为规划层，从而能够在更高的抽 象层次上指导动画角色的行为。 ( 2 ) 基于神经网络和遗传算法优化的角色训练的研究，通过神经网络来建立n p c 的自学 习模型，使n p c 具有一定的基本识别能力和自适应能力，并且通过遗传算法来对n p c 的神 经网络进行优化，使n p c b p 神经网络能在环境中自主地进行学习。 ( 3 ) 游戏原型的设计和实现。本游戏原型的设计是基于我们专门为一家游戏培训机构所设 计的一个游戏框架，目前已经作为该培训机构的一个案例。本文主要研究该框架中的智能 角色部分的设计和实现，开发平台基于d o tn e t 2 0 0 3 ，开发语言采用v c n e t 。 1 a 研究方法和技术路线 针对角色及其环境模型的建立，拟采用认知建模的方法，通过认知建模来对n p c 的自主 性进行建模。 针对n p c 的自学习能力的研究拟采用多层前向反馈神经网络和遗传算法相结合的研究 方法。采用多层前向反馈神经网络处理学习问题，利用遗传算法优化神经网络演化的速度。 原型设计采用的是基y - c o m 组件的面向对象开发的方法，在开发中要大量运用d i r e c t x 开 发工具包，开发环境采用微软的v m u a ls t u i o n e t 2 0 0 3 。 1 5 本文组织安捧 本文共有五章。第一章主要介绍本文工作的研究背景、意义、内容、及其技术路线； 2 第一章绪论 第二章主要介绍了基于认知建模的n p c 自主性模犁；第三章研究了基于神经网络和遗传算 法的n p c 自主角色系统；第四章利用神经网络和遗传算法实现了一个n p c 自主角色的原型； 第五章总结本文所做的研究工作，指出尚未解决和有待改进之处。 1 6 本章小结 本章主要介绍了游戏中自主角色的概念和研究背景，引出文章要解决的问题。进而提 出了论文= 作的目标及解决的方法路线，作为论文进一步阐述的基础。 3 东南大学硕士学位论文 第二章基于认知建模的n - p c 自主模型 本文采用认知建模方法来对n p c 的自主性进行建模，通过认知建模方法研究n p c 的高级 行为规划，指导n p c ，提j 孙印c 的智能水平能力，使n p c 能够对环境作出判断，并根据当前的 状态进行推理，进而完成相应的行动序列，有利于创建具有认知能力的n p c 自主角色。因此 本章首先介绍游戏中的认知建模方法，在此基础上研究基于认知建模的- 眦自主模型。 2 1 游戏中的认知建模方法 加拿大多伦多大学的j o h nf u n g e 博士提出通过认知建模的方法【1 2 1 控制人工生命的行为。 在人工智能研究中，“认知模型”是以系统的领域知识及专家的经验为基础，运用知识表 示方法来建立的。建立认知模型常用的知识表达方法有：谓词逻辑表示、框架表示、语义网 络、产生式规则、典例表示、非单调表示、模糊表示。利用认知模型进行推理的类型有：演 绎、归纳、类比。基于知识的方法曾被广泛使用，但后来也受到了强烈的反对i l ”。原因是 它忽略了感知反馈的重要性。 另一个缺陷是因要求角色或机器人在行动之前应该做大量思考，而实现难度较大。j o h n f u n g e 强调了感知反馈是非常重要的，但是，如果有时间，角色应该利用它的认知模型尽量 在行动以前考虑充分将会发生什么。 在计算机游戏和动画中，可将动画角色关于其所在世界的内部模型称为“认知模型” ( c o g n i t i v e m o d e l ) 。认知模型可以用于动画和游戏中，控制一类自主的角色。通过认知模型支 配动画角色对其所在环境的了解程度，如何获取知识，以及如何利用知识选择行动。 在计算机游戏或动画中，我们将能够决定自己如何行动的角色定义为“自主角色” ( a u t o n o m o u sc h a r a c t e r ) 。为了能够建立一个自主角色，我们需要关于角色行为的计算模型。 同时，自主角色也需要对自己所处虚拟世界的某些知识具有明确表示。在最简单的情况下， 知识仅仅由一些变量表示，这些变量的值决定角色当前所处世界的状态。 另一种情况是，角色对于自己所处的虚拟世界如何变化具有显示表达的知识。我们将 有关其世界动力学的知识称为角色的“领域知识”( d o m a i nk n o w l e d g e ) 0 4 1 。为了将两种角色 区分开来，专门将具有领域知识的角色称为( 自主) 认知角色( c o g n i t i v ec h a r a c t e r s ) 。除非我 们对角色的领域知识如何表达特别关注，否则对角色一系列行动所产生的影响进行有效地 推理将是很困难的。问题在于，当我们凭直觉思考一种行动的效果时，利用了许多隐式的 常识性假设。例如，虽然有些事情是由某种行动产生的，但是我们并不明确指出，因为我 们假设这些事情的发生是很自然的。然而，典型计算机角色先天并不具有内嵌的常识：因此 当它们对自己世界进行推理时，不可能得出我们所期望的结论解决的方法是将我们自己的 一些常识概念嵌入到角色底层的框架结构中i l ”，用于表达其世界的动力学知识。 当然，认知模型仅仅是我们要创建的游戏这个虚拟世界所有模孳! 的顶部，其下面各层 对上层模型的设计也是有影响的计算机游戏中的认知层次模型如图2 - 1 所示。 4 第二章基于认知建模的n - p c 自主模型 图2 一i 认知层次模型图 认知建模是一种新的方法，它将计算机图形学与人工智能技术相结合，赋予游戏角色 所希望的行为能力，比已有方法达到更高的抽象水平，可广泛应用于交互式动画、机器人、 多媒体、虚拟现实及游戏产业。 2 2 基于认知建模的n p c 自主模型 采用认知建模方法，首先要确定n p c 的行为模型，所谓行为模型是指n p c 在生存活动过 程中，基于条件反射或非条件反射功能，由经验积累的行动规则和逻辑判断能力。接着要 设计高级行为规划器，它能使n p c 具有高级的行为规划能力，可在某种目标引导下，满足约 束条件，协调其行为。 2 2 1n p c 行为模型 在计算机游戏中，n p c 的行为可分为两种，一种是“确定性的”或“预定义的”行为i l ， 这种行为我们可以预先对他们在各种情况下应采取的行动进行定义。简单的n p c 的行为特 性往往是属丁二确定性的。但另一种行为是“非确定性的”，这种行为带有随机性i l ”。例如， 在虚拟游戏世界中，一些实力强大的n p c 会杀死实力较弱的n p c ，因此实力较弱的n p c 必须 设法逃避，这是预定义行为。如果没有足够大的障碍物可以躲避，弱的i x w p c 只能尽可能快和 远地逃离：如果在背景中加些障碍物，那么弱的n p c 可以利用障碍物来躲避敌人，这其中 就涉及到了非确定性的行为，要想实现具有真实感的n p c 行为，n p c 的行为必须具有非确定 性的特点。 其次，n p c 角色与其所在的虚拟世界是一个复杂的统一体。其中包括角色与环境的关 系，角色与其它角色的关系等【l q 。但是，影响n p c 当前行动的因素并不是整个虚拟世界。 例如，处于漫游状态而又没有其它外界干扰的n p c 当前感兴趣的只是寻找路径。 最后，n p c 应该具有“自学习”的能力。即从对各种行动影响的大量的观察中设法发 现反复出现的模式，根据发现的模式采取正确的行动1 1 。由于n p c 行为的特殊性，致使认 知模型也有其特殊性。首先，n p c 的行为分为“预定义的”和“随意性的”的两种，我们 建立的认知模型也各不相同。建立预定义行为的认知模型比较简单，只要将事先定义好的 n p c 所在环境的领域知识赋予n p c 系统，n p c 就可以根据人们的要求采取某种行动。而非确 定性的行为不容易控制。为了实现人为的控制。我们采取是一种折中的方法，即将领域知 5 东南大学硕士学位论文 识和人的指导赋予n p c t 2 0 】，住n p c 主动地向人们希望它达到的目标发展。 可由下面的公式表示： 知识+ 指导= 行为 领域知识能够_ i j 来规划目标口”，而指导对如何达到目标提供一种框架计划。n p c 的认 知模础是角色对其虚拟世界的一种内部简化模型( s i m p l i f i e d m o d e l ) 。n p c 能凭自己的能力 自动获取某些知识是一个重要的智力特征。n p c 的学习也是概念学习。需要为n p c 提供训练 集合、目标函数等口”。 从g v j n p c 认知特点的分析，我们对n p c 行为的模型示意图如图2 2 所示： 图2 2n p c 行为模型图 其中，领域知识通过自学习获得，主要指当前游戏世界的状态，例如，对方是朋友还 是敌人；如果遇到障碍物，该如何避开等等。内部刺激主要指n p c 的内部状态，例如，是否 处于战斗状态，是否处于受伤状态等。推理机制根据领域知识和内部刺激决定采取何种预 定义行为。突发事件可以有多个，例如，在同一时间既过来一个敌人，又出现了一位朋友， 那麽n p c 是要进入战斗状态还是进入对话状态取决于优先级的选择。如果预定义行为优先级 高，则继续执行预定义行为。在执行非确定性行为之前，要保存当前状态信息，如果非确 定行为执行完后，新的状态信息和保存的状态信息一致，则继续执行原来的预定义行为， 否则，重新规划新的预定义行为。每执行一步预定义行为或非确定性行为，都要进行领域 知识的感知，以便接受新的突发事件。 为了清楚地表达我们的想法，我们用精确的数学定义进行说明。当讨论认知模型时， 描述“什么将会发生”最有用的数学方法是数理逻辑田j 。我们使用标准有序一阶等值逻辑 来描述认知模型。 下面简要说明一下我们使用的符号。我们使用的标准逻辑符号有： ( 与) 、v ( 或) 、- 1 ( 非) 、= 争( 蕴涵) 、( 等价) 、= ( 相等) 。变量用斜体表示，例如：盂只z 。 同时，我们都将用下面这些标准符号作为参数：v ( 全称量词) ，j ( 存在量词) 6 第二章基于认知建模的n p c 自主模型 2 2 2n p c 预定义行为的表示 在游戏世界中的普通自主角色，它们并不具备领域知识，我们必须为它们在各种情况 下所应采取的行动进行预定义。在这种情况下，我们称角色的行为是“确定性的” ( d e “m i n i s t i c ) 或“预定义的”0 r c d e f i i l e d ) 。由丁：程序设计人员对预定义的行为已经预先 做了许多上作，所以运行速度很快。本文对n p c 预定义行为的表示方法结合情景演算和流 来实现，通过行动前提公理和作用公理来规划预定义行为。 ( 1 ) 情景演算( s i t u a t i o nc a l c u l u s ) 情景演算是一种用一阶逻辑描述改变世界的方法嘲。由于我们想让n p c 知道的是如何行 动，从而改变当前的状态，而情景演算被证明正好适合描述这些微妙变化及在知识表达中 发现的问题。特别是，情景演算为角色提供了其内部虚拟世界表示法的基本语义。 q ) 流( f l u e n t ) 随时间变化的事物被称为流 2 6 1 。流是一种函数，习惯上将状态条件作为参数。 例如有两个n p c 相遇，假设n p c i 与n p c 2 属于敌对状态，n p c i 主动攻击n p c 2 的条件是 n p c 当前的生命值应该大于零。我们可以将下面一些状态公式转化为情景演算。 u n k i n d ( s ，n p c 2 ) ：n p c i 在状态s 遇见的n p c 2 是敌人。 l i p ( s ) ：n p c i 在状态s 的生命值大于零。 f i g h t i n g ( s ，n p c 2 ) ：n p c i 在状态s 产生对n p c 2 的交战欲望。 在状态s 下行动发生的可能性由概率布尔值p o s s 口”来表示：a c t i o n s i t u a t i o n 。为 了简化问题的复杂性，通常情况下概率布尔值p o s s 的取值为真值，即为1 ，在执行某些行动 之前，用于指明当前世界状态的断言被称为前提公理( p r e c o n d i t i o na x i o m s ) 。在我们的例子 中，我们给出如下用于行动的公理： p o s s ( g o o d ，s 1 ：n p c 当前生命值大于零。 lo s s ( f i g h t ，s ) = u n k i n d ( s ) ：如果对面过来的角色是敌人，则攻击对方。 ( 3 ) 行动前提公理 行动前提公理给出了充要条件死( x ，s ) 对于行动a ( x ) 何时可以发生。它们的表现形 式如公式2 1 所示： ( x ，s ) j v o s s ( a ( x ) ，s ) ( 2 1 ) 例如，如果不考虑其它条件因素，上例中的必要条件集合也就成了一个充分条件集合。 在这种假设下，我们对于n p c 的前提公理就变成： p o s s ( f i 曲s ) 营u n k i n d ( s ) a h p ( s ) ：表示当对方是敌人时并且己方的生命值大于0 时，则攻 击对方 7 东南大学硕士学位论文 “) 作用公理 在执行了一个行动后，作用公理对于流所应取得的值给出了必要条件依据。在我们的 例子中，我们可以使用作用公理来说明行动c o m e ( 走过来一个n p c ) 对流的影响。 u n k i n d ( d o ( c o m e ，s ) ) ：走过来一个敌对n p c 。 p o s s ( h p ，s ) u n k i n d ( s ) f i g h t ( d o ( c o m e s ) ) ：如果走过来的是一个敌对g 孤p c 2 ，并且n p c i 生命值人于零，则n p c l 会r 、j n p c 2 产生交战的欲望。 2 2 3 基于认知建模的n p c 自主模型 在本文中，基于认知建模的n p c 自主模型主要体现为n p c 的自主战斗认知模型和非确 定性自主行为模型，下面分别介绍： 2 2 3 1b 盹的战斗认知模型 在r p g 游戏中，n p c 与对方( 玩家或另一n p c ) 的交互更多的是体现为相互战斗的状 态，在游戏刚开始运行时，首先n p c 要确定与对方是否是敌人抑或是朋友，在本中我们假定 n p c 需要通过学习才能确认对方的身份，当对方主动向n p c 发出友好的招呼时，n p c 会将 对方示为朋友，反之当对方主动攻击n p c 或者攻击n p c 的同类时，下次游戏运行时，n p c 会将对方作为敌人，该认知模型简单表示如图2 3 所示： 甲甲 t 走过来一个敌人健康值正常 n p c 推理 1 n p c 产生战斗欲望 反馈 1r 游戏环境 图2 - 3n p c 战斗认知模型示意图 8 第二章基于认知建模的n p c 自主模型 其中的数学表示如下： 相关流： i s v i s i o n ( s ) ：n p c 在状态s 下发现对方处于自己的视野范围内，通过调用n p c 的视野函 数来实现。 i s l i v i n g ( s ) ：n p c 在状态s 下是否处于激活状态 i s e n e m y ( s ，n p c 2 ) ：n p c i 将n p c 2 视为敌人。 f i g h t i n g ( s ) ：n p c 在状态s 下是否处r 战斗状态。 其中i s l i v i n g ( s ) 和f i g h t i n g ( s ) 为n p c 的内部状态参数，i s v i s i o n ( s ) 为感知获得的领域知 识。 行动的前提条件公理； 假定有下面的行动： c o m t s ： 走过来一个n p c 2 。 r o a m ：n p c i 在场景中漫游。 f i g h t ：n p c i 产生交战欲望。 在游戏中n p c i 产生交战欲望的充分必要条件是： 1 ) n p c 处于激活状态，即n p c 。健康值处于正常状态，既没有受伤，更没有死亡。 2 ) n p c ：是否处于n p c i 的可视范围。 3 ) n p c i 将n p c 2 作为敌人对待。 相应的前提条件公理为： p o s s ( f i g h t ，s ) l s l i v i n g ( s ) ai s v i s i o n ( s ) i s e n e m y ( s ) 。 行动的作用公理； 行动c o m e ( 走过来一个虚拟角色) 对流的影响之一( 走过来的n p c 是朋友) ： g o o d ( d o ( r o a m ，s ) ) ：n p c 在场景中漫游，且身体状况良好，可以交战或者对话。 f r i e n d c a r a e ( d o ( c o m e ，s ) ) ：从对面走过来的是一个朋友。 g o o d ( s ) af r i e n d c a m e ( s ) i s v i s i o n ( s ) j t a l k ( d o ( c o m e , s ) ) ：如果从对面走到n p c 视野范围内的虚拟角色是朋友，并且n p c 处于激活状态，则n p c 会与对方进行友好对 话。行动c o m e ( 走过来一个虚拟角色) 对流的影响之二( 走过来的n p c 是敌人) ： g o o d ( d o ( r o a m ，s ) ) ：n p c 在场景中漫游，且身体状况良好，可以交战或者对话。 - 1f d e n d c a m e ( d o ( c c ，s ) ) ：从对面走过来的是一个敌人。 g o o d ( s ) a _ 1 f d e n d c a m e ( s ) ai s v i s i o n ( s ) = ，1 t a l k ( d o ( c o m e ，s ) ) ：如果从对面走到 n p c 视野范围内的虚拟角色是朋友，并且n p c 处于激活状态，则n p c 会与对方处于 交战状态。 2 2 3 2n p c 非确定性行为的模型 n p c 的行为完全由它所执行的行动序列决定。我们可以将n p c 的行为分为两种：预定义 行为和面向目标的行为o ”。当然，从某种感觉上说，n p c 的所有行为都是程序员预先设定 的。因此，为了更加明确，我们引入区分预定义行为和面向目标行为的判断依据：n p c 的 行动是非确定性的还是确定性的。依据非确定性性行为选择，无i 仓n v c 什么时候选择行动， 它都要记得所有它能够作出的其它选择。 9 东南大学硕士学位论文 当n p c 考虑了某个行动方案后，如果它意识到此方案不能达到期望的输出时，那么它 可以返回，重新考虑其它可用方案，使得从其它选择中得到想要的结果。 n p c 的选择完全是自由的，直到找到一个合适的行动序列，或者己经搜寻过所有可用的方 案。对可以按非确定性方式行动的n p c ，比较容易接受指导，但响应时问比较慢。特别是 我们可以通过将目标提供给认知角色，告诉它满意结果的组成内容。n p c 因此能够利用自 己的领域知识，勾画出自己选择的行动序列是否能够达到目标要求。 我们考虑的第三个可能性是在预定义的行动和面向目标的行动之间的某些折中方案。 我们引入复杂行动的概念，_ j _ 丁：解释它们如何能够朋于提供目标以及规划完成目标的计划。 描述面向目标行为的第一步是引出定义认知角色目标的方法。n p c 的目标能够依据与其相 关的流值来表达。冈此，目标可以表示为被定义的流，例如，一个流依据其他流来定义。 例如，n p c 的目标是战胜玩家： g o a l ( s ) k i l l ( s ) 为了说明n p c 如何能够自动得到完成目标的行动序列，我们引入情景树。我们可以将行 动和影响看成是描述未来可能状态的树，树根是初始状态s o 。树的每个分支是一个行动，每 一个节点是一个状态。 每个节点流的值由作用公理决定。目标状态是一种情景，此时目标流( g o a l ) 的值为真。 通常，并不保证每一个目标状态完全存在。如果目标状态存在，那么任何完成目标的行动 序列就称为一个计划。 对于预定义行为，无须进行任何搜索就可以达到目标，仅简单的依据指令完成任务。 因此对于一个给定的输入集，通过情景树的路径就事先被确认下来。如果这个预定义行为 定义的合适，那麽他们通过树的路径就可以到达最佳状态。 对于情景树，我们可以采用传统的广度优先搜索和深度优先搜索以及启发式搜索。广 度优先搜索口9 j 是在进入下一层之前将每一层的节点都搜索到。就是说，先考虑所有长度0 的 计划，然后是长度1 的计划等。因此，广度搜索保证只要存在计划就一定能够找到，并且也 能够找到最短的计划。但是广度搜索需要耗费大量内存存储角色已有的搜索状态。而对于 深度优先就不需要这样多的额外内存，因为它并不保存大量的树信息。也就是说，深度优 先搜索”w 一次只需要保存一个分支的信息，它始终注意一个分支直到得到目标或到达叶子 节点。不幸的是，即使有一个目标存在，深度优先搜索也不能够保证找得到。特别地，可 能树的分支是无穷的。这样n p c 仅能够执行一些行动序列，但永远无法达到目标。因为树很 可能有一个无限分支，n p c 可能永远无法达到目标或到达叶子节点，所以程序永远无法结束。 深度优先另一个缺点就是：即使能够找到计划，也不能够保证是最短的。 因此我们决定采用神经网络和遗传算法来处理情景树，下一章我们将研究神经网络和 遗传算法在n p c 自主系统中的应用 2 3 本章小结 在游戏设计中，人们希望控制n p c 的行为进程，也就是在更高级别上指导n p c 的行为。 为此我们在现有游戏系统之上建造一个高级行为规划器实现对n p c 的行为指导。 高级行为规划器的核心是n p c 的认知模型，n p c 的认知模型是游戏角色关于它所在世界 的内部模型。根据n p c 认知的特点，我们将n p c 的认知模型分为预定义行为模型和非确定行 为模型。 本章，我们建立了n p c 的预定义行为模型，并用情景演算和流相结合的方法进行描述， 建立了n p c 的战斗认知模型。对于随意性行为，我们通过加入指导来完成对情景树的搜索。 虽然认知模型能够很好的处理预定义行为以及通过简单推理来实现的- c 非确定性行 为，但是对于涉及到较多复杂因素的非确定行为，则不能够有效的处理，第三章将讨论如 l o 第二章基于认知建模的n p c 自主模型 何利用神经网络和遗传算法相结合来处理涉及到较多复杂冈素的非确定行为。 东南大学硕士学位论文 第三章基于神经网络和遗传算法的n p c 自主角色系统 在角色扮演类型游戏中，生活在虚拟游戏世界中的n p c 往往种类繁多，相互之间关系复 杂。受着环境因素的影响，一个具有自主能力的n p c 应该会产生各种变化，以便适应环境。 在游戏中我们常见的n p c 行为有漫游、对话、攻击、躲避、逃跑等等”“。这些行为是对自身、 时间和环境条件的变化而产生的反应，传统游戏往往采用一些确定性算法比如决策树，有限状 态机等算法来实现角色的自主能力，当影响角色的行为属性很有限，且属性之间的关系是线 性可控时，确定性算法还是很有效的，但随着现代游戏日益复杂，影响角色自主决策的因素 也随之增多，并且相互之间的关系很难预测，确定性算法处理这类问题则显得有些力不从 心，因此本章尝试通过遗传算法和神经网络相结合的方法来实现游戏中n p c 自主角色系统， 具体先是通过改进后的b p 神经网络算法来训练n p c 神经网络，经过若干次迭代后形成一组权 重集，接着通过遗传算法对这些权重进行相应的训练，最终形成一个n p c 自主角色系统。本章 共分为四个小节，第- - d , 节说明了自主角色的系统构成；第二小节设计了一个n p c 的神经网 络结构；第三小节提出了一个基于遗传算法的n p c 神经网络优化的思路；第四小节对本章作 了一个总结。 3 1n p c 自主角色系统构成 3 1 1n p c 的组成 角色扮演类型游戏中的n p c 由四部分组成：运动系统、感知系统、决策系统和行为系统 3 3 1 见图3 1 所示： 图3 1n p c 内部结构图 运动系统包括基于物理的模型和一组运动控制器，这些运动控制器构成n p c 的运动控制 中心运动控制器是参数化的进程，可将控制参数，如：前进速度、转动角度以及攻击行为 第三章基于神经网络和遗传算法的n p c 自主角色系统 转化为n p c 的动作。运动系统是n p c 实现各种行为功能的基础。 感知系统依靠一组在线的虚拟传感器，提供有关动态环境的感知信息。 决策系统根据通过感知系统输入的感知信息进行学习，推理和分析，最终通过输出参 数来确定n p c 的行为”。 n p c 的行为系统介于它的决策系统和运动系统之间。行为系统将习性与感知信息结合 起来，可以产生n p c 的动态意图，如：战斗、逃跑及求援等。 n p c 的内部结构中体t e n p c 自主性的部分就是决策系统，本文也重点研究n p c 的决策系 统。在本文中，n p c 的决策系统是通过神经网络和遗传算法相结合的框架来实现的。 3 1 2n p c 行为决策的影响因素 在游戏中n p c 的自主性是通过其行为而体现的，根据n p c 行为的特点，我们将n p c 的行 为分为预定义的规则确定的行为( 预定义行为) 和通过学习而形成的规则确定的行为( 非确 定性行为) 。 在游戏中不管何种类型的n p c ，都有一些确定性行为，现举出几例n p c 角色在游戏中 的确定性行为： ( 1 ) n p c 应该具有识别障碍物的能力，当遇到障碍物时，n p c 会绕开。 ( 2 ) 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 的自主行为主要体现在它的非确定性行为上，因此本文研究i 鬟j n p c 的自主能力 主要也是通过n p c 的确定性行为所体现。 n p c 的行为决策能力越强，意味着n p c 的自主性越高，在角色扮演类型游戏中，角 色之间的关系更多是体现为战斗的关系，因此决策过程中最重要的因素是对战斗形势和打 斗过程的描述p “。具体包含以下几个因素： 1 ) 玩家当前状态 决策本来就很具有主观性，玩家角色的状态极大地影响了游戏的结局，比如，身体 状况和装备等级都可能影响决策的制定，武器和弹药同样也会对此产生影响，甚至是玩 家的货物清单中的其他物品都可能成为影响决策的因素。 2 ) 敌人当前状态 在死亡竞赛游戏中，也会根据其他n p c 的当前状态作出决策：敌人的可