基于Android平台手机游戏引擎的设计与实现

黎忠文，覃志东，王全宇，倪仲余，3

（1.成都大学 信息学院，四川 成都610106；2.东华大学 计算机科学与技术学院，上海201620；3.西华大学 数学与计算机学院，四川 成都610039）

0 引 言

智能手机是指具有独立操作系统，支持用户下载安装第三方服务商提供的聊天、游戏等应用程序，并可以通过移动通讯网络实现无线网络接入的一类手机的总称。目前，主流的智能手机操作系统有Android，iOS和 Windows Mobile等系统。其中，Android是由Google开发的开源操作系统，其SDK已非常完善。随着Android手机成本的下降，以及Google公司成功收购摩托罗拉移动公司，其市场占有率将更大。所以，基于Android平台的游戏等各种应用开发将具有广阔的发展前景。对游戏创意的良好性能支撑，提高开发效率，缩短开发和推出市场的周期，都是影响一款游戏是否成功的关键因素，而这些因素的改善都与游戏引擎的设计息息相关。

游戏引擎是为运行某类游戏的机器所设计的，并且能够被该机器所识别的代码集合。经过不断的发展，游戏引擎已经成为一套由多个子系统共同构成的复杂系统，控制游戏的执行，使玩家与终端能够交互［1］。在现代手机游戏中，游戏角色的真实感体验是衡量游戏品质的一个重要标准［2］。通常游戏的真实感体验由图形渲染、物理模拟和人工智能等模块完成。目前，已有的手机游戏引擎在图形渲染和物理模拟方面取得了长足的进步，但其人工智能模块仍然显得简单甚至没有［3］，应用这些引擎设计出的游戏其非玩家控制角色过于迟钝或者程式化，影响了游戏的真实性，所以游戏引擎的人工智能仍有很大的发展和创新空间［4］。对于在线游戏而言，由于这类游戏需要技术性能和用户感知视觉质量并举［5］，对人工智能技术的需求很大。同样在3D游戏开发中，相对于游戏引擎的其它部分，人工智能的研究力度还有待进一步加强，比如路径搜索算法［6］直接影响着游戏的响应速度［7］。当前越来越多的游戏引擎是基于移动平台的。当游戏越来越复杂的时候，软件基本开发方法将很难满足这些游戏的开发要求。文献 ［8］研究结果表明，在移动平台上开发一个游戏引擎时，选定一个设计模式，理清设计目标和思路是很重要的。

本文通过对Android游戏的程序结构进行研究，基于模块化的思想，设计实现了一个基于Android系统的2D游戏引擎LAndGame2D，重点对人工智能模块中的基本算法：最短路径搜索算法进行了优化，有益于提高游戏的真实感体验。

1 游戏引擎的基本原理

游戏引擎是面向游戏开发的通用内核，将游戏程序设计中最通用的功能集成为一个游戏开发平台。通常游戏引擎包括的模块有智能模拟、物体成像、物理演算、碰撞运算、角色的操作、声音管理等，游戏开发人员可以通过API函数调用这些模块，快速方便的开发游戏。

1.1 Android平台游戏运行机制

设计游戏引擎，首先需要分析游戏的运行机制，提取游戏的基本构成元素。Android游戏主要包括一个Activity类、一个流程控制类、一个游戏线程类和若干个游戏对象类。其中Activity类是游戏程序的基本执行单元，控制复杂的游戏生命周期，如游戏的启动、暂停、退出等。游戏控制类提供了游戏的界面切换的方法。游戏线程类循环检测可能发生的各种事件，计算游戏状态，刷新屏幕。游戏对象类需要定义对象和执行动作。当游戏事件触发时，游戏对象通过回调函数调用相应的操作。

Android平台游戏运行机制如图1所示。

1.2 游戏引擎中的人工智能技术

在游戏设计中通常采用的人工智能技术主要有模糊逻辑、有限状态机、寻径算法等。模糊逻辑使用模糊值来表示模糊的概念和进行知识推理，被广泛应用于决策推理和行为选择。例如，非玩家角色评估玩家展示的威胁，控制非玩家队友的行为等。有限状态机是基于规则的人工智能系统，来源于自动机理论，可以管理整个游戏场景，也可以操作单个游戏对象和人物。

图1 Android平台游戏运行机制

寻径算法是游戏开发中的常见算法，非玩家角色需要在较短时间内找到由当前位置到主角位置的最短路径并且避免与障碍物碰撞，其依赖的核心基础是人工智能中的最短路径搜索算法。在现有游戏引擎中，对于最短路径求解问题，先后有深度优先算法、广度优先算法、Dijkstra算法、A＊算法等诸多算法被提出。其中，深度优先和广度优先算法属于状态空间搜索算法，其最大缺陷是搜索速度低，当状态空间很大或者不可预测的情况下则无法给出最优解。Dijkstra算法能够保证搜索成功率，但是由于需要遍历计算的节点过多，所以搜索速度慢。而A＊算法是启发式搜索算法，它只需要产生全部状态空间的部分结点及关系，就可求解，搜索效率较高，但是由于该算法没有回溯，不能确保寻找到的路径一定是最优路径。

近年来，遗传算法因为其强大的并行搜索能力，也被用来求解最短路径问题，其搜索成功率优于A＊算法，且搜索速度优于Dijkstra算法。但标准遗传算法存在易陷入早熟的缺陷，采用该算法实现寻径，则在游戏中常导致非玩家角色在一个角落不停地绕圈。显然，这会极大影响玩家的真实感体验。综合考虑算法的搜索速度和搜索成功率，本文引入Boltzmann行动选择策略解决标准遗传算法易早熟的缺陷，并以此优化遗传算法作为引擎寻径问题求解的基本算法。

2 基于Boltzmann行动选择策略的优化遗传算法

Boltzmann行动选择策略是一种被搜索算法所采用的，适于求解非精确状态信息下的顺序决策过程问题的行动选择策略。本文所改进的遗传算法利用基于Boltzmann行动选择策略［9］替代轮盘赌选择策略，从而解决标准遗传算法容易早熟的问题。

2.1 Boltzmann行动选择策略

标准遗传算法一般采用轮盘赌选择策略，给定种群规模为n的群体p ＝ ｛a1，a2，···，an｝ ，个体aj∈P的适应值为f（aj），其选择概率为

式 （1）决定后代种群中个体的概率分布。当种群中个体的适应值差异较大时，最优个体和最差个体被选择的概率之比成指数级增长。最优个体将显著增加在下一代的生存机会，而最差个体的生存机会则会被剥夺。最优个体快速充满种群，从而导致种群的多样性迅速降低，遗传算法也就过早地丧失进化能力，陷入算法早熟问题。

Boltzmann行动选择策略采用随机接收准则选择行动，并根据当前状态下可选行动的估计价值决定选择行动的概率。Boltzmann选择机制可以有效地解决优化算法难以避免的局部最优问题，使系统最终演化到全局极小点［10］，寻找到最优的行动选择策略。设行动全体集合为A，行动估计价值集合为VA，a1，a2，…，an∈A为当前状态下可选的行动，而v（a1），v（a2），…，v（an）∈VA分别为各行动估计价值提出对应的估计价值，当前状态下选择任一行动ak｛a1，a2，…，an｝ 的概率为

其中，k＝1，2，…，n，T＞0是退火温度，是控制进化过程中选择压力的关键，在种群的进化过程中，进化早期时选择压力较小，适应值较差的个体也需要一定的生存能力，退火温度缓慢地递减；进化后期需要较大的选择压力来缩小搜索邻域，加快最优解改善的速度，退火温度递减也需要越快，因此退火温度变化趋势应该是不断成非线性下降的过程，所以，本文引入神经网络中的Sigmoid函数作为退火温度的变化系数，即

其函数曲线图如图2所示。

图2 Sigmoid函数曲线

基于Boltzmann选择机制的遗传算法中个体被选择的概率定义为

式中：n——种群规模，c——种群进化迭代循环次数，m——最大迭代次数，T0——退火温度初始值，Tmin——冷却温度。T会随着迭代次数的增加而减小，选择压力就随之增大，最终达到冷却温度。

2.2 优化遗传算法的测试

为了验证算法的收敛性能以及跳出局部最优解的能力，本文对基于轮盘赌选择的标准遗传算法 （SGA）和基于Boltzmann选择的优化遗传算法 （BGA）进行了比较测试。测试选取3个经典的遗传算法性能测试函数，这些测试函数都是既有全局解又有多个极值点的函数

其中，－2.048≤xi≤2.048，i＝1，2；该函数是二维单峰难以极小化的病态函数，函数最小值是0

其中，－3≤x1≤3，－2≤x2≤2，函数最小值是10.316

其中，－10≤xi≤10，i＝1，2，函数最小值是186.731。

用SGA和BGA两种遗传算法，对以上的测试函数进行100次计算，求出收敛值。其中，计算机的配置为Pentium（R）4微处理器，主频为2.8GHz，内存容量为1.5G。遗传参数设置：种群规模为60，最大迭代次数100，交叉率0.8，变异率0.05。计算结果见表1和表2。表中结果都是平均值，收敛时间单位为s。

表1 SGA测试函数时的性能比较

表2 BGA测试函数时的性能比较

由表1和表2可知，BGA遗传算法虽然在收敛时间开销上比SGA遗传算法有所增加，但是成功的收敛次数多，提高了算法的收敛率，而且收敛的极值更加接近理论计算得到的函数值，收敛的稳定性较好，从而很好的避免了遗传算法陷入早熟的问题。

此外，我们对BGA遗传算法和A＊算法在游戏设计中的应用效果进行了比较。图3和图4是某次设定的两点最短路径搜索效果示意，显然，BGA遗传算法优于A＊算法寻找到的路径。由于搜索速度快，A＊算法在游戏设计中广泛采用；但是，A＊算法不能回溯，不一定能够找到最短路径，表现在游戏中就是非玩家角色易走错路、乱跑、行为飘忽和绕圈子等。相反，BGA遗传算法则能保证较高的最短路径搜索成功率，非玩家角色能智能地找到主角位置，增加了游戏的真实感体验。虽然在时间开销方面，BGA遗传算法搜索速度逊于A＊算法，但由于当前嵌入式CPU的主频极高，玩家体验不出这种时间开销差别。综合考虑，我们采用BGA遗传算法作为基础寻径算法。

3 游戏引擎的设计与实现

3.1 游戏引擎设计框架

游戏引擎是一种中间件，它是依赖操作系统来控制硬件的。本文设计的游戏引擎LAndGame2D架构在操作系统层之上，其主要包括图形引擎、物理引擎、人工智能模块，网络模块、音效模块、工具模块、事件处理模块等等［11］，模块结构如图5所示。

其中，游戏的核心类是为游戏提供框架，主要实现游戏逻辑类、流程控制类。人工智能模块是提高游戏的智能，增加游戏的真实感体验。图形引擎的功能是用于产生游戏角色及周边场景的图形，把读取的所有数据及时转化成屏幕显示的图形。物理引擎用于在游戏中准确地实现物理模拟，通过刚体物体赋予真实的物理属性的方式来计算运动和碰撞。网络模块负责游戏的联网对战任务，管理游戏中所需要交互的数据的传送工作。音效模块主要处理播放声音和声音的管理功能。工具模块是将游戏中常用的操作进行封装，如向量计算、定时器等。事件处理完成对用户输入操作进行响应和对游戏内部事件处理的功能。

3.2 游戏引擎的实现

在游戏逻辑类的实现中，LAndGame2DActivity是游戏的主类和入口程序，将对整个游戏的生命周期进行控制，同时还提供了事件处理函数。比如：处理按键、触摸等。LAndGame2DActivity继承了Android应用框架提供的Activity类。流程控制类主要用于游戏状态机制来控制不同界面之间的切换，状态机制就是对游戏定义多个状态，每一个状态所显示的界面都不同。游戏引擎框架中的流程控制类是LAndGame2DView，该类继承自Android应用开发框架层的SurfaceView类，SurfaceView类的实现原理是在绘图之前必须使用lockCanvas方法锁定画布，得到画布后在画布上进行绘制，绘制完成后使用unlockCanvasAndPost方法解锁画布，最后显示到屏幕上。线程类使用run（）方法可以随时监听事件的触发，进而改变状态，更新界面显示。监视事件需要继承SurfaceHolder.Callback接口增加回调函数。

人工智能模块主要实现了基于Boltzmann选择遗传算法的寻径算法、模糊逻辑和有限状态机。基于Boltzmann选择遗传算法的寻径算法实现步骤是首先为染色体进行二进制编码。由于游戏地图是由一些单元格组成，当非玩家角色处在起始点时运动方向有上、下、左和右4种选择，因此需要用两个比特表示这4种情况。见表3。

表3 路径搜索的基因编码

接着产生初始种群个体，设置遗传算法的参数，测试每个染色体能使非玩家角色所能到达的最远位置距离目标点的长度，即计算适应度值。函数CalculateFitnessValue（）经过计算会返回一个适应度值，其中计算适应度值的程序如下：

int dist＿x＝abs（npc＿x－end＿x）；

int dist＿y＝abs（npc＿y－end＿y）

第三，实验环境的搭建，需要进行特征提取和筛选，建立一个良好的实验环境对图像质量的好坏有很大的作用，在拍照所选择的相机镜头，拍照过程中的背景、灯光、相机的视场等，都会对最终农产品的分类结果产生一定的影响，同时也要利用这个实验环境进行实验验证，因此搭建什么样的实验环境是该设计中的一个重点和难点。

int dist＝dist＿x＋dist＿y；

return 1／（dist＋1）；

程序中dist＿x和dist＿y就是非玩家角色所在的位置相对于目标点的水平和垂直偏离值。如果非玩家角色到达出口，则dist＿x＋dist＿y＝0。计算两点间距离比较常用的方法是两点间距离坐标公式，但是为了优化程序的性能，减小计算量，可以利用不需要开方和平方的蒙特卡罗距离计算两点间距离。dist计算的就是蒙特卡罗距离。最后通过Boltzmann选择选出参与交叉的两个个体后，实现交叉和变异操作后得到新的染色体继续加入新的群体，完成一次迭代过程。不断重复以上过程直到非玩家角色到达目标点。模糊实现了几种归属函数，如布尔归属函数，三角形归属函数，梯形归属函数等。模糊处理定义了联集、交集、补集操作。有限状态机定义了一个简单状态机框架。

图形引擎主要是负责地图场景管理模块的实现。地图管理中的图层对象由Layer类实现，Layer类封装一个可视元素的位置、宽度、高度和可见性等信息。图层不是每次显示一个单个的图像，而是显示多个依次排列的图像，当创建图层时，通过指定贴砖排列构成图层。图层要求所有的贴砖图像大小必须相同。当布置贴砖栅格时，贴砖可以按任意的组合方式混合和匹配。

物理引擎是通过刚体物体赋予真实的物理属性的方式来计算运动和碰撞。本文设计的物理引擎主要提供碰撞检测技术的功能。在游戏中实体对象的位置改变的情况下会发生碰撞，实现碰撞检测主要包括：确定检测对象、检测是否碰撞、处理碰撞这3个方面。碰撞对象主要分为游戏实体对象之间的碰撞和游戏实体对象与环境之间的碰撞。

网络模块为游戏支持网络服务。网络连接主要分为互联网和局域网，互联网需要封装Http协议，可以通过标准java接口实现Android游戏引擎的联网操作，另外需要注意网络通信的中文乱码问题。局域网则主要封装蓝牙连接及传输数据的功能。

音效模块提供对背景音效和动作音效的管理，其中包括音乐类型、当前播放次数、音乐结束处理，循环播放音乐、音乐模式管理等函数。

事件处理模块主要负责用户和手机终端交互的处理，需要考虑到事件的类型、发起者、被发起者、事件参数等因素。当一个事件被触发时，发送消息给事件响应者，事件响应者收到消息后，根据消息的内容来判断处理相应的事件。

4 应用实例

在游戏引擎LAndGame2D完成的基础上，本文利用该游戏引擎开发了一款飞行射击游戏，该游戏运行的流程图如图6所示。

图6 游戏运行流程

根据游戏流程图将飞行射击游戏划分为5个模块：

（1）移动模块和炮弹生成模块，完成飞机和炮弹的移动、生成功能，主要由图形引擎中的人物显示模块完成。

（2）绘图模块，绘制游戏界面，主要由图形引擎的场景绘制完成。

（3）碰撞检测模块，检测炮弹和飞机之间以及飞机与飞机的之间的碰撞，主要由物理引擎完成。

（4）资源初始化模块，初始化游戏数据，加载声音、图片资源，主要由游戏程序完成。

（5）游戏AI模块，为了使生成的敌机更加智能，采用基于Boltzmann选择的遗传算法，使得游戏更加具有真实感。游戏中具体的编码设计是：一个基因表示一帧时间内敌机的移动方向。基因长度限制在m＝60以内，对于每秒刷新30帧的游戏，在2秒内，敌机的运行轨迹都是精确模拟的。适应度评估将精确模拟2秒内飞机的移动判断飞机的生存概率，粗略评估2秒之后的生存概率。经过迭代得到飞机最佳的运行路径，从而敌机更加难以击落，增加游戏的可玩性。飞行射击游戏的界面如图7所示。

图7 飞行游戏界面

由此可见，利用LAndGame2D开发一款游戏，游戏开发人员只要集中精力设计游戏的创意、美工及资源即可，其余工作可以利用游戏引擎完成，这样就能提高游戏的开发效率，缩短开发和推出市场的周期，降低游戏开发的难度。

5 结束语

本文实现了一个基于Android操作系统的游戏引擎LAndGame2D，包含的子系统模块有图形引擎、物理引擎、人工智能模块，网络模块、音效模块、工具模块、事件处理模块，这些模块具有很高的灵活性和扩展性，特别是基于Boltzmann选择遗传算法上实现的人工智能模块，能够明显提高非玩家角色的智能，增加了游戏的真实感体验。利用LAndGame2D开发的几款游戏能够在Android模拟机仿真运行及真机运行，游戏运行流畅，效果令人满意。

［1］RAN Jing.Analysis and design of 2Dmobile game engine based on J2ME ［D］.Chengdu：Southwest Jiaotong University，2007：1－82 （in Chinese）.［冉静.基于J2ME的2D手机游戏引擎的分析与设计 ［D］.成都：西南交通大学，2007：1－82.］

［2］Eva Hudlicka.Affective game engines：Motivation and requirements ［C］／／Proceedings of the 4th International Conference on Foundations of Digital Games.New York，USA：ACM，2009：299－306.

［3］CHEN Song.Design of graphic engine based on changeable angle ［J］.Computer Science，2006，33 （11）：240－242 （in Chinese）.［陈松.基于斜视角可变的游戏引擎设计 ［J］.计算机科学，2006，33 （11）：240－242.］

［4］Eike F A，Steffen E，Peter C.The case for research in game engine architecture ［C］／／Proceedings of the Conference on Future Play：Research，Play，Share.New York，USA：ACM，2008：228－231.

［5］Frederick W B，Rynson W H，Danny K.Game－on－demand：An online game engine based on geometry streaming ［J］.ACM Transactions on Multimedia Computing，Communications，and Applications，2011，7 （3）：118－131.

［6］LIN Dubin，LI Xin.Improved A＊path－finding algorithm based on DEM－grid［J］.Computer Engineering and Design，2011，33（10）：3414－3418 （in Chinese）.［林笃斌，李欣.基于 DEM格网的改进型A＊路径搜索算法 ［J］.计算机工程与设计，2011，33 （10）：3414－3418.］

［7］LI Hongbo，WU Yuxin，ZHAO Kuan.Survey of research and application of 3Dgame engine technology on android platform［J］.Digital Communication，2012，10：28－33 （in Chinese）.［李红波，吴雨芯，赵宽.Android平台下3D游戏引擎技术的研究及应用综述 ［J］.数字通信，2012，10：28－33.］

［8］Peker G A，Can T.A design goal and design pattern based approach for development of game engines for mobile platforms［C］／／Proceedings of the 16th International Conference on Computer Games.Washington，USA：IEEE Computer Society，2011：114－120.

［9］DING Haijun，FENG Qingxian.Artificial bee colony algorithm based on Boltzmann selection policy ［J］.Computer Engineering and Applications，2009，45 （3）：53－55 （in Chinese）.［丁海军，冯庆娴.基于Boltzmann选择策略的人工蜂群算法［J］.计算机工程与应用，2009，45 （3）：53－55.］

［10］ZHAO Xiaoqiang，ZHANG Shouming.Boltzmann selectionbased KFCM algorithm incorporated with artificial bee colony algorithm ［J］.Journal of Lanzhou University of Technology，2011，37 （1）：71－75 （in Chinese）.［赵小强，张守明.基于Boltzmann选择的人工蜂群KFCM算法 ［J］.兰州理工大学学报，2011，37 （1）：71－75.］

［11］REN Wei.An application of artificial intelligence in computer game software ［D］.Xi’an：Xi’an University of Electronic Science and Technology，2006：1－66 （in Chinese）.［任巍.人工智能技术在计算机游戏软件中的应用 ［D］.西安：西安电子科技大学，2006：1－66.］