摘  要： 碰撞檢測(cè)是游戲人工智能設(shè)計(jì)領(lǐng)域中的基本研究問(wèn)題，快速智能的碰撞檢測(cè)算法直接決定游戲效果的好壞。針對(duì)捕魚(yú)類(lèi)游戲的碰撞要求，設(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)化。另一方面，不同類(lèi)型、玩法、主題的游戲?qū)τ趯?duì)象的碰撞要求存在著很大的差異。例如，射擊類(lèi)游戲比較關(guān)注子彈與目標(biāo)物體的碰撞，又如動(dòng)作類(lèi)游戲則比較關(guān)心對(duì)象運(yùn)動(dòng)間的碰撞。由此可見(jiàn)，要根據(jù)具體游戲碰撞需求設(shè)計(jì)適合的碰撞算法來(lái)給予解決。本文根據(jù)當(dāng)下熱門(mén)的捕魚(yú)游戲中的碰撞要求，設(shè)計(jì)了一種以空間網(wǎng)格劃分為基礎(chǔ)，結(jié)合多重因素分析的高效智能碰撞算法，增加了相關(guān)游戲的可玩性及運(yùn)行效率。
1 碰撞檢測(cè)模型的建立  
　近年來(lái)以捕魚(yú)為題材的休閑類(lèi)游戲發(fā)展相當(dāng)迅速。例如，《捕魚(yú)達(dá)人》成為2011年iPhone付費(fèi)應(yīng)用收入最高的國(guó)產(chǎn)游戲之一[1]。該類(lèi)游戲大體是由玩家購(gòu)買(mǎi)子彈，調(diào)整網(wǎng)槍的威力，就可以攻擊游戲中游動(dòng)的魚(yú)類(lèi)以獲取積分。被攻擊的魚(yú)類(lèi)品種不同，其積分也不同。玩家用來(lái)攻擊魚(yú)類(lèi)的網(wǎng)槍共分為若干個(gè)等級(jí)，等級(jí)越高的網(wǎng)槍耗費(fèi)的子彈越多，但其漁網(wǎng)捕魚(yú)能力也越大。對(duì)于該類(lèi)游戲碰撞問(wèn)題的關(guān)鍵是如何檢測(cè)漁網(wǎng)與魚(yú)類(lèi)動(dòng)態(tài)碰撞的情況。不少開(kāi)發(fā)者改良使用GJK算法[2]和LC算法[3]等有關(guān)碰撞位置計(jì)算的著名算法。以上算法都是通過(guò)計(jì)算物體間表面的最小距離來(lái)確定碰撞位置，實(shí)施過(guò)程中需要遍歷檢測(cè)所有魚(yú)類(lèi)對(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ì)象間的相交情況即可。在捕魚(yú)類(lèi)游戲中，主要檢測(cè)的是漁網(wǎng)與魚(yú)類(lèi)的碰撞，所以漁網(wǎng)也要進(jìn)行網(wǎng)格化，可以利用場(chǎng)景網(wǎng)格來(lái)記錄即可，這樣只要直接檢查漁網(wǎng)打開(kāi)時(shí)所屬網(wǎng)格矩陣范圍內(nèi)有可能碰撞的魚(yú)類(lèi)對(duì)象，而無(wú)需遍歷所有的魚(yú)類(lèi)對(duì)象了，因此大大減少了檢測(cè)的數(shù)量。
　為了不影響碰撞檢測(cè)的精確度，場(chǎng)景分割網(wǎng)格應(yīng)以正方形單元格為單位，大小與最小魚(yú)類(lèi)的正方形包圍盒一致。魚(yú)類(lèi)要設(shè)置捕捉特征點(diǎn)，等級(jí)越高的魚(yú)類(lèi)越大，特征點(diǎn)就越多（最多有6個(gè)）。特征點(diǎn)也可以是動(dòng)態(tài)變化的，例如魔鬼魚(yú)當(dāng)翅膀全部打開(kāi)的時(shí)候所有特征點(diǎn)才可以被捕捉到，如圖1所示。然后根據(jù)魚(yú)類(lèi)對(duì)象特征點(diǎn)所在的位置將各個(gè)魚(yú)類(lèi)對(duì)象分配到該網(wǎng)格的對(duì)應(yīng)單元格內(nèi)。

　場(chǎng)景網(wǎng)格分割更好地記錄了魚(yú)類(lèi)對(duì)象在屏幕的位置和漁網(wǎng)捕魚(yú)矩陣，從而利于隨后的碰撞檢測(cè)。魚(yú)類(lèi)對(duì)象的位置可以通過(guò)其特征點(diǎn)定位實(shí)現(xiàn)，給每一個(gè)單元格建立一個(gè)寄存器來(lái)存儲(chǔ)該單元格中不同魚(yú)類(lèi)對(duì)象的特征點(diǎn)。實(shí)際應(yīng)用時(shí)可以利用一個(gè)二維數(shù)組來(lái)實(shí)現(xiàn)單元格特征點(diǎn)存儲(chǔ)器的功能，二維數(shù)組行數(shù)是網(wǎng)格單元格總數(shù)，列數(shù)是游戲魚(yú)類(lèi)對(duì)象的實(shí)例數(shù)上限。當(dāng)一種魚(yú)類(lèi)對(duì)象實(shí)例化時(shí)都需要產(chǎn)生一個(gè)對(duì)應(yīng)流水標(biāo)識(shí)號(hào)，利用單元格索引號(hào)和魚(yú)類(lèi)對(duì)象流水標(biāo)識(shí)號(hào)構(gòu)成二維數(shù)組內(nèi)特征點(diǎn)存儲(chǔ)單元的索引值。這樣的算法能迅速實(shí)現(xiàn)數(shù)據(jù)查找和更新。與此同時(shí)，魚(yú)類(lèi)對(duì)象也需要設(shè)置一個(gè)存儲(chǔ)特征點(diǎn)所在單元格索引值的存儲(chǔ)器，存儲(chǔ)器的大小根據(jù)對(duì)應(yīng)魚(yú)類(lèi)特征點(diǎn)數(shù)量來(lái)確定。該存儲(chǔ)器可以使用一個(gè)一維數(shù)組來(lái)實(shí)現(xiàn)，特征點(diǎn)標(biāo)識(shí)號(hào)可以作為數(shù)組的索引下標(biāo)。
　魚(yú)類(lèi)對(duì)象在游動(dòng)過(guò)程中，特征點(diǎn)位置必然發(fā)生變化，因此需要實(shí)時(shí)判斷特征點(diǎn)所在的單元格，更新單元格特征點(diǎn)寄存器對(duì)應(yīng)的數(shù)據(jù)項(xiàng)目，并且把單元格索引值重新計(jì)入魚(yú)類(lèi)對(duì)象的特征點(diǎn)存儲(chǔ)器。這樣就可以實(shí)時(shí)地為碰撞檢測(cè)提供準(zhǔn)確的數(shù)據(jù)基礎(chǔ)。
2 碰撞檢測(cè)的過(guò)程
　碰撞檢測(cè)首先需要建立監(jiān)聽(tīng)器，監(jiān)聽(tīng)對(duì)象的狀態(tài)變化以便觸發(fā)碰撞檢測(cè)過(guò)程。例如，魚(yú)類(lèi)對(duì)象碰撞檢測(cè)可以利用游戲場(chǎng)景網(wǎng)格，監(jiān)聽(tīng)單元格特征點(diǎn)寄存器，若寄存器存有不同魚(yú)類(lèi)對(duì)象的特征點(diǎn)，就可以觸發(fā)魚(yú)類(lèi)對(duì)象碰撞檢測(cè)過(guò)程進(jìn)行處理。
　當(dāng)玩家使用某種等級(jí)網(wǎng)槍撒網(wǎng)捕魚(yú)時(shí)，根據(jù)撒網(wǎng)點(diǎn)所在的單元格，推算出漁網(wǎng)陣列，即可獲得一個(gè)單元格索引值集合Ai。碰撞檢測(cè)過(guò)程是逐一抽取集合中的單元格，檢測(cè)其中存在有特征點(diǎn)的魚(yú)類(lèi)對(duì)象，然后逐一把這些魚(yú)類(lèi)對(duì)象的特征點(diǎn)位置寄存器數(shù)據(jù)集合Bi直接與漁網(wǎng)單元格索引值集合Ai進(jìn)行比較，若是Bi∈Ai，則可以判斷該魚(yú)類(lèi)對(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代表某魚(yú)類(lèi)對(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ú)技巧和游戲難度之間的體驗(yàn)感就會(huì)發(fā)生變化。再者，可以在一些因素中加入動(dòng)態(tài)參數(shù)，使因素權(quán)值發(fā)生游戲性的變化。例如，對(duì)用戶(hù)在線時(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)的魚(yú)類(lèi)對(duì)象才會(huì)觸發(fā)碰撞檢測(cè)函數(shù)，函數(shù)是根據(jù)各項(xiàng)因素權(quán)重值返回碰撞值，以此決定是否發(fā)生實(shí)質(zhì)性碰撞。例如，上文提到的鯉魚(yú)和墨魚(yú)，因?yàn)锽1∈A1、B2∈A1，所以它們的x1權(quán)重值都可以得到40，而魔鬼魚(yú)因?yàn)锽3∩A1=20，只有一個(gè)特征點(diǎn)與漁網(wǎng)碰撞，它的x1權(quán)重值只為8（魔鬼魚(yú)共有5個(gè)特征點(diǎn)）。從難度系數(shù)上來(lái)說(shuō)，魔鬼魚(yú)最高、鯉魚(yú)最低，通過(guò)隨機(jī)換算可得魔鬼魚(yú)x2=10，墨魚(yú)x2=12，鯉魚(yú)x2=20。若其他因素假定都一樣合共為20，則可以推算出鯉魚(yú)碰撞值P1=40+20+20=80，墨魚(yú)P2=72，魔鬼魚(yú)P3=38。碰撞確認(rèn)與響應(yīng)的過(guò)程如圖5所示，碰撞檢測(cè)Y值低于60分，則判斷漁網(wǎng)捕魚(yú)不成功，需要累計(jì)該魚(yú)類(lèi)對(duì)象被攻擊的次數(shù)，以增加下次被捕的得分值。最重要的是要觸發(fā)魚(yú)類(lèi)轉(zhuǎn)向逃跑的函數(shù)。若碰撞檢測(cè)Y值高于或等于60，則判斷該魚(yú)類(lèi)對(duì)象被捕獲，魚(yú)類(lèi)對(duì)象觸發(fā)捕獲函數(shù)啟動(dòng)捕獲動(dòng)畫(huà)，并實(shí)時(shí)增加玩家的積分值。但一個(gè)游戲往往會(huì)暗含一些非常規(guī)因素。例如，玩家突然獲得了超級(jí)魚(yú)槍?zhuān)灰皶r(shí)使用超級(jí)漁網(wǎng)接觸的所有魚(yú)類(lèi)都被捕獲。在實(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] 艾瑞咨詢(xún).2011年中國(guó)網(wǎng)絡(luò)游戲行業(yè)四大盤(pán)點(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)畫(huà)高級(jí)教程[M].蘇金國(guó)，譯.北京：人民郵電出版社，2010.
[5] STAHLER W.游戲編程數(shù)學(xué)和物流基礎(chǔ)[M].北京：機(jī)械工業(yè)出版社，2008.