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

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

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

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

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

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

　游戲AI算法跟一般程序的算法要求不同的是除了要考慮時間復雜度與空間復雜度的因素外，還要考慮游戲復雜多樣的可玩性要求。本文提出了一種新的基于空間網格劃分結合多重因素分析的智能碰撞算法，利用空間網格劃分和特征點來判斷對象碰撞關系，并分析游戲性的各項因素，合理分配權重實現碰撞檢測，從而提高了算法的執行速度，增加了游戲的可玩性。對相關游戲程序設計具有一定的應用參考價值。
參考文獻
[1] 艾瑞咨詢.2011年中國網絡游戲行業四大盤點[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.游戲編程數學和物流基礎[M].北京：機械工業出版社，2008.