android手機(jī)引擎的設(shè)計(jì)與實(shí)現(xiàn)

android手機(jī)引擎的設(shè)計(jì)與實(shí)現(xiàn)

0游戲引擎的發(fā)展現(xiàn)狀智能手機(jī)是指獨(dú)立的操作系統(tǒng)，支持用戶下載、安裝第三方服務(wù)提供商提供的聊天、游戲和其他應(yīng)用程序，并通過移動(dòng)通信網(wǎng)絡(luò)實(shí)現(xiàn)無線網(wǎng)絡(luò)接入的手機(jī)的總稱。目前,主流的智能手機(jī)操作系統(tǒng)有Android,iOS和WindowsMo-bile等系統(tǒng)。其中,Android是由Google開發(fā)的開源操作系統(tǒng),其SDK已非常完善。隨著Android手機(jī)成本的下降,以及Google公司成功收購摩托羅拉移動(dòng)公司,其市場占有率將更大。所以,基于Android平臺的游戲等各種應(yīng)用開發(fā)將具有廣闊的發(fā)展前景。對游戲創(chuàng)意的良好性能支撐,提高開發(fā)效率,縮短開發(fā)和推出市場的周期,都是影響一款游戲是否成功的關(guān)鍵因素,而這些因素的改善都與游戲引擎的設(shè)計(jì)息息相關(guān)。游戲引擎是為運(yùn)行某類游戲的機(jī)器所設(shè)計(jì)的,并且能夠被該機(jī)器所識別的代碼集合。經(jīng)過不斷的發(fā)展,游戲引擎已經(jīng)成為一套由多個(gè)子系統(tǒng)共同構(gòu)成的復(fù)雜系統(tǒng),控制游戲的執(zhí)行,使玩家與終端能夠交互［１］。在現(xiàn)代手機(jī)游戲中,游戲角色的真實(shí)感體驗(yàn)是衡量游戲品質(zhì)的一個(gè)重要標(biāo)準(zhǔn)［２］。通常游戲的真實(shí)感體驗(yàn)由圖形渲染、物理模擬和人工智能等模塊完成。目前,已有的手機(jī)游戲引擎在圖形渲染和物理模擬方面取得了長足的進(jìn)步,但其人工智能模塊仍然顯得簡單甚至沒有［３］,應(yīng)用這些引擎設(shè)計(jì)出的游戲其非玩家控制角色過于遲鈍或者程式化,影響了游戲的真實(shí)性,所以游戲引擎的人工智能仍有很大的發(fā)展和創(chuàng)新空間［４］。對于在線游戲而言,由于這類游戲需要技術(shù)性能和用戶感知視覺質(zhì)量并舉［５］,對人工智能技術(shù)的需求很大。同樣在3D游戲開發(fā)中,相對于游戲引擎的其它部分,人工智能的研究力度還有待進(jìn)一步加強(qiáng),比如路徑搜索算法［６］直接影響著游戲的響應(yīng)速度［７］。當(dāng)前越來越多的游戲引擎是基于移動(dòng)平臺的。當(dāng)游戲越來越復(fù)雜的時(shí)候,軟件基本開發(fā)方法將很難滿足這些游戲的開發(fā)要求。文獻(xiàn)研究結(jié)果表明,在移動(dòng)平臺上開發(fā)一個(gè)游戲引擎時(shí),選定一個(gè)設(shè)計(jì)模式,理清設(shè)計(jì)目標(biāo)和思路是很重要的。本文通過對Android游戲的程序結(jié)構(gòu)進(jìn)行研究,基于模塊化的思想,設(shè)計(jì)實(shí)現(xiàn)了一個(gè)基于Android系統(tǒng)的2D游戲引擎LAndGame2D,重點(diǎn)對人工智能模塊中的基本算法:最短路徑搜索算法進(jìn)行了優(yōu)化,有益于提高游戲的真實(shí)感體驗(yàn)。1功能集的開發(fā)游戲引擎是面向游戲開發(fā)的通用內(nèi)核,將游戲程序設(shè)計(jì)中最通用的功能集成為一個(gè)游戲開發(fā)平臺。通常游戲引擎包括的模塊有智能模擬、物體成像、物理演算、碰撞運(yùn)算、角色的操作、聲音管理等,游戲開發(fā)人員可以通過API函數(shù)調(diào)用這些模塊,快速方便的開發(fā)游戲。1.1游戲控制類設(shè)計(jì)游戲引擎,首先需要分析游戲的運(yùn)行機(jī)制,提取游戲的基本構(gòu)成元素。Android游戲主要包括一個(gè)Activity類、一個(gè)流程控制類、一個(gè)游戲線程類和若干個(gè)游戲?qū)ο箢?。其中Activity類是游戲程序的基本執(zhí)行單元,控制復(fù)雜的游戲生命周期,如游戲的啟動(dòng)、暫停、退出等。游戲控制類提供了游戲的界面切換的方法。游戲線程類循環(huán)檢測可能發(fā)生的各種事件,計(jì)算游戲狀態(tài),刷新屏幕。游戲?qū)ο箢愋枰x對象和執(zhí)行動(dòng)作。當(dāng)游戲事件觸發(fā)時(shí),游戲?qū)ο笸ㄟ^回調(diào)函數(shù)調(diào)用相應(yīng)的操作。Android平臺游戲運(yùn)行機(jī)制如圖1所示。1.2人工智能中的最短路徑搜索在游戲設(shè)計(jì)中通常采用的人工智能技術(shù)主要有模糊邏輯、有限狀態(tài)機(jī)、尋徑算法等。模糊邏輯使用模糊值來表示模糊的概念和進(jìn)行知識推理,被廣泛應(yīng)用于決策推理和行為選擇。例如,非玩家角色評估玩家展示的威脅,控制非玩家隊(duì)友的行為等。有限狀態(tài)機(jī)是基于規(guī)則的人工智能系統(tǒng),來源于自動(dòng)機(jī)理論,可以管理整個(gè)游戲場景,也可以操作單個(gè)游戲?qū)ο蠛腿宋?。尋徑算法是游戲開發(fā)中的常見算法,非玩家角色需要在較短時(shí)間內(nèi)找到由當(dāng)前位置到主角位置的最短路徑并且避免與障礙物碰撞,其依賴的核心基礎(chǔ)是人工智能中的最短路徑搜索算法。在現(xiàn)有游戲引擎中,對于最短路徑求解問題,先后有深度優(yōu)先算法、廣度優(yōu)先算法、Dijkstra算法、A*算法等諸多算法被提出。其中,深度優(yōu)先和廣度優(yōu)先算法屬于狀態(tài)空間搜索算法,其最大缺陷是搜索速度低,當(dāng)狀態(tài)空間很大或者不可預(yù)測的情況下則無法給出最優(yōu)解。Dijkstra算法能夠保證搜索成功率,但是由于需要遍歷計(jì)算的節(jié)點(diǎn)過多,所以搜索速度慢。而A*算法是啟發(fā)式搜索算法,它只需要產(chǎn)生全部狀態(tài)空間的部分結(jié)點(diǎn)及關(guān)系,就可求解,搜索效率較高,但是由于該算法沒有回溯,不能確保尋找到的路徑一定是最優(yōu)路徑。近年來,遺傳算法因?yàn)槠鋸?qiáng)大的并行搜索能力,也被用來求解最短路徑問題,其搜索成功率優(yōu)于A*算法,且搜索速度優(yōu)于Dijkstra算法。但標(biāo)準(zhǔn)遺傳算法存在易陷入早熟的缺陷,采用該算法實(shí)現(xiàn)尋徑,則在游戲中常導(dǎo)致非玩家角色在一個(gè)角落不停地繞圈。顯然,這會極大影響玩家的真實(shí)感體驗(yàn)。綜合考慮算法的搜索速度和搜索成功率,本文引入Boltzmann行動(dòng)選擇策略解決標(biāo)準(zhǔn)遺傳算法易早熟的缺陷,并以此優(yōu)化遺傳算法作為引擎尋徑問題求解的基本算法。2非精確狀態(tài)下的行動(dòng)選擇策略Boltzmann行動(dòng)選擇策略是一種被搜索算法所采用的,適于求解非精確狀態(tài)信息下的順序決策過程問題的行動(dòng)選擇策略。本文所改進(jìn)的遺傳算法利用基于Boltzmann行動(dòng)選擇策略［９］替代輪盤賭選擇策略,從而解決標(biāo)準(zhǔn)遺傳算法容易早熟的問題。2.1算法熟化能力標(biāo)準(zhǔn)遺傳算法一般采用輪盤賭選擇策略,給定種群規(guī)模為n的群體p={a１,a２,···,aｎ},個(gè)體aｊ∈P的適應(yīng)值為f(aｊ),其選擇概率為式(1)決定后代種群中個(gè)體的概率分布。當(dāng)種群中個(gè)體的適應(yīng)值差異較大時(shí),最優(yōu)個(gè)體和最差個(gè)體被選擇的概率之比成指數(shù)級增長。最優(yōu)個(gè)體將顯著增加在下一代的生存機(jī)會,而最差個(gè)體的生存機(jī)會則會被剝奪。最優(yōu)個(gè)體快速充滿種群,從而導(dǎo)致種群的多樣性迅速降低,遺傳算法也就過早地喪失進(jìn)化能力,陷入算法早熟問題。Boltzmann行動(dòng)選擇策略采用隨機(jī)接收準(zhǔn)則選擇行動(dòng),并根據(jù)當(dāng)前狀態(tài)下可選行動(dòng)的估計(jì)價(jià)值決定選擇行動(dòng)的概率。Boltzmann選擇機(jī)制可以有效地解決優(yōu)化算法難以避免的局部最優(yōu)問題,使系統(tǒng)最終演化到全局極小點(diǎn)［１０］,尋找到最優(yōu)的行動(dòng)選擇策略。設(shè)行動(dòng)全體集合為A,行動(dòng)估計(jì)價(jià)值集合為VＡ,a１,a２,…,aｎ∈A為當(dāng)前狀態(tài)下可選的行動(dòng),而v(a１),v(a２),…,v(aｎ)∈VＡ分別為各行動(dòng)估計(jì)價(jià)值提出對應(yīng)的估計(jì)價(jià)值,當(dāng)前狀態(tài)下選擇任一行動(dòng)aｋ{a１,a２,…,aｎ}的概率為其中,k=1,2,…,n,T>0是退火溫度,是控制進(jìn)化過程中選擇壓力的關(guān)鍵,在種群的進(jìn)化過程中,進(jìn)化早期時(shí)選擇壓力較小,適應(yīng)值較差的個(gè)體也需要一定的生存能力,退火溫度緩慢地遞減;進(jìn)化后期需要較大的選擇壓力來縮小搜索鄰域,加快最優(yōu)解改善的速度,退火溫度遞減也需要越快,因此退火溫度變化趨勢應(yīng)該是不斷成非線性下降的過程,所以,本文引入神經(jīng)網(wǎng)絡(luò)中的Sigmoid函數(shù)作為退火溫度的變化系數(shù),即其函數(shù)曲線圖如圖2所示。基于Boltzmann選擇機(jī)制的遺傳算法中個(gè)體被選擇的概率定義為式中:n———種群規(guī)模,c———種群進(jìn)化迭代循環(huán)次數(shù),m———最大迭代次數(shù),T０———退火溫度初始值,Tｍｉｎ———冷卻溫度。T會隨著迭代次數(shù)的增加而減小,選擇壓力就隨之增大,最終達(dá)到冷卻溫度。2.2算法有效性測試為了驗(yàn)證算法的收斂性能以及跳出局部最優(yōu)解的能力,本文對基于輪盤賭選擇的標(biāo)準(zhǔn)遺傳算法(SGA)和基于Bo-ltzmann選擇的優(yōu)化遺傳算法(BGA)進(jìn)行了比較測試。測試選取3個(gè)經(jīng)典的遺傳算法性能測試函數(shù),這些測試函數(shù)都是既有全局解又有多個(gè)極值點(diǎn)的函數(shù)其中,-2.048≤xｉ≤2.048,i=1,2;該函數(shù)是二維單峰難以極小化的病態(tài)函數(shù),函數(shù)最小值是0其中,-3≤x１≤3,-2≤x２≤2,函數(shù)最小值是10.316其中,-10≤xｉ≤10,i=1,2,函數(shù)最小值是186.731。用SGA和BGA兩種遺傳算法,對以上的測試函數(shù)進(jìn)行100次計(jì)算,求出收斂值。其中,計(jì)算機(jī)的配置為Pen-tium(R)4微處理器,主頻為2.8GHz,內(nèi)存容量為1.5G。遺傳參數(shù)設(shè)置:種群規(guī)模為60,最大迭代次數(shù)100,交叉率0.8,變異率0.05。計(jì)算結(jié)果見表1和表2。表中結(jié)果都是平均值,收斂時(shí)間單位為s。由表1和表2可知,BGA遺傳算法雖然在收斂時(shí)間開銷上比SGA遺傳算法有所增加,但是成功的收斂次數(shù)多,提高了算法的收斂率,而且收斂的極值更加接近理論計(jì)算得到的函數(shù)值,收斂的穩(wěn)定性較好,從而很好的避免了遺傳算法陷入早熟的問題。此外,我們對BGA遺傳算法和A*算法在游戲設(shè)計(jì)中的應(yīng)用效果進(jìn)行了比較。圖3和圖4是某次設(shè)定的兩點(diǎn)最短路徑搜索效果示意,顯然,BGA遺傳算法優(yōu)于A*算法尋找到的路徑。由于搜索速度快,A*算法在游戲設(shè)計(jì)中廣泛采用;但是,A*算法不能回溯,不一定能夠找到最短路徑,表現(xiàn)在游戲中就是非玩家角色易走錯(cuò)路、亂跑、行為飄忽和繞圈子等。相反,BGA遺傳算法則能保證較高的最短路徑搜索成功率,非玩家角色能智能地找到主角位置,增加了游戲的真實(shí)感體驗(yàn)。雖然在時(shí)間開銷方面,BGA遺傳算法搜索速度遜于A*算法,但由于當(dāng)前嵌入式CPU的主頻極高,玩家體驗(yàn)不出這種時(shí)間開銷差別。綜合考慮,我們采用BGA遺傳算法作為基礎(chǔ)尋徑算法。3游戲引擎的設(shè)計(jì)和實(shí)現(xiàn)3.1游戲系統(tǒng)模塊結(jié)構(gòu)游戲引擎是一種中間件,它是依賴操作系統(tǒng)來控制硬件的。本文設(shè)計(jì)的游戲引擎LAndGame2D架構(gòu)在操作系統(tǒng)層之上,其主要包括圖形引擎、物理引擎、人工智能模塊,網(wǎng)絡(luò)模塊、音效模塊、工具模塊、事件處理模塊等等［１１］,模塊結(jié)構(gòu)如圖5所示。其中,游戲的核心類是為游戲提供框架,主要實(shí)現(xiàn)游戲邏輯類、流程控制類。人工智能模塊是提高游戲的智能,增加游戲的真實(shí)感體驗(yàn)。圖形引擎的功能是用于產(chǎn)生游戲角色及周邊場景的圖形,把讀取的所有數(shù)據(jù)及時(shí)轉(zhuǎn)化成屏幕顯示的圖形。物理引擎用于在游戲中準(zhǔn)確地實(shí)現(xiàn)物理模擬,通過剛體物體賦予真實(shí)的物理屬性的方式來計(jì)算運(yùn)動(dòng)和碰撞。網(wǎng)絡(luò)模塊負(fù)責(zé)游戲的聯(lián)網(wǎng)對戰(zhàn)任務(wù),管理游戲中所需要交互的數(shù)據(jù)的傳送工作。音效模塊主要處理播放聲音和聲音的管理功能。工具模塊是將游戲中常用的操作進(jìn)行封裝,如向量計(jì)算、定時(shí)器等。事件處理完成對用戶輸入操作進(jìn)行響應(yīng)和對游戲內(nèi)部事件處理的功能。3.2人工智能模塊設(shè)計(jì)在游戲邏輯類的實(shí)現(xiàn)中,LAndGame2DActivity是游戲的主類和入口程序,將對整個(gè)游戲的生命周期進(jìn)行控制,同時(shí)還提供了事件處理函數(shù)。比如:處理按鍵、觸摸等。LAndGame2DActivity繼承了Android應(yīng)用框架提供的Ac-tivity類。流程控制類主要用于游戲狀態(tài)機(jī)制來控制不同界面之間的切換,狀態(tài)機(jī)制就是對游戲定義多個(gè)狀態(tài),每一個(gè)狀態(tài)所顯示的界面都不同。游戲引擎框架中的流程控制類是LAndGame2DView,該類繼承自Android應(yīng)用開發(fā)框架層的SurfaceView類,SurfaceView類的實(shí)現(xiàn)原理是在繪圖之前必須使用lockCanvas方法鎖定畫布,得到畫布后在畫布上進(jìn)行繪制,繪制完成后使用unlockCanvasAndPost方法解鎖畫布,最后顯示到屏幕上。線程類使用run()方法可以隨時(shí)監(jiān)聽事件的觸發(fā),進(jìn)而改變狀態(tài),更新界面顯示。監(jiān)視事件需要繼承SurfaceHolder.Callback接口增加回調(diào)函數(shù)。人工智能模塊主要實(shí)現(xiàn)了基于Boltzmann選擇遺傳算法的尋徑算法、模糊邏輯和有限狀態(tài)機(jī)?；贐oltzmann選擇遺傳算法的尋徑算法實(shí)現(xiàn)步驟是首先為染色體進(jìn)行二進(jìn)制編碼。由于游戲地圖是由一些單元格組成,當(dāng)非玩家角色處在起始點(diǎn)時(shí)運(yùn)動(dòng)方向有上、下、左和右4種選擇,因此需要用兩個(gè)比特表示這4種情況。見表3。接著產(chǎn)生初始種群個(gè)體,設(shè)置遺傳算法的參數(shù),測試每個(gè)染色體能使非玩家角色所能到達(dá)的最遠(yuǎn)位置距離目標(biāo)點(diǎn)的長度,即計(jì)算適應(yīng)度值。函數(shù)CalculateFitnessValue()經(jīng)過計(jì)算會返回一個(gè)適應(yīng)度值,其中計(jì)算適應(yīng)度值的程序如下:程序中dist_x和dist_y就是非玩家角色所在的位置相對于目標(biāo)點(diǎn)的水平和垂直偏離值。如果非玩家角色到達(dá)出口,則dist_x+dist_y=0。計(jì)算兩點(diǎn)間距離比較常用的方法是兩點(diǎn)間距離坐標(biāo)公式,但是為了優(yōu)化程序的性能,減小計(jì)算量,可以利用不需要開方和平方的蒙特卡羅距離計(jì)算兩點(diǎn)間距離。dist計(jì)算的就是蒙特卡羅距離。最后通過Boltzmann選擇選出參與交叉的兩個(gè)個(gè)體后,實(shí)現(xiàn)交叉和變異操作后得到新的染色體繼續(xù)加入新的群體,完成一次迭代過程。不斷重復(fù)以上過程直到非玩家角色到達(dá)目標(biāo)點(diǎn)。模糊實(shí)現(xiàn)了幾種歸屬函數(shù),如布爾歸屬函數(shù),三角形歸屬函數(shù),梯形歸屬函數(shù)等。模糊處理定義了聯(lián)集、交集、補(bǔ)集操作。有限狀態(tài)機(jī)定義了一個(gè)簡單狀態(tài)機(jī)框架。圖形引擎主要是負(fù)責(zé)地圖場景管理模塊的實(shí)現(xiàn)。地圖管理中的圖層對象由Layer類實(shí)現(xiàn),Layer類封裝一個(gè)可視元素的位置、寬度、高度和可見性等信息。圖層不是每次顯示一個(gè)單個(gè)的圖像,而是顯示多個(gè)依次排列的圖像,當(dāng)創(chuàng)建圖層時(shí),通過指定貼磚排列構(gòu)成圖層。圖層要求所有的貼磚圖像大小必須相同。當(dāng)布置貼磚柵格時(shí),貼磚可以按任意的組合方式混合和匹配。物理引擎是通過剛體物體賦予真實(shí)的物理屬性的方式來計(jì)算運(yùn)動(dòng)和碰撞。本文設(shè)計(jì)的物理引擎主要提供碰撞檢測技術(shù)的功能。在游戲中實(shí)體對象的位置改變的情況下會發(fā)生碰撞,實(shí)現(xiàn)碰撞檢測主要包括:確定檢測對象、檢測是否碰撞、處理碰撞這3個(gè)方面。碰撞對象主要分為游戲?qū)嶓w對象之間的碰撞和游戲?qū)嶓w對象與環(huán)境之間的碰撞。網(wǎng)絡(luò)模塊為游戲支持網(wǎng)絡(luò)服務(wù)。網(wǎng)絡(luò)連接主要分為互聯(lián)網(wǎng)和局域網(wǎng),互聯(lián)網(wǎng)需要封裝Http協(xié)議,可以通過標(biāo)準(zhǔn)java接口實(shí)現(xiàn)Android游戲引擎的聯(lián)網(wǎng)操作,另外需要注意網(wǎng)絡(luò)通信的中文亂碼問題。局域網(wǎng)則主要封裝藍(lán)牙連接及傳輸數(shù)據(jù)的功能。音效模塊提供對背景音效和動(dòng)作音效的管理,其中包括音樂類型、當(dāng)前播放次數(shù)、音樂結(jié)束處理,循環(huán)播放音樂、音樂模式管理等函數(shù)。工具模塊主要封裝游戲經(jīng)常使用的工具類。實(shí)現(xiàn)的工具類主要有計(jì)時(shí)器類、坐標(biāo)類、隨機(jī)數(shù)類、字符串?dāng)U展類、文件操作類等。事件處理模塊主要負(fù)責(zé)用戶和手機(jī)終端交互的處理,需要考慮到事件的類型、發(fā)起者、被發(fā)起者、事件參數(shù)等因素。當(dāng)一個(gè)事件被觸發(fā)時(shí),發(fā)送消息給事件響應(yīng)者,事件響應(yīng)者收到消息后,根據(jù)消息的內(nèi)容來判斷處理相應(yīng)的事件。4飛行彈射游戲的實(shí)現(xiàn)在游戲引擎LAndGame2D完成的基礎(chǔ)上,本文利用該游戲引擎開發(fā)了一款飛行射擊游戲,該游戲運(yùn)行的流程圖如圖6所示。根據(jù)游戲流程圖將飛行射擊游戲劃分為5個(gè)模塊:(1)移動(dòng)模塊和炮彈生成模塊,完成飛機(jī)和炮彈的移動(dòng)、生成功能,主要由圖形引擎中的人物顯示模塊完成。(2)