三維游戲中的空中尋路算法研究

王淼 田野

摘要:本文針對現有關于三維游戲中脫離地表的尋路算法的研究文獻較少的情況,討論了二維尋路A*算法的改進和優化,在滿足三維空間尋路要求的算法原理和計算過程中的作用。算法的改進和優化包括三維網格節點的優化,三維場景中障礙物的設定,估價函數的修改和優化,節點坐標計算以及OPEN表和CLOSED表的維護等。

關鍵詞:空中尋路 A*算法 估價函數 移動步長 坐標變換

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

一、尋路算法的選擇

游戲開發中較為成熟的尋路算法有很多,可分為盲目搜索和啟發式搜索兩大類。針對三維游戲的空中尋路數據量大,障礙物環境復雜的特點,使用盲目搜索將導致搜索代價巨大,甚至無解的結果,故本文選擇啟發式搜索中的A*算法,并對其估價函數和搜索過程進行修改,使其適應三維環境下的路徑的計算要求。

二、A*算法的主要思想

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

三、A*算法在三維空中尋路應用中的修改和優化

1.三維網格節點的優化

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

2.估價函數的修改和優化

三維游戲中的空中尋路相對二維地圖中的尋路,對于從起始點開始的節點的搜索,每個節點相鄰節點的數量從8個激增至26個。使用傳統的A*算法,尋路的過程將很可能因為CPU資源耗費太大而嚴重影響游戲的流暢性。決定A*算法尋路效率的關鍵因素是估價函數f(n),對它的修改和優化可從下面兩個方面進行:

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

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

3.節點坐標計算

在三維空間中,如果考慮物體或角色隨飛行方向(或游泳方向)產生的運動姿態的改變問題,則會涉及到旋轉操作。為了使用同樣的方法,來處理平移和旋轉變換并實現變換間的復合,需引入齊次坐標系,使線性變換以統一的格式進行。所以,平移變換(即計算當前節點的相鄰節點的坐標)的計算公式可用矩陣乘法表示如下:

其中,Tx、Ty和Tz分別是節點在三個坐標軸方向上的位移量,Xn、Yn、Zn為當前節點的坐標,x、y、z為當前節點的相鄰節點的坐標。因物體或角色運動姿態的改變,而需采取的旋轉操作的計算公式可用矩陣乘法表示如下:

其中,Rx、Ry、Rz分別是繞X、Y、Z軸逆時針旋轉的變換矩陣,對于圍繞任意旋轉軸旋轉的情況,可由上面3個變換矩陣的復合變換得到。

4.OPEN表和CLOSED表的維護

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

四、Virtools中的陣列具有類似數據庫中表的功能,能夠為陣列表中的列建立索引,并可通0

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

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

參考文獻:

[1]李慧哲、張麗萍等.A*算法在游戲尋徑中的應用.內蒙古師范大學學報.2009年第2期.

[2]陳勇、王棟、陳戈.一種三維虛擬場景自動漫游的快速路徑規劃算法.系統仿真學報.2007年第11期.

[3]朱耿青、陳崇成等.三維最短路徑分析算法的實現及其可視化.計算機工程與應用.2007年第33期.

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

[5]沃特、波力卡波.沈一帆譯.3D游戲實時渲染與軟件技術.機械工業出版社,2005.