【正文】 景。隨著使用平臺開發(fā)3D游戲，本文深入研究了碰撞檢測算法和人工智能技術(shù)在游戲中的應(yīng)用，以龐大的計算量，使用結(jié)合類保衛(wèi)盒和空間分割段檢測法來提高碰撞檢測算法的速度慢、碰撞檢測計算不精確，可以有效地提高碰撞算法的精確度和速度。此外，本文完善了游戲路徑搜索算法，提高了長時間的搜索問題，搜索速度慢在A*路徑搜索算法的改進A*算法的路徑搜索方法，限制搜索范圍和加重的啟發(fā)函數(shù)數(shù)量。1. 碰撞檢測算法BVH（層次包圍盒的碰撞算法）是一種最為廣泛使用的碰撞檢測法。BBB的交叉實驗是很簡單，但是緊密的BBB碰撞測試卻很復(fù)雜。本文對包圍體的密實度和AABB包圍盒的碰撞檢測算法的檢測方法進行了改進。改進思想：提高碰撞檢測算法的核心是實時性和精確度。有些游戲會犧牲一些精確度來的得到實時。該系統(tǒng)采用基于AABB包圍盒的碰撞算法，并且使用提高目的碰撞檢測算法簡單、快速和精確的方法，一定程度的提高了在AABB包圍盒碰撞檢測算法中密實度差、計算量大的問題。改進思想主要包括以下幾個方面：1）應(yīng)用BSP分解空間場景來減少碰撞檢測的計算量；2）優(yōu)化包圍盒；3）提出了段的碰撞檢測算法，來提高AABB碰撞檢測的速度。BSP分解場景：精確度和碰撞檢測速度是游戲的重要屬性。假設(shè)在RPG游戲視圖中有100個物體，則系統(tǒng)要做出100個碰撞測試和1002個碰撞測試計算。如果還有其他的對象存在系統(tǒng)中，大量的計算和糟糕的系統(tǒng)是很難被玩家接受的。因此，提高碰撞檢測的速度是很有必要的。本文主要提出了一下兩種方法來提高碰撞檢測的速度。首先，如上所述，如果游戲場景中不分解，碰撞測試就要對每一個對象進行碰撞，但是在這些檢測中，大部分的碰撞測試時無用的，一次，寶貴的時間和資源就在這些工作上浪費掉了。那么要如何減緩這種現(xiàn)象呢？從數(shù)據(jù)結(jié)構(gòu)方面考慮，二叉樹的理念可以應(yīng)用到場景的分解中。二叉樹法不僅可以應(yīng)用在管理場景中，還可以應(yīng)用到碰撞檢測里。二叉樹法可以分為不同的區(qū)域?qū)ο蟆Ｃ總€區(qū)域由小的對象組成，碰撞測試可以以區(qū)域為單位進行。遍歷BSP樹具有三維空間的優(yōu)勢。對于每次的循環(huán)，50%的對象不可能在對象的中心節(jié)點找到符合對象時才被樹維空間沖突排除掉。該方法快速簡單，它只需要log2N一個公式哪怕N是一個很復(fù)雜的數(shù)字，就能完成碰撞測試。因此，在分解場景采用BSP樹有利于碰撞檢測，并且在很大程度上減少了碰撞檢測的計算量。其次，可以從空間的角度來提高碰撞檢測的速度。游戲場景包括靜態(tài)和動態(tài)對象。如果包圍盒不斷更新，這將會花費大量的時間去計算包圍盒的所有對象，這無疑增加了不必要的計算。由于靜態(tài)的包圍體并沒有改變，所以不需要更新他們的包圍盒。因此，在靜態(tài)場景對象中已經(jīng)確認了它在調(diào)用級的包圍盒，并沒有更新他們的包圍盒。為了確保碰撞檢測的精確度，動態(tài)的對象包圍體必須實時更新。采用這樣的方法可以很大程度上減少碰撞檢測算法的計算量提高游戲運行速度。優(yōu)化包圍盒：來提高碰撞檢測的精確度。但是，游戲場景中包括動態(tài)和靜態(tài)對象，如果每個物體的包圍盒都實時更新，這將增加不必要的時間來計算。因此，開發(fā)此游戲時使用AABB包圍盒對場景中的對象進行測試比較適宜。對于場景中的靜態(tài)對象如墻、房子、樹和其他規(guī)則形狀的對象只屬于一個包圍盒，并不會實時更新，這樣游戲中的碰撞檢測將會受到很大的影響。該系統(tǒng)只實時更新動態(tài)對象的包圍盒。包圍體的寬度應(yīng)設(shè)為對象動作的最大跨度。如果邊界體積太小，碰撞檢測是不夠精確的，碰撞顯示也會有失真的現(xiàn)象；如果邊界體積過大，碰撞實時將會過長，所以設(shè)計一個合理的包圍體會使碰撞檢測得到事半功倍的效果。動態(tài)對象的活動范圍也影響著碰撞檢測的精確度。如果對象的活動范圍過大，可能會發(fā)生以下情況：當(dāng)前的幀沒有碰撞到對象，而下一幀又錯過了該對象，這意味著很容易出現(xiàn)對象小于活動范圍的現(xiàn)象。為了防止漏過，在創(chuàng)建對象動畫的過程中應(yīng)為對象的活動范圍制定一個適當(dāng)?shù)闹怠７侄蔚呐鲎矙z測算法：游戲系統(tǒng)對碰撞檢測的要求不高，但對游戲的運行速度有著較高的要求。在游戲場景中，靜態(tài)對象不需要碰撞檢測，碰撞只是發(fā)生在動態(tài)對象和靜態(tài)對象間。游戲的場景模型大多是普通的對象，因此，采用AABB包圍盒足以表達場景中對象的近似。兩個AABB包圍盒之間的碰撞檢測需要計算6次，如果在做碰撞之前有M個碰撞檢測，則在AABB包圍盒需要6M次的計算。這樣不僅計算量大，而且浪費時間，因為如果沒有碰撞只需要計算M即可。解決方案是在射線和靜態(tài)AABB兩個物體碰撞之前做交叉測試。在這過程中，AABB測發(fā)生沖突是無疑的，不改變動態(tài)和靜態(tài)AABB是可能發(fā)生碰撞的，知道兩個物體將要碰撞時才會有碰撞檢測。然而，機會決定AABB包圍盒的移動射線從射線和靜態(tài)對象AABB包圍盒中獲得的距離。用改進的碰撞檢測算法計算量能減少近一半。該算法描述如下：1）選擇玩家角色包圍盒的中心點S和移動距離的矢量V并且以（S,V）作為參照做一個射線；2）利用BSP樹分解法很快就會發(fā)現(xiàn)可能是帶碰撞檢測的區(qū)域；帶碰撞檢測的射線和靜態(tài)AABB對象：估計出射線和靜態(tài)AABB對象之間的距離和AABB包圍盒可能發(fā)生碰撞，消除不可能發(fā)生，如果達到設(shè)定的臨界值之后繼續(xù)；帶碰撞檢測的動態(tài)AABB和靜態(tài)AABB平面，否則，返回。2. 優(yōu)化算法大面積的空間和緩慢的計算速度是A*尋路算法的最大不足。本文采用了三種方法來優(yōu)化和提高路徑搜索。隨著路徑搜索分級法，A*算法體現(xiàn)了NPC在路徑搜索的智能，但有兩個缺陷：A*算法需要保持啟發(fā)式信息，現(xiàn)節(jié)點和擴充節(jié)點，它需要擴大，為最壞情況下的指數(shù)數(shù)量的內(nèi)存，目的節(jié)點的A*算法的搜索都是靜態(tài)的，但在這個系統(tǒng)中的玩家角色是動態(tài)的，這顯然增加了路徑搜索的復(fù)雜性。A*路徑的搜索難以實現(xiàn)。因此，有必要改進A*尋路算法。通過觀察，我們發(fā)現(xiàn)，所有的路線在沒有障礙物的情況下，起始點和終點是直線的。如果有障礙物，每個轉(zhuǎn)折點必須在障礙物的凸多邊形的峰值。在上述尋路思想的基礎(chǔ)上，本系統(tǒng)采用分級路徑搜索方法，即非玩家在沒有障礙物的路徑上接近對象時，A*算法應(yīng)用于尋路時在非玩家角色和障礙物范圍之間設(shè)置一個臨界值d ，然后使最有節(jié)點應(yīng)該選擇實時改變路徑。對于另一個點間的直線運動而言，延長節(jié)點是非常小計算量也會很小。圖1是分級尋路法即本文采用的示意圖，其中起點顯示NPC，終點表示玩家的角色。U是NPC的移動方向，V是玩家的移動方向。從NPC出發(fā)點到節(jié)點采用直線路徑運動。當(dāng)NPC和障礙物之間的距離是臨界值d時，改進好的A*算法應(yīng)用于正規(guī)尋路。分段搜索法將會大大縮短搜索時間，并不會因為距離的增加而增加搜索時間。圖1：段路徑搜索示意圖改進算法的步驟：1）讓非玩家角色的調(diào)節(jié)點S作為起始節(jié)點，調(diào)節(jié)玩家角色的G點作為目標(biāo)節(jié)點；2）計算d= | GS |；3）如果d＜D（人為設(shè)定的臨界值），NPC被激活，否則，返回到1）；4）按直線進行路徑搜索，玩家角色行動沿著射線方向；5）如果在路徑遇到障礙物Q，計算| QS |；如果| QS |＜k（人為設(shè)定的臨界值）即為改進的A*算法；否則，返回5）；6）返回到4）。重復(fù)操作。3. 實驗結(jié)果和分析碰撞檢測算法：在這一過程中的作用，行動對碰撞作出反應(yīng)是虛擬角色沿著該物體的邊緣避免碰撞障礙物。在這個過程中要注意的是D是0. 本實驗采用AABB包圍盒的碰撞檢測算法及改進算法。比較存儲的調(diào)用時間和2種算法的游戲編譯頻率的實驗數(shù)據(jù)，其中100組實驗數(shù)據(jù)進行規(guī)定和10組隨機選擇平均值進行了比較。實驗結(jié)果的比較如圖2和圖3所示。圖2 算法訪問量的實驗結(jié)果 圖3 FPS的算法實驗結(jié)果10