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

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

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

【部分圖文】：

地圖Delaunay三角剖分

髡??直至滿足二叉堆的堆序性。利用二叉堆存儲(chǔ)Open列表可快速插入和刪除列表中鄰居結(jié)點(diǎn)，從而提高A*算法的搜索效率。2.3基于目標(biāo)范圍界限的優(yōu)化目標(biāo)范圍界限是一種在預(yù)處理地圖信息時(shí)快速劃分目標(biāo)點(diǎn)的方法，核心思想是預(yù)先計(jì)算一個(gè)邊界框，其中包含所有通過(guò)探索其邊達(dá)到目標(biāo)最優(yōu)路徑的結(jié)點(diǎn)。在進(jìn)行地圖預(yù)處理時(shí)，對(duì)應(yīng)邊界框的參數(shù)也相應(yīng)被存儲(chǔ)。當(dāng)運(yùn)行尋路算法時(shí)，可以實(shí)時(shí)讀取存儲(chǔ)邊界框的參數(shù)，從而只需要對(duì)目標(biāo)結(jié)點(diǎn)所處目標(biāo)范圍邊界框內(nèi)的結(jié)點(diǎn)進(jìn)行考察，從而減少所搜索的結(jié)點(diǎn)數(shù)量，提高搜索效率。圖3多邊形網(wǎng)格地圖目標(biāo)范圍界限計(jì)算目標(biāo)范圍界限的方法為：（1）定義選取起始點(diǎn)鄰接方向的鄰居結(jié)點(diǎn)，如圖3（a）所示，起始結(jié)點(diǎn)分別有A、B、C等3個(gè)鄰接方向。（2）利用Dijkstra算法遍歷鄰接方向所有結(jié)點(diǎn)，記錄從起始點(diǎn)出發(fā)進(jìn)行該方向探索的最優(yōu)路徑點(diǎn)，并作標(biāo)記。如圖3（a）中標(biāo)記C的三角網(wǎng)格結(jié)點(diǎn)，探索下方網(wǎng)格，只有通過(guò)標(biāo)記C的網(wǎng)格才是該方向最優(yōu)路徑的網(wǎng)格結(jié)點(diǎn)。（3）當(dāng)計(jì)算完所有網(wǎng)格結(jié)點(diǎn)時(shí)，劃分生成目標(biāo)結(jié)點(diǎn)的范圍界限，并且存儲(chǔ)在相應(yīng)文件中。（4）在運(yùn)用尋路算法之前，讀取文件中的目標(biāo)界限參數(shù)，尋路算法只需對(duì)目標(biāo)點(diǎn)所在目標(biāo)范圍界限中的結(jié)點(diǎn)進(jìn)行考察。3優(yōu)化A*算法實(shí)現(xiàn)優(yōu)化后的A*算法，同樣適用于多邊形導(dǎo)航網(wǎng)格。方格地圖網(wǎng)格都是規(guī)則的正方形網(wǎng)格，因此在計(jì)算網(wǎng)格距離時(shí)，只需要計(jì)算網(wǎng)格中心點(diǎn)之間的距離。與方格網(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）的計(jì)算不能統(tǒng)一。因此，為了統(tǒng)一三角網(wǎng)格自身耗費(fèi)以及提高估價(jià)函數(shù)的準(zhǔn)確性，需要對(duì)G（n）值和h（n）的計(jì)算方法加以改進(jìn)。改進(jìn)策略：G（n）為當(dāng)前三角網(wǎng)格至下一個(gè)網(wǎng)格代價(jià)總和，H（n）為三角形中心到目標(biāo)三角中心的距離。如圖4，三角網(wǎng)格自身代價(jià)為穿入邊AB中點(diǎn)至穿出邊AC中點(diǎn)的距離。g(n)=12(x3-x22)2+(y3-y22)2（4）改進(jìn)后的A*算法如下：輸入：ΔS/*起始點(diǎn)，ΔE/*終點(diǎn)輸出：PathΠ（ΔS，ΔE）（1）CreateOpenlist，Closelist；（2）WithinBoundingBox（Δ（s），goal））；//搜索在目標(biāo)點(diǎn)所在目標(biāo)范圍界限內(nèi)的鄰居結(jié)點(diǎn)（3）foreachΔ（n）inneighbor（Δs）｛//遍歷在目標(biāo)范圍內(nèi)，起始點(diǎn)的所有可到達(dá)的鄰接三角網(wǎng)格（4）AddΔ（n）inOpenlist，AddΔsinCloseList；（5）While（Openlist！=null）｛（6）MinHeuristic（Δ（m））inOpenlist；//從Open列表中取出估值F最小的結(jié)點(diǎn)Δ（m）（7）if（Δ（m）==Δ（e）｛Break；｝（8）foreach（Δ（m）的每個(gè)子結(jié)點(diǎn)Δ（X））｛；（9）if（Δ（X）inOpenList）｛（10）if（MinHeuristic（Δ（X））inOpenlist==true）（11）SetΔ（m）asParentNode；Update｝//設(shè)Δ（m）為Δ（X）的父結(jié)點(diǎn)（12）else

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

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



本文編號(hào)：3110667