基于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選擇遺傳算法的尋徑算法、模糊邏輯和有限狀態機?；贐oltzmann選擇遺傳算法的尋徑算法實現步驟是首先為染色體進行二進制編碼。由于游戲地圖是由一些單元格組成，當非玩家角色處在起始點時運動方向有上、下、左和右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選擇的遺傳算法，使得游戲更加具有真實感。游戲中具體的編碼設計是：一個基因表示一幀時間內敵機的移動方向?；蜷L度限制在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.］