摘  要： 碰撞檢測是游戲人工智能設(shè)計領(lǐng)域中的基本研究問題，快速智能的碰撞檢測算法直接決定游戲效果的好壞,。針對捕魚類游戲的碰撞要求,，設(shè)計了一種以空間網(wǎng)格劃分為基礎(chǔ)結(jié)合多重因素分析的高效智能碰撞算法，增加了相關(guān)游戲的可玩性及運(yùn)行效率,。
關(guān)鍵詞： 游戲算法,；人工智能；碰撞檢測,；網(wǎng)格

　人工智能技術(shù)在游戲設(shè)計中的應(yīng)用越來越廣泛,，已經(jīng)成為游戲設(shè)計成功與否的關(guān)鍵因素。碰撞問題則是游戲AI設(shè)計領(lǐng)域中的基本研究問題,。碰撞問題的解決過程大致可以分為碰撞模型建立,、碰撞檢測、碰撞確認(rèn)與響應(yīng)三個階段,。碰撞模型建立就是建立參與碰撞的對象以及建立便于碰撞檢測的數(shù)據(jù)模型,，碰撞檢測過程是根據(jù)一定的碰撞規(guī)則和因素對參與碰撞的對象在既定的數(shù)據(jù)模型下進(jìn)行檢測的過程，對碰撞檢測的反饋數(shù)據(jù)進(jìn)行分析篩查得出確認(rèn)結(jié)果并執(zhí)行相應(yīng)的操作就是碰撞響應(yīng),。雖然國內(nèi)外有關(guān)學(xué)者就碰撞問題也作了大量的研究,，但是針對游戲設(shè)計的算法不多，若在游戲AI設(shè)計中實現(xiàn),，需要進(jìn)行修改優(yōu)化,。另一方面，不同類型,、玩法,、主題的游戲?qū)τ趯ο蟮呐鲎惨蟠嬖谥艽蟮牟町悺＠?，射擊類游戲比較關(guān)注子彈與目標(biāo)物體的碰撞,，又如動作類游戲則比較關(guān)心對象運(yùn)動間的碰撞。由此可見,，要根據(jù)具體游戲碰撞需求設(shè)計適合的碰撞算法來給予解決,。本文根據(jù)當(dāng)下熱門的捕魚游戲中的碰撞要求，設(shè)計了一種以空間網(wǎng)格劃分為基礎(chǔ),，結(jié)合多重因素分析的高效智能碰撞算法,，增加了相關(guān)游戲的可玩性及運(yùn)行效率。
1 碰撞檢測模型的建立  
　近年來以捕魚為題材的休閑類游戲發(fā)展相當(dāng)迅速,。例如,，《捕魚達(dá)人》成為2011年iPhone付費(fèi)應(yīng)用收入最高的國產(chǎn)游戲之一[1]。該類游戲大體是由玩家購買子彈，調(diào)整網(wǎng)槍的威力,，就可以攻擊游戲中游動的魚類以獲取積分,。被攻擊的魚類品種不同，其積分也不同,。玩家用來攻擊魚類的網(wǎng)槍共分為若干個等級,，等級越高的網(wǎng)槍耗費(fèi)的子彈越多，但其漁網(wǎng)捕魚能力也越大,。對于該類游戲碰撞問題的關(guān)鍵是如何檢測漁網(wǎng)與魚類動態(tài)碰撞的情況,。不少開發(fā)者改良使用GJK算法[2]和LC算法[3]等有關(guān)碰撞位置計算的著名算法。以上算法都是通過計算物體間表面的最小距離來確定碰撞位置,，實施過程中需要遍歷檢測所有魚類對象與漁網(wǎng)的實時距離來判斷碰撞,。這樣的算法雖然實現(xiàn)簡單，但是對于變速轉(zhuǎn)向?qū)ο蟮呐鲎矙z測精度不高,，而且隨著對象數(shù)量的上升而增加運(yùn)算量影響運(yùn)行速率,。
　本文提出的一種基于空間網(wǎng)格劃分的碰撞檢測優(yōu)化算法既能增加碰撞檢測精度又能減少CPU的運(yùn)算量。具體是根據(jù)某種規(guī)則將游戲場景劃分成一個個小的網(wǎng)格,，為每個網(wǎng)格對應(yīng)一個列表用來記錄所有屬于該單元網(wǎng)格的對象,。由于不相鄰單元網(wǎng)格的對象之間距離較遠(yuǎn)，因此只需檢測同一個單元網(wǎng)格或相鄰單元網(wǎng)格內(nèi)的對象間的相交情況即可,。在捕魚類游戲中,，主要檢測的是漁網(wǎng)與魚類的碰撞，所以漁網(wǎng)也要進(jìn)行網(wǎng)格化,，可以利用場景網(wǎng)格來記錄即可,，這樣只要直接檢查漁網(wǎng)打開時所屬網(wǎng)格矩陣范圍內(nèi)有可能碰撞的魚類對象，而無需遍歷所有的魚類對象了,，因此大大減少了檢測的數(shù)量,。
　為了不影響碰撞檢測的精確度，場景分割網(wǎng)格應(yīng)以正方形單元格為單位,，大小與最小魚類的正方形包圍盒一致,。魚類要設(shè)置捕捉特征點，等級越高的魚類越大,，特征點就越多（最多有6個）,。特征點也可以是動態(tài)變化的，例如魔鬼魚當(dāng)翅膀全部打開的時候所有特征點才可以被捕捉到,，如圖1所示。然后根據(jù)魚類對象特征點所在的位置將各個魚類對象分配到該網(wǎng)格的對應(yīng)單元格內(nèi),。

　場景網(wǎng)格分割更好地記錄了魚類對象在屏幕的位置和漁網(wǎng)捕魚矩陣,，從而利于隨后的碰撞檢測。魚類對象的位置可以通過其特征點定位實現(xiàn)，給每一個單元格建立一個寄存器來存儲該單元格中不同魚類對象的特征點,。實際應(yīng)用時可以利用一個二維數(shù)組來實現(xiàn)單元格特征點存儲器的功能,，二維數(shù)組行數(shù)是網(wǎng)格單元格總數(shù)，列數(shù)是游戲魚類對象的實例數(shù)上限,。當(dāng)一種魚類對象實例化時都需要產(chǎn)生一個對應(yīng)流水標(biāo)識號,，利用單元格索引號和魚類對象流水標(biāo)識號構(gòu)成二維數(shù)組內(nèi)特征點存儲單元的索引值。這樣的算法能迅速實現(xiàn)數(shù)據(jù)查找和更新,。與此同時,，魚類對象也需要設(shè)置一個存儲特征點所在單元格索引值的存儲器，存儲器的大小根據(jù)對應(yīng)魚類特征點數(shù)量來確定,。該存儲器可以使用一個一維數(shù)組來實現(xiàn),，特征點標(biāo)識號可以作為數(shù)組的索引下標(biāo)。
　魚類對象在游動過程中,，特征點位置必然發(fā)生變化,，因此需要實時判斷特征點所在的單元格，更新單元格特征點寄存器對應(yīng)的數(shù)據(jù)項目,，并且把單元格索引值重新計入魚類對象的特征點存儲器,。這樣就可以實時地為碰撞檢測提供準(zhǔn)確的數(shù)據(jù)基礎(chǔ)。
2 碰撞檢測的過程
　碰撞檢測首先需要建立監(jiān)聽器,，監(jiān)聽對象的狀態(tài)變化以便觸發(fā)碰撞檢測過程,。例如，魚類對象碰撞檢測可以利用游戲場景網(wǎng)格,，監(jiān)聽單元格特征點寄存器,，若寄存器存有不同魚類對象的特征點，就可以觸發(fā)魚類對象碰撞檢測過程進(jìn)行處理,。
　當(dāng)玩家使用某種等級網(wǎng)槍撒網(wǎng)捕魚時,，根據(jù)撒網(wǎng)點所在的單元格，推算出漁網(wǎng)陣列,，即可獲得一個單元格索引值集合Ai,。碰撞檢測過程是逐一抽取集合中的單元格，檢測其中存在有特征點的魚類對象,，然后逐一把這些魚類對象的特征點位置寄存器數(shù)據(jù)集合Bi直接與漁網(wǎng)單元格索引值集合Ai進(jìn)行比較,，若是Bi∈Ai，則可以判斷該魚類對象所有特征點都包含在漁網(wǎng)中,。

　傳統(tǒng)碰撞檢測過程最重要的是準(zhǔn)確地檢測碰撞,，但從游戲的可玩性來說，僅以對象物理狀態(tài)來判斷碰撞是不夠的,，需要分析其他游戲性因素進(jìn)行判斷,。由此可以設(shè)定碰撞檢測函數(shù)Pi=f（x1+x2+x3+x4+x5+xn）， Pi代表某魚類對象與漁網(wǎng)碰撞值，x1~xn代表各項因素,，每項因素都有不同的權(quán)重,，從而影響最終的碰撞值。各項因素設(shè)定及權(quán)重分配（以5項因素為例）如表1所示,。

　根據(jù)不同因素所起的作用,，可以動態(tài)調(diào)節(jié)它們之間的權(quán)重值，游戲在相同的框架下也能體現(xiàn)出不同的游戲性,。例如,，動態(tài)修改x1與x2之間的權(quán)重，則捕魚技巧和游戲難度之間的體驗感就會發(fā)生變化,。再者,，可以在一些因素中加入動態(tài)參數(shù)，使因素權(quán)值發(fā)生游戲性的變化,。例如,，對用戶在線時間參數(shù)x4引入相關(guān)計算公式y(tǒng)=[1+sin（x×π/t）]×x/30，y是因數(shù)權(quán)值,，x是時間值,，t是游戲送分減分周期，如圖4所示,，曲線的斜率和周期都可以作適當(dāng)調(diào)節(jié),，使權(quán)重值隨在線時間波動上升。

3 碰撞的確認(rèn)與響應(yīng)
　此外,，必須是在漁網(wǎng)矩陣單元格中存在特征點的魚類對象才會觸發(fā)碰撞檢測函數(shù),，函數(shù)是根據(jù)各項因素權(quán)重值返回碰撞值，以此決定是否發(fā)生實質(zhì)性碰撞,。例如,，上文提到的鯉魚和墨魚，因為B1∈A1,、B2∈A1,，所以它們的x1權(quán)重值都可以得到40，而魔鬼魚因為B3∩A1=20,，只有一個特征點與漁網(wǎng)碰撞,，它的x1權(quán)重值只為8（魔鬼魚共有5個特征點）。從難度系數(shù)上來說,，魔鬼魚最高,、鯉魚最低，通過隨機(jī)換算可得魔鬼魚x2=10,，墨魚x2=12,，鯉魚x2=20,。若其他因素假定都一樣合共為20，則可以推算出鯉魚碰撞值P1=40+20+20=80,，墨魚P2=72，魔鬼魚P3=38,。碰撞確認(rèn)與響應(yīng)的過程如圖5所示,，碰撞檢測Y值低于60分，則判斷漁網(wǎng)捕魚不成功,，需要累計該魚類對象被攻擊的次數(shù),，以增加下次被捕的得分值。最重要的是要觸發(fā)魚類轉(zhuǎn)向逃跑的函數(shù),。若碰撞檢測Y值高于或等于60,，則判斷該魚類對象被捕獲，魚類對象觸發(fā)捕獲函數(shù)啟動捕獲動畫,，并實時增加玩家的積分值,。但一個游戲往往會暗含一些非常規(guī)因素。例如,，玩家突然獲得了超級魚槍,，只要及時使用超級漁網(wǎng)接觸的所有魚類都被捕獲。在實現(xiàn)中,，直接將非常規(guī)因素折算成相應(yīng)的得分值與Pi累加后再進(jìn)行判斷就可以了,。

　游戲AI算法跟一般程序的算法要求不同的是除了要考慮時間復(fù)雜度與空間復(fù)雜度的因素外，還要考慮游戲復(fù)雜多樣的可玩性要求,。本文提出了一種新的基于空間網(wǎng)格劃分結(jié)合多重因素分析的智能碰撞算法,，利用空間網(wǎng)格劃分和特征點來判斷對象碰撞關(guān)系，并分析游戲性的各項因素,，合理分配權(quán)重實現(xiàn)碰撞檢測,，從而提高了算法的執(zhí)行速度，增加了游戲的可玩性,。對相關(guān)游戲程序設(shè)計具有一定的應(yīng)用參考價值,。
參考文獻(xiàn)
[1] 艾瑞咨詢.2011年中國網(wǎng)絡(luò)游戲行業(yè)四大盤點[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動畫高級教程[M].蘇金國,，譯.北京：人民郵電出版社，2010.
[5] STAHLER W.游戲編程數(shù)學(xué)和物流基礎(chǔ)[M].北京：機(jī)械工業(yè)出版社,，2008.