【正文】
r path search. A* path search is rather difficult to achieve. So, it is necessary to improve A* path search algorithm.By observation,we find that all the optimal routes are the straight line between starting point and objective point in the condition of no obstacle. If there is obstacle, each turning point must locate in the peak of convex polygon of obstacle. On the basis of the above idea for searching path, this system adopts grading path search method, which means that nonplayer role approach object at the path without obstacle, A* algorithm shall be used for path search when the distance between nonplayer role and obstacle reaches set threshold d, then the optimal node shall be selected real time to change path. For the movement in the straight line of two points, the extending node is very little, and calculation amount is very small. Figure 1 is the sketch map for the grading path search method adopted in this article, among which starting point indicates NPC, objective point indicates player role. U is the moving direction of NPC, V is moving direction of player role. The part from starting point NPC to node adopts path movement of straight line. When the distance between NPC and obstacle reaches threshold d, the improved A* algorithm shall be used to make regular path search. Segment path search method will greatly reduce the searching times, and would not increase the searching time for the increase of distance.Figure 1: the sketch map of segment path searchThe steps of improved algorithm: 1) let coordinate point S of nonplayer role as starting node and coordinate point G of player role as objective node。 5) if there is obstacle Q in path, calculate |QS|。因此,加強(qiáng)對3D游戲技術(shù)的研究具有重要的現(xiàn)實(shí)意義。1. 碰撞檢測算法BVH(層次包圍盒的碰撞算法)是一種最為廣泛使用的碰撞檢測法。有些游戲會犧牲一些精確度來的得到實(shí)時。假設(shè)在RPG游戲視圖中有100個物體,則系統(tǒng)要做出100個碰撞測試和1002個碰撞測試計(jì)算。首先,如上所述,如果游戲場景中不分解,碰撞測試就要對每一個對象進(jìn)行碰撞,但是在這些檢測中,大部分的碰撞測試時無用的,一次,寶貴的時間和資源就在這些工作上浪費(fèi)掉了。每個區(qū)域由小的對象組成,碰撞測試可以以區(qū)域?yàn)閱挝贿M(jìn)行。因此,在分解場景采用BSP樹有利于碰撞檢測,并且在很大程度上減少了碰撞檢測的計(jì)算量。由于靜態(tài)的包圍體并沒有改變,所以不需要更新他們的包圍盒。優(yōu)化包圍盒:來提高碰撞檢測的精確度。該系統(tǒng)只實(shí)時更新動態(tài)對象的包圍盒。如果對象的活動范圍過大,可能會發(fā)生以下情況:當(dāng)前的幀沒有碰撞到對象,而下一幀又錯過了該對象,這意味著很容易出現(xiàn)對象小于活動范圍的現(xiàn)象。游戲的場景模型大多是普通的對象,因此,采用AABB包圍盒足以表達(dá)場景中對象的近似。在這過程中,AABB測發(fā)生沖突是無疑的,不改變動態(tài)和靜態(tài)AABB是可能發(fā)生碰撞的,知道兩個物體將要碰撞時才會有碰撞檢測。2. 優(yōu)化算法大面積的空間和緩慢的計(jì)算速度是A*尋路算法的最大不足。因此,有必要改進(jìn)A*尋路算法。對于另一個點(diǎn)間的直線運(yùn)動而言,延長節(jié)點(diǎn)是非常小計(jì)算量也會很小。當(dāng)NPC和障礙物之間的距離是臨界值d時,改進(jìn)好的A*算法應(yīng)用于正規(guī)尋路。3. 實(shí)驗(yàn)結(jié)果和分析碰撞檢測算法:在這一過程中的作用,行動對碰撞作出反應(yīng)是虛擬角色沿著該物體的邊緣避免碰撞障礙物。圖2 算法訪問量的實(shí)驗(yàn)結(jié)果 圖3 FPS的算法實(shí)驗(yàn)結(jié)果10。比較存儲的調(diào)用時間和2種算法的游戲編譯頻率的實(shí)驗(yàn)數(shù)據(jù),其中100組實(shí)驗(yàn)數(shù)據(jù)進(jìn)行規(guī)定和10組隨機(jī)選擇平均值進(jìn)行了比較。圖1:段路徑搜索示意圖改進(jìn)算法的步驟:1)讓非玩家角色的調(diào)節(jié)點(diǎn)S作為起始節(jié)點(diǎn),調(diào)節(jié)玩家角色的G點(diǎn)作為目標(biāo)節(jié)點(diǎn);2)計(jì)算d= | GS |;3)如果d<D(人為設(shè)定的臨界值),NPC被激活,否則,返回到1);4)按直線進(jìn)行路徑搜索,玩家角色行動沿著射線方向;5)如果在路徑遇到障礙物Q,計(jì)算| QS |;如果| QS |<k(人為設(shè)定的臨界值)即為改進(jìn)的A*算法;否則,返回5);6)返回到4)。U是NPC的移動方向,V是玩家的移動方向。如果有障礙物,每個轉(zhuǎn)折點(diǎn)必須在障礙物的凸多邊形的峰值。隨著路徑搜索分級法,A*算法體現(xiàn)了NPC在路徑搜索的智能,但有兩個缺陷:A*算法需要保持啟發(fā)式信息,現(xiàn)節(jié)點(diǎn)和擴(kuò)充節(jié)點(diǎn),它需要擴(kuò)大,為最壞情況下的指數(shù)數(shù)量的內(nèi)存,目的節(jié)點(diǎn)的A*算法的搜索都是靜態(tài)的,但在這個系統(tǒng)中的玩家角色是動態(tài)的,這顯然增加了路徑搜索的復(fù)雜性。用改進(jìn)的碰撞檢測算法計(jì)算量能減少近一半。這樣不僅計(jì)算量大,而且浪費(fèi)時間,因?yàn)槿绻麤]有碰撞只需要計(jì)算M即可。分段的碰撞檢測算法:游戲系統(tǒng)對碰撞檢測的要求不高,但對游戲的運(yùn)行速度有著較高的要求。如果邊界體積太小,碰撞檢測是不夠精確的,碰撞顯示也會有失真的現(xiàn)象;如果邊界體積過大,碰撞實(shí)時將會過長,所以設(shè)計(jì)一個合理的包圍體會使碰撞檢測得到事半功倍的效果。因此,開發(fā)此游戲時使用AABB包圍盒對場景中的對象進(jìn)行測試比較適宜。為了確保碰撞檢測的精確度,動態(tài)的對象包圍體必須實(shí)時更新。游戲場景包括靜態(tài)和動態(tài)對象。