采用改進HPA*算法的大型游戲地圖路徑規劃

李藝貴,郭 銳,邱國鵬,2

(1.三明學院 藝術與設計學院,福建 三明 365004;2.克拉斯諾達爾文化學院,俄羅斯 克拉斯諾達爾 350072)

在計算機游戲設計中,游戲角色自動尋路到指定地點并生成最短可達路徑是最基礎和常用的技術,如圖1。對于小地圖的游戲來說,使用一些基本的尋路算法就可以很好地解決尋路問題。然而,當游戲場景地圖龐大,尋路的兩點距離很長且中間有很多障礙物時,傳統的尋路算法就會遇到性能瓶頸,出現角色等待時間過長、走錯路、游戲畫面卡頓等問題。因此,在游戲角色長距離尋路時,需要改進算法,以求解兼顧計算效率和響應速度的最短路徑,減小節點計算量,提高運算速度。針對這些問題,本文提出基于HPA*的改進算法,以提高游戲角色自動尋路的速度,從而更好地滿足游戲設計的需求。

1 相關研究

針對最短路徑求解問題,Dijkstra、Floyd、A*[1]等算法相繼被提出并被廣泛應用。然而,Dijkstra和Floyd算法的時間和空間復雜度很高,其中Dijkstra算法的時間和空間復雜度均為O(N2),Floyd算法的時間復雜度為O(N3),空間復雜度為O(N2)。在游戲中,這種復雜度的算法很少被使用。相比之下,A*算法是一種啟發式最短路徑規劃方法,時間平均復雜度為O(NlgN)。A*算法常被用于小地圖尋路規劃,但在大規模地圖的長距離尋路時,它會消耗大量計算量,導致CPU被尋路阻塞的情況出現。因此,在設計大場景游戲地圖時,有必要提供兼顧搜索速度和效率的改進算法,以提高游戲角色自動尋路的效率和性能。

Hotle等[2-3]提出了一種基于層次化的A*算法,稱為HPA(hierarchical path-finding)算法,用于解決大規模地圖上的路徑規劃問題。相對于傳統的A*算法,HPA*算法將地圖劃分為多個區塊,并通過關鍵節點將這些區塊連接起來,形成抽象地圖。在區塊中,A*算法能夠有效地尋找最短路徑。如果起點和終點在同一區塊中,直接使用A*算法尋找最短路徑即可。而當起點和終點位于不同的區塊時,需要在連接這些區塊的關鍵節點中尋找最短路徑。這一過程可以在抽象地圖上使用A*算法進行,從而減少了搜索空間,提高了搜索速度。

當前,HPA*算法的研究主要集中在工業機器人路徑規劃方面,以減少運動響應延遲、降低規劃時間和內存負載(Lee等[4]、仲朝亮等[5]、Zuo等[6]和李梓遠等[7])。然而,在游戲地圖中,對于HPA*算法的研究較少,尤其在場景復雜的大型游戲地圖中。Marc等[8-9]通過將游戲地圖分為多個抽象層次,逐層搜索后得到完整路徑,實驗驗證了游戲地圖的層次抽象表達可以有效減少路徑規劃計算負荷量。但是,隨著地圖場景變大和復雜度增加,基本的HPA*分層搜索算法,會導致搜索節點劇增,影響搜索效率。因此,李艷等[10-11]提出了基于HPA*的分層動態路徑搜索HPLPA*算法。該算法將游戲地圖分層抽象,并在動態環境中及時更新,采用 LPA*算法代替A*算法,實時尋找抽象路徑再細化,從而得到最終的路徑規劃結果,雖然該算法在一定程度上提高了在大型地圖上的搜索性能,但由于沒有考慮到大型地圖的復雜性,只適用于含有少量障礙物的空曠地圖。當地圖中存在大量障礙物時,HPA*算法的搜索節點數量會劇增,導致預處理時間和存儲空間的開銷增加,進而影響搜索效率。目前的HPA*改進算法的研究主要集中在場景簡單的空曠地圖上,忽略了地圖復雜性,此外,改進算法沒有考慮緩存區塊間的尋路路徑,都是實時的計算抽象路徑并細化,如果尋路距離很長,中間有很多障礙物時,實時路徑計算就會遇到性能瓶頸。因此,我們需要進一步研究改進HPA*算法,結合緩存技術,減少實時計算量,以適應復雜的大型游戲地圖,提高算法的搜索效率和性能。

本文針對HPA*算法在搜索大規模地圖時可能存在的問題,提出了一種HPA*改進算法。該算法基于層級地圖,將原始地圖進行抽象映射,從而形成抽象地圖層,并通過在不同層級之間進行路徑搜索來緩存關鍵節點間的最短路徑和構建層級映射矩陣。通過這種方式,可以減少搜索節點的數量,提高算法的搜索效率和速度。此外,還設置了節點權重值,以引導尋路方向和規避closeList循環遍歷,從而進一步提高尋路效率和速度。為了驗證該算法的性能,我們在不同尺寸的游戲網格地圖上進行了實驗。實驗結果表明,相比于傳統的A*和HPA*算法,本文提出的算法能夠在搜索效率和速度上都取得很大的提高。

2 HPA*算法

2004年,Botea等學者提出了一種基于A*的多層路徑搜索算法,稱為HPA*算法。該算法通過對地圖進行分層,將大地圖轉換成多個小地圖,形成抽象地圖,從而減少搜索空間。HPA*算法的搜索過程包含兩個主要部分,離線預處理和實時尋路。在離線預處理階段,算法通過將地圖分層,將大地圖轉換為多個小地圖,形成抽象地圖,并在抽象地圖上尋找關鍵節點。在實時尋路階段,算法根據起點和終點所在的區塊,以及這些區塊之間的關鍵節點,對抽象地圖進行A*搜索,從而找到最短路徑。通過在不同層級之間進行路徑搜索,HPA*算法能夠有效地減少搜索空間,提高搜索效率。

2.1 離線預處理

2.1.1 預處理地圖

選取一副游戲地圖進行均勻分區,如圖2。地圖被分為30×30的網格單元,每個網格單元可以稱為節點。圖3為圖2的分區結果,按照每個區塊10×10大小,把地圖均勻分成9個子區塊。白色節點代表可行走區域,藍色節點為不可行走區域。

圖2 實際游戲地圖

圖3 游戲網格地圖

2.1.2 尋找關鍵節點

在相鄰區塊的公共邊上選擇左右兩側單元格作為關鍵節點。關鍵節點的選擇規則為:對于任意相鄰的兩個區塊如Zi和Zj,選取公共邊上連續無障礙物區域作為相鄰區塊的互通區域,選擇互通區域中間左右兩側單元格作為關鍵節點。如圖4所示,區塊Z0與Z1的公共邊上黃色網格為互通區域,綠色網格為關鍵節點。

圖4 關鍵節點示意圖

2.1.3 形成抽象地圖

在區塊內使用A*算法將圖4的關鍵節點依次進行連接形成intra邊,連接屬于同一個互通區域的關鍵節點形成inter邊,最終形成抽象地圖,如圖5。

圖5 抽象地圖

2.2 實時尋路

2.2.1 抽象尋路

根據游戲角色的起點和目標位置信息,找到其所在的區塊,在抽象圖上使用局部A*方法進行抽象尋路,得到起點與終點之間的一條抽象路徑,所得抽象路徑如圖6所示。

圖6 抽象路徑

2.2.2 細化路徑

對抽象路徑上相應的關鍵節點使用A*算法尋找節點間的實際路徑,將抽象路徑細化為低層級的實際路徑。HPA*算法采用抽象分層思想加速尋路,解決了大規模地圖的尋路問題。它的執行步驟簡單易懂,易于實現。通過多層抽象,可以根據地圖規模進一步縮小搜索空間,從高層到低層逐一細化得到實際路徑[12]。相比A*算法,HPA*算法的尋路速度顯著加快。 然而,當地圖中存在大量障礙物或者地圖比較復雜時,在抽象圖上使用局部A*方法進行抽象尋路時,會出現過多的搜索節點,從而影響搜索效率。為了解決這個問題,本文通過調整關鍵節點選取規則、構建層級映射矩陣和緩存路徑等方式改進HPA*算法。

3 HPA*改進算法

在空間記憶系統研究中,廣泛提出了區域化多層嵌套的組織方式。該方式認為,空間對象可以被劃分為多個區塊,并且這些區塊可以組合成更高級別的空間對象。這種組合形成了區塊間的包含關系,這種關系可以被表示為樹形結構。同時,不同區塊對象之間也可以存在連通關系[13]。改進算法的核心思想是在離線狀態下,將游戲地圖分為多個區塊,并將每個區塊抽象為一個節點形成高層級抽象地圖。高層級地圖是低層級地圖的抽象版本,其中低層級地圖中的區塊可以映射為高層級地圖中的節點,形成類似圖7所示的結構。由該圖可見,該模型主要分為兩層:原始地圖表示層和抽象地圖表示層,抽象地圖層是由原始地圖的關鍵節點映射而成。

圖7 區塊化多層表示

該算法首先在抽象地圖中進行抽象尋路,形成抽象尋路序列,再在底層地圖進行尋路細化。傳統HPA*算法需要實時計算關鍵節點間的最短路徑,這往往會浪費過多的計算性能。為了解決這個問題,改進算法通過構建層級映射矩陣,體現層級地圖間的映射關系,加快尋路細化過程。在此過程中,首先需要繪制抽象地圖,進而計算區塊間最短尋路路徑。通過最短路徑的關鍵節點對,構建層級映射矩陣M。最后,創建哈希表緩存最短路徑,用于將抽象路徑轉換為低層級地圖細化路徑。在映射矩陣中,每個元素M(i,j)表示從區塊i到區塊j的最短路徑中所經過的第一個區塊。

在實時尋路過程中,改進算法首先判斷起點和目標點是否在同一個區塊,再在映射矩陣M中進行抽象尋路,得到從起點區塊到終點區塊的抽象路徑,最后進行路徑細化。抽象地圖的節點數量比低層級地圖中的節點數量要少得多,在抽象地圖中進行路徑搜索的復雜度更低,可以顯著縮短搜索時間。最后通過設置節點權重值和判斷節點是否被取,規避Closelist循環遍歷,引導尋路方向,提高尋路效率和速度。改進算法的流程圖如圖8,實現步驟分為離線預處理和實時路徑搜索兩個部分。

圖8 HPA*改進算法的流程圖

3.1 離線預處理

3.1.1 預處理地圖

每個區塊都被分配了一個唯一的編號,用于區分不同的區塊。如圖3所示,地圖被分為30×30的網格單元,每個區塊大小為10×10,將地圖均勻分成9個子區塊。從第一行左上角的第一個區塊開始,按照從左向右,從右向左,從左向右的順序,依次給9個區塊分配編號:0、1、2、一直到8。這樣的編號方式可以方便地對區塊進行標識和索引,便于后續算法的實現和優化。

區塊數據結構為:Zone { int zoneId; GridNode[] topAbsNode; GridNode[] downAbsNode; GridNode[] leftAbsNode; GridNode[] rightAbsNode }。zoneId為區塊編號,topAbsNode、downAbsNode、leftAbsNode、rightAbsNode分別為區塊頂部、下部、左邊、右邊公共邊上關鍵節點集合。

網格單元節點數據結構為:GridNode { Vector2 position; int zoneId; int nodeFindIndex; int weight; enum nodeType{walk; notWalk }; GridNode nodeFather; floatf; floatg; floath}。Position為網格節點坐標,zoneId、nodeFindIndex、weight分別為節點所在區塊編號、游戲尋路次數、網格權重值,nodeType為節點類型,nodeFather為父節點,f、g、h分別為期望值、實際代價值、估計代價值。

3.1.2 選擇關鍵節點

首先在相鄰區塊的公共邊上定義互通區域,互通區域的選擇規則為:任意相鄰區塊Zi和Zj,選擇公共邊上連續無障礙物區域作為互通區域,互通區域兩側節點分別組成Ti和Tj,則互通點集E是互通區域節點的集合,symm(t)為對稱關系,t為互通點,滿足下列條件:

E?Ti∪Tj;

(1)

?t∈Ti∪Tj:t∈ E ? symm(t) ∈E;

(2)

t.nodeType!=notWalk。

(3)

在互通區域Zi側,選擇中間網格單元作為關鍵節點,并按照順時針方向在每個區塊內為關鍵節點設置唯一的編號,其中,關鍵節點a必須符合以下條件:

i>j? a∈Ti:a∈Tj,

(4)

a=E[E.length/4]。

(5)

如圖9所示,區塊Z0與Z1 的公共邊上黃色網格為互通區域,Z0上綠色網格為關鍵節點,Z0與Z5公共邊上黃色網格為互通區域,Z0上綠色網格為關鍵節點。在Z0區塊中按照順時針方向依次給關鍵節點設置編號:0、1。

圖9 關鍵節點示意圖

3.1.3 繪制抽象地圖

抽象地圖是指在每個區塊內,使用A*算法將公共邊上的關鍵節點相互連接,進行連通測試,從而形成intra邊,記錄下每條邊的權重值,權重值表示兩個關鍵節點之間的最短距離,并將每條intra邊的最短路徑保存在數據文件中。如圖10,連通圖9的關鍵節點,形成抽象地圖,每條intra邊的權值是節點間最短路徑。

圖10 抽象地圖

3.1.4 構建區塊間映射矩陣

為了構建區塊間的映射矩陣,首先需要計算區塊間的最短路徑。為此,在抽象地圖上使用A*算法進行抽象尋路,以搜索出區塊間最短尋路路徑,即起始點區塊關鍵節點到其他區塊關鍵節點的最短路徑。如公式6,在A*算法的啟發式函數中,n表示當前搜索的關鍵節點,f(n)表示n的期望值,g(n)表示從起始關鍵節點到n的實際代價,h(n)表示從n到目標關鍵節點的估計代價。在改進的算法中,g(n)和h(n)的值可以直接獲取intra邊權重,從而減少節點搜索計算。

f(n)=g(n)+h(n)

(6)

區塊間的最短路徑可以表示為一條關鍵節點的序列,其中每個關鍵節點可以代表一個區塊。為了實現不同區塊之間的連接和查找,需要構建一個大小為N×N的層級映射矩陣M,存儲了每個區塊到其他區塊的最短抽象路徑。矩陣中的每個元素M(i,j)表示從區塊i到區塊j的最短路徑中所經過的第一個區塊,如果起始點區塊和目標點區塊在同一個區塊,那么M(i,j)=-1。N是區塊的個數,行代表初始起始區塊,列代表終點區塊。通過直接訪問起始區塊id和終點區塊id,可以在矩陣中查找最優路徑。這個映射矩陣是通過將從一個區塊到另一個區塊的路徑“記錄”為指向路徑上下一個節點的一系列指針的方式來實現的。例如,在圖10中,假設起始點在區塊0,目標點在區塊8。通過抽象尋路,我們可以確定起點需要經過關鍵節點 0、3、7 、6才能形成最短路徑到達區塊 8,其中節點3、7、6分別代表區塊1 、區塊4和區塊3。因此,區塊0到區塊8的中間轉移區塊為區塊1、4、3。我們將區塊1的編號填入M(0,8) 中,然后區塊1經過區塊4可以到達區塊8,將區塊4的編號填入M(1,8) 中,區塊4經過區塊3可以達到區塊8,將區塊3填入M(3,8)中,依此類推,即可填滿層級映射矩陣M。

(7)

3.1.5 緩存區塊間最短路徑

緩存搜索結果是減少尋路算法中搜索節點數量的一種常見技術。通過避免再次搜索已經探索過的節點,算法可以顯著減少尋路所需的搜索次數。這種技術可以被廣泛應用于各種尋路算法中,以提高算法的效率和性能[14]。改進算法按照前后順序依次連接區塊間尋路序列中的每個關鍵節點,得出一條抽線路徑。例如,對于區塊0到區塊8,其尋路序列為(0,3,7,6),形成<0,3>,<3,7>,<7,6> ,三個關鍵節點對。然后,根據所保存的intra邊最短尋路數據文件,對關鍵節點對的抽象路徑進行細化,形成節點對的底層細化路徑。為了提高算法的性能,我們使用哈希表緩存節點對路徑上的所有節點。哈希表的鍵值可以根據節點對所在的區塊ID計算所得,這樣可以快速地查找起始關鍵節點對的細化路徑。這種方法可以避免重復計算已經搜索過的路徑,從而提高算法的效率。

哈希表定義如下:

Dictionary> cacheTable = new Dictionary>()

哈希鍵值定義如下:

Cache[Start.zoneId.GetHashCode() ^ end.zoneId.GetHashCode() &0x7FFFFFFF]

3.2 實時路徑搜索

在游戲啟動時,將層級映射矩陣M和哈希表cacheTable加載到內存中。當游戲角色需要尋路時,需要先判斷其起點和目標點是否在同一個區塊。如果在同一個區塊,A*算法會直接在此區塊內進行路徑搜索。如果不在同一個區塊,需要查詢層級映射矩陣M,以獲取從起始區塊到目標區塊的抽象尋路序列。接著,按照序列中節點的順序,連接關鍵節點對,并根據這些節點對查詢哈希表cacheTable,找到細化的關鍵節點對尋路路徑。最后,將這些細化路徑拼接在一起,形成區塊間尋路路徑。

根據抽象尋路序列,找出第一個序列元素,此元素是起點所在區塊通向目標區塊的起點關鍵節點,利用A*算法找出從起點到此關鍵節點的最短路徑,這是起點區塊內的起點局部尋路。然后,根據尋路序列找到最后一個序列元素,該元素是通向目標區塊的終點關鍵節點,利用A*算法找出從終點到該關鍵節點的最短路徑,這是目標區塊內的終點局部尋路。最終,將起點局部尋路路徑、區塊間尋路路徑、終點局部尋路路徑拼接在一起,形成完整的長距離導航路徑。在實時A*搜索中,可以通過權重引導尋路方向和規避closeList列表的循環遍歷來提高尋路效率和速度。

(1)權重引導尋路方向

為了加快局部區塊尋路速度,可以給關鍵節點周圍的節點設置權重值,通過權重引導尋路方向。具體地,在A*算法中,期望值f(n)不僅可以幫助算法更快地找到目標節點,還能起到引導算法的作用。根據公式6,每次提取相鄰可行節點時,都要實時計算期望值,并根據該值優先級從高到低的順序在openList隊列中進行擴展搜索,選擇期望值最小的節點作為下一個要擴展的節點。

期望值對于尋路的方向判斷很重要,通向目的地的方向越準確,尋路的效率就會越高,尋找路徑的速度也就越快。從這個角度上來看,期望值問題就變成了如何幫助期望值更加準確的判斷通向目的地的方向[15]。在節點中加入權重值來改變期望值從而引導算法快速找到關鍵節點是一種很好的方式。

如圖9,黃色網格是為關鍵節點標記的引導路徑。如果普通節點權重值為100的話,黃色節點權重值為10。在實時A*算法中,計算節點期望值時,需要加上節點的權重值,期望值公式如下。

f(n)=g(n)+h(n) +E(n)。

(8)

式(8)中,n為當前搜索節點,g(n)為起點到n的實際代價,h(n)為當n到目標點的啟發式估計代價,E(n)為n的權重。根據公式8,計算期望值時,黃色引導節點比其它節點獲得更小的值,這也意味著引導節點在OpenList隊列中更靠前,更容易搜索到目標節點。如圖11,當A*算法從起點S到目標點D時,搜索到黃色節點時,就會很容易沿著黃色節點一直延伸到關鍵節點n0和n4,從而減少了openList中節點搜索,加快了搜索速度。

圖11 網格權重圖

(2)規避openList隊列循環遍歷

在每次尋路中,當一個節點被加入到openList列表時,需要檢查該節點是否已經在closeList列表中。如果在closeList中,就不需要添加到openList列表中。然而,隨著closeList列表中搜索節點的增加,會導致CPU計算量的增加,從而影響性能。為了避免這種情況,可以定義一個全局靜態整型變量pathFindTimes,用于記錄尋路次數。此外,每個節點還需要定義一個nodeFindIndex。每次尋路時,將pathFindTimes的值加1。例如,在游戲開啟時,pathFindTimes和nodeFindIndex的初始值相同。當玩家第一次尋路時,pathFindTimes的值會加1。在將一個節點加入到closeList之后,該節點的nodeFindIndex也會加1。當玩家第二次尋路時,在將節點添加到開啟列表之前,需要檢查該節點的nodeFindIndex 是否等于pathFindTimes的值。如果相等,表示該節點已經在開啟列表中,不需要再次添加。通過這種優化方法,可以規避closeList的遍歷循環,提高尋路的效率。該優化可歸納如下。

path Find Times+=1;

closeList.Add(node);

node.nodeFindIndex+=1;

While path Find Times!=node.node FindIndex

{open List.Add(node);}

4 實驗結果及分析

本文采用C#在Unity游戲引擎上實現A*、HPA*和HPA*改進算法,在不同尺寸游戲網格地圖中進行了三組數值仿真實驗。地圖大小分為3種,分別為64×64、512×512和1024×1024。藍色節點障礙物按照每幅地圖10%的比例隨機生成,如圖12所示。在64×64的地圖上隨機選取50對起始點和目標點,并且路徑長度都大于30;在512×512的地圖上隨機選取50對起始點和目標點,并且路徑長度都大于250;在1024×1024的地圖上隨機選取50對起始點和目標點,并且路徑長度都大于500。

(a)A*

表1～2給出了3種算法在不同尺寸游戲地圖上的尋路時間,在64×64的地圖上,3種算法的平均尋路時間相差不大,都在12 ms左右。這是因為64×64的地圖規模較小,搜索空間有限,3種算法的效率差異不是很明顯。但是在512×512的中等規模地圖上,三種算法的平均時間差異非常明顯。其中,A*算法的平均時間達到了53 ms以上,而傳統HPA*算法和HPA*改進算法的平均時間分別為17.13和9.43 ms。在1024×1024的大型規模地圖上,A*算法的平均時間達到了170.12 ms,HPA*算法和HPA*改進算法的平均時間分別為31.76和11.62 ms。這是因為在大規模地圖上,搜索空間非常龐大,傳統的啟發式搜索算法對搜索空間的控制比較弱,而HPA*算法可以將地圖劃分成更小的區塊,從而大大減小搜索空間,提高搜索效率。改進算法在此基礎上采用了一系列的優化,如緩存關鍵節點對最短路徑、構建層級間映射矩陣、優化A*實時查詢等進一步提高了搜索效率和速度。

如表2,在平均路徑長度方面,HPA*和改進算法的表現差異不大,但是A*算法的平均路徑長度更短,這是因為A*算法是一種完整的路徑搜索算法,它會在搜索過程中保證找到的路徑是最優的。而HPA*算法和HPA*改進算法是一種分層搜索算法,它們通過對地圖進行分層處理,將搜索空間縮小到一定程度,來提高搜索效率。但由于HPA*只在相鄰區域邊界選取少量關鍵點形成抽象圖,所以它得到的路徑是接近最優的,而不是最優路徑,如圖13所示。

表2 路徑搜索節點實驗結果 單位:ms

(a)HPA*路徑

在搜索節點數量上,改進算法遠低于A*和HPA*算法。A*算法是一種全局搜索算法,需要搜索整個地圖才能找到最優解。在搜索過程中,A*算法會考慮周圍所有的節點,并計算與目標節點的距離,導致節點數量非常龐大,搜索效率較低。而HPA*算法通過分層的方式,將搜索空間限制在局部范圍內,大大減少了搜索節點數量,提高了搜索效率。相比HPA*算法,改進算法通過合并關鍵節點、緩存搜索結果避免重復搜索等優化策略,從而減少搜索節點,可以更快地找到目標位置。

5 結論

本文針對HPA*算法在運行時容易出現搜索節點過多的問題,提出了一種改進的HPA*算法。該算法的核心思想是將游戲地圖分解為兩個層級地圖,并通過不同層級之間的路徑搜索來緩存關鍵節點對路徑和構建層級映射矩陣。此外,還引入了節點權重值以引導尋路方向和規避closeList循環遍歷等方式來優化HPA*算法。實驗結果表明,改進算法在尋路時間和效率上相較于其他兩種算法具有一定優勢,且其綜合性能相對穩定。未來的研究可以進一步提高改進算法的尋路精度,以使其更好地應用于大規模游戲場景地圖設計中。