人工智能技术在基于BREW的手机游戏中的应用
陈禾，陈丰，赵良毕
北京邮电大学电信工程学院，北京(100876)
akinis.chen@
摘要：随着第三代移动通信系统在全球范围内的商用以及手持移动终端功能的丰富，手机的应用已经大大超出了传统的打电话、发短信等，用户对以手机游戏为代表的移动应用的要求也越来越高。
对于目前的手机游戏来说，玩家的对手主要是手机程序模拟的“敌人”，因此游戏的可玩性就主要取决于“敌人”的水平，具有适当智能的“敌人”将使用户得到更好的娱乐效果，而人工智能就是一种可以使游戏更加有挑战性的技术，本文结合作者在BREW平台下开发手机游戏的实际项目经历，详细叙述了人工智能在移动应用中的几个关键技术。
关键词：手机游戏人工智能BREW平台
中图分类号：TP319
1.引言
电子和电脑游戏一直是为人们所喜欢的娱乐方式，它们在带给人们欢乐的同时还起到益智、锻炼人的反应能力等作用。
游戏行业中最新的热点就是可移动性。
手机游戏将来自传统商业公司（如Sun Microsystems的新游戏区）、设备生产厂（如：Nokia的N-Gage和Qualcomm的BREW设备）、和网络经营者（如Vodafone的内容服务）的那些原本不可能在一起的商家拉到了一起。
因此，近年来，手机游戏成为了信息产业的兴起给人们带来的又一项新的娱乐方式。
这些游戏操作简单、娱乐性强、老少皆宜，非常适合手机用户在闲暇时休闲娱乐。
在最近几年，手机游戏成绩斐然，成IT产业中增长最快的部分之一。
人工智能（Artificial Intelligence），英文缩写为 AI，是一门综合了计算机科学、生理学、哲学的交叉学科。
对于人工智能的定义随不同的年代而有所差异。
广义地讲，人工智能是关于人造物的智能行为，将人工智能加入游戏中将会使游戏变得更丰富、更具有挑战性。
2.BREW平台简介及基于BREW平台的无线应用
2.1 BREW平台简介
BREW是Binary Runtime Environment for Wireless（无线二进制运行时环境）的缩写，是美国高通公司（QUALCOMM）为无线数据应用程序开发和执行提供的通用接口平台，该平台的架构见图1[1]。
图1 BREW解决方案平台框图
BREW是高通公司提供的全面的、端到端的无线应用开发、设备配置、应用分发、计费和支付的解决方案。
借助于BREW技术，用户可以随时随地下载自己喜爱的应用，定制自己手机的功能，使之更具个性化。
BREW一经推出，便已受到全球许多运营商的认可，特别是BREW提供的差异化优势，更为市场中勇于创新的运营商青睐有加。
2.2 BREW平台的特性及基于BREW的应用
BREW应用程序模型是基于事件驱动的协作式多任务系统，这种系统简单的说，就是在单线程下的状态机，有某个注册事件发生时，就调用注册的处理代码，这会大大简化内核和用户系统的设计。
这有别于Windows2000等系统的事件驱动的抢先式多任务系统[2]。
BREW应用程序从应用程序被载入开始，它通过接收所有的事件响应输入，来驱动整个应用程序的进行。
比如用户的按键输入，是通过系统向应用程序发送的EVT_KEY等事件来响应的。
用户的应用程序，必须及时接收并处理来自系统的事件，这样才能保证应用程序的正常运行。
如果程序陷入长时间的运行而不能及时响应系统事件，将会导致设备死机或强制性重新启动。
因此在处理系统事件时，应该尽量使用快速的算法和简单的语句，尽量在短时间内处理结束。
具体方法在下文有介绍。
BREW中没有多线程的概念，只能通过应用程序执行完一个任务，才能接下来处理另外的任务，并不能执行并行的任务。
因此在BREW应用程序中，在同一时间内（指的不是时间片，就是普通的时间概念），只能有一个进程在运行，其他进程处于挂起状态，当系统得到某个特定的事件或者信息之后，重新切换到相应的处理进程，而把当前的进程挂起。
BREW是在系统软件和底层驱动程序与应用程序之间的一层，隔离了硬件驱动程序和用户应用程序。
因此我们不必关注底层硬件平台和它们之间的差异性，而只关注BREW提供的接口和应用程序本身即可。
因此说BREW相当于软件接口层。
BREW提供给应用程序的执行环境称为AEE，为高度可扩展的，面向对象的应用程序执行环境。
应用程序的启动执行销毁都在此环境执行。
AEE环境中包括两种模块（module），一种为小程序（Applet），另一种为类（classes）。
一个module就是一段在BREW中的可执行代码，非常类似于其他平台上的共享库。
module包括了class的定义，class是BREW系统中可以复用的最小单元，是用来构建应用程序的接口的实现代码。
许多这样的类都是从客户手机的ROM里按照客户应用程序的需要而相应载入。
当然，开发人员也可以在你自己的应用程序中定义自己的类，这样，模块成为可扩展的了。
Applet为应用程序的基本执行单元。
AEE每次只能激活一个Applet。
在Applet中可以激活另一个Applet，但是只有那个被激活的Applet在运行，原先的Applet处于挂起状态，可以由运行的这个再次把它激活[3]。
和大多数其他面向对象的平台一样，Applet自己就是一个类，是IApplet类的子类。
它必须实现由IApplet类定义的接口，来处理系统发出的事件。
由于一个Applet只是一个类，因此一个module可以包含几个Applet。
classes和Applet这两种module都分为动态和静态的。
静态的module只有由设备制造商能够植入，动态的module由用户下载。
使用SDK只能够开发动态的module。
图2 BREW的基本体系结构
3.人工智能技术
从计算机的角度来说，人工智能就是研究使计算机来模拟人的某些思维过程和智能行为（如推理、思考、规划等）的学科，主要包括计算机实现智能的原理、制造类似于人脑智能的计算机，使计算机能实现更高层次的应用。
人工智能的研究课题涵盖面很广，从机器视觉到专家系统，包括了许多不同的领域。
这其中共同的基本特点是让机器学会“思考”。
为了区分机器是否会“思考”（thinking），有必要给出“智能”（intelligence）的定义。
究竟“会思考”到什么程度才叫智能？比方说，解决复杂的问题，还是能够进行概括和发现关联? 还有什么是“知觉”（perception），什么是“理解”（comprehension）等等？对学习过程、语言和感官知觉的研究为科学家构建智能机器提供了帮助。
现在，人工智能专家们面临的最大挑战之一是如何构造一个系统，可以模仿由上百亿个神经元组成的人脑的行为, 去思考宇宙中最复杂的问题。
或许衡量机器智能程度的最好的标准是英国计算机科学家阿伦·图灵的试验。
他认为，如果一台计算机能骗过人，使人相信它是人而不是机器，那么它就应当被称作有智能。
人工智能从诞生发展到今天经历了一条漫长的路，许多科研人员为此而不懈努力。
人工智能的开始可以追溯到电子学出现以前。
例如布尔和其他一些哲学家和数学家建立的理论原则后来成为人工智能逻辑学的基础。
而人工智能真正引起研究者的兴趣则是1943年计算机发明以后的事。
技术的发展最终使得人们可以仿真人类的智能行为，至少看起来不太遥远。
接下来的四十年里，尽管碰到许多阻碍，人工智能仍然从最初只有十几个研究者成长到现在数以千计的工程师和专家在研究；从一开始只有一些下棋的小程序到现在的用于疾病诊断的专家系统，人工智能的发展有目共睹。
人工智能始终处于计算机发展的最前沿。
高级计算机语言、计算机界面及文字处理器的存在或多或少都得归功于人工智能的研究。
人工智能研究带来的理论和洞察力指引了计算技术发展的未来方向。
4.人工智能技术在手机游戏中的应用
目前，基于BREW应用可以利用到人工智能的主要就是游戏类应用，尤其是格斗类、设计类以及牌类游戏。
人们在用手机玩游戏的过程中，已经不能满足于简单的自我娱乐，而
更追求能够有相当的对手。
因此在游戏设计过程中，我们更多的使用了人工智能。
在游戏的设计过程中，我们更多的使用有限状态机（Finite State Machine）来实现人工智能[4]。
有限状态机是包含一组状态集（states）、一个起始状态（start state）、一组输入符号集（alphabet）、一个映射输入符号和当前状态到下一状态的转换函数（transition function）的计算模型。
当输入符号串，模型随即进入起始状态。
它要改变到新的状态，依赖于转换函数。
在有限状态机中，会有许多变量，例如，状态机有很多与动作（actions）转换(Mealy 机)或状态（摩尔机）关联的动作，多重起始状态，基于没有输入符号的转换，或者指定符号和状态（非定有限状态机）的多个转换，指派给接收状态（识别者）的一个或多个状态，等等。
下面以本人开发的《无敌坦克》游戏具体介绍人工智能技术在应用到基于BREW平台的手机游戏开发时的几个关键技术。
4.1自动射击算法中的人工智能
在《无敌坦克》应用中，敌人在巡逻过程中，炮塔时刻在监视进入扫描范围之内的目标，扫描范围为一个固定半径的圆。
如果发现目标，敌人停止，并对瞄准目标。
如果目标进入火力范围，敌人自动开始射击，目标摧毁以后，或者目标逃出火力范围，敌人继续巡逻，并继续扫描，其流程图如下所示：
图3 自动扫描与自动射击流程图
其核心实现代码如下
if ( TRUE == IsInScope(hostRect) )
{
if ( TRUE == CushionDir() )
{
if ( TRUE == CScanSprite::IsInScope(m_nFireSize,hostRect) )
{
if (m_nAimCnt++ > _AIM_CNT_)
{
0;
=
m_nAimCnt
TRUE;
return
}
}
else
0;
m_nAimCnt
=
}
else
m_nAimCnt = 0;
m_bInScrop = TRUE;
}
else
{
m_nAimCnt = 0;
m_bInScrop = FALSE;
}
4.2目标自动锁定算法的人工智能
在《无敌坦克》应用中，坦克任意时刻，炮塔都扫描周围的目标，坦克在方向键的控制下，可以在无障碍物的地方随意12方向行走，其炮塔也可以12方向任意旋转。
任意时刻，炮塔自动扫描范围内的目标，当发现目标时候，炮塔调整方向，自动瞄准锁定先发现的目标，如果在范围内有多个目标，其在坦克正向的目标锁定的优先级最高。
当有开火按键时，炮轰目标。
当目标消灭后或出了刚才扫描目标的范围，炮塔继续扫描目标。
任意时刻，炮塔总是锁定优先级最高的目标
其流程图如下所示：
图4 目标自动锁定流程图
其核心实现代码如下
if (TRUE == IsInScope(pHostBody,pSprite))
{
AEERect rect;
AEERect objRect;
int unHostState = pHostBody->GetHostState()%(_HOST_STATE_/2);
int16 hostDx = tank_DxDy[unHostState];
int16 hostDy = tank_DxDy[unHostState+_HOST_STATE_/2];
int hostPosX = m_Pos.m_nPointX+(m_DrawRect.dx - hostDx)/2;
int hostPosY = m_Pos.m_nPointY+(m_DrawRect.dy - hostDy)/2;
SETAEERECT(&rect,hostPosX,hostPosY,hostDx,hostDy);
SETAEERECT(&objRect,
pSprite->GetPos()->m_nPointX,
pSprite->GetPos()->m_nPointY,
pSprite->GetDrawRect()->dx,
pSprite->GetDrawRect()->dy);
AddPriArray(m_nIndex,AjustDir(rect,objRect));
if(!m_bInScope)
{
m_bInScope = TRUE;
}
}
4.3 寻路算法中的人工智能
在《无敌坦克》游戏中，寻路的应用随处可见，现在主要的寻路算法有：
1. 深度优先算法：即能走就走，若有多条路可走则按照一定的次序选择（如上下左右），但不走回头路。
如果无路可走就退回。
显然这种方法不一定能找到最短的路径，但它对内存的要求很小。
由于与真实的找路过程有相似之处，所以可以让精灵直接按搜索的过程移动，不需任何等待。
不过由于上下左右的次序太机械，精灵一开始并不是朝着最短的路线走去，所以移动路线还不够真实，特别在比较空阔的时候会容易找不到路。
2. 广度优先算法：与深度优先搜索相对应的是广度优先搜索。
这种方法的思路很简单，就是先搜索一步可到的点，再搜索两步可到的点……如此直到找到目标点为止。
这种搜索方法显然能保证走的是最短路径，搜索速度也较快，不过对空间的占用较大。
3. A*算法。
原理是通过不断搜索逼近目的地的路点来获得最短路径。
这种算法会首先进行试探，查看从起始点到终点的成本并做预估，即使还没有访问过的节点。
显然，A*算法比上面所讲述的方法更加精确，但是对于手机来讲过于庞大，它需要耗费大量的CPU运算速率，并存在一定缺陷。
深度优先的算法，虽然耗费内存小，但是由于寻找路径的时间比较慢，且寻路方法比较机械，因此，并不是一个很好的寻路算法。
而广度优先算法好用内存较多，这对内存较小的手机来讲是一个挑战。
而A*算法对于运算速率较低的手机来讲过于庞大。
现在，有一种新的AI寻路方式——矢量寻路算法。
通过观察，我们可以发现，所有的最优路线，如果是一条折线，那么、其每一个拐弯点一定发生在障碍物的突出边角，而不会在还没有碰到障碍物就拐弯的情况，如下图所示：
图5 矢量巡路算法示意图
我们可以发现，所有的拐弯点都是在障碍物（可以认为是一个凸多边形）的顶点处，所以，我们搜索路径时，其实只需要搜索这些凸多边形顶点就可以了。
如果将各个顶点连接成一条通路就找到了最优路线，而不需要每个点都检索一次，这样就大大减少了搜索次数，不会因为距离的增大而增大搜索时间。
下面给出这个算法的流程：
1.建立各个凸多边形顶点的通路表TAB，表示顶点A到顶点B是否可达，将可达的顶点分组保存下来。
如：( (0,0) (100,0) ),这一步骤在程序刚开始时完成，不要放在搜索过程中空耗时间[5]。
2.开始搜索A点到B点的路线。
3.检测A点可以直达凸多边形顶点中的哪一些，挑选出最合适的顶点X1。
4.检测与X1相连（能够接通）的有哪些顶点，挑出最合适的顶点X2。
5.X2是否是终点B？是的话结束，否则转步骤4（X2代入X1）。
如此下来，搜索只发生在凸多边形的顶点，节省了大量的搜索时间，而且找到的路线无需再修剪锯齿，保证了路线的最优性。
另外场景中的凸多边形的顶点的通路表在建立场景的时候就可以一并建立了。
使用这种方法的主要原因还在于我们在建立场景的时候都是使用了凸多边形(主要为矩形)。
这种方法搜索可以减少大量搜索点，从本质上来说是一种空间换时间的方法，而且搜索时A*能够用的启发条件，在矢量搜索时依然可以使用。
4.4 人工智能在BREW开发中应该注意的问题
在人工智能当中，有很多决策的算法。
但是并不是每种方法都适用于移动终端的开发。
这是由于手机的CPU运算速率较慢和内存容量较小所造成的。
因此我们在选择算法时要尽量选择高效、快速和内存较小的算法。
另外，即使我们使用的AI算法只有一个缺陷，也会使得这个缺陷暴露。
因此，我们要尽量选择精确、完备的AI算法。
5.结束语
现有的人工智能产品相对于即将到来的人工智能应用可以说微不足道，但是它们预示着人工智能的未来。
对人工智能更高层次的需求已经并会继续影响我们的工作、学习和生活，本文以本人在实际项目中开发的多款基于BREW 平台的手机游戏为基础，结合理论知识，介绍了人工智能的基本概念，详细分析了应用于手机游戏中人工智能的关键技术、编程实现细节以及需要注意的问题。
参考文献
[1]Ray Rischpater．Software Development for the QUALCOMM BREW Platform［M］．Berkeley, Apress, 2003
[2]李贺、尹国强、蒋亮．BREW技术开发与应用［M］．北京，机械工程出版社，2006
[3]QUALCOMM．BREW SDK User’s Guide［EB/OL］．, 2002
[4]傅京孙，蔡自兴，徐光佑．人工智能及其应用［M］．北京，:清华大学出版社，2001
[5]Jacquin A E．A novel fractal block-coding technique for digital Image [C]．Proceedings of ICASSP IEEE
International conference on ASSP, 1990. 872-891.
Application of Artificial Intelligence in Cell Phone Games
Based on BREW Platform
Chen He, Chen Feng, Zhao Liangbi
School of Telecommunication Engineering，Beijing University of Posts and Telecommunication,
Beijing, China (100876)
Abstract
With the implement of 3rd Generation Mobile Network and the more multiplex function on the mobile terminal, the application of the cell phone is now going far beyond from the traditional function of calling and sending messages, and the user requirement on the mobile applications, such as cell phone game, is upgrading. Presently the opponent to the game user in cell phone games are primary the “enemies” which are simulated by the game program themselves, so the entertainment degree of the game is determined by the level of the “enemies”. The artificial intelligence is a good method for increasing the challengeable level of the “enemies” in the games and this paper depicts the key technology of applying artificial intelligence in cell phone games with the author’s experience on developing mobile applications based on the BREW platform.
Keywords: cell phone game artificial intelligence BREW platform。
