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

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

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

1 相關研究

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

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

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

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

2 HPA*算法

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

2.1 離線預處理

2.1.1 預處理地圖

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

圖2 實際游戲地圖

圖3 游戲網(wǎng)格地圖

2.1.2 尋找關鍵節(jié)點

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

圖4 關鍵節(jié)點示意圖

2.1.3 形成抽象地圖

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

圖5 抽象地圖

2.2 實時尋路

2.2.1 抽象尋路

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

圖6 抽象路徑

2.2.2 細化路徑

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

3 HPA*改進算法

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

圖7 區(qū)塊化多層表示

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

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

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

3.1 離線預處理

3.1.1 預處理地圖

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

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

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

3.1.2 選擇關鍵節(jié)點

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

E?Ti∪Tj;

(1)

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

(2)

t.nodeType!=notWalk。

(3)

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

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

(4)

a=E[E.length/4]。

(5)

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

圖9 關鍵節(jié)點示意圖

3.1.3 繪制抽象地圖

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

圖10 抽象地圖

3.1.4 構建區(qū)塊間映射矩陣

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

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

(6)

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

(7)

3.1.5 緩存區(qū)塊間最短路徑

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

哈希表定義如下:

Dictionary> cacheTable = new Dictionary>()

哈希鍵值定義如下:

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

3.2 實時路徑搜索

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

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

(1)權重引導尋路方向

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

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

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

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

(8)

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

圖11 網(wǎng)格權重圖

(2)規(guī)避openList隊列循環(huán)遍歷

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

path Find Times+=1;

closeList.Add(node);

node.nodeFindIndex+=1;

While path Find Times!=node.node FindIndex

{open List.Add(node);}

4 實驗結果及分析

本文采用C#在Unity游戲引擎上實現(xiàn)A*、HPA*和HPA*改進算法,在不同尺寸游戲網(wǎng)格地圖中進行了三組數(shù)值仿真實驗。地圖大小分為3種,分別為64×64、512×512和1024×1024。藍色節(jié)點障礙物按照每幅地圖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的地圖規(guī)模較小,搜索空間有限,3種算法的效率差異不是很明顯。但是在512×512的中等規(guī)模地圖上,三種算法的平均時間差異非常明顯。其中,A*算法的平均時間達到了53 ms以上,而傳統(tǒng)HPA*算法和HPA*改進算法的平均時間分別為17.13和9.43 ms。在1024×1024的大型規(guī)模地圖上,A*算法的平均時間達到了170.12 ms,HPA*算法和HPA*改進算法的平均時間分別為31.76和11.62 ms。這是因為在大規(guī)模地圖上,搜索空間非常龐大,傳統(tǒng)的啟發(fā)式搜索算法對搜索空間的控制比較弱,而HPA*算法可以將地圖劃分成更小的區(qū)塊,從而大大減小搜索空間,提高搜索效率。改進算法在此基礎上采用了一系列的優(yōu)化,如緩存關鍵節(jié)點對最短路徑、構建層級間映射矩陣、優(yōu)化A*實時查詢等進一步提高了搜索效率和速度。

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

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

(a)HPA*路徑

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

5 結論

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