面向大型三維場景的優化分層A*尋路算法研究

朱昌龍 劉黎志

摘 要：針對大型三維場景中A*尋路算法存在搜索節點過多、尋路效率低的問題，提出了一種面向三維場景網格的改進分層A*算法。首先將三維場景進行體素劃分，根據三維體素的屬性生成可行走域的導航網格，并利用多級K劃分對導航網格進行抽象分層，形成抽象分層路徑，然后使用雙向搜索策略對A*算法進行優化。建立了大型三維場景環境下尋路仿真實驗平臺，將傳統A*算法與改進分層A*算法進行性能對比，實驗證明改進分層A*算法搜索效率明顯高于傳統A*算法。

關鍵詞：A*算法；體素化；分層路徑；導航網格；雙向搜索

DOI：10. 11907/rjdk. 182335

中圖分類號：TP312 文獻標識碼：A 文章編號：1672-7800（2019）005-0013-04

Abstract： Regarding the shortcoming of A-star algorithm's excessive searching nodes of path and inefficiency of searching in large 3D scenes， an improved hierarchical A-star algorithm for 3D scene mesh is presented. Firstly， the voxel is divided into three-dimensional scenes， and the navigation mesh of the walkable domain is generated according to the attributes of the three-dimensional voxel， and the navigation mesh is abstractly divided by Multilevel K-way Partitioning to form an abstract hierarchical path. Secondly， the A-star algorithm is optimized using a bidirectional search strategy. Finally， a pathfinding simulation experiment platform in a large three-dimensional scene environment is established. The performance difference between the traditional A-star algorithm and the hierarchical A-star algorithm is analyzed and compared. The experiment proves that the improved hierarchical A-star algorithm has higher search efficiency than the traditional A-star algorithm.

Key Words： A* algorithm； voxelization； hierarchical path； navigation mesh； bidirectional search

0 引言

玩家喜愛擁有大型三維場景的游戲。如何提高游戲路徑搜索性能是游戲人工智能的研究熱點 [1-4]，路徑搜索過程分為地圖預處理和尋路算法兩方面。

地圖預處理常用的方法是柵格法[5-7]，它將地圖劃分為等面積大小方格，根據障礙物占柵格的百分比判斷柵格屬性。柵格法是一種較簡單的地圖劃分方法，但針對大型三維場景地圖，尋路算法搜索的網格節點過多，從而導致搜索效率過低。導航網格法[8-11]是將可行走域的地圖以多邊形或三角形數組進行劃分的方法，在大面積地圖區域中可減少大量的搜索節點。

尋路算法目前應用最多的是A*算法[12-14]，它是一種最基本的啟發式全局路徑搜索，通過啟發式函數估計從當前節點到達鄰居節點到目標點的成本進行路徑搜索。A*算法近年來得到了很多改進 [15-17]，如為降低基于網格的地圖路徑查找復雜性，Adi Botea等[18]提出了基于網格的分層A*方法，該技術將地圖根據四叉樹算法等距離劃分為相互連接的本地集群，在本地級別預先計算并緩存跨越每個群集的最佳距離，在全局層面路徑搜索直接跨越集群而不是移動到相鄰的節點位置。但是這種分層路徑方法可能導致不平衡的抽象路徑集群，所得到的更高級別層次結構在節點之間具有不均勻的邊緣數量。基于導航網格的分層尋路算法，利用多級K劃分方法進行分層，采用雙向搜索策略進行優化，可極大減少節點數量，提高尋路搜索效率[19-21]。

1 三維場景導航網格

導航網格是一組用來劃分地圖信息的多邊形數組集合。三維導航網格與二維導航網格區別在于：三維場景中允許有不同高度上的重疊移動區域，導航網格可行走的區域劃分取決于游戲設定的人物可行走坡度。

三維導航生成步驟：①體素化輸入三維地圖模型，生成體素集合。體素是三維空間的劃分單位，每個體素單位包含地圖的屬性信息，如圖1（a）所示為地圖模型體素化；②根據三維場景的配置信息（如可行走的坡度等），過濾障礙物以及角色無法行走的區域，生成可行走的區域體素集合。如圖1（b）所示，藍色為可行走區域，當坡度不滿足設置要求時則為不可通過區域；③使用分水嶺算法進行多邊形劃分，將可行走域劃分為多個凸多邊形的形式，如圖1（c）劃分了多個凸多邊形；④對凸多邊形繼續使用三角剖分算法細分為三角網格，如圖1（d）所示。

生成三維場景導航流程如圖2所示，已生成的導航網格以三角形網格集合形式呈現。為使三角網格同樣適用于A*算法尋路，需要對A*算法的網格代價重新定義，定義三角網格之間的耗費代價為三角網格中心之間的距離。

2 多層K路劃分分層

三維導航網格是大小不同的三角形網格，不能采用基于柵格地圖的均勻四叉樹方法劃分。為使導航網格分層的各區域更加平衡，采用多級K路劃分算法進行抽象分層。

粗化階段的主要目的是降低原始圖的復雜性，方便構建圖的層次結構。在粗化過程中，從原始圖G0=（V0，E0）創建出一系列較小的Gi=（Vi，Ei），并滿足 |Vi | < |Vi-1|。由Gi創建下一層級圖Gi+1的方法是：通過找到Gi的最大匹配Mi？Ei，并將在相匹配的每個邊的相關聯頂點折疊在一起，不相關聯頂點保留。如果沒有發現相關聯的頂點則稱為最大匹配，不需要繼續分層。為保持粗化后的圖能保持原始圖的一致性及保留連接信息，將粗化后的圖的頂點和邊的權重分別設置為上一層圖的頂點和邊的權重之和。

初始化階段分區使用多級二分算法，以保證每個分區的節點權重之和大致等于原始圖|V0|/K的節點權重。劃分方法使用Kernighan-Lin算法，該算法本質是迭代的。首先將節點劃分為兩個不相交的子集，并使兩個不相交的子集最小化，再從每個子集中找到一個頂點繼續劃分。

在細化階段，將粗化圖的分區（Gm，Gm-1，…G1）投影回原始圖中。在每個投影步驟之后，使用動態方法來細化分區，在分區之間迭代地移動節點，從而改善分區質量。當所有分區投影至原始圖時，細化階段結束。

3 優化A*算法

A*尋路算法是基本的啟發式路徑搜索算法，根據估價函數對當前節點周圍的鄰居節點進行評估，選擇代價最小的節點作為下一路徑點。常規的A*算法是從起始點開始依次循環遍歷直到搜索到目標點為止，采用雙向搜索策略可極大提高搜索效率。

3.1 A*算法優化

A*尋路算法是基本的啟發式路徑搜索算法，根據估價函數對當前節點周圍的鄰居節點進行評估，選擇代價最小的節點作為下一路徑點。常規的A*算法是從起始點開始依次循環遍歷，直到搜索到目標點為止。A*算法對節點數據操作采用兩個優先隊列表，一個是Open列表，用來存儲待考察的節點，另一個是Close列表，用來存儲已考察的節點。每進行一次尋路過程，都需要更新Open列表和Close列表。當地圖規模很大時會產生大量節點，導致搜索效率過慢，因此采取雙向搜索策略。

雙向搜索算法同時運行兩個搜索方法：一個從起始點正向搜索，另一個從目標點反向搜索，當各個方向搜索出相同最優路徑點則停止搜索并連接。A*算法的雙向搜索策略需要建立4個優先隊列表：正向的Fopen列表、Fclose列表以及反向的Bopen列表和Bclose列表，用于存儲搜索節點。A*尋路算法性能很大程度上取決于啟發式函數和估價函數。

搜索路徑過程分為4個階段：

（1）確定起始點S與目標點G。預先確定起始點S和目標點G的層次分區并連接分區的邊界。對于已經確定的起始點S和目標點G，依次遞歸地從L0層查找至最高層，存儲所在的層次。

（2）在抽象圖中插入起始點S和目標點G。將起始S和目標G位置插入最低層次L0的圖中，然后遞歸地查找最高層次的相應節點層次結構，將起始點S、目標點G作為臨時節點Nts和Ntg插入更高層次級別的抽象圖中。分別連接至所在抽象分區的鄰接邊緣，由最底層分區至最高層分區，分別計算并存儲起始點S到分區的每個鄰接邊緣的最短路徑。如圖5（a）所示為起始點連接分區邊緣。

（3）在最高層次抽象圖中搜索起始點S至目標點G的最短路徑。當最高層次抽象圖中確定了起始點S和目標點G的臨時節點，就可在最高層次抽象圖中使用A*尋路算法。

（4）連接完整路徑。A*尋路算法給出了在抽象圖中各個層次的最短路徑，路徑搜索從最高層次抽象圖搜索至最低層次結束，連接各個層次的臨時節點獲得完整路徑，見圖5（b），得到S到G的最短路徑，最后再刪除臨時節點釋放內存。

4 實驗仿真及評估

為驗證基于導航網格分層優化A*算法的性能，實驗仿真地圖采用某大型城市游戲三維地圖，如圖6（a）所示。首先將游戲地圖導出為模型文件，利用建模工具3DMax剔除障礙物，只保留可行走的域模型并生成導航網格，以導航圖的形式保存下來。最后利用Unity3D游戲引擎搭建實驗平臺，導入導航圖，劃分三層抽象圖，利用優化分層A*算法找到最優路徑，如圖6（b）所示。

對三維大型地圖經過實驗對比分析，在測試50次的標準下取平均值，測試結果見表1。雖然導航網格預處理地圖的時間高于傳統方格地圖，但在搜索時間上明顯小于基于方格A*算法。綜合實驗分析，基于導航網格分層優化A*算法搜索速度明顯高于傳統A*算法。

5 結語

本文基于靜態大型地圖進行全局尋路并給出了一種高效的尋路算法。首先將地圖預處理為導航網格并將地圖進行分層處理，利用雙向搜索策略進行改進，利用Unity3D引擎搭建實驗平臺，實驗證明該算法在尋路效率上有明顯提升。但在動態地圖和局部動態尋路方面，分層劃分和雙向搜索算法有一定的局限性，動態尋路問題是下一步研究重點。

參考文獻：

[1] 何國輝，陳家琪. 游戲開發中智能路徑搜索算法的研究[J]. 計算機工程與設計，2006，27（13）：2334-2337.

[2] 詹海波. 人工智能尋路算法在電子游戲中的研究和應用[D]. 武漢：華中科技大學，2006.

[3] 李井頌. 游戲中的智能路徑搜索算法及其應用[D]. 昆明：昆明理工大學，2017.

[4] 周振華. 游戲場景中分層尋路算法及地圖復雜性度量研究[D]. 保定：河北大學，2014.

[5] 于紅斌，李孝安. 基于柵格法的機器人快速路徑規劃[J]. 微電子學與計算機，2005，22（6）：98-100.

[6] 王衛紅，顧國民，秦緒佳，等. 基于柵格法的矢量路徑規劃算法[J]. 計算機應用研究，2006，23（3）：57-59.

[7] 夏梁盛. 基于柵格法移動機器人運動規劃研究[J]. 計算機仿真，2012，29（12）：229-233.

[8] 朱慶，王燁萍，張駿驍，等. 綜合導航網格模型及其在智慧旅游尋徑中的應用[J]. 西南交通大學學報，2017，52（1）：195-201.

[9] 王燁萍. 基于綜合導航網格的智慧旅游動態尋徑方法[D]. 成都：西南交通大學，2017.

[10] 陳娜，黃明和，劉清華. 基于DAF算法的地圖尋徑研究[J]. 科學技術與工程，2010，10（30）：7536-7540.

[11] 林巍凌. 引入導航網格的室內路徑規劃算法[J]. 測繪科學， 2016，41（2）：39-43.

[12] 陳和平，張前哨. A*算法在游戲地圖尋徑中的應用與實現[J]. 計算機應用與軟件，2005， 22（12）：118-120.

[13] 劉浩，鮑遠律. A*算法在矢量地圖最優路徑搜索中的應用[J]. 計算機仿真， 2008（4）：253-257.

[14] 熊偉，張仁平，劉奇韜，等. A*算法及其在地理信息系統中的應用[J]. 計算機系統應用，2007，16（4）：14-17.

[15] HARABOR D， GRASTIEN A. Online graph pruning for pathfinding on grid maps[C]. California：AAAI Conference on Artificial Intelligence，2011.

[16] DEKIM H，YU K，KIM J. Reducing the search space for pathfinding in navigation meshes by using visibility tests[J]. Journal of Electrical Engineering & Technology，2011，6（6）：867-873.

[17] 陳剛，付少鋒，周利華. A*算法在游戲地圖尋徑中的幾種改進策略研究[J]. 科學技術與工程，2007，7（15）：3731-3736.

[18] BOTEA A， MüLLER M， SCHAEFFER J. Near optimal hierarchical path-finding[J]. Journal of Game Development，2004， 1（7）：7-28.

[19] 鄭麗麗. 帶權圖的k劃分算法研究[D]. 天津：天津工業大學，2013.

[20] KARYPIS G，KUMAR V. Parallel multilevel k-way partitioning scheme for irregular graphs[J]. Siam Review，1999，41（2）：278-300.

[21] 高松，陸鋒，段瀅瀅. 一種基于雙向搜索的K則最優路徑算法[J]. 武漢大學學報：信息科學版，2008，33（4）：418-421.

（責任編輯：杜能鋼）