摘 要: 碰撞檢測(cè)是游戲人工智能設(shè)計(jì)領(lǐng)域中的基本研究問(wèn)題,快速智能的碰撞檢測(cè)算法直接決定游戲效果的好壞。針對(duì)捕魚類游戲的碰撞要求,設(shè)計(jì)了一種以空間網(wǎng)格劃分為基礎(chǔ)結(jié)合多重因素分析的高效智能碰撞算法,增加了相關(guān)游戲的可玩性及運(yùn)行效率。
關(guān)鍵詞: 游戲算法;人工智能;碰撞檢測(cè);網(wǎng)格
人工智能技術(shù)在游戲設(shè)計(jì)中的應(yīng)用越來(lái)越廣泛,已經(jīng)成為游戲設(shè)計(jì)成功與否的關(guān)鍵因素。碰撞問(wèn)題則是游戲AI設(shè)計(jì)領(lǐng)域中的基本研究問(wèn)題。碰撞問(wèn)題的解決過(guò)程大致可以分為碰撞模型建立、碰撞檢測(cè)、碰撞確認(rèn)與響應(yīng)三個(gè)階段。碰撞模型建立就是建立參與碰撞的對(duì)象以及建立便于碰撞檢測(cè)的數(shù)據(jù)模型,碰撞檢測(cè)過(guò)程是根據(jù)一定的碰撞規(guī)則和因素對(duì)參與碰撞的對(duì)象在既定的數(shù)據(jù)模型下進(jìn)行檢測(cè)的過(guò)程,對(duì)碰撞檢測(cè)的反饋數(shù)據(jù)進(jìn)行分析篩查得出確認(rèn)結(jié)果并執(zhí)行相應(yīng)的操作就是碰撞響應(yīng)。雖然國(guó)內(nèi)外有關(guān)學(xué)者就碰撞問(wèn)題也作了大量的研究,但是針對(duì)游戲設(shè)計(jì)的算法不多,若在游戲AI設(shè)計(jì)中實(shí)現(xiàn),需要進(jìn)行修改優(yōu)化。另一方面,不同類型、玩法、主題的游戲?qū)τ趯?duì)象的碰撞要求存在著很大的差異。例如,射擊類游戲比較關(guān)注子彈與目標(biāo)物體的碰撞,又如動(dòng)作類游戲則比較關(guān)心對(duì)象運(yùn)動(dòng)間的碰撞。由此可見,要根據(jù)具體游戲碰撞需求設(shè)計(jì)適合的碰撞算法來(lái)給予解決。本文根據(jù)當(dāng)下熱門的捕魚游戲中的碰撞要求,設(shè)計(jì)了一種以空間網(wǎng)格劃分為基礎(chǔ),結(jié)合多重因素分析的高效智能碰撞算法,增加了相關(guān)游戲的可玩性及運(yùn)行效率。
1 碰撞檢測(cè)模型的建立
近年來(lái)以捕魚為題材的休閑類游戲發(fā)展相當(dāng)迅速。例如,《捕魚達(dá)人》成為2011年iPhone付費(fèi)應(yīng)用收入最高的國(guó)產(chǎn)游戲之一[1]。該類游戲大體是由玩家購(gòu)買子彈,調(diào)整網(wǎng)槍的威力,就可以攻擊游戲中游動(dòng)的魚類以獲取積分。被攻擊的魚類品種不同,其積分也不同。玩家用來(lái)攻擊魚類的網(wǎng)槍共分為若干個(gè)等級(jí),等級(jí)越高的網(wǎng)槍耗費(fèi)的子彈越多,但其漁網(wǎng)捕魚能力也越大。對(duì)于該類游戲碰撞問(wèn)題的關(guān)鍵是如何檢測(cè)漁網(wǎng)與魚類動(dòng)態(tài)碰撞的情況。不少開發(fā)者改良使用GJK算法[2]和LC算法[3]等有關(guān)碰撞位置計(jì)算的著名算法。以上算法都是通過(guò)計(jì)算物體間表面的最小距離來(lái)確定碰撞位置,實(shí)施過(guò)程中需要遍歷檢測(cè)所有魚類對(duì)象與漁網(wǎng)的實(shí)時(shí)距離來(lái)判斷碰撞。這樣的算法雖然實(shí)現(xiàn)簡(jiǎn)單,但是對(duì)于變速轉(zhuǎn)向?qū)ο蟮呐鲎矙z測(cè)精度不高,而且隨著對(duì)象數(shù)量的上升而增加運(yùn)算量影響運(yùn)行速率。
本文提出的一種基于空間網(wǎng)格劃分的碰撞檢測(cè)優(yōu)化算法既能增加碰撞檢測(cè)精度又能減少CPU的運(yùn)算量。具體是根據(jù)某種規(guī)則將游戲場(chǎng)景劃分成一個(gè)個(gè)小的網(wǎng)格,為每個(gè)網(wǎng)格對(duì)應(yīng)一個(gè)列表用來(lái)記錄所有屬于該單元網(wǎng)格的對(duì)象。由于不相鄰單元網(wǎng)格的對(duì)象之間距離較遠(yuǎn),因此只需檢測(cè)同一個(gè)單元網(wǎng)格或相鄰單元網(wǎng)格內(nèi)的對(duì)象間的相交情況即可。在捕魚類游戲中,主要檢測(cè)的是漁網(wǎng)與魚類的碰撞,所以漁網(wǎng)也要進(jìn)行網(wǎng)格化,可以利用場(chǎng)景網(wǎng)格來(lái)記錄即可,這樣只要直接檢查漁網(wǎng)打開時(shí)所屬網(wǎng)格矩陣范圍內(nèi)有可能碰撞的魚類對(duì)象,而無(wú)需遍歷所有的魚類對(duì)象了,因此大大減少了檢測(cè)的數(shù)量。
為了不影響碰撞檢測(cè)的精確度,場(chǎng)景分割網(wǎng)格應(yīng)以正方形單元格為單位,大小與最小魚類的正方形包圍盒一致。魚類要設(shè)置捕捉特征點(diǎn),等級(jí)越高的魚類越大,特征點(diǎn)就越多(最多有6個(gè))。特征點(diǎn)也可以是動(dòng)態(tài)變化的,例如魔鬼魚當(dāng)翅膀全部打開的時(shí)候所有特征點(diǎn)才可以被捕捉到,如圖1所示。然后根據(jù)魚類對(duì)象特征點(diǎn)所在的位置將各個(gè)魚類對(duì)象分配到該網(wǎng)格的對(duì)應(yīng)單元格內(nèi)。
場(chǎng)景網(wǎng)格分割更好地記錄了魚類對(duì)象在屏幕的位置和漁網(wǎng)捕魚矩陣,從而利于隨后的碰撞檢測(cè)。魚類對(duì)象的位置可以通過(guò)其特征點(diǎn)定位實(shí)現(xiàn),給每一個(gè)單元格建立一個(gè)寄存器來(lái)存儲(chǔ)該單元格中不同魚類對(duì)象的特征點(diǎn)。實(shí)際應(yīng)用時(shí)可以利用一個(gè)二維數(shù)組來(lái)實(shí)現(xiàn)單元格特征點(diǎn)存儲(chǔ)器的功能,二維數(shù)組行數(shù)是網(wǎng)格單元格總數(shù),列數(shù)是游戲魚類對(duì)象的實(shí)例數(shù)上限。當(dāng)一種魚類對(duì)象實(shí)例化時(shí)都需要產(chǎn)生一個(gè)對(duì)應(yīng)流水標(biāo)識(shí)號(hào),利用單元格索引號(hào)和魚類對(duì)象流水標(biāo)識(shí)號(hào)構(gòu)成二維數(shù)組內(nèi)特征點(diǎn)存儲(chǔ)單元的索引值。這樣的算法能迅速實(shí)現(xiàn)數(shù)據(jù)查找和更新。與此同時(shí),魚類對(duì)象也需要設(shè)置一個(gè)存儲(chǔ)特征點(diǎn)所在單元格索引值的存儲(chǔ)器,存儲(chǔ)器的大小根據(jù)對(duì)應(yīng)魚類特征點(diǎn)數(shù)量來(lái)確定。該存儲(chǔ)器可以使用一個(gè)一維數(shù)組來(lái)實(shí)現(xiàn),特征點(diǎn)標(biāo)識(shí)號(hào)可以作為數(shù)組的索引下標(biāo)。
魚類對(duì)象在游動(dòng)過(guò)程中,特征點(diǎn)位置必然發(fā)生變化,因此需要實(shí)時(shí)判斷特征點(diǎn)所在的單元格,更新單元格特征點(diǎn)寄存器對(duì)應(yīng)的數(shù)據(jù)項(xiàng)目,并且把單元格索引值重新計(jì)入魚類對(duì)象的特征點(diǎn)存儲(chǔ)器。這樣就可以實(shí)時(shí)地為碰撞檢測(cè)提供準(zhǔn)確的數(shù)據(jù)基礎(chǔ)。
2 碰撞檢測(cè)的過(guò)程
碰撞檢測(cè)首先需要建立監(jiān)聽器,監(jiān)聽對(duì)象的狀態(tài)變化以便觸發(fā)碰撞檢測(cè)過(guò)程。例如,魚類對(duì)象碰撞檢測(cè)可以利用游戲場(chǎng)景網(wǎng)格,監(jiān)聽單元格特征點(diǎn)寄存器,若寄存器存有不同魚類對(duì)象的特征點(diǎn),就可以觸發(fā)魚類對(duì)象碰撞檢測(cè)過(guò)程進(jìn)行處理。
當(dāng)玩家使用某種等級(jí)網(wǎng)槍撒網(wǎng)捕魚時(shí),根據(jù)撒網(wǎng)點(diǎn)所在的單元格,推算出漁網(wǎng)陣列,即可獲得一個(gè)單元格索引值集合Ai。碰撞檢測(cè)過(guò)程是逐一抽取集合中的單元格,檢測(cè)其中存在有特征點(diǎn)的魚類對(duì)象,然后逐一把這些魚類對(duì)象的特征點(diǎn)位置寄存器數(shù)據(jù)集合Bi直接與漁網(wǎng)單元格索引值集合Ai進(jìn)行比較,若是Bi∈Ai,則可以判斷該魚類對(duì)象所有特征點(diǎn)都包含在漁網(wǎng)中。
傳統(tǒng)碰撞檢測(cè)過(guò)程最重要的是準(zhǔn)確地檢測(cè)碰撞,但從游戲的可玩性來(lái)說(shuō),僅以對(duì)象物理狀態(tài)來(lái)判斷碰撞是不夠的,需要分析其他游戲性因素進(jìn)行判斷。由此可以設(shè)定碰撞檢測(cè)函數(shù)Pi=f(x1+x2+x3+x4+x5+xn), Pi代表某魚類對(duì)象與漁網(wǎng)碰撞值,x1~xn代表各項(xiàng)因素,每項(xiàng)因素都有不同的權(quán)重,從而影響最終的碰撞值。各項(xiàng)因素設(shè)定及權(quán)重分配(以5項(xiàng)因素為例)如表1所示。
根據(jù)不同因素所起的作用,可以動(dòng)態(tài)調(diào)節(jié)它們之間的權(quán)重值,游戲在相同的框架下也能體現(xiàn)出不同的游戲性。例如,動(dòng)態(tài)修改x1與x2之間的權(quán)重,則捕魚技巧和游戲難度之間的體驗(yàn)感就會(huì)發(fā)生變化。再者,可以在一些因素中加入動(dòng)態(tài)參數(shù),使因素權(quán)值發(fā)生游戲性的變化。例如,對(duì)用戶在線時(shí)間參數(shù)x4引入相關(guān)計(jì)算公式y(tǒng)=[1+sin(x×π/t)]×x/30,y是因數(shù)權(quán)值,x是時(shí)間值,t是游戲送分減分周期,如圖4所示,曲線的斜率和周期都可以作適當(dāng)調(diào)節(jié),使權(quán)重值隨在線時(shí)間波動(dòng)上升。
3 碰撞的確認(rèn)與響應(yīng)
此外,必須是在漁網(wǎng)矩陣單元格中存在特征點(diǎn)的魚類對(duì)象才會(huì)觸發(fā)碰撞檢測(cè)函數(shù),函數(shù)是根據(jù)各項(xiàng)因素權(quán)重值返回碰撞值,以此決定是否發(fā)生實(shí)質(zhì)性碰撞。例如,上文提到的鯉魚和墨魚,因?yàn)锽1∈A1、B2∈A1,所以它們的x1權(quán)重值都可以得到40,而魔鬼魚因?yàn)锽3∩A1=20,只有一個(gè)特征點(diǎn)與漁網(wǎng)碰撞,它的x1權(quán)重值只為8(魔鬼魚共有5個(gè)特征點(diǎn))。從難度系數(shù)上來(lái)說(shuō),魔鬼魚最高、鯉魚最低,通過(guò)隨機(jī)換算可得魔鬼魚x2=10,墨魚x2=12,鯉魚x2=20。若其他因素假定都一樣合共為20,則可以推算出鯉魚碰撞值P1=40+20+20=80,墨魚P2=72,魔鬼魚P3=38。碰撞確認(rèn)與響應(yīng)的過(guò)程如圖5所示,碰撞檢測(cè)Y值低于60分,則判斷漁網(wǎng)捕魚不成功,需要累計(jì)該魚類對(duì)象被攻擊的次數(shù),以增加下次被捕的得分值。最重要的是要觸發(fā)魚類轉(zhuǎn)向逃跑的函數(shù)。若碰撞檢測(cè)Y值高于或等于60,則判斷該魚類對(duì)象被捕獲,魚類對(duì)象觸發(fā)捕獲函數(shù)啟動(dòng)捕獲動(dòng)畫,并實(shí)時(shí)增加玩家的積分值。但一個(gè)游戲往往會(huì)暗含一些非常規(guī)因素。例如,玩家突然獲得了超級(jí)魚槍,只要及時(shí)使用超級(jí)漁網(wǎng)接觸的所有魚類都被捕獲。在實(shí)現(xiàn)中,直接將非常規(guī)因素折算成相應(yīng)的得分值與Pi累加后再進(jìn)行判斷就可以了。
游戲AI算法跟一般程序的算法要求不同的是除了要考慮時(shí)間復(fù)雜度與空間復(fù)雜度的因素外,還要考慮游戲復(fù)雜多樣的可玩性要求。本文提出了一種新的基于空間網(wǎng)格劃分結(jié)合多重因素分析的智能碰撞算法,利用空間網(wǎng)格劃分和特征點(diǎn)來(lái)判斷對(duì)象碰撞關(guān)系,并分析游戲性的各項(xiàng)因素,合理分配權(quán)重實(shí)現(xiàn)碰撞檢測(cè),從而提高了算法的執(zhí)行速度,增加了游戲的可玩性。對(duì)相關(guān)游戲程序設(shè)計(jì)具有一定的應(yīng)用參考價(jià)值。
參考文獻(xiàn)
[1] 艾瑞咨詢.2011年中國(guó)網(wǎng)絡(luò)游戲行業(yè)四大盤點(diǎn)[DB/OL].(2011-12-13)[2012-02-01].http://game.iresearch.cn/15/20111213/158889.shtml.
[2] Matthew Peterson. Interactive QuickTime[M]. Elsevier Inc.2004:99-115.
[3] DOBKIN D P, KIRKPATRICK D G. A linear algorithm for determining the separation of convex polyhedra[J]. Journal of Algorithms, 1985(6):381-392.
[4] PETERS K. Flash ActionScript3.0動(dòng)畫高級(jí)教程[M].蘇金國(guó),譯.北京:人民郵電出版社,2010.
[5] STAHLER W.游戲編程數(shù)學(xué)和物流基礎(chǔ)[M].北京:機(jī)械工業(yè)出版社,2008.