第３０卷第２期 ２０１０年４月 南京邮电大学学报（自然科学版） Ｊｏｕｒｎａｌ ｏｆ Ｎａｎｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｐｏｓｔｓ ａｎｄ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ（Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ） Ｖｏ１．３０ Ｎｏ．２ Ａｐｒ．２０１０ 基于ＯＧＲＥ的智能游戏引擎的设计与实现 林巧民 一，林 萍 ，王汝传 厂１．南京邮电大学软件学院，江苏南京２１００４６ 、 ｌ ２．南京邮电大学数字媒体研究中心，江苏南京２１００４６ Ｉ ３．南京邮电大学计算机学院，江苏南京２１００４６ 摘要：基于ＯＧＲＥ（Ｏｂｊｅｃｔ—ｏｒｉｅｎｔｅｄ Ｇｒａｐｈｉｃｓ Ｒｅｎｄｅｒｉｎｇ Ｅｎｇｉｎｅ）设计并实现了一个智能游戏引擎ＯＩＧＥ（ＯＧＲＥ—ｂａｓｅｄ Ｉｎｔｅｌｌｉｇｅｎｔ Ｇａｍｅ Ｅｎｇｉｎｅ），ＯＩＧＥ具有较完善的功能，包含游戏开发各个环节所需的关键模块，如人工智能系统、网络 系统、物理系统、声音系统、输入系统等，ＯＩＧＥ采用面向对象机制来设计和实现，以保证系统结构清晰且具有良好 的可扩展性。详细分析ＯＧＲＥ渲染系统和介绍ＡＩ智能系统的设计和实现，此外，基于ＯＩＧＥ引擎开发了一个简单 的小游戏，对系统功能进行了初步验证。 关键词：游戏引擎；面向对象的图形渲染引擎；人工智能 中图分类号：ＴＰ３７ 文献标识码：Ｂ 文章编号：１６７３－５４３９（２０１０）０２－００７１－０６ Ｔｈｅ Ｄｅｓｉｇｎ ａｎｄ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ａｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｇａｍｅ Ｅｎｇｉｎｅ Ｂａｓｅｄ ｏｎ ＯＧＲＥ ＬＩＮ Ｑｉａｏ－ａｉｒｎ 一，ＬＩＮ Ｐｉｎｇ ，ＷＡＮＧ Ｒｕ．ｃｈｕａｎ。 ｒ １．Ｃｏｌｌｅｇｅ ｏｆ Ｓｏｔｆｗａｒｅ，Ｎａｍｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｐｏｓｔｓ ａｎｄ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｎａｍｉｎｇ ２１００４６，Ｃｈｉｎａ ３．Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ，Ｎａｎｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｐｏｓｔｓ ａｎｄ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｎａｎｊｉｎｇ ２１００４６，Ｃｈｉｎａ 、 ｌ ２．Ｄｉｇｉｔａｌ Ｍｅｄｉａ Ｒｅｓｅａｒｃｈ Ｃｅｎｔｅｒ，Ｎａｎｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｐｏｓｔｓ ａｎｄ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｎａｍｉｎｇ ２１００４６，Ｃｈｉｎａ Ｉ Ａｂｓｔｒａｃｔ：Ｔｈｅ ｄｅｓｉｇｎ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ａｎ ＯＧＲＥ—ｂａｓｅｄ Ｉｎｔｅｌｌｉｇｅｎｔ Ｇａｍｅ Ｅｎｇｉｎｅ（ＯＩＧＥ）ｉｓ ｐｒｅｓｅｎ— ｔｅｄ．ＯＩＧＥ ｈａｓ ｖｅｒｓａｔｉｌｅ ｆｕｎｃｔｉｏｎｓ ｓｕｃｈ ａｓ ａｒｔｉｉｃｉｆａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ，ｎｅｔｗｏｒｋ ｃｏｍｍｕｎｉｃａｔｉｏｎ，ｐｈｙｓｉｃａｌ ｓｉｍｕｌａ— ｔｉｏｎ，ａｕｄｉｏ ｓｙｓｔｅｍ ａｎｄ ｉｎｐｕｔ ｓｙｓｔｅｍ，ｗｈｉｃｈ ａｒｅ ｋｅｙ ｔｏ ｔｈｅ ｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ｇａｍｅｓ．Ｏｂｊｅｃｔ—ｏｒｉｅｎｔｅｄ ｍｅｃｈａ— ｎｉｓｍ ｉｓ ｏｂｓｅｒｖｅｄ ｄｕｒｉｎｇ ｔｈｅ ｄｅｓｉｇｎ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ＯＩＧＥ ＳＯ ａｓ ｔｏ ｍａｋｅ ｔｈｅ ｓｙｓｔｅｍ ｌｅｇｉｂｌｅ ａｎｄ ｅｘ・ ｔｅｎｓｉｂｔｅ．ＯＧＲＥ ｒｅｎｄｅｒｉｎｇ ｓｙｓｔｅｍ，ＡＩ ｄｅｓｉｇｎ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ａｒｅ ａｎａｌｙｚｅｄ ｉｎ ｄｅｔａｉｌ．Ｂｅｓｉｄｅｓ，ａ ｓｉｍｐｌｅ ｇａｍｅ ｄｅｖｅｌｏｐｅｄ ｂａｓｅｄ ｏｎ ＯＩＧＥ ｉｓ ｄｅｍｏｎｓｔｒａｔｅｄ ｔｏ ｔｅｓｔｉｆｙ ｔｈｅ ｓｙｓｔｅｍｇ ｃｏｒｒｅｃｔｎｅｓｓ． Ｋｅｙ ｗｏｒｄｓ：ｇａｍｅ ｅｎｇｉｎｅ；ｏｂｊｅｃｔ—ｏｒｉｅｎｔｅｄ ｇｒａｐｈｉｃｓ ｒｅｎｄｅｒｉｎｇ ｅｎｇｉｎｅ；ａｒｔｉｉｆｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ ０ 引 言 近年来国内的游戏引擎技术有了较快发展，如 《武林外传》、《完美世界》和《赤壁》等网络游戏的 支撑引擎为北京完美时空公司自主研发的Ａｎｇｅｌｉ— ｃａ，２００８年３月出口新加坡的ＯｖｅｒＭａｘ引擎更是开 前市场上主流的游戏引擎基本上为外国所垄断，如 ＭＡＸ—ＦＸ，Ｇｅｏ．Ｍｏｄ，Ｑｕａｋｅ ＩＩＩ ，Ｓｅｒｉｏｕｓ，Ｕｎｒｅａｌ３ 等。以《机战》、《征服》、《魔域》、《投名状Ｏｎｌｉｎｅ）） 等网络游戏开发而闻名的网龙公司，一直着眼于国 外市场，虽旗下几款游戏在欧美网络游戏市场皆有 良好的运营业绩，但这些游戏都是基于巨资购买的 Ｕｎｒｅａｌ３引擎开发出来的，显然，加快研发具有自主 知识产权的游戏引擎技术对发展我国游戏动漫产业 创了我国游戏引擎出口的先河。不过，与国外的游 戏引擎技术研发相比，国内的差距还是明显的。目 收稿日期：２００９一ｌＯ－２９ 基金项目：国家自然科学基金（６０５７３１４１，６０７７３０４１）、国家高技术研究发展计划（８６３计划）（２００７ＡＡ０１Ｚ４０４，２００７ＡＡ０１ＺＡ７８）、江苏省高技术研 究计划（ＢＧ２００６００１）、南京市高科技项目（２００７软资１２７）、现代通信国家重点实验室基金（９１４０Ｃ１１０５０４０８０５）、江苏省高校科技创新 计划基金（ＣＸ０８Ｂ４）８５Ｚ，ＣＸ０８Ｂ￣８６Ｚ）、南京邮电大学科研基金（ＮＹ２０６０３０）资助项目 通讯作者：王汝传电话：（０２５）８３８０６００１ Ｅ－ｍａｉｌ：ｗａｎｇｒｃ＠ｎｊｕｐｔ．ｅｄｕ．ｃｎ ７２ 南京邮电大学学报（自然科学版） ２０１０年 具有重要的现实意义。 那么，什么是游戏引擎？其实，无论是２Ｄ游戏 还是３Ｄ游戏，无论是角色扮演游戏（ＲＰＧ）、即时策 略游戏、冒险解谜游戏或是动作射击游戏，哪怕是一 个只有几ｋ的小游戏，都有那样一段起控制作用的 代码，它就是引擎，经过不断的进化，如今的游戏引 擎已经发展为一套由多个子系统共同构成的复杂 系统 。 １ ＯＩＧＥ引擎架构 游戏引擎是游戏的“心脏”，整个游戏（甚至是 一系列游戏）的性能表现直接依赖它，它把游戏中 的所有关键元素，如渲染系统 Ｊ、智能系统、网络通 信、碰撞检测 、声效和输入输出等，有机结合在一 起，引导它们有序、协调工作。由于游戏引擎牵涉面 较广，ＯＩＧＥ引擎的设计中采用了一部分已有的开源 系统（ＯＧＲＥ 、ＯＤＥ 等），如图１所示。 图１ ＯＩＧＥ引擎架构 渲染系统是整个游戏引擎中非常关键的一个模 块，担负着游戏画面的实时渲染工作，ＯＩＧＥ采用了 ＯＧＲＥ。ＯＧＲＥ是用Ｃ＋＋编写的面向对象且使用灵 活的３Ｄ渲染器，它可以帮助开发者更方便和直接 地基于３Ｄ硬件设备进行游戏或动画的制作。 ＯＧＲＥ中类库是对底层系统库（如Ｄｉｒｅｃｔ３Ｄ和Ｏｐｅｎ． ＧＬ）的封装，并提供了基于现实世界对象的接口和 其它相关类。 人工智能系统（ＡＩ）负责处理游戏中的逻辑，譬 如场景中角色间的群集、追逐或者躲避，以及通过归 属函数 来模糊化角色的反应等，降低游戏的可预 测性，提高玩家兴致。 网络系统（ＮＳ）是一个基于ＵＤＰ网络传输协议 实现的Ｃ＋＋网络库，它提供一组网络相关的应用程 序编程接口，即ＡＰＩ，利用它可以快速建立套接字连 接并进行游戏数据包的传送，实现高效的网络传输 服务。 物理系统采用ＯＤＥ（ｏｐｅｎ ｄｙｎａｍｉｃｓ ｅｎ￣ｎｅ）。 ＯＤＥ是一个开源的物理引擎，支持不同的图形库 （Ｄｉｒｅｃｔ３Ｄ以及ＯｐｅｎＧＬ），可以对真实对象的物理特 性进行仿真，也可以用来对合成环境中的各种对象 （如三维游戏环境中的人物或虚拟驾驶中的交通工 具）进行建模，不但速度快，而且还可以进行实时的 碰撞检测，它支持各种碰撞原语（例如球面碰撞和 平面碰撞）。ＯＤＥ采用Ｃ＋＋编写并提供了清晰的 接口，因此可以很方便地与ＯＧＲＥ系统进行插件式 集成。 声音系统和输入系统均直接选用微软公司的 ＤｉｒｅｃｔＸ序列中的Ｄｉ一ｒ一ｅｃｔＡｕｄｉ一ｏ Ｄｉ一一ｒｅｃｔＳｏｕｎｄ以及Ｄｉ一 － ｒｅｃｔＩｎｐｕｔ。 除此之外，一个完整的游戏引擎还应包括一系 列的辅助开发工具，如脚本编辑器、ＧＵＩ编辑器、动 画编辑器、材质编辑器、场景或地形编辑器等等，由 于篇幅所限，在此不一一列举。 ２ ＯＧＲＥ渲染系统分析 ２．１系统基本组成 ＯＧＲＥ系统包含ＳｃｅｎｅＭａｎａｇｅｒ、ＳｃｅｎｅＮｏｄｅ、Ｅｎｔｉ－ ｔｙ、Ｌｉｇｈｔ和Ｃａｍｅｒａ等一些基础类。ＳｃｅｎｅＭａｎａｇｅｒ是 场景管理器，ＯＧＲＥ支持的场景类型有：普通场景、 室外封闭场景、室外无限场景和室内场景等，场景管 理器通过调用ｇｅｔＲｏ０ｔＳｃｅｎｅＮｏｄｅ（）来获取整棵场景 树的根（Ｒｏｏｔ）；ＳｃｅｎｅＮｏｄｅ则为从场景树根Ｒｏｏｔ “伸”出的节点，它主要起组织场景中物体的作用， 本质上决定挂接到该节点的物体位置和方向，挂接 到ＳｃｅｎｅＮｏｄｅ上的物体可以是Ｅｎｔｉｔｙ、Ｌｉｇｈｔ或者 Ｃａｍｅｒａ等，数量也可以为多个，场景中某个Ｓｃｅｎｅ． Ｎｏｄｅ仍然可以继续“伸”出它的子节点，并在子节点 上再挂接其他物体，需要注意的是，这时挂接物体的 位置和方向是由沿着该子节点一直到根Ｒｏｏｔ这条路 径上所有的位置和方向变换决定的；Ｅｎｔｉｔｙ为场景中 的可活动物体（即实体），它可以通过如ｍＥｎｔｉｔｙ＝ ｍＳｃｅｎｅＭｇｒ一＞ｃｒｅａｔｅＥｎｔｉｔｙ（”Ｒｏｂｏｔ”，”ｒｏｂｏｔ．ｍｅｓｈ”）； 语句来创建，参数表中第一个参数为实体名称，第二 个参数为ｍｅｓｈ网格文件，ｍｅｓｈ网格文件代表实体的 模型，可以利用诸如３ＤＳ Ｍａｘ等软件来进行物体建 模，然后通过一些插件（如ｏＦｕｓｉｏｎ）将模型导出为可 供ＯＧＲＥ直接调用的ｍｅｓｈ格式，若是骨骼动画，则 还会导出相应的ｓｋｅｌｅｔｏｎ骨架文件；Ｃａｍｅｒａ是场景 中的摄像机视点类，一个场景允许有多个摄像机视 第２期 林巧民等：基于ＯＧＲＥ的智能游戏引擎的设计与实现 ７３ 点；Ｌｉｇｈｔ则为用来照明的场景灯光类。 文件，ＯＧＲＥ就能通过自身的一套机制在初始化阶 ２．２系统功能和流程 ＯＧＲＥ渲染系统的主要功能是根据给定的虚拟 段或运行期间动态地载人插件，这些插件被载入程 序的进程中来，提供一些简单的信号和协议给Ｏ． ＧＲＥ调用，据此实现无缝对接。下面的智能系统ＡＩ 就是以插件形式来实现的。 相机、三维场景、光源、光照明模型和纹理等，在屏幕 上绘制二维图像。其中，场景物体在屏幕上的形状 和位置由物体本身的几何、相机的方位和参数决定。 而物体在屏幕上的外观则由物体材质属性、光源属 ３ ＡＩ的设计与实现 性、纹理和设置的光照模型决定。对于不同的底层 图形绘制ＡＰＩ（如ＯｐｅｎＧＬ和ＤｉｒｅｃｔＸ），渲染流程的 阶段和实现的功能基本相同，差异在于各个阶段的 实现细节。 ＯＧＲＥ图形渲染流程可分为３个阶段，即物体 层、顶点层和像素层，具体的绘制实现还可进一步细 化为多个子阶段。物体层由应用程序驱动，在软件 中实现，如碰撞检测、可见性判断、变形动画等；顶点 层的大部分过程由硬件来实现、相机参数的设置等； 最后一个阶段在图形硬件中将顶点层生成的数据着 色为最终的图像。 ２．３设计模式 ＯＧＲＥ使用设计模式来提高程序库的可用性和 弹性。例如，ＯＧＲＥ使用观察者（ｏｂｓｅｒｖｅｒ）模式将系 统的每一个状态变化通知给应用程序，客户代码通 过注册来监听ＯＧＲＥ中事件和状态的改变以得到 相应通知（例如ＦｒａｍｅＬｉｓｔｅｎｅｒ对象可以监听到应用 程序每一帧渲染的开始和结束事件）。单件模式 （ｓｉｎｇｌｅｔｏｎ）用来保证一个类仅有一个实例，迭代器 模式（ｈｅｒａｔｏｒ）用来历遍一个数据结构中的所有数 据。访问者模式（ｖｉｓｉｔｏｒ）可以让用户在不改变对象 （例如，场景中所有节点）的前提下，增加一个新对 象操作的定义。外观模式（ｆａｃａｄｅ）为子系统中的一 组操作接口暴露给调用层一个统一的接口。最后， 工厂模式（ｆａｃｔｏｒｙ）以及它的近亲抽象工厂模式（ａｂ－ ｓｔｒａｃｔ ｆａｃｔｏｒｙ）被广泛的用来创建抽象接口的实例。 ２．４插件体系 ＯＧＲＥ被设计成可扩展的，用户可以根据需要 组合不同的插件以实现各种功能。譬如ＯＧＲＥ只 在接口层来管理场景的实现，这就意味着用户没有 被一定要使用现有的场景管理方案，而是可以 根据实际游戏需要将新的场景算法“插入”到ＯＧＲＥ 程序库中，并且它们可以和ＯＧＲＥ本身提供的算法 一样良好地工作。此外，这种插件机制在加入新的 功能插件时不用重新编译生成ＯＧＲＥ程序库，这对 于构建基于ＯＧＲＥ的ＯＩＧＥ智能游戏引擎无疑是个 重大的便利，只要简单放人符合ＯＧＲＥ规范的插件 ＡＩ对于游戏的可玩性至关重要，多年来游戏开 发者利用ＡＩ让无数的游戏角色看起来像是有智慧 的生命，如经典游戏“小精灵”（Ｐａｃ．Ｍａｎ）里的魔鬼、 “Ｕｎｒｅａｌ”第一人称射击游戏里的虚拟队友，以及许 多介于两者之间的其他游戏角色。ＡＩ包含了游戏 中许多重要的逻辑，这些逻辑驱动着游戏场景中的 玩家角色（ｐｌａｙｅｒ ｃｈａｒａｃｔｅｒ，ＰＣ）和非玩家角色（ｎｏｎ— ｐｌａｙｅｒ ｃｈａｒａｃｔｅｒ，ＮＰＣ）做出各种各样看似“智能”的 行为 。 图２列出ＯＩＧＥ引擎中人工智能系统的具体组 成模块，除了虚线框里的贝叶斯预测、遗传算法和神 经网络由于较复杂没有实现，其他智能模块如追逐 和闪躲、群聚、路径寻找、有限状态机（ｆｉｎｉｔｅ ｓｔａｔｅ ｍａ－ ｃｈｉｎｅ，ＦＳＭ）、模糊逻辑和规则子系统等均在引擎中 得到了实现。下面就对这些“智能”算法的设计和 实现进行详细介绍。 群聚ｌ ｌ寻径ｌ Ｉ有限状态机ｌ ｌ模糊逻辑 ｝ ．． 一一一 －＿，： 一 ～一 一一一： 一， ！贝叶斯预测－ ：遗传算法ｔ ．神经网络・ ３．１ 群聚 群聚算法可以用来模拟现实生活中羊群或鸟群 的行为，游戏场景中需要进行群聚的每个角色只要 遵守两条规则即可：（１）每个角色都往其视野内角 色的平均位置移动；（２）每个角色移动时对齐在其 视野内角色的平均方向上。其中视野如下图所示 （角色以三角形示意）。 由图３可见，视野区域是由两个参数控制的，即 角度（０）和视野半径（尺），在程序中它们可以根据实 际需要做动态调整。当０和 取值增大时，视野内 可以包含更多的角色，因此角色群体更能趋于抱团 而不易开，因为每个角色可以看到多数临近角 色或全部临近角色，再据此共同前行；而０和 取值 变小时，群体则容易或趋于排成纵队前进。当 ７４ 南京邮电大学学报（自然科学版） 游戏中需要模拟发起进攻的角色群时，可以采用较 大的参数值以调遣集中兵力；而当模拟一群鬼鬼祟 祟前行的士兵时，采用小的０值和Ｒ值可以使游戏 效果更加逼真，这里需要注意的是，视野半径Ｒ值 也不能取得过小，否则角色群容易分散掉，具体采用 什么值，可以通过实际测试来确定。算法１为上述 两条规则的具体实现。 △ 图３视野区域 算法１ ＯＩＧＥ引擎中群聚算法的代码 ／／规则１： ｉｆ（ＤｏＦｌｏｃｋ＆＆（Ｎ＞０）） ｛ Ｐａｖｅ＝Ｐａｖｅ／Ｎ； ｖ＝Ｕｎｉｔｓ［ｉ］．ｖＶｅｌｏｃｉｔｙ； ｖ．Ｎｏｒｍａｌｉｚｅ（）； ｕ＝Ｐａｖｅ—Ｕｎｉｔｓ［ｉ］．ｖＰｏｓｉｔｉｏｎ； Ｕ．Ｎｏｒｍａｌｉｚｅ（）； Ｗ＝ＶＲｏｔａｔｅ２Ｄ（一Ｕｎｉｔｓ［ｉ］．ｆＯｒｉｅｎｔａｔｉｏｎ，１１）； ｉｆ（Ｗ．ｘ＜０）ｒｌｌ＝一１； ｉｆ（Ｗ．ｘ＞０）ｎｌ＝１； ｉｆ（ｆａｂｓ（ｖ｝ｕ）＜１．Ｏｆ） ．ｘ＋＝ｍ ＳＴＥＥＲＩＮＧＦＯＲＣＥ｛ａｃｏｓ（ｖ￥ｎ）／ｐｉ； ｝／／规则２： ｉｆ（ＤｏＦｌｏｃｋ＆＆（Ｎ＞０）） ｛ Ｖａｖｅ＝Ｖａｖｅ／Ｎ； Ｕ：Ｖａｖｅ； ｎ．Ｎｏｒｍａｌｉｚｅ（）； ｖ＝Ｕｎｉｔｓ［ｉ］．ｖＶｅｌｏｃｉｔｙ； ｖ．Ｎｏｒｍａｌｉｚｅ（）； Ｗ＝ＶＲｏｔａｔｅ２Ｄ（一Ｕｎｉｔｓ［ｉ］．ｆＯｒｉｅｎｔａｔｉｏｎ，ｎ）； ｉｆ（Ｗ．ｘ＜０）ｍ＝一１； ｉｆ（Ｗ．ｘ＞０）１１１＝１； ｉｆ（１ａｂｓ（ｖ ｎ）＜１） Ｆｓ．ｘ＋＝ｍ ＳＴＥＥＲＩＮＧＦＯＲＣＥ｝ａｃｏｓ（ｖ ｎ、／ｐｉ； 根据上述两条规则就能实现群聚效果了，但是 却出现了另外一个问题：角色间可能会撞到一起？ 假如采用物理系统中的碰撞检测算法，的确可以解 决这个问题，但却不是最理想的，较好的办法是再设 计一条新规则，不妨称之为避开规则，就像两块磁铁 靠得很近时会互相排斥一样。设置一个角色间的安 全距离，当这个距离之外，其他两条群聚规则在起作 用，而当进入安全距离后，则应再启用第三条规则进 行避开努力，且距离越近，避开规则的影响力要越 大，即影响力与距离成反比，据此，我们在实现算法 时只需采用简单的反函数即可。图４、５显示了避开 规则启用前后的对比结果。 图４未启用避免开规则及碰撞检测 图５启用避免开规则 ３．２寻径 寻径算法是用来解决游戏角色如何从当前位置 移到目的地的问题。最简单的寻径算法采用不断缩 小当前坐标与目标坐标的各方向坐标间隔，当某个 方向已无间隔时，则继续下一个方向的间隔缩小， 这样虽仍达到目的地，但游戏角色走过的路径显 然很不自然，且看起来一点“智能”都没有，故不予 采用。ＯＩＧＥ引擎中寻径算法设计如下：在没有障 碍物情况下，采用Ｂｒｅｓｅｎｈａｍ线段扫描算法来进行 寻径，这样不仅路径自然，而且速度还快；在有少 数障碍物时，采用随机移动视线算法，即当目标不 在游戏角色的视线内（被障碍物挡住了），由于障 碍物很少，只要随机移动下角色位置，目标很可能 就进入视线，再结合前面的Ｂｒｅｓｅｎｈａｍ算法就可实 现此种情形的寻径问题；而当障碍物较多时，则采 用启发式Ａ 算法。 启发式Ａ 算法与常见的两种搜索算法：深度 第２期 林巧民等：基于ＯＧＲＥ的智能游戏引擎的设计与实现 ７５ 优先（ｄｅｅｐ ｆｉｒｓｔ ｓｅａｒｃｈ，ＤＦＳ）和广度优先（ｂｒｅａｄｔｈ ｉｆｒｓｔ ｓｅａｒｃｈ，ＢＦＳ）有些关联，ＤＦＳ和ＢＦＳ在展开子节 点时是盲目的，它们不会选择哪个节点在下一次搜 索中更优而转至该节点进行下一步的搜索。在最坏 情况下，它们会遍历整个解空间，因此只能适用于问 题规模不大的情形。所谓启发式搜索是指在当前搜 索节点（或位置）往下选择下一步节点（即邻接位 置）时，可以通过一个估价函数来进行选择，选择代 价（不～定只是距离）最少的节点作为下一步搜索 节点（当代价最少的节点多于一个时，随机选择其 中之一进行下一步搜索）。一个经过仔细设计的估 价函数，往往能在很快的时间内就可得到一个搜索 问题的最优解，对于ＮＰ问题，亦可在多项式时间内 得到一个较优解 。 Ａ 算法的估价函数设计为：ｆ＝ｇ＋ｈ。其中，－厂 是起始点到终点的总代价，它由两部分构成：ｇ表示 从起始点到当前点的实际代价，另一部分ｈ表示当 前节点到终点的估计代价，估计代价的计算式在实 现时是由动态参数控制的，可以根据不同的应用需 求决定其取值。譬如，对于普通的带障碍物砖块游 戏场景，游戏角色在移动时其估计代价可以直接设 置为当前节点到终点的移动步数（无视障碍物）。 算法２为ＯＩＧＥ引擎中Ａ 算法实现的伪代码。 算法２ ＯＩＧＥ引擎中Ａ半算法的实现 ＡＳｔａｒＳｅａｒｃｈ（）｛ Ｏｐｅｎ＝［起始节点］； Ｃｌｏｓｅｄ＝［］； ｗｈｉｌｅ（Ｏｐｅｎ表非空） ｛ Ｘ＝Ｏｐｅｎ表中估计代价最小的节点； ｉｆ（Ｘ是目标节点） ｛ 寻径结束； ｅｌｓｅ ｛ Ｃｌｏｓｅｄ＋＝［ｘ］； ｆ０ｒ ｘ节点的每个相邻节点Ｙｉ ｉｆ（Ｙｊ不在Ｏｐｅｎ表）且（Ｙｉ不在Ｃｌｏｓｅｄ表）且（Ｙｉ 不是无效节点，如障碍物） Ｏｐｅｎ＋＝［Ｙｉ］； 计算Ｙｉ节点的总代价； ３．３其他智能 ＯＩＧＥ引擎中还实现了其他“智能”算法，如追 逐和闪躲、模糊规则等，由于篇幅所限，这里仅对它 们做简要介绍。 在每次游戏循环中，更新追击者的坐标，让追击 者和猎物的坐标相距越来越近，这种算法最简单，它 不用考虑追击者和猎物各自的前进方向和速度，但 是该算法有很大局限性，比如追击者很可能“永远” 追不上猎物。因此，我们基于物理系统ＯＤＥ实现了 一个通过计算追击者与猎物的位置和速度，让追击 者能看似“智能”地去拦截猎物的算法，该算法确保 追击者能赶上猎物，而不是机械地一直追下去。 传统的布尔逻辑（Ｔｒｕｅ ｏｒ Ｆａｌｓｅ）只能让游戏角 色做出单一选择：做或不做。利用模糊逻辑则可以 通过“程度”来定义多种可能，使得游戏行为更加多 样化。整个模糊过程可以分为３个步骤：（１）模糊 化：即把明确数据转换为模糊数据，这个步骤中最关 键的就是归属函数的选用；（２）模糊逻辑规则：将模 糊数据结合起来，求出模糊结果；（３）反模糊化：将 模糊结果对应到明确的输出数值。ＯＩＧＥ引擎提供 多种不同的归属函数，如常用的折线段归属函数、三 角归属函数、梯形归属函数、高斯曲线函数以及ｓ形 曲线函数等。用户可以根据实际情况进行选用，不 过要注意的是：根据实践经验，游戏中具体调用何种 归属函数以及该函数的具体参数（形状），通常需要 进行反复试验，以能获取较好（或者较真实）效果为 标准¨ 。多数游戏程序选用折线、三角、梯形等线 性归属函数就够用了，少数要求精度高或有非线性 需求时才选用高斯曲线或Ｓ形曲线归属函数。 ４引擎验证 为了方便与渲染系统ＯＧＲＥ及物理系统ＯＤＥ 等的集成，ＯＩＧＥ引擎中的其他系统均采用面向对象 ｃ＋＋语言进行实现，再以插件的形式进行扩展，对 于用户而言，ＯＩＧＥ引擎展现在他们面前的其实就是 一系列的Ｃ＋＋功能类，因此，游戏制作者可以很容 易地在该引擎的基础上进行编程开发。图６展示的 是基于ＯＩＧＥ引擎实现的一款简单ＲＰＧ小游戏的画 面：靠近屏幕的是玩家控制角色，而它前面有两个非 玩家控制角色，此时它们正在激烈战中。另外，在 游戏场景中，还分布着房子、树等物件，它们既是 “景观”，同时又是障碍物。游戏开始时，ＮＰＣ不会 主动追击玩家，而是按设定的“巡逻”路线行进，当 ７６ 南京邮电大学学报（自然科学版） ２０１０年 遭遇玩家角色（即与玩家的间隔在设定安全距离范 围内）时，ＮＰＣ才会主动上前攻击玩家，当有ＮＰＣ被 玩家击毙后，在击毙处的一定范围内的ＮＰＣ将会 “看见”此景并变得警觉起来，此时大视野群聚规则 被启用，ＮＰＣ群聚在一起并前往拦截、攻击玩家，假 如有Ｊ７、，个（～由玩家在游戏开始时设置）ＮＰＣ相继 被玩家击毙，则所有ＮＰＣ将变得“害怕”起来并四处 躲避玩家，这时，玩家需要逐个地追击ＮＰＣ并消灭 它们，才能赢得游戏的胜利。 图６ ＲＩＧ小游戏场景画面 ５结束语 本文设计并实现了一个基于ＯＧＲＥ的智能游 戏引擎ＯＩＧＥ，它具备游戏开发所需的较为完善的功 能体系：渲染系统、人工智能系统、网络系统、物理系 统、声音系统以及输入系统等。ＯＩＧＥ采用面向对象 机制设计，以ＯＧＲＥ为基础平台，通过插件方式扩 充实现其他引擎模块，整个系统结构清晰且具有良 好的扩展性。最后通过ＲＰＧ小游戏的开发和测试， ＯＩＧＥ引擎中的许多功能得到了初步验证。 下一步的工作将对部分功能进行完善，比如网 络系统。另外，游戏中不确定状态下决策所需的贝 叶斯预测算法以及在实时战略游戏中所需的遗传算 法¨ 等也需要加以研究和实现，以进一步提高 ＯＩＧＥ引擎的“智能性”。 参考文献： ［１］Ｑｕａｋｅ ＩＩＩ［ＥＢ／ＯＬ］．［２００９－０８－２９］．ｈｔｔｐ：ｗｗｗ．ｉｄｓｏｆｔｗａｒｅ．ｃｏｒｎ／ ｇａｍｅｓ／ｑｕａｋｅ／ｑｕａｋｅ３一ａｉ￣ｎａ ［２］Ｕｎｒｅａｌ３［ＥＢ／ＯＬ］．［２ｏｏ９－０ｓ－２９３．ｈｔｔｐ：∥ ．ｕｎｒｅａｈｅｃｈｎｏｌｏｇｙ．ｃｏｎｌ ［３］ＢＩＳＨＯＰ Ｌ，ＥＢＥＲＬＹ Ｄ．Ｄｅｓｉｇｎｉｎｇ ａ ＰＣ Ｇａｍｅ Ｅｎｇｉｎｅ［Ｊ］．ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ，１９９８，ｌ８（１）：４６—５３． ［４］ＭＯＬＬＥＲ Ｔ Ａ，ＨＡＩＮＥＳ Ｅ．Ｒｅａｌ—ｔｉｍｅ ｒｅｎｄｅｒｉｎｇ［Ｍ］．Ｗｅｌｌｅｓｌｅｙ：Ａ． Ｋ．Ｐｅｔｅｒｓ Ｌｔｄ，２００３． ［５］ＧＡＲＣＩＡ Ａ Ａ，ＳＥＲＲＡＮＯ Ｎ，ＦＬＡＱＵＥＲ Ｊ．Ｓｏｌｖｉｎｇ ｔｈｅ Ｃｏｌｌｉｓｉｏｎ Ｄｅｔｅｃｔｉｏｎ Ｐｒｏｂｌｅｍ［Ｊ］．ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ， １９９４，１３（３）：３６—４３． ［６］ＯＧＲＥ［ＥＢ／ＯＬ］．［２００９—１０－０９］．ｈｔｔｐ：∥ｗｗｗ．ｏｇｒｅ３ｄ．ｏｒｇ ［７］Ｏｐｅｎ Ｄｙｎａｍｉｃｓ Ｅｎｇｉｎｅ［ＥＢ／ＯＬ］．［２００９—１０－０９］．ｈｔｔｐ：∥ｗｗｗ． ｏｄｅ．ｏｒｇ ［８］ＢＯＵＲＧ Ｄ Ｍ．游戏开发中的人工智能［Ｍ］．影印版．南京：东南 大学出版社，２００５年． ＢＯＵＲＧ Ｄ Ｍ．ＡＩ ｆｏｒ Ｇａｍｅ Ｄｅｖｅｌｏｐｅｒｓ［Ｍ］．ｐｈｏｔｏｃｏｐｉｅｄ ｅｄ．Ｎａｎ－ ｊｉｎｇ：Ｓｏｕｔｈｅａｓｔ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ，２００５． ［９］王永庆．人工智能原理与方法［Ｍ］．西安：西安交通大学出版 社，２００１． ＷＡＮＧ Ｙｏｎｇｑｉｎｇ．Ｐｒｉｎｃｉｐｌｅｓ ａｎｄ ｍｅｔｈｏｄｓ ｏｆ ａｒｔｉｉｆｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ ［Ｍ］．Ｘｉｈｎ：Ｘｉｈｎ Ｊｉａｏｔｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ，２００１． ［１０］ＳＣＨＷＡＢ Ｂ．ＡＩ Ｇａｍｅ Ｅｎｇｉｎｅ Ｐｒｏｇｒａｍｍｉｎｇ［Ｍ］．２ｎｄ ｅｄ．Ｈｉｎｇ— ｈａｍ：Ｃｈａｒｌｅｓ Ｒｉｖｅｒ Ｍｅｄｉａ，２００８． ［１１］ＭＡＲＫ Ｄ．Ｂｅｈａｖｉｏｒａｌ Ｍａｔｈｅｍａｔｉｃｓ ｆｏｒ Ｇａｍｅ ＡＩ［Ｍ］．Ｂｏｓｔｏｎ： Ｃｏｕｒｓｅ Ｔｅｃｈｎｏｌｏｇｙ ＰＴＲ，２００９． 作者简介： 林巧民（１９７９一），男，福建泉 州人。南京邮电大学软件学院讲 师，博士研究生。主要研究方向为 基于通信网络的计算机软件技术、 数字媒体技术及多媒体传感器网 络等。 林萍（１９８５一），女，福建泉州人。南京邮电大学计算 机学院硕士研究生。主要研究方向为计算机软件、计算机网 络和通信协议等。 王汝传（１９４３一），男，安徽合肥人。南京邮电大学计算 机学院教授，博士生导师。（见本刊本期第４０页）
