朱昌龍 劉黎志

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

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

DOI：10. 11907/rjdk. 182335

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

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

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

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

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

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

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

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

2 多層K路劃分分層

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

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

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

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

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

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

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

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

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

搜索路徑過程分為4個(gè)階段：

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

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

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

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

4 實(shí)驗(yàn)仿真及評(píng)估

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

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

5 結(jié)語

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

[9] 王燁萍. 基于綜合導(dǎo)航網(wǎng)格的智慧旅游動(dò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]. 測(cè)繪科學(xué)， 2016，41（2）：39-43.

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

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

[14] 熊偉，張仁平，劉奇韜，等. A*算法及其在地理信息系統(tǒng)中的應(yīng)用[J]. 計(jì)算機(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ìn)策略研究[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é)報(bào)：信息科學(xué)版，2008，33（4）：418-421.

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