李藝貴,郭 銳,邱國(guó)鵬,2

(1.三明學(xué)院 藝術(shù)與設(shè)計(jì)學(xué)院,福建 三明 365004;2.克拉斯諾達(dá)爾文化學(xué)院,俄羅斯 克拉斯諾達(dá)爾 350072)

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

1 相關(guān)研究

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

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

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

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

2 HPA*算法

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

2.1 離線(xiàn)預(yù)處理

2.1.1 預(yù)處理地圖

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

圖2 實(shí)際游戲地圖

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

2.1.2 尋找關(guān)鍵節(jié)點(diǎn)

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

圖4 關(guān)鍵節(jié)點(diǎn)示意圖

2.1.3 形成抽象地圖

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

圖5 抽象地圖

2.2 實(shí)時(shí)尋路

2.2.1 抽象尋路

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

圖6 抽象路徑

2.2.2 細(xì)化路徑

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

3 HPA*改進(jìn)算法

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

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

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

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

圖8 HPA*改進(jìn)算法的流程圖

3.1 離線(xiàn)預(yù)處理

3.1.1 預(yù)處理地圖

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

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

網(wǎng)格單元節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)為:GridNode { Vector2 position; int zoneId; int nodeFindIndex; int weight; enum nodeType{walk; notWalk }; GridNode nodeFather; floatf; floatg; floath}。Position為網(wǎng)格節(jié)點(diǎn)坐標(biāo),zoneId、nodeFindIndex、weight分別為節(jié)點(diǎn)所在區(qū)塊編號(hào)、游戲?qū)ぢ反螖?shù)、網(wǎng)格權(quán)重值,nodeType為節(jié)點(diǎn)類(lèi)型,nodeFather為父節(jié)點(diǎn),f、g、h分別為期望值、實(shí)際代價(jià)值、估計(jì)代價(jià)值。

3.1.2 選擇關(guān)鍵節(jié)點(diǎn)

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

E?Ti∪Tj;

(1)

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

(2)

t.nodeType!=notWalk。

(3)

在互通區(qū)域Zi側(cè),選擇中間網(wǎng)格單元作為關(guān)鍵節(jié)點(diǎn),并按照順時(shí)針?lè)较蛟诿總€(gè)區(qū)塊內(nèi)為關(guān)鍵節(jié)點(diǎn)設(shè)置唯一的編號(hào),其中,關(guān)鍵節(jié)點(diǎn)a必須符合以下條件:

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

(4)

a=E[E.length/4]。

(5)

如圖9所示,區(qū)塊Z0與Z1 的公共邊上黃色網(wǎng)格為互通區(qū)域,Z0上綠色網(wǎng)格為關(guān)鍵節(jié)點(diǎn),Z0與Z5公共邊上黃色網(wǎng)格為互通區(qū)域,Z0上綠色網(wǎng)格為關(guān)鍵節(jié)點(diǎn)。在Z0區(qū)塊中按照順時(shí)針?lè)较蛞来谓o關(guān)鍵節(jié)點(diǎn)設(shè)置編號(hào):0、1。

圖9 關(guān)鍵節(jié)點(diǎn)示意圖

3.1.3 繪制抽象地圖

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

圖10 抽象地圖

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

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

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

(6)

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

(7)

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

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

哈希表定義如下:

Dictionary> cacheTable = new Dictionary>()

哈希鍵值定義如下:

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

3.2 實(shí)時(shí)路徑搜索

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

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

(1)權(quán)重引導(dǎo)尋路方向

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

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

如圖9,黃色網(wǎng)格是為關(guān)鍵節(jié)點(diǎn)標(biāo)記的引導(dǎo)路徑。如果普通節(jié)點(diǎn)權(quán)重值為100的話(huà),黃色節(jié)點(diǎn)權(quán)重值為10。在實(shí)時(shí)A*算法中,計(jì)算節(jié)點(diǎn)期望值時(shí),需要加上節(jié)點(diǎn)的權(quán)重值,期望值公式如下。

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

(8)

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

圖11 網(wǎng)格權(quán)重圖

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

在每次尋路中,當(dāng)一個(gè)節(jié)點(diǎn)被加入到openList列表時(shí),需要檢查該節(jié)點(diǎn)是否已經(jīng)在closeList列表中。如果在closeList中,就不需要添加到openList列表中。然而,隨著closeList列表中搜索節(jié)點(diǎn)的增加,會(huì)導(dǎo)致CPU計(jì)算量的增加,從而影響性能。為了避免這種情況,可以定義一個(gè)全局靜態(tài)整型變量pathFindTimes,用于記錄尋路次數(shù)。此外,每個(gè)節(jié)點(diǎn)還需要定義一個(gè)nodeFindIndex。每次尋路時(shí),將pathFindTimes的值加1。例如,在游戲開(kāi)啟時(shí),pathFindTimes和nodeFindIndex的初始值相同。當(dāng)玩家第一次尋路時(shí),pathFindTimes的值會(huì)加1。在將一個(gè)節(jié)點(diǎn)加入到closeList之后,該節(jié)點(diǎn)的nodeFindIndex也會(huì)加1。當(dāng)玩家第二次尋路時(shí),在將節(jié)點(diǎn)添加到開(kāi)啟列表之前,需要檢查該節(jié)點(diǎn)的nodeFindIndex 是否等于pathFindTimes的值。如果相等,表示該節(jié)點(diǎn)已經(jīng)在開(kāi)啟列表中,不需要再次添加。通過(guò)這種優(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 實(shí)驗(yàn)結(jié)果及分析

本文采用C#在Unity游戲引擎上實(shí)現(xiàn)A*、HPA*和HPA*改進(jìn)算法,在不同尺寸游戲網(wǎng)格地圖中進(jìn)行了三組數(shù)值仿真實(shí)驗(yàn)。地圖大小分為3種,分別為64×64、512×512和1024×1024。藍(lán)色節(jié)點(diǎn)障礙物按照每幅地圖10%的比例隨機(jī)生成,如圖12所示。在64×64的地圖上隨機(jī)選取50對(duì)起始點(diǎn)和目標(biāo)點(diǎn),并且路徑長(zhǎng)度都大于30;在512×512的地圖上隨機(jī)選取50對(duì)起始點(diǎn)和目標(biāo)點(diǎn),并且路徑長(zhǎng)度都大于250;在1024×1024的地圖上隨機(jī)選取50對(duì)起始點(diǎn)和目標(biāo)點(diǎn),并且路徑長(zhǎng)度都大于500。

(a)A*

表1～2給出了3種算法在不同尺寸游戲地圖上的尋路時(shí)間,在64×64的地圖上,3種算法的平均尋路時(shí)間相差不大,都在12 ms左右。這是因?yàn)?4×64的地圖規(guī)模較小,搜索空間有限,3種算法的效率差異不是很明顯。但是在512×512的中等規(guī)模地圖上,三種算法的平均時(shí)間差異非常明顯。其中,A*算法的平均時(shí)間達(dá)到了53 ms以上,而傳統(tǒng)HPA*算法和HPA*改進(jìn)算法的平均時(shí)間分別為17.13和9.43 ms。在1024×1024的大型規(guī)模地圖上,A*算法的平均時(shí)間達(dá)到了170.12 ms,HPA*算法和HPA*改進(jìn)算法的平均時(shí)間分別為31.76和11.62 ms。這是因?yàn)樵诖笠?guī)模地圖上,搜索空間非常龐大,傳統(tǒng)的啟發(fā)式搜索算法對(duì)搜索空間的控制比較弱,而HPA*算法可以將地圖劃分成更小的區(qū)塊,從而大大減小搜索空間,提高搜索效率。改進(jìn)算法在此基礎(chǔ)上采用了一系列的優(yōu)化,如緩存關(guān)鍵節(jié)點(diǎn)對(duì)最短路徑、構(gòu)建層級(jí)間映射矩陣、優(yōu)化A*實(shí)時(shí)查詢(xún)等進(jìn)一步提高了搜索效率和速度。

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

表2 路徑搜索節(jié)點(diǎn)實(shí)驗(yàn)結(jié)果 單位:ms

(a)HPA*路徑

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

5 結(jié)論

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