92 第 33 卷 AI 基本单位 (NPC) 的智能决策相互无关 ; 软件体系结构的设计要有高度的灵活性. 因此, 设计 AI 引擎的目标是 : 逻辑开发模块化工具化 ;AI 算法独立性插件化 ; 体系结构不依赖任何游戏类型且支持并行计算. 1.2 非形式构造根据文献 [1,4] 提出的非形

Size: px

Start display at page:

Download "92 第 33 卷 AI 基本单位 (NPC) 的智能决策相互无关 ; 软件体系结构的设计要有高度的灵活性. 因此, 设计 AI 引擎的目标是 : 逻辑开发模块化工具化 ;AI 算法独立性插件化 ; 体系结构不依赖任何游戏类型且支持并行计算. 1.2 非形式构造根据文献 [1,4] 提出的非形"

仟端
7 years ago
Views:

1 第 33 卷第 2 期 2012 年 3 月 JOURNALOFMINJIANGUNIVERSITY Vol.33No.2 Mar.2012 一种网络游戏 AI 引擎软件体系结构模型吴拥民 ( 闽江学院计算机科学系, 福建福州 ) 摘要 : 根据非形式化方法, 构造了 AI 引擎的软件体系结构模型.AI 引擎模型由物理视图进程视图开发视图和逻辑视图组成, 重点描述了逻辑视图中的 4 个层次 : 核心层服务层业务层与工具层, 最后对模型进行性能测试与评估. 关键词 : 网络游戏 ; 软件体系结构 ;AI 引擎 ; 非形式化构造中图分类号 :TP311 文献标识码 :A 文章编号 : (2012) AIenginesoftwarearchitecturemodelofMMOG WUYong min (DepartmentofComputerScience,MinjiangUniversity,Fuzhou,Fujian350108,China) Abstract:Basedonthewayofnon formal,aienginesoftwarearchitecturemodelisformed.aiengine modeliscomposedofphysicalview,procesview,developrmentviewandlogicalview.focusondescri binglogicalview,whichincludecorelayer,servelayer,busineslayer,toolslayer.finaly,themodel performanceistestedandevaluated. Keywords:MMOG;softwarearchitecture;AIengine;non formalmodeling 人工智能 (AI) 是大型网络游戏 (MMOG) 中不可或缺的有机组成部分.AI 主要有集中式和分布式两种类型. 无论采用哪种系统,AI 都作为一个独立的软件系统演化发展. 有必要系统地描述 AI 引擎的软件体系结构模型. MMOG 中的人工智能和学术界主流的人工智能理论研究, 在目标上并不完全相同. 学术界主流人工智能是研究人类智能活动的规律, 构造具有一定智能的人工系统, 研究如何让计算机去完成以往需要人的智力才能胜任的工作, 也就是研究如何应用计算机的软硬件来模拟人类某些智能行为的基本理论方法和技术 [2]. 比如模拟人的认知 ( 神经网络 ) 进化 ( 遗传算法 ) 或者交流理解 ( 自然语言处理 ). 相比之下,MMOG 中的人工智能更多是为了增加游戏的趣味性, 赋予非玩家控制角色 (NPC) 一些人类才有的行为特点. 因此, 在开发游戏中的人工智能时候, 要把注意力放在那些智能角色的表现上, 而不能陶醉于人工智能技术本身 [3]. 另一方面, 游戏玩家感受到的 AI 与我们研究的 MMOG 的 AI 也是有区别的. 例如, 游戏玩家看到 NPC 在运动中能逼真地做出适应地形的合理动作碰到弹性的障碍会被弹出, 理解为 AI. 实际上, 前者是物理系统, 后者是动作系统在起作用. MMOG 受计算规模与网络通信延迟的约束,AI 计算会根据游戏类型选择在服务端或客户端进行, 因此 MMOG 的 AI 具有分布性. 因游戏世界的利益问题, 在 MMOG 设计中有一条黄金定律 : 永远不要信任客户端的消息. 影响游戏公平性的 AI 计算都必须放在服务端, 客户端的 AI 计算只能是表现性的. 本文研究的 MMOG 的 AI 是在服务端计算的, 准确地定义 MMOG 的 AI 是本研究的前提. 1 AI 引擎的模型 1.1 设计理念 Wiener 从理论上指出, 所有的智能活动都是反馈机制的结果. 也就是说 AI 是由 2 部分构成的 : 决策与行为, 决策是智能算法, 行为是表现. 最简单的 AI 是一个状态机或自动机. MMOG 的多样性娱乐性以及软件体系结构由集中式向分布式演化, 要求 AI 引擎能支持复杂的逻辑开发, 收稿日期 : 基金项目 : 福建省教育厅科技项目 (JK ) 作者简介 : 吴拥民 (1968-), 男, 福建闽侯人, 闽江学院计算机科学系副教授.

2 92 第 33 卷 AI 基本单位 (NPC) 的智能决策相互无关 ; 软件体系结构的设计要有高度的灵活性. 因此, 设计 AI 引擎的目标是 : 逻辑开发模块化工具化 ;AI 算法独立性插件化 ; 体系结构不依赖任何游戏类型且支持并行计算. 1.2 非形式构造根据文献 [1,4] 提出的非形式化构造方法, 描述 MMOG 的 AI 引擎软件体系结构. 非形式化构造方法是一种基于 Kruchten 4+1 模型理论, 以 Medvidovic 的 ADL 框架形式化描述, 以 UML 表示配置结构中拓扑约束构件间的交互, 从整体描述软件体系结构的方法. Kruchten 4+1 模型由逻辑视图开发视图进程视图和物理视图组成, 并通过场景将这 4 个视图有机地结合起来, 比较细致地描述了需求和软件体系结构之间的关系. 每一个视图只关心系统的一个侧面, 所有视图结合在一起才能够反映系统的软件体系结构的全部内容 [5]. Medvidovic 的 ADL 框架为 :Softwarearchitecture={Components,Connectors,Configuration,Toolsupport}. 构件 (component) 可以是一个计算或数据存储的单元, 可能有自己的数据或存储空间. 连接器 (connector) 表示构件之间的相互作用和管理相互作用的规则. 配置结构 (configuration) 是以构件和连接器为元素描述软件体系结构的连接图 [6]. 以下从 4 个视图描述一种可以商业应用的网络游戏 AI 引擎软件体系结构模型物理视图该视图将软件映射到硬件上. 可以将 AI 引擎的全部进程部署或映射在同一个硬件上, 也可部署或映射在不同一个硬件上. 一种典型的映射 : 将消息收发进程与消息路由进程在部署或映射到网关服务器上, 将 n 个地图组进程部署或映射到 1 个工作服务器. 用 Medvidovic 的 ADL 框架描述如下 : 构件 : 网关服务器, 工作服务器 1 n; 连接器 : 节点之间的网络连接 ; 配置 : 如图 1 用 UML 的实施图表示了物理结构进程视图该视图进行进程分解, 表达了并行性和分布性问题. 由于强调并行计算,AI 引擎被设计成并行线程或进程的结构. 用 Medvidovic 的 ADL 框架描述如下 : 构件 : 消息收发进程, 消息路由进程, 工作组进程 1 n; 连接器 : 进程之间的 Socket 连接 ( 实现进程之间可靠的消息通信 ); 配置 : 图 2 用 UML 的构件图表示了进程结构开发视图该视图进行子系统分解, 子系统被组织成一个层级, 每一层提供一个充分而定义完整的接口给上一层. 我们 [7](25) 采用层次系统风格描述 AI 引擎的软件体系结构. 用图 1 AI 引擎的物理视图 Fig.1 AIenginephysicalview Medvidovic 的 ADL 框架描述如下 : 构件 : 核心包, 服务包, 插件包, 工具包 ; 连接器 :IPort,IServe,IPlugins,ITools; 配置 : 图 3 用模块图与 UML 的包图表示了开发结构. 图 2 AI 引擎的进程视图逻辑视图 Fig.2 AIengineprocesview 该视图进行面向对象的分解, 系统被分解为一个关键抽象集, 以对象或类简化了问题域. 逻辑视图是对开发视图的各层次进行了进一步的细化, 描述一个特定细化模型可以采用 UML 的类图对象图时序图协作图状态图和活动图等, 但清晰的表达并不需要以上全部的 UML 图. 因此, 我们根据需要选择不同的 UML 图表示 AI 引擎软件体系结构模型逻辑结构的 4 个层, 包 [7](22) 括 : 核心层服务层业务层和工具层. 我们采用了面向对象风格描述了 AI 引擎软件体系结构模型的逻辑结构. 1) 核心层 [8] 我们采用了消息队列系统设计了 AI 引擎核心层. 核心层主要实现服务层的服务线程化, 并自动注册到内核中, 这样并发线程之间的同步问题转化由消息通信机制来解决, 避免了线程间互斥问题. 这里内核的主要部分是一个消息路由 (MsgRouter), 它组合了 n 个的消息口 (IPort); 与微内核的消息通信机制不同 : 收发

3 第 2 期吴拥民 : 一种网络游戏 AI 引擎软件体系结构模型 93 消息的对象不是进程, 而是线程, 因此我们称之为服务 (Serve); 整个核心层对上一层提供一个抽象接口 (IServe), 上一层 ( 服务层 ) 中的服务对象只要继承该接口就可以很方便的注册到核心层中, 消息就可以通过消息路由转发, 这一点与通用路由器的原理没有什么不同. 用 Medvidovic 的 ADL 框架描述如下 : 构件 :MsgRouter,Serve; 连接器 :IPort,IServe; 配置 : 如图 4 用 UML 的类图表示了核心层的静态设计结构. 图 3 AI 引擎的开发视图 Fig.3 AIenginedevelopmentview 图 4 核心层消息路由的设计 Fig.4 Kernellayer designmsgrouter 2) 服务层服务层是为了实现并行计算, 每一个服务都有一个与之相对应的进程或线程关联, 且任何 2 个服务间都是线性无关的. 该层实现了界面服务 (ShelServe) 网络服务 (NetworkServe) 数据库服务 (DBServe) 地图组服务 (MapServe), 参见图 3. 其中, 网络服务提供了方便客户端进程连接机制 ; 数据库服务用于连接数据库服务器. [7](33) 采用基于事件的隐式调用系统风格设计了地图服务 (MapServe). 该系统风格存在一个和所有的构件相连接的框架构件, 所有的构件对象仅与框架联系而且互相独立. 构件对象需求其他构件对象的服务时, 向框架发出事件, 所有构件对象在框架注册自身响应的事件, 框架将事件广播或发往接受事件的构件对象. 该结构的优点是构件仅和框架有关, 构件的更新将不会影响其他的构件, 该结构还支持多个构件依次接受和响应一个事件. 在该例中, 框架构件是地图对象 (Map), 注册构件是模块 (xxxplugins), 连接器是消息触发的事件处理 (IPlugins::OnRcvMsg) 与插件定时器 (IPlugins::OnTimer), 地图服务通过消息事件调用驱动相应的模块, 执行标准的行为. 用 Medvidovic 的 ADL 框架描述如下 : 构件 :MapServe,Map,xxxPlugins; 连接器 :IServe,IPlugins::OnTimer,IPlugins::OnRcvMsg; 配置 : 如图 5 用 UML 的类图表示服务层的静态结构, 图 6 用 UML 的时序图表示服务层的动态过程. 3) 业务层该层采用插件容器进行模块化设计, 每个插件都可以自由得独立被加载和使用, 这方便了 AI 引擎的业务的定制扩充和移植. 主要的插件包含 : 实体插件逻辑插件 AI 算法插件与脚本引擎插件. 其中, 实体插件加载地图数据, 生成和销毁怪物对象玩家对象 NPC 对象, 提供 C++ 对象的 Lua 导出接口 ; 逻辑插件对实体插件算法插件 Lua 脚本引擎插件的接口进行集成, 实现怪物的业务逻辑功能, 提供 C++ 接口给 Lua 调用的 API;AI 算法插件实现了效率统计算法有限状态机算法模糊逻辑算法 A 星算法阵形算法遗传算法, 这些算法都是可配置的 ; 脚本引擎插件实现了启动 Lua 虚拟机加载运行 Lua 脚本, 编辑器控制插件通过接收工具层的可视化编辑器的消息对 AI 服务器进行远程控制, 例如 Lua 断点调试远程修改脚本动态刷怪修改状态机重启服务器, 它为工具层的编辑器开发提供基础支持. 用 Medvidovic 的 ADL 框架描述如下 : 构件 :EntityPlugin,LogicPlugin,AlgorithmPlugin,LuaPlugin,EditorPlugin; 连接器 :IPlugins::OnTimer,IPlugins::OnRcvMsg,IPlugins::GetData,IPlugins::Run;

4 94 第 33 卷图 5 服务层 MapServe 的静态设计结构 Fig.5 Servelayer staticclasdiagramofmapserve 图 6 服务层 MapServe 的动态调用序列 Fig.6 Servelayer dynamicsequencediagramofmapserve 配置 : 用 UML 的类图表示了插件结构 ( 见图 7). 4) 工具层该层主要完成一些根据不同网络游戏类型而经常变化的业务. 例如 :NPC 的分布 (NPC 在地图上的布局 ),NPC 的状态与变迁条件设置 ( 状态机编辑 ),NPC 行为个性化逻辑控制 (Lua 脚本的解析与调试 ) 等. 所有这些编辑的结果都以标准的 XML 脚本形式来描述, 并以消息方式传送给 AI 引擎. 用 Medvidovic 的 ADL 框架描述如下 : 构件 :NPCLayout,StateMachine,LuaParser&Debugger,ScriptManager; 连接器 :ITools::OnSndMsg,ITools::OnRcvMsg; 配置 : 如图 8 用 UML 的类图表示工具的设计. 图 7 业务层插件类图设计 Fig.7 Pluginlayer pluginclasdiagram 图 8 工具层功能类设计 Fig.8 Toolslayer functionclasdiagram 2 AI 引擎模型的应用我们已经在一个内部项目中成功应用该 AI 引擎, 该项目是为了展现 AI 引擎大规模计算能力与大量消息吞吐能力. 在项目中, 玩家扮演一个角色可以控制 500 个 NPC 的队伍, 而 NPC 队伍又可以分为若干个小队, 每个小队赋予不同状态机模型与任务行为, 任务行为通过不同的 AI 算法来控制,AI 算法的选择与状态机是可编辑的. 2.1 AI 引擎的性能测试为了分析 AI 引擎的性能, 对 AI 服务器的业务压力单位通信压力以及消息响应时间作了一组测试, 然

5 第 2 期吴拥民 : 一种网络游戏 AI 引擎软件体系结构模型 95 后分析比对测试数据, 评估 AI 服务器的负载能力. 测试是在 8 核 1.6G 的 CPU,4G 内存的物理服务器上进行,AI 服务器生成大量的怪物, 怪物基本上都处在走路或者跟敌对阵营的怪物战斗这样高度活跃的状态, 这样的业务压力会生成大量的消息跟游戏服务器进行通信. 笔者进行 4 次测试, 分不同的服务器部署和业务压力. 报告 1 和报告 2 的测试中 AI 服务器和游戏服务器部署在同一台物理机器上, 有不同的业务压力 ; 报告 3 和报告 4 的测试中 AI 服务器和游戏服务器分开部署在不同的物理机器. 其中报告 3 的测试是满负荷测试, CPU 的使用率接近 100%; 报告 4 的测试中, 业务压力和资源使用情况都适中, 是 AI 服务器的建议负载. 表 1 4 次测试的数据比对了某个时刻的采样数据 ( 采样周期 1 次 /10s) Tab.1 Aperiodoffourtestsampleddata(per10secondssampling) 维度测试 1 测试 2 测试 3 测试 4 活跃怪物总数 / 只当前发送消息总量 /( 条 /s) 最大发送消息总量 /( 条 /s) 当前接收消息总量 /( 条 /s) 最大接收消息总量 /( 条 /s) 当前消息吞吐总量 /( 条 /s) 最大消息吞吐总量 /( 条 /s) 当前响应时间平均值 /ms 平均响应时间平均值 /ms 最大响应时间平均值 /ms CPU 使用率 /% 内存使用率 /K 从表 1 看, 测试 1 和测试 2 的平均响应时间分别为 384ms 和 329ms, 资源使用量也比较低, 还可以增加业务压力 ; 测试 4 的平均响应时间为 1012ms, 资源使用率较高, 特别是 CPU 占用率高达 95% 以上, 达到了极限, 在这种情况下已无法增加业务压力了 ; 测试 4 的平均响应时间为 596ms, 资源使用率适中, 并预留了一定的 CPU 资源供其他业务使用. 2.2 AI 引擎的性能评估以上的测试结果是基于服务协同的分布式系统模型得出的, 游戏类型是 MMORPG [9]. 与其对比的是 MMORPG 的集中式系统模型, 活跃怪物的数量是 5000 只左右,CPU 的使用率是 15% 左右. 在集中式系统模型中, 业务是线性相关的, 所有业务是在一个线程或进程中, 无法充分利用 CPU 的多核性能,CPU 只有 1 个核得到充分的利用.MMORPG 中的怪物或 NPC 是除玩家之外最重要的角色, 但有一个黄金定律是 : 玩家永远优先. 也就是服务器在响应消息上, 应优先处理玩家的信息, 怪物或 NPC 信息处理 ( 又称为 AI, 包括对象的生成属性的更新行为的控制消息的发送 ) 都可以延迟. 因此 AI 业务就可能与其它业务无关, 且 AI 业务的粒度足够大, 可将其独立为一个 AI 服务器. 针对 MMOG 的游戏类型, 该 AI 引擎特别适应 RPG [10](291) 类型的游戏. 但因 NPC 的 AI 计算分布且存在消息延迟, 对强调及时客户响应的游戏类型 ( 例如 : RTS [10](290) ACT FTG 类型的游戏 ), 就明显响应不够. 在 MMORPG 中, 引入该 AI 引擎可以得到以下 3 点好处 :CPU 的多个核得到了充分地利用 ;NPC 的 AI 计算被分布了, 极大改善角色的业务计算性能, 提高对客户端的性能响应 ;NPC 的 AI 计算与角色的业务计算分别在不同进程中进行, 增强了 MMOG 服务器的容错性能. 参考文献 : [1] 吴拥民, 陈宏展.MMORPG 软件体系结构研究构造模型的演化 [J]. 昆明理工大学学报,2008,12(6): [2] 百度公司. 人工智能 [EB/OL].[ ]( )htp://baike.baidu.com/view/2949.htm. [3] 付恒. 基于多 Agent 系统的游戏 AI 引擎 [D]. 天津 : 天津大学,2007. [4] 吴拥民.MMORPG 软件体系结构研究非形式化构造 [J]. 计算机工程与应用,2006,42(32): [5]PhilippeK.The 4+1 viewmodelofsoftwarearchitecture[j].ieeesoftware,1995,12(6): [6]MedvidovicN,RichardNT.Aclasificationandcomparisonframeworkforsoftwarearchitecturedescriptionlanguages[J].IEEE TransactionsonSoftwareEngineering,2000,26(1): [7]ShawM,GarlanD.Softwarearchitecture:perspectivesonanemergingdiscipline[M].UpperSaddleRiver:PrenticeHal,1996. [8] 吴拥民, 张祖昌. 消息队列系统在 MMORPG 服务器软件体系结构中的应用 [J].,2007,28(5): [9]ThorAlexander.MasivelyMultiplayerGameDevelopment[M].NewtonCenter:CharlesRiverMediaInc,2003:1. [10][ 美 ]ErnestA,AndrewR. 游戏设计基础 [M]. 王鹏杰, 董西广, 霍建同, 译. 北京 : 机械工业出版社,2010. ( 责任编辑 : 唐诚 )

第 5 期吴拥民 : 三维引擎软件体系结构模型 101 3D 引擎分为实时 3D 引擎和离线 3D 引擎实时 3D 引擎能用 PC 机及游戏机即时计算出实时 3D 画面, 用多边形表示 3D 模型, 任何

第 5 期吴拥民 : 三维引擎软件体系结构模型 101 3D 引擎分为实时 3D 引擎和离线 3D 引擎实时 3D 引擎能用 PC 机及游戏机即时计算出实时 3D 画面, 用多边形表示 3D 模型, 任何第 33 卷第 5 期 2012 年 9 月闽江学院学报 JOURNALOFMINJIANGUNIVERSITY Vol.33No.5 Sep.2012 三维引擎软件体系结构模型吴拥民 ( 闽江学院计算机科学系, 福建福州 350121) 摘要 : 根据非形式化方法, 构造了三维引擎的软件体系结