一種基于A*的RPG游戲尋路算法

謝吉剛

(南京工業職業技術學院計算機與軟件學院，江蘇南京，210023)

0 引言

路徑搜索是一項在各個領域中廣泛應用的重要技術，是計算機游戲尤其是在角色扮演類、戰略類游戲的重要組成部分。智能游戲中的路徑搜索就是玩家根據地圖場景中各類物體的分布信息，控制角色找到從起點到目標節點之間最佳路徑的過程[1]。除了基本的避障算法之外，目前該領域已經有許多路徑搜索算法，有傳統的啟發式A*尋路算法，基于抽象圖的HPA*、M-A*等尋路方法，考慮地圖分布信息的CDHPA*分層路徑搜索算法等[2]。這些算法雖然各有不同的優缺點，但都是希望快速找出一條最優路徑，使角色能夠盡快到達目的地。

角色扮演游戲簡稱為RPG游戲，一般就是玩家控制角色在虛擬空間中不斷地自主探索，并在探索過程不斷的提升[3]，場景一般都會比較大，而且會隨著游戲劇情的展開而動態的變化，現有的尋路方法難以適應這些要求。本文提出一種專門針對角色扮演游戲特點的尋路算法——分層避障尋路算法。該算法使用分層處理提高搜索效率，A*算法選取最優路徑，避障處理解決場景的動態變化問題，兼顧了大場景的快速尋路，同時也能夠體現出角色的探索過程，保證了玩家的游戲樂趣。

1 典型路徑搜索算法

1.1 簡單避障算法

虛擬場景中的尋路，簡單說就是向目標點靠近的過程。如果沒有障礙物，用基本的跟蹤算法就可以實現。在有障礙物的地圖中，需只要使用一定的避障策略才能到達目的地。具體的有試探法、輪廓跟蹤法等[4]。

試探法的基本思路是當智能體與障礙物發生碰撞后，先退后左轉或右轉一定角度，然后向前移動一段距離，再根據目標位置調整朝向進行尋路?；蛘唠S機的移動一段位置。該方法雖然簡單，但會使智能體顯得比較笨拙。相對真實和高效的尋路技術是輪廓跟蹤，就是在智能體遇到障礙物一定距離時，就旋轉移動方向使之繞著障礙物的輪廓進行移動[5]。

避障算法屬于盲目的搜索，不能實現最優尋路，但是響應快，無論多么復雜的場景，多少對象的同時尋路，系統都會立刻響應，而且這種盲目性在游戲過程中顯現出來的探索過程也正是RPG游戲所需要的，適度的探索在一定程度上能夠增加游戲的真實感。但是如果起始點和目標點距離較遠，或者障礙物分布比較復雜，比如典型的U型障礙，單純使用盲目避障算法可能會導致角色多次迂回、很長時間不能到達目的地[6]，這是玩家所不能接受的。

1.2 A＊算法

盲目搜索算法又叫做無信息搜索，一般只適用于求解比較簡單的問題[7]。有信息搜索稱為啟發式搜索，其在搜索過程中加入了特定問題領域的啟發信息，使得每次搜索向著最有希望的方向進行。最經典的啟發式搜索算法為A*算法，該算法被廣泛應用在目前流行的即時戰略游戲中，同時也是大量后續尋路算法的基礎。關于虛擬場景的最優尋路問題中最為著名的是A*尋路算法，其他很多方法都是基于此方法。A*算法是一種典型的啟發式搜索算法，經常被用于游戲人工智能的尋路實現中,主要是通過檢查特定狀態的相鄰或鄰接狀態來搜索從起始狀態到目標狀態的最小代價路徑[8]。它使用啟發函數f(n)來估計當前節點到目標點的距離并決定一步如何進行。其構造原則是盡量使求解問題的搜索耗費和路徑成本之和最小，所以使得搜索總是向著最有希望的方向發展，其性能依賴于地圖的分布和具體任務。當地圖規模較大時，耗費大量的存儲和時間，性能急速下降，往往不能滿足游戲的實時性要求[9]。而且，對于多個對象尋路的時候效率很有影響。所以直接使用A* 算法不能滿足RPG游戲的要求。

1.3 分層抽象算法

由于A*算法不能滿足大規模地圖的尋路問題，大量的研究人員基于A*算法開發了一系列基于抽象思想的分層路徑搜索算法，其主要思想是對地圖進行抽象分層，建立一個層次結構，將原始地圖變成一個多層次的小地圖。在進行路徑搜索時，首先從最高層次進行抽象搜索，在下一層進行細化，直到最后一層得到實際路徑。

分層網格化有幾種方式，1996年Hotle，Perez等人提出的HPA*算法提出簡單的做法是根據場景的規模，選擇一個系數均勻分區。這種做法算法簡單，分區快，但未考慮地圖場景中障礙物的分布信息，這使得空曠區域會出現多余分區，這樣采用A*尋路算法會使尋路速度及路徑最優性降低[10]。當HPA*在含有大片空曠區域的地圖上進行尋路時此缺點尤為明顯，而真實的計算機游戲地圖中總是存在大量的空白區域。改進的算法是M-A*算法，該算法每次執行尋路任務時根據起始點與目標點的信息重新對地圖進行劃分，并且在劃分時只針對包含起點與終點的子區域進行細分，直到該區域只包含起點或終點[11]。M-A*算法在進行分區時考慮了不同尋路任務對于算法的影響，依據起點與終點的信息進行分區并構造四叉樹，改善了A*算法在最壞情況下的計算復雜度，并且得到最優路徑。使用多尺度環境信息進行分層同樣縮小了搜索空間，但M-A*在每次分區前需要給定起點與終點的信息，對于同一幅地圖的多次尋路任務需要進行多次分區，大大增加了玩家的在線等待時間。而RPG游戲通常尋路對象會比較多，而且分布在不同的位置。還有一種Quadtree算法是一種通過考慮地圖場景中的障礙物分布信息將地圖進行分區抽象的分層路徑搜索算法[12]。該算法首先將地圖進行均勻四分，然后分別判斷每一個子區域中所有單元格的狀態。若當前分區中的所有單元格均為障礙或非障礙則不再進行細分，否則將單元格繼續四分，直到每一個分區中都只包含一種狀態的單元格。Quadtree算法在分區時雖然考慮了地圖中障礙物的分布信息，但其要求每一個分區都只能包含一種狀態的節點，導致抽象節點非常多，耗費了大量的內存，且不能保證找到最優路徑。因此這種方法只能對于大規模地圖還是顯得無能為力。

抽象分層思想的使用加速了尋路速度，減小了存儲耗費，解決了大規模地圖的尋路問題。但在分層及尋路時不考慮地圖場景中障礙物的分布信息或在任何區域都使用A*方法進行尋路，大大降低了空曠區域上的搜索效率，另外如果地圖動態變化，就需要對地圖進行再一次預處理，增加了很多資源耗費，有時候效率可能反而會有所下降。

2 分層避障搜索算法

從前面的分析我們可以看出，避障算法響應快，但過于盲目；A*尋路算法能最優尋路，但不能適應大地圖；分層能夠提高搜索效率，但是不能適應地圖的動態變化，這幾種算法都有各自的優缺點，單純使用其中任何一種算法都不能很好地解決RPG游戲這種大場景、多對象、快速響應的動態大場景尋路問題。結合這三種方法，本文提出一種新的路徑搜索算法——分層避障搜索算法。具體算法思路可以分為分層預處理，避障尋路兩個過程進行實現。為了論述簡單，只選擇某一游戲地圖的部分場景作為示例（如圖1）。下面結合該例對該算法進行詳細論述。

圖1 游戲場景圖

2.1 分層預處理

首先對場景進行分層預處理。該過程包括分層網格化、確定關鍵點、構成抽象圖三個步驟?？紤]到本算法需要采用的碰撞檢測算法的特點，這種算法對于空曠區會直接沿著直線前進，不會影響效率。因此直接采用均勻分區的方式分層，這樣算法很簡單，而且即使有大片的空曠區也不會影響算法效率。對于分區的大小的確定，本算法認為應該把角色的尺寸考慮進來，因為簡單避障尋路算法的主要問題是避免角色進入較大的U型甚至C型障礙，一般而言，相對于角色尺寸10倍以內的U型障礙角色都不需要花太多時間就能夠繞出來。因此本算法采用均勻分層，分層網格選定為角色尺寸10倍左右即可。為提高計算效率，一般采用對分法，即先將該地圖均勻分成2×2網格，再分成4×4網格直至將地圖分成10倍角色大小左右的網格。這樣最后結果就總會以2的整數次冪劃分。本例將地圖分成4×4網格。然后把每一個網格分成8×8子網格。每個子網格大小就與角色大小基本一致了。網格化之后再標記子網格，黑色區域為障礙區域，白色區域為可通行區域（如圖2）。

圖2 分層網格化后的地圖

確定關鍵點是指在相鄰區域的邊界上定義邊界之間的關鍵點，這些關鍵點將會作為后面的搜索依據。根據分層網格的大小和分層方法的不同，關鍵點的選擇規則也幾種不同的方法。在大部分分層算法（如HPA*）中，采用的是遍歷兩個相鄰區域的公共邊界，然后去公共邊界上最長的連續非障礙區的中點作為關鍵點[13]。有的算法（如M-A*算法）采用的是最長的連續非障礙區的兩個端點作為關鍵點[14]。本算法分層網格相對于尋路角色而言比較小，因此采用的基本確定規則為:遍歷所有相鄰的四個區域（如Area1、Area2、Area3、Area4），找出公共邊界上的最長的連續非障礙物網格作為相鄰網格的出入口，若該非障礙區小于區域邊界的1.2倍（如Grid1，本例選擇10），則確定該區域中點為關鍵點。反之，若該非障礙區大于區域邊界的1.2倍（如Grid2），則將該區域邊界對分，然后這兩個對分區中點為關鍵點。也就是說對于較大的可通行公共邊確定兩個關鍵點，較小的邊確定一個關鍵點。這樣可以避免尋路時角色出現明顯的繞行。最后確定關鍵點仍然在圖2種標出。

接下來構成抽象圖。對任意四個相鄰區域中的任意兩個關鍵點，使用A*算法確定該兩點在該區域范圍內是否連通，若能夠連通，確定它們的最優的連通路徑，形成關鍵點路徑抽象圖（如圖3）。至此預處理過程結束。

2.2 避障尋路

關于行進路線的確定，傳統的諸如HPA*算法等基本是采用依據給定的起點和終點信息，找到其所在子區域，然后利用A*算法找出起點和終點到相鄰關鍵點的最優路徑，然后將該路徑插入到抽象圖中，然后進行平滑處理形成起點到終點的最優路徑[15]。這種方法僅僅減小了A*的計算規模，每次形成最優路徑還是需要一定的計算耗費，因此如果出現多個對象同時尋路就可能出現遲滯現象，會讓玩家不能接受。另外一旦地圖發生變化，比如新建了一個基地，或者增加或取走一個寶箱等等，就需要再次進行地圖預處理，形成新的路徑抽象圖。因此本算法在起點和終點到它們的相鄰關鍵點采用簡單避障尋路，在行進過程中進行碰撞檢測，這樣即使有多個對象同時尋路，也不會出現遲滯現象。因此本算法從起點到鄰近關鍵點就采用最簡單的帶碰撞檢測的直線尋路算法。

圖3 關鍵點路徑抽象圖

具體搜索過程可以如下描述。假定角色需要從位置Start移動到位置End。首先判斷起點和終點是否處于被包圍狀態，如果是，不必尋路。然后判斷是否在同一區域，如果是，就直接利用避障直線尋路算法即可。反之則分別確定起點和終點所在區域，并選取該區域中的最近關鍵點分別作為起始關鍵點和結束關鍵點。這里選取了A點為起始關鍵點，B點為結束關鍵點。然后使用A*尋路算法在抽象圖層次中搜索一條最優的從關鍵點A到B的抽象路徑。之后運用避障算法使角色從起點Start搜索移動到A點，同樣，當角色到達終點區域的結束關鍵點B點后，運用避障搜索移動到終點End。至此整個尋路過程結束。

該過程部分主要代碼如下：

bool Role_PathPlanner::CreatePathToPosition(Vec tor2D TargetPos,std::list＜Vector2D>&path)

//如果起點或終點處于被包圍或其他原因，不能尋路

{ if(ClosestNodeToBot==no_closest_node_found)

{ return false }

//如果起點和終點處于同一個區域，不必搜索，直接避障尋路

if(!m_pOwner()->GetWorld()->isPathObstructed(m_pOwnerPos(),TargetPos,m_pOwner->BRadius()))

{path.push_back(TargetPos);

Return true }

//創建A*搜索類實例，在起始和結束關鍵點之間搜索一條路徑

Astar searh(m_NavGraph,CloseNodeToBot,CloseNode ToTarget);

Std::list＜int>PathOfNodeIndices=search.GetPathToTarget();

//搜索成功，開始行進

if(!PathOfNodeIndices.empty())

{path.push_back(TargetPos);

return true; }

//搜索失敗

else

{return flase } }

2.3 地圖動態變化的處理

如果地圖發生變化，傳統的做法就是重新預處理，生成新的抽象圖。對于RPG游戲而言，地圖變化會比較頻繁，每次變化就生成新的抽象圖顯然不合適。本算法針對不同地圖的動態變化采用不同的處理方法。如果新的障礙不在抽象路徑上，那么并不影響尋路，不需要任何新的處理。如果正好在抽象路徑上出現了一個新的障礙，如圖3中的Obstracl。由于角色在行進過程中同時進行碰撞檢測，當檢測到障礙存在，即啟用避障算法行進到下一個關鍵點，到達下一個關鍵點之后繼續沿原有抽象路徑前進即可。如果在沿抽象圖行進過程中遇到三次以上的障礙，說明地圖變化已經比較大了，本次尋路雖然繼續進行，但同時呼叫系統重新進行預處理，生成新的抽象圖。

3 結語

經過將分層避障算法應用于RPG游戲發現，該算法由于經過分層預處理，大大減小了A*算法所存在的計算規模問題。對起點位置向起始關鍵點利用避障算法尋路，避免了路徑規劃過程的等待時間，這一點尤其在多個角色的同時尋路的時候顯得尤其明顯，而且近距離的避障試探過程顯得更加符合實際情況，遠距離采用A*尋路使角色能夠快速到達目的地。在尋路過程中增加碰撞檢測，很容易地解決了RPG游戲的地圖動態變化問題。