基于半邊數據結構的A-star 路徑規劃算法及實現

古天馳，李曉東，蘇龍生

（佛山科學技術學院 計算機系，廣東 佛山 528225）

路徑規劃在游戲AI 自動尋路、航路規劃、人工智能避障以及駕車地圖導航等現代計算機科學領域中都有著廣泛的應用[1-2]，其主要實現障礙躲避以及最佳路徑的選擇。A-star 算法則是一種能夠達到最優解且常運用于最優路徑規劃的算法。在路徑規劃方面，A-star算法通常基于方格地圖實現，而方格地圖的空間描述局限性較大導致路徑選擇自由度受限。

傳統圖的鄰接表存儲結構復雜而使用不便，導致搜索鄰接點、線和面時效率較低。而半邊數據結構則是一種基于多邊形網格的空間數據結構，常用于三維地圖表達，具有較強的拓撲性和靈活性，因此其在計算機圖形學、三維建模等領域有著廣泛的應用[3-4]。本文提出含鄰接邊中點信息的半邊數據結構，并與利用優化預估代價計算模型的A-star 算法結合，運用于三角網格3D 地圖，可突破方格地圖的空間局限，有利于提高網格地圖的空間利用率，同時提高路徑搜索效率。

1 算法原理

1.1 半邊數據結構描述

半邊數據結構是可用于網格中鄰接元素查詢的一種數據結構，相較于鄰接表方式，半邊數據結構更有利于點、線及面的拓撲搜索訪問，同時半邊數據結構對于網格的表達要求是流形結構[5]，其中三角形是簡單的流形結構，故下面是基于三角網格的問題研究。一個網格地圖包含點集、邊集和面集，其中三角面的每條邊為有向邊，且逆時針構成環。頂點結構HE_Vertex 包含坐標及其出半邊edge 的信息；半邊結構HalfEdge 包含目標頂點target、相鄰半邊pair、下一條半邊next 以及所屬面face 的信息；面結構HE_Face 包含其中一條半邊edge 的信息（圖1）。

圖1 半邊數據結構示意圖

為方便A-star 算法在半邊數據結構上的應用，在傳統半邊結構HalfEdge 中添加了邊的中點坐標信息center，從而方便路徑規劃過程中相鄰半邊的搜索以及最終結果路徑頂點的確定，有利于后續A-star 算法基于鄰接邊中點的路徑選擇方式的實現（圖2）。

圖2 含中點信息的半邊數據結構三角網格

1.2 HEAS 算法原理

啟發式的A-star 算法在路徑規劃問題中根據終點已有的啟發信息來引導搜索，通過計算每一步的代價來決定下一步的去向，代價的計算模型如下所示。

記當前節點自起點累計已花費的代價為G（n），當前節點到達目標點的預估代價為H（n），則當前綜合總代價F（n）表示為

記2 個相鄰路徑節點V1（x1，y1）和V2（x2，y2）間的距離計算利用歐氏距離公式

記當前搜索節點為Vn，其前驅節點為Vn-1，目標點為Vg，當前搜索節點與目標點的相連線段經過障礙的合計距離為di，其間經過的障礙半邊數為n。傳統預估代價H（n）的計算利用歐式距離，下面通過考慮當前節點與終點連線經過的障礙因素對傳統預估代價進行優化，得到新的預估代價計算模型，當前已花費代價G（n）及優化的預估代價H（n）分別表示為下列式（3）和式（4）

下面以具有162 個單位三角網格的地圖為基礎，在均勻分布的地圖障礙面積占整個地圖的不同比例下，分別對利用優化預估函數的HEAS 算法和傳統預估函數運用在A-star 算法中搜索的三角網格數進行對比測試，如圖3 所示。

圖3 優化的預估函數與傳統預估函數的搜索網格數對比

通過測試，可見利用優化后的預估函數，算法搜索的網格數總是小于或等于利用傳統預估函數的搜索網格數，且與障礙面積所占地圖比例相關，隨著障礙面積平均占比的增大，優化的搜索網格數也隨之增大。當起點到目標點的路徑上不存在障礙時，2 種預估函數的搜索個數相等，而當起點到目標點的路徑上存在障礙時，優化的預估函數其搜索網格數總是更少。

HEAS 算法應用于多邊形網格地圖在搜索路徑決定下一步節點時，對于路徑節點的選擇是沿多邊形的鄰接邊的中點，在三角網格基礎上即2 個三角面之間公共邊的中點（圖4）。

圖4 基于鄰接邊中點的路徑選擇方式示意圖

算法每一步搜索將當前搜索半邊所在面的其他2條半邊納入搜索范圍，同時利用當前搜索半邊的中點計算當前累計的已花費代價G（n）和預估代價H（n），并始終選擇兩者之和最小即代價最小的半邊繼續搜索，當遇障礙無法繼續搜索時則從搜索范圍內的其他半邊繼續搜索，如此算法則始終體現出整體逼近終點方向搜索的狀態。

2 算法的實現

2.1 改進半邊數據結構的實現

實現路徑規劃算法前，首先需要利用含半邊中點信息的半邊數據結構實現三角網格地圖的構造。三角網格地圖包含頂點集、半邊集和面集，需依次構造單位三角面的頂點、半邊以及面結構，并通過對半邊結構HalfEdge 添加中點坐標的改進，在構造單位半邊結構時，利用半邊兩端頂點坐標計算出半邊中點坐標并進行存儲，可方便結果路徑的節點獲取。

三角網格地圖構造過程描述如下：

2.2 HEAS 算法實現三角網格地圖最優路徑的搜尋

算法執行的輔助結構包含開放隊列open，路徑前驅節點容器path 以及當前累計代價容器cost。其中開放隊列open 為基于小頂堆的優先隊列，用其存儲等待搜索的半邊節點及其優先值，其中優先值按當前累計已花費代價G（n）和預估代價H（n）之和計算，由此確保隊頭元素總是目前綜合代價最小的預搜索半邊節點。路徑前驅節點容器path 和當前代價容器cost 都是鍵值對map 容器，path 用于存儲已搜索半邊節點信息及其搜索過程的前驅半邊節點信息，而cost 則存儲各半邊節點及其自起始點累計已走的距離。

結合上述輔助結構，將利用優化預估代價計算模型的A-star 算法應用于含鄰接邊中點信息的半邊數據結構所構造的三角網格地圖的HEAS 算法描述如下：

算法最終所得的結果路徑則存儲在path 容器的記錄中，可從目標節點逐層遞推地找到各節點的搜索路徑前驅節點，從而通過目標點倒推到起始點找到結果目標路徑。

3 實驗測試與分析

測試環境所使用的開發工具包括VisualStudio 2019 和OpenGL 應用工具包v3.7 版本，測試用例為半邊數據結構構建的三角網格地圖，其中包括障礙區域和不可達三角區域，自定義起點和終點并繪制最短路徑，以下在基于半邊中點的路徑節點選擇方式下的可達路徑進行測試，其中起點和終點的連線為算法所得結果路徑，深色網格表示已搜索過的三角面（圖5）。

圖5 三角網格測試地圖示意以及最短路徑測試結果

在整體三角面大小較為均勻的地圖基礎上，以鄰接邊中點為路徑節點的路徑選擇方式整體較優，可進一步進行三角面細分[6]及利用平滑路徑算法來優化冗余路徑[7-8]。

在3 個具有不同障礙分布的三角網格地圖中基于鄰接邊中點的路徑節點選擇方式，分別對Dijkstra 算法、貪心的最佳優先搜索算法（GBFS）以及本文提出的HEAS 算法在搜索網格數量和搜索時間2 個方面的運行情況進行對比，圖6 為測試結果。

圖6 各路徑規劃算法對比測試結果

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

可見，當地圖中有障礙物時，Dijkstra 算法的結果路徑總是最優，但在時間效率上欠佳；最佳優先貪心算法在時間效率上最優，但其結果路徑并不總是理想的；而采用居中策略的HEAS 算法所得到尋路時間效率和結果路徑則是綜合最優的方案。

4 結束語

本文利用含鄰接邊中點信息的半邊數據結構表達地圖的三角網格信息，結合改進的預估代價計算模型的A-star 算法以及沿三角形的鄰接邊中點的路徑表達方式，證明了HEAS 算法高效適用于三角形網格的路徑規劃問題，可以得到綜合最優的路徑方案，同時三角形網格可從二維空間拓展至三維空間，在解決3D游戲場景以及實際三維地形圖中的諸多尋路導航問題中更具優勢。