朱昌龍 劉黎志

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

關(guān)鍵詞：A*算法；體素化；分層路徑；導(dǎo)航網(wǎng)格；雙向搜索

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]，路徑搜索過程分為地圖預(yù)處理和尋路算法兩方面。

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

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

1 三維場景導(dǎo)航網(wǎng)格

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

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

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

2 多層K路劃分分層

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

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

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

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

3 優(yōu)化A*算法

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

3.1 A*算法優(yōu)化

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

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

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

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

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

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

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

4 實驗仿真及評估

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

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

5 結(jié)語

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

參考文獻：

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

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

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

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

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

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

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

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

[9] 王燁萍. 基于綜合導(dǎo)航網(wǎng)格的智慧旅游動態(tài)尋徑方法[D]. 成都：西南交通大學(xué)，2017.

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

[11] 林巍凌. 引入導(dǎo)航網(wǎng)格的室內(nèi)路徑規(guī)劃算法[J]. 測繪科學(xué)， 2016，41（2）：39-43.

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

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

[14] 熊偉，張仁平，劉奇韜，等. A*算法及其在地理信息系統(tǒng)中的應(yīng)用[J]. 計算機系統(tǒng)應(yīng)用，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]. 科學(xué)技術(shù)與工程，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] 鄭麗麗. 帶權(quán)圖的k劃分算法研究[D]. 天津：天津工業(yè)大學(xué)，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則最優(yōu)路徑算法[J]. 武漢大學(xué)學(xué)報：信息科學(xué)版，2008，33（4）：418-421.

（責(zé)任編輯：杜能鋼）