針對A*尋路算法在大型地圖中搜索路徑結(jié)點過多、搜索效率過低的問題,提出一種基于多邊形導(dǎo)航網(wǎng)格的改進(jìn)A*算法。首先利用建模工具對地圖中障礙物進(jìn)行剔除,生成可行走域的多邊形導(dǎo)航網(wǎng)格;其次對多邊形網(wǎng)格進(jìn)行Delaunay三角剖分,形成三角導(dǎo)航網(wǎng)格,利用二叉堆對A*算法所使用的數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化,采用目標(biāo)范圍界限方法對導(dǎo)航網(wǎng)格進(jìn)行預(yù)處理,并將處理A*算法的啟發(fā)函數(shù)進(jìn)行改進(jìn)以適用于多邊形導(dǎo)航網(wǎng)格,對多邊形導(dǎo)航網(wǎng)格生成路徑利用漏斗算法進(jìn)行路徑平滑處理,生成實際最優(yōu)路徑;最后利用Unity3d游戲引擎搭建地圖尋路實驗平臺,對比分析算法的性能差距。實驗證明,基于多邊形導(dǎo)航網(wǎng)格改進(jìn)A*算法在大型地圖中的搜索效率明顯高于基于傳統(tǒng)方格地圖A*算法。 

【文章來源】：軟件導(dǎo)刊. 2019,18(01)

【文章頁數(shù)】：5 頁

【部分圖文】：

地圖Delaunay三角剖分

髡??直至滿足二叉堆的堆序性。利用二叉堆存儲Open列表可快速插入和刪除列表中鄰居結(jié)點，從而提高A*算法的搜索效率。2.3基于目標(biāo)范圍界限的優(yōu)化目標(biāo)范圍界限是一種在預(yù)處理地圖信息時快速劃分目標(biāo)點的方法，核心思想是預(yù)先計算一個邊界框，其中包含所有通過探索其邊達(dá)到目標(biāo)最優(yōu)路徑的結(jié)點。在進(jìn)行地圖預(yù)處理時，對應(yīng)邊界框的參數(shù)也相應(yīng)被存儲。當(dāng)運行尋路算法時，可以實時讀取存儲邊界框的參數(shù)，從而只需要對目標(biāo)結(jié)點所處目標(biāo)范圍邊界框內(nèi)的結(jié)點進(jìn)行考察，從而減少所搜索的結(jié)點數(shù)量，提高搜索效率。圖3多邊形網(wǎng)格地圖目標(biāo)范圍界限計算目標(biāo)范圍界限的方法為：（1）定義選取起始點鄰接方向的鄰居結(jié)點，如圖3（a）所示，起始結(jié)點分別有A、B、C等3個鄰接方向。（2）利用Dijkstra算法遍歷鄰接方向所有結(jié)點，記錄從起始點出發(fā)進(jìn)行該方向探索的最優(yōu)路徑點，并作標(biāo)記。如圖3（a）中標(biāo)記C的三角網(wǎng)格結(jié)點，探索下方網(wǎng)格，只有通過標(biāo)記C的網(wǎng)格才是該方向最優(yōu)路徑的網(wǎng)格結(jié)點。（3）當(dāng)計算完所有網(wǎng)格結(jié)點時，劃分生成目標(biāo)結(jié)點的范圍界限，并且存儲在相應(yīng)文件中。（4）在運用尋路算法之前，讀取文件中的目標(biāo)界限參數(shù)，尋路算法只需對目標(biāo)點所在目標(biāo)范圍界限中的結(jié)點進(jìn)行考察。3優(yōu)化A*算法實現(xiàn)優(yōu)化后的A*算法，同樣適用于多邊形導(dǎo)航網(wǎng)格。方格地圖網(wǎng)格都是規(guī)則的正方形網(wǎng)格，因此在計算網(wǎng)格距離時，只需要計算網(wǎng)格中心點之間的距離。與方格網(wǎng)格地圖不同，經(jīng)Delaunay剖分所形成的三角網(wǎng)絡(luò)導(dǎo)航網(wǎng)格具有不朱昌龍，劉黎志：基于多邊形導(dǎo)航網(wǎng)格地圖的改進(jìn)A*算法··19

軟件導(dǎo)刊2019年規(guī)則性，導(dǎo)致G（n）值和h（n）的計算不能統(tǒng)一。因此，為了統(tǒng)一三角網(wǎng)格自身耗費以及提高估價函數(shù)的準(zhǔn)確性，需要對G（n）值和h（n）的計算方法加以改進(jìn)。改進(jìn)策略：G（n）為當(dāng)前三角網(wǎng)格至下一個網(wǎng)格代價總和，H（n）為三角形中心到目標(biāo)三角中心的距離。如圖4，三角網(wǎng)格自身代價為穿入邊AB中點至穿出邊AC中點的距離。g(n)=12(x3-x22)2+(y3-y22)2（4）改進(jìn)后的A*算法如下：輸入：ΔS/*起始點，ΔE/*終點輸出：PathΠ（ΔS，ΔE）（1）CreateOpenlist，Closelist；（2）WithinBoundingBox（Δ（s），goal））；//搜索在目標(biāo)點所在目標(biāo)范圍界限內(nèi)的鄰居結(jié)點（3）foreachΔ（n）inneighbor（Δs）｛//遍歷在目標(biāo)范圍內(nèi)，起始點的所有可到達(dá)的鄰接三角網(wǎng)格（4）AddΔ（n）inOpenlist，AddΔsinCloseList；（5）While（Openlist！=null）｛（6）MinHeuristic（Δ（m））inOpenlist；//從Open列表中取出估值F最小的結(jié)點Δ（m）（7）if（Δ（m）==Δ（e）｛Break；｝（8）foreach（Δ（m）的每個子結(jié)點Δ（X））｛；（9）if（Δ（X）inOpenList）｛（10）if（MinHeuristic（Δ（X））inOpenlist==true）（11）SetΔ（m）asParentNode；Update｝//設(shè)Δ（m）為Δ（X）的父結(jié)點（12）else

【參考文獻(xiàn)】：
期刊論文
[1]基于三角形細(xì)分的三角網(wǎng)格模型表面體素化算法[J]. 趙芳壘,敬石開,李向前,邢昊,劉晨燕,宋國華.  計算機集成制造系統(tǒng). 2017(11)
[2]各向同性三角形重新網(wǎng)格化方法綜述[J]. 嚴(yán)冬明,胡楷模,郭建偉,王逸群,張義寬,張曉鵬.  計算機科學(xué). 2017(08)
[3]Dijkstra最短路徑算法的堆優(yōu)化實驗研究[J]. 張翰林,關(guān)愛薇,傅珂,孫廷凱.  軟件. 2017(05)
[4]引入導(dǎo)航網(wǎng)格的室內(nèi)路徑規(guī)劃算法[J]. 林巍凌.  測繪科學(xué). 2016(02)
[5]利用堆排序優(yōu)化路徑搜索效率的分析[J]. 孫玉昕,章瑾.  武漢工程大學(xué)學(xué)報. 2013(06)
[6]基于DAF算法的地圖尋徑研究[J]. 陳娜,黃明和,劉清華.  科學(xué)技術(shù)與工程. 2010(30)
[7]基于地圖分割與以矢量信息描述地圖的A*尋路算法[J]. 李立,唐寧九,林濤.  四川大學(xué)學(xué)報(自然科學(xué)版). 2010(04)
[8]一種基于導(dǎo)航網(wǎng)格的路徑搜索技術(shù)[J]. 王天順,張莉.  電腦知識與技術(shù). 2010(12)
[9]游戲開發(fā)中智能路徑搜索算法的研究[J]. 何國輝,陳家琪.  計算機工程與設(shè)計. 2006(13)
[10]平面多邊形域的快速約束Delaunay三角化[J]. 曾薇,孟祥旭,楊承磊,楊義軍.  計算機輔助設(shè)計與圖形學(xué)學(xué)報. 2005(09)

碩士論文
[1]基于綜合導(dǎo)航網(wǎng)格的智慧旅游動態(tài)尋徑方法[D]. 王燁萍.西南交通大學(xué) 2017
[2]游戲中的智能路徑搜索算法及其應(yīng)用[D]. 李井頌.昆明理工大學(xué) 2017
[3]游戲場景中分層尋路算法及地圖復(fù)雜性度量研究[D]. 周振華.河北大學(xué) 2014
[4]游戲地圖尋路及其真實性研究[D]. 韓瑋.西南大學(xué) 2013
[5]人工智能尋路算法在電子游戲中的研究和應(yīng)用[D]. 詹海波.華中科技大學(xué) 2006
[6]基于A*算法的地圖尋徑的研究[D]. 張前哨.武漢科技大學(xué) 2005



本文編號：3110667