基于半邊數(shù)據(jù)結(jié)構(gòu)的A-star 路徑規(guī)劃算法及實(shí)現(xiàn)

古天馳，李曉東，蘇龍生

（佛山科學(xué)技術(shù)學(xué)院 計(jì)算機(jī)系，廣東 佛山 528225）

路徑規(guī)劃在游戲AI 自動(dòng)尋路、航路規(guī)劃、人工智能避障以及駕車地圖導(dǎo)航等現(xiàn)代計(jì)算機(jī)科學(xué)領(lǐng)域中都有著廣泛的應(yīng)用[1-2]，其主要實(shí)現(xiàn)障礙躲避以及最佳路徑的選擇。A-star 算法則是一種能夠達(dá)到最優(yōu)解且常運(yùn)用于最優(yōu)路徑規(guī)劃的算法。在路徑規(guī)劃方面，A-star算法通?；诜礁竦貓D實(shí)現(xiàn)，而方格地圖的空間描述局限性較大導(dǎo)致路徑選擇自由度受限。

傳統(tǒng)圖的鄰接表存儲(chǔ)結(jié)構(gòu)復(fù)雜而使用不便，導(dǎo)致搜索鄰接點(diǎn)、線和面時(shí)效率較低。而半邊數(shù)據(jù)結(jié)構(gòu)則是一種基于多邊形網(wǎng)格的空間數(shù)據(jù)結(jié)構(gòu)，常用于三維地圖表達(dá)，具有較強(qiáng)的拓?fù)湫院挽`活性，因此其在計(jì)算機(jī)圖形學(xué)、三維建模等領(lǐng)域有著廣泛的應(yīng)用[3-4]。本文提出含鄰接邊中點(diǎn)信息的半邊數(shù)據(jù)結(jié)構(gòu)，并與利用優(yōu)化預(yù)估代價(jià)計(jì)算模型的A-star 算法結(jié)合，運(yùn)用于三角網(wǎng)格3D 地圖，可突破方格地圖的空間局限，有利于提高網(wǎng)格地圖的空間利用率，同時(shí)提高路徑搜索效率。

1 算法原理

1.1 半邊數(shù)據(jù)結(jié)構(gòu)描述

半邊數(shù)據(jù)結(jié)構(gòu)是可用于網(wǎng)格中鄰接元素查詢的一種數(shù)據(jù)結(jié)構(gòu)，相較于鄰接表方式，半邊數(shù)據(jù)結(jié)構(gòu)更有利于點(diǎn)、線及面的拓?fù)渌阉髟L問，同時(shí)半邊數(shù)據(jù)結(jié)構(gòu)對(duì)于網(wǎng)格的表達(dá)要求是流形結(jié)構(gòu)[5]，其中三角形是簡(jiǎn)單的流形結(jié)構(gòu)，故下面是基于三角網(wǎng)格的問題研究。一個(gè)網(wǎng)格地圖包含點(diǎn)集、邊集和面集，其中三角面的每條邊為有向邊，且逆時(shí)針構(gòu)成環(huán)。頂點(diǎn)結(jié)構(gòu)HE_Vertex 包含坐標(biāo)及其出半邊edge 的信息；半邊結(jié)構(gòu)HalfEdge 包含目標(biāo)頂點(diǎn)target、相鄰半邊pair、下一條半邊next 以及所屬面face 的信息；面結(jié)構(gòu)HE_Face 包含其中一條半邊edge 的信息（圖1）。

圖1 半邊數(shù)據(jù)結(jié)構(gòu)示意圖

為方便A-star 算法在半邊數(shù)據(jù)結(jié)構(gòu)上的應(yīng)用，在傳統(tǒng)半邊結(jié)構(gòu)HalfEdge 中添加了邊的中點(diǎn)坐標(biāo)信息center，從而方便路徑規(guī)劃過程中相鄰半邊的搜索以及最終結(jié)果路徑頂點(diǎn)的確定，有利于后續(xù)A-star 算法基于鄰接邊中點(diǎn)的路徑選擇方式的實(shí)現(xiàn)（圖2）。

圖2 含中點(diǎn)信息的半邊數(shù)據(jù)結(jié)構(gòu)三角網(wǎng)格

1.2 HEAS 算法原理

啟發(fā)式的A-star 算法在路徑規(guī)劃問題中根據(jù)終點(diǎn)已有的啟發(fā)信息來引導(dǎo)搜索，通過計(jì)算每一步的代價(jià)來決定下一步的去向，代價(jià)的計(jì)算模型如下所示。

記當(dāng)前節(jié)點(diǎn)自起點(diǎn)累計(jì)已花費(fèi)的代價(jià)為G（n），當(dāng)前節(jié)點(diǎn)到達(dá)目標(biāo)點(diǎn)的預(yù)估代價(jià)為H（n），則當(dāng)前綜合總代價(jià)F（n）表示為

記2 個(gè)相鄰路徑節(jié)點(diǎn)V1（x1，y1）和V2（x2，y2）間的距離計(jì)算利用歐氏距離公式

記當(dāng)前搜索節(jié)點(diǎn)為Vn，其前驅(qū)節(jié)點(diǎn)為Vn-1，目標(biāo)點(diǎn)為Vg，當(dāng)前搜索節(jié)點(diǎn)與目標(biāo)點(diǎn)的相連線段經(jīng)過障礙的合計(jì)距離為di，其間經(jīng)過的障礙半邊數(shù)為n。傳統(tǒng)預(yù)估代價(jià)H（n）的計(jì)算利用歐式距離，下面通過考慮當(dāng)前節(jié)點(diǎn)與終點(diǎn)連線經(jīng)過的障礙因素對(duì)傳統(tǒng)預(yù)估代價(jià)進(jìn)行優(yōu)化，得到新的預(yù)估代價(jià)計(jì)算模型，當(dāng)前已花費(fèi)代價(jià)G（n）及優(yōu)化的預(yù)估代價(jià)H（n）分別表示為下列式（3）和式（4）

下面以具有162 個(gè)單位三角網(wǎng)格的地圖為基礎(chǔ)，在均勻分布的地圖障礙面積占整個(gè)地圖的不同比例下，分別對(duì)利用優(yōu)化預(yù)估函數(shù)的HEAS 算法和傳統(tǒng)預(yù)估函數(shù)運(yùn)用在A-star 算法中搜索的三角網(wǎng)格數(shù)進(jìn)行對(duì)比測(cè)試，如圖3 所示。

圖3 優(yōu)化的預(yù)估函數(shù)與傳統(tǒng)預(yù)估函數(shù)的搜索網(wǎng)格數(shù)對(duì)比

通過測(cè)試，可見利用優(yōu)化后的預(yù)估函數(shù)，算法搜索的網(wǎng)格數(shù)總是小于或等于利用傳統(tǒng)預(yù)估函數(shù)的搜索網(wǎng)格數(shù)，且與障礙面積所占地圖比例相關(guān)，隨著障礙面積平均占比的增大，優(yōu)化的搜索網(wǎng)格數(shù)也隨之增大。當(dāng)起點(diǎn)到目標(biāo)點(diǎn)的路徑上不存在障礙時(shí)，2 種預(yù)估函數(shù)的搜索個(gè)數(shù)相等，而當(dāng)起點(diǎn)到目標(biāo)點(diǎn)的路徑上存在障礙時(shí)，優(yōu)化的預(yù)估函數(shù)其搜索網(wǎng)格數(shù)總是更少。

HEAS 算法應(yīng)用于多邊形網(wǎng)格地圖在搜索路徑?jīng)Q定下一步節(jié)點(diǎn)時(shí)，對(duì)于路徑節(jié)點(diǎn)的選擇是沿多邊形的鄰接邊的中點(diǎn)，在三角網(wǎng)格基礎(chǔ)上即2 個(gè)三角面之間公共邊的中點(diǎn)（圖4）。

圖4 基于鄰接邊中點(diǎn)的路徑選擇方式示意圖

算法每一步搜索將當(dāng)前搜索半邊所在面的其他2條半邊納入搜索范圍，同時(shí)利用當(dāng)前搜索半邊的中點(diǎn)計(jì)算當(dāng)前累計(jì)的已花費(fèi)代價(jià)G（n）和預(yù)估代價(jià)H（n），并始終選擇兩者之和最小即代價(jià)最小的半邊繼續(xù)搜索，當(dāng)遇障礙無法繼續(xù)搜索時(shí)則從搜索范圍內(nèi)的其他半邊繼續(xù)搜索，如此算法則始終體現(xiàn)出整體逼近終點(diǎn)方向搜索的狀態(tài)。

2 算法的實(shí)現(xiàn)

2.1 改進(jìn)半邊數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)

實(shí)現(xiàn)路徑規(guī)劃算法前，首先需要利用含半邊中點(diǎn)信息的半邊數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)三角網(wǎng)格地圖的構(gòu)造。三角網(wǎng)格地圖包含頂點(diǎn)集、半邊集和面集，需依次構(gòu)造單位三角面的頂點(diǎn)、半邊以及面結(jié)構(gòu)，并通過對(duì)半邊結(jié)構(gòu)HalfEdge 添加中點(diǎn)坐標(biāo)的改進(jìn)，在構(gòu)造單位半邊結(jié)構(gòu)時(shí)，利用半邊兩端頂點(diǎn)坐標(biāo)計(jì)算出半邊中點(diǎn)坐標(biāo)并進(jìn)行存儲(chǔ)，可方便結(jié)果路徑的節(jié)點(diǎn)獲取。

三角網(wǎng)格地圖構(gòu)造過程描述如下：

2.2 HEAS 算法實(shí)現(xiàn)三角網(wǎng)格地圖最優(yōu)路徑的搜尋

算法執(zhí)行的輔助結(jié)構(gòu)包含開放隊(duì)列open，路徑前驅(qū)節(jié)點(diǎn)容器path 以及當(dāng)前累計(jì)代價(jià)容器cost。其中開放隊(duì)列open 為基于小頂堆的優(yōu)先隊(duì)列，用其存儲(chǔ)等待搜索的半邊節(jié)點(diǎn)及其優(yōu)先值，其中優(yōu)先值按當(dāng)前累計(jì)已花費(fèi)代價(jià)G（n）和預(yù)估代價(jià)H（n）之和計(jì)算，由此確保隊(duì)頭元素總是目前綜合代價(jià)最小的預(yù)搜索半邊節(jié)點(diǎn)。路徑前驅(qū)節(jié)點(diǎn)容器path 和當(dāng)前代價(jià)容器cost 都是鍵值對(duì)map 容器，path 用于存儲(chǔ)已搜索半邊節(jié)點(diǎn)信息及其搜索過程的前驅(qū)半邊節(jié)點(diǎn)信息，而cost 則存儲(chǔ)各半邊節(jié)點(diǎn)及其自起始點(diǎn)累計(jì)已走的距離。

結(jié)合上述輔助結(jié)構(gòu)，將利用優(yōu)化預(yù)估代價(jià)計(jì)算模型的A-star 算法應(yīng)用于含鄰接邊中點(diǎn)信息的半邊數(shù)據(jù)結(jié)構(gòu)所構(gòu)造的三角網(wǎng)格地圖的HEAS 算法描述如下：

算法最終所得的結(jié)果路徑則存儲(chǔ)在path 容器的記錄中，可從目標(biāo)節(jié)點(diǎn)逐層遞推地找到各節(jié)點(diǎn)的搜索路徑前驅(qū)節(jié)點(diǎn)，從而通過目標(biāo)點(diǎn)倒推到起始點(diǎn)找到結(jié)果目標(biāo)路徑。

3 實(shí)驗(yàn)測(cè)試與分析

測(cè)試環(huán)境所使用的開發(fā)工具包括VisualStudio 2019 和OpenGL 應(yīng)用工具包v3.7 版本，測(cè)試用例為半邊數(shù)據(jù)結(jié)構(gòu)構(gòu)建的三角網(wǎng)格地圖，其中包括障礙區(qū)域和不可達(dá)三角區(qū)域，自定義起點(diǎn)和終點(diǎn)并繪制最短路徑，以下在基于半邊中點(diǎn)的路徑節(jié)點(diǎn)選擇方式下的可達(dá)路徑進(jìn)行測(cè)試，其中起點(diǎn)和終點(diǎn)的連線為算法所得結(jié)果路徑，深色網(wǎng)格表示已搜索過的三角面（圖5）。

圖5 三角網(wǎng)格測(cè)試地圖示意以及最短路徑測(cè)試結(jié)果

在整體三角面大小較為均勻的地圖基礎(chǔ)上，以鄰接邊中點(diǎn)為路徑節(jié)點(diǎn)的路徑選擇方式整體較優(yōu)，可進(jìn)一步進(jìn)行三角面細(xì)分[6]及利用平滑路徑算法來優(yōu)化冗余路徑[7-8]。

在3 個(gè)具有不同障礙分布的三角網(wǎng)格地圖中基于鄰接邊中點(diǎn)的路徑節(jié)點(diǎn)選擇方式，分別對(duì)Dijkstra 算法、貪心的最佳優(yōu)先搜索算法（GBFS）以及本文提出的HEAS 算法在搜索網(wǎng)格數(shù)量和搜索時(shí)間2 個(gè)方面的運(yùn)行情況進(jìn)行對(duì)比，圖6 為測(cè)試結(jié)果。

圖6 各路徑規(guī)劃算法對(duì)比測(cè)試結(jié)果

Dijkstra 算法在尋路過程中是以距離起點(diǎn)最近為導(dǎo)向，而GBFS 算法在尋路過程中則是以距離終點(diǎn)最近為導(dǎo)向，但這種貪心思想所得的最終結(jié)果未必是最短的路徑。HEAS 算法則是在兩者中取得平衡，在尋路過程中以距起點(diǎn)距離和距終點(diǎn)距離綜合最近為導(dǎo)向，同時(shí)考慮兩者代價(jià)以做出權(quán)衡，所得到的結(jié)果路徑為最短路徑。

可見，當(dāng)?shù)貓D中有障礙物時(shí)，Dijkstra 算法的結(jié)果路徑總是最優(yōu)，但在時(shí)間效率上欠佳；最佳優(yōu)先貪心算法在時(shí)間效率上最優(yōu)，但其結(jié)果路徑并不總是理想的；而采用居中策略的HEAS 算法所得到尋路時(shí)間效率和結(jié)果路徑則是綜合最優(yōu)的方案。

4 結(jié)束語

本文利用含鄰接邊中點(diǎn)信息的半邊數(shù)據(jù)結(jié)構(gòu)表達(dá)地圖的三角網(wǎng)格信息，結(jié)合改進(jìn)的預(yù)估代價(jià)計(jì)算模型的A-star 算法以及沿三角形的鄰接邊中點(diǎn)的路徑表達(dá)方式，證明了HEAS 算法高效適用于三角形網(wǎng)格的路徑規(guī)劃問題，可以得到綜合最優(yōu)的路徑方案，同時(shí)三角形網(wǎng)格可從二維空間拓展至三維空間，在解決3D游戲場(chǎng)景以及實(shí)際三維地形圖中的諸多尋路導(dǎo)航問題中更具優(yōu)勢(shì)。