王淼 田野

摘要:本文針對(duì)現(xiàn)有關(guān)于三維游戲中脫離地表的尋路算法的研究文獻(xiàn)較少的情況,討論了二維尋路A*算法的改進(jìn)和優(yōu)化,在滿足三維空間尋路要求的算法原理和計(jì)算過程中的作用。算法的改進(jìn)和優(yōu)化包括三維網(wǎng)格節(jié)點(diǎn)的優(yōu)化,三維場景中障礙物的設(shè)定,估價(jià)函數(shù)的修改和優(yōu)化,節(jié)點(diǎn)坐標(biāo)計(jì)算以及OPEN表和CLOSED表的維護(hù)等。

關(guān)鍵詞:空中尋路 A*算法 估價(jià)函數(shù) 移動(dòng)步長 坐標(biāo)變換

近年來,三維游戲產(chǎn)業(yè)高速發(fā)展,帶動(dòng)了游戲相關(guān)技術(shù),特別是人工智能(Artificial Intelligence,簡稱AI)技術(shù)的發(fā)展。游戲中的空中尋路問題,相對(duì)于緊貼地表的物體運(yùn)動(dòng)路徑的計(jì)算,計(jì)算量大大增加,路徑節(jié)點(diǎn)為三維網(wǎng)格而非二維三角面。除此之外,還需解決物體或角色隨飛行方向(或游泳方向)產(chǎn)生的運(yùn)動(dòng)姿態(tài)改變問題。本文針對(duì)三維游戲中對(duì)空中尋路技術(shù)的需求,通過對(duì)二維尋路A*算法的改進(jìn),討論了如何實(shí)現(xiàn)三維游戲中空中路徑的計(jì)算過程。

一、尋路算法的選擇

游戲開發(fā)中較為成熟的尋路算法有很多,可分為盲目搜索和啟發(fā)式搜索兩大類。針對(duì)三維游戲的空中尋路數(shù)據(jù)量大,障礙物環(huán)境復(fù)雜的特點(diǎn),使用盲目搜索將導(dǎo)致搜索代價(jià)巨大,甚至無解的結(jié)果,故本文選擇啟發(fā)式搜索中的A*算法,并對(duì)其估價(jià)函數(shù)和搜索過程進(jìn)行修改,使其適應(yīng)三維環(huán)境下的路徑的計(jì)算要求。

二、A*算法的主要思想

啟發(fā)式搜索的各種算法中,A*算法是較為成熟的算法之一。它的思想是在對(duì)狀態(tài)空間進(jìn)行搜索時(shí),對(duì)每一個(gè)被搜索的節(jié)點(diǎn)通過估價(jià)函數(shù)進(jìn)行評(píng)估,指導(dǎo)搜索前進(jìn)的方向,直到找到目標(biāo)節(jié)點(diǎn)為止。估價(jià)函數(shù)的常規(guī)形式是:f(n)=g(n)+h(n),其中,f(n)是估價(jià)函數(shù),g(n)是從起點(diǎn)S沿著產(chǎn)生的路徑移動(dòng)到節(jié)點(diǎn)n的當(dāng)前已知最短路徑,h(n)是指從節(jié)點(diǎn)n移動(dòng)到終點(diǎn)D的預(yù)估移動(dòng)耗費(fèi)。估價(jià)函數(shù)的定義沒有確定的模式,在A*算法中,對(duì)h(n)做了限制,使其對(duì)所有節(jié)點(diǎn)x均有h(x)≤h*(x),其中h*(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的最小代價(jià),即實(shí)際最短距離。這樣設(shè)計(jì)的估價(jià)函數(shù)可以找出最短路徑,稱之為尋路算法的可采納性,A*算法就是一個(gè)可采納的尋路算法。

三、A*算法在三維空中尋路應(yīng)用中的修改和優(yōu)化

1.三維網(wǎng)格節(jié)點(diǎn)的優(yōu)化

在三維游戲中,針對(duì)三維場景如果仿照二維游戲地圖讀取的做法,單位網(wǎng)格的數(shù)量將達(dá)到一個(gè)驚人的數(shù)字,這是不可行的。所以,三維場景中的節(jié)點(diǎn),不是以邊長為單位長度的立方體,其邊長大小應(yīng)參照尋路物體(或角色)的長度、寬度、高度中最大的數(shù)值來確定,即尋路物體(或角色)的移動(dòng)步長(step),這樣最終路徑的節(jié)點(diǎn)數(shù)量才能被控制在可接受的范圍。

2.估價(jià)函數(shù)的修改和優(yōu)化

三維游戲中的空中尋路相對(duì)二維地圖中的尋路,對(duì)于從起始點(diǎn)開始的節(jié)點(diǎn)的搜索,每個(gè)節(jié)點(diǎn)相鄰節(jié)點(diǎn)的數(shù)量從8個(gè)激增至26個(gè)。使用傳統(tǒng)的A*算法,尋路的過程將很可能因?yàn)镃PU資源耗費(fèi)太大而嚴(yán)重影響游戲的流暢性。決定A*算法尋路效率的關(guān)鍵因素是估價(jià)函數(shù)f(n),對(duì)它的修改和優(yōu)化可從下面兩個(gè)方面進(jìn)行:

第一,節(jié)點(diǎn)g(n)值計(jì)算過程的優(yōu)化。每一個(gè)新加入OPEN表的節(jié)點(diǎn)的g值的計(jì)算,可通過其父節(jié)點(diǎn)的g值(起始節(jié)點(diǎn)的g值為0)和從父節(jié)點(diǎn)到該節(jié)點(diǎn)的移動(dòng)耗費(fèi)相加來得到。在三維空間中,如果父節(jié)點(diǎn)和子節(jié)點(diǎn)的x、y、z坐標(biāo)分量中有2個(gè)相同,則移動(dòng)耗費(fèi)為step(step為對(duì)移動(dòng)步長取整操作后的結(jié)果),有1個(gè)相同,則移動(dòng)耗費(fèi)為1.4×step后取整,都不相同則為1.7×step后取整(這樣可避免求根運(yùn)算和小數(shù))。

第二,節(jié)點(diǎn)h(n)值計(jì)算過程的優(yōu)化。將h(n)設(shè)定為節(jié)點(diǎn)n與終點(diǎn)D的直線距離,可滿足可采納性的條件。由于h(n)>0,在h(n)的計(jì)算中是否開根號(hào)并不影響各節(jié)點(diǎn)f(n)值的比較結(jié)果,故h(n)=|Xd-Xn|+|Yd-Yn|+|Zd-Zn|。

3.節(jié)點(diǎn)坐標(biāo)計(jì)算

在三維空間中,如果考慮物體或角色隨飛行方向(或游泳方向)產(chǎn)生的運(yùn)動(dòng)姿態(tài)的改變問題,則會(huì)涉及到旋轉(zhuǎn)操作。為了使用同樣的方法,來處理平移和旋轉(zhuǎn)變換并實(shí)現(xiàn)變換間的復(fù)合,需引入齊次坐標(biāo)系,使線性變換以統(tǒng)一的格式進(jìn)行。所以,平移變換(即計(jì)算當(dāng)前節(jié)點(diǎn)的相鄰節(jié)點(diǎn)的坐標(biāo))的計(jì)算公式可用矩陣乘法表示如下:

其中,Tx、Ty和Tz分別是節(jié)點(diǎn)在三個(gè)坐標(biāo)軸方向上的位移量,Xn、Yn、Zn為當(dāng)前節(jié)點(diǎn)的坐標(biāo),x、y、z為當(dāng)前節(jié)點(diǎn)的相鄰節(jié)點(diǎn)的坐標(biāo)。因物體或角色運(yùn)動(dòng)姿態(tài)的改變,而需采取的旋轉(zhuǎn)操作的計(jì)算公式可用矩陣乘法表示如下:

其中,Rx、Ry、Rz分別是繞X、Y、Z軸逆時(shí)針旋轉(zhuǎn)的變換矩陣,對(duì)于圍繞任意旋轉(zhuǎn)軸旋轉(zhuǎn)的情況,可由上面3個(gè)變換矩陣的復(fù)合變換得到。

4.OPEN表和CLOSED表的維護(hù)

OPEN表和CLOSED表的維護(hù)是A*算法中的重要組成部分,在《三維游戲中NPC的尋路算法研究》項(xiàng)目中,由于使用Virtools游戲引擎作為三維游戲平臺(tái)搭建工具,故使用Virtools中的陣列來保存節(jié)點(diǎn)元素,如圖1所示。

四、Virtools中的陣列具有類似數(shù)據(jù)庫中表的功能,能夠?yàn)殛嚵斜碇械牧薪⑺饕?并可通0

基于以上文中的算法思路,以《三維游戲中NPC的尋路算法研究》項(xiàng)目為實(shí)驗(yàn)平臺(tái),利用Virtools,VSL語言在三維地形中實(shí)現(xiàn)了三維游戲中空中最短路徑的搜尋工作,最終的可視化結(jié)果如圖2所示。

(作者單位:四川音樂學(xué)院成都美術(shù)學(xué)院)

參考文獻(xiàn):

[1]李慧哲、張麗萍等.A*算法在游戲?qū)街械膽?yīng)用.內(nèi)蒙古師范大學(xué)學(xué)報(bào).2009年第2期.

[2]陳勇、王棟、陳戈.一種三維虛擬場景自動(dòng)漫游的快速路徑規(guī)劃算法.系統(tǒng)仿真學(xué)報(bào).2007年第11期.

[3]朱耿青、陳崇成等.三維最短路徑分析算法的實(shí)現(xiàn)及其可視化.計(jì)算機(jī)工程與應(yīng)用.2007年第33期.

[4]何國輝、陳家琪.游戲開發(fā)中智能路徑搜索算法的研究.計(jì)算機(jī)工程與設(shè)計(jì).2006年第13期.

[5]沃特、波力卡波.沈一帆譯.3D游戲?qū)崟r(shí)渲染與軟件技術(shù).機(jī)械工業(yè)出版社,2005.