朱昌龍 劉黎志

摘 要：針對(duì)A*尋路算法在大型地圖中搜索路徑結(jié)點(diǎ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*算法。

關(guān)鍵詞：A*算法;Delaunay三角;多邊形導(dǎo)航網(wǎng)格;平滑路徑;漏斗算法

DOI：10. 11907/rjdk. 181825

中圖分類號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1672-7800（2019）001-0017-05

Abstract： Regarding the A-Star algorithm shortcomings of excessive searching nodes of path and inefficiency of searching in large tradition grid map，this paper propose an improved A-Star algorithm based on polygon navigation mesh map. Firstly， the obstacles are eliminated by using the modeling tool in the map to generate a polygonal navigation mesh for the walking domain. Secondly， a triangular navigation mesh is generating by using Delaunay triangulation on polygonal meshes， the data structure of A-Star algorithm is optimized by a binary heap，and the navigation mesh is precompted by goal bounding method and then the heuristic function of the A-Star algorithm is modified to apply to the polygonal navigation mesh， and then the path generated by the polygon navigation mesh is smoothed by funnel algorithm to generate the actual optimal path. Finally， building map-finding path comparative experimental platform is buitt by using the Unity3d game engine to compare analysis the performance gap of the algorithm. Experiments show that the search efficiency of improved A-Star algorithm based on polygon navigation mesh is significantly higher than that based on the traditional grid map A-Star algorithm in large maps.

Key Words： A-Star;Delaunay triangulation; polygon navigation mesh; smoothing path; funnel algorithm

0 引言

路徑搜索一直是人工智能領(lǐng)域研究的熱點(diǎn)，高效性和真實(shí)性一直是判斷尋路算法性能的指標(biāo)[1-3]。在人工智能路徑搜索方面，運(yùn)用最多的是A*算法[4]。相關(guān)領(lǐng)域研究者在A*算法基礎(chǔ)上，進(jìn)行了尋路算法的優(yōu)化和改進(jìn)，提高了尋路算法的性能。例如Daniel Harabor[5]提出JPS算法，利用跳點(diǎn)搜索的方法解決了傳統(tǒng)等價(jià)方格地圖中存在的對(duì)稱性搜索結(jié)點(diǎn)問題，從而提高了搜索效率。但是目前大多數(shù)A*算法優(yōu)化都是基于具有對(duì)稱性的方格地圖進(jìn)行的，方格地圖在大型地圖中尋路網(wǎng)格結(jié)點(diǎn)較多，占用系統(tǒng)資源過多，從而導(dǎo)致搜索效率過慢。對(duì)此，本文提出基于多邊形導(dǎo)航網(wǎng)格地圖的改進(jìn)A*算法，在A*算法搜索結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)上采用二叉堆技術(shù)，在地圖預(yù)處理上運(yùn)用一種目標(biāo)范圍界限的方法對(duì)地圖進(jìn)行信息劃分，從而有效提高基于多邊形導(dǎo)航網(wǎng)格A*算法的搜索效率[6-13]。

尋路地圖也可以看作是一組存儲(chǔ)地圖信息的數(shù)據(jù)結(jié)構(gòu)[14-16]。在運(yùn)用尋路算法之前，需要先將地圖進(jìn)行預(yù)處理，地圖劃分方法有方格柵格法和導(dǎo)航網(wǎng)格法。

方格柵格法是將地圖等距離劃分為面積大小相同的網(wǎng)格，根據(jù)障礙物占網(wǎng)格面積的百分比確定是否為障礙物，使用遍歷方法對(duì)地圖中的信息進(jìn)行預(yù)處理。利用方格柵格法預(yù)處理地圖是一種簡單的劃分方法，劃分地圖占用內(nèi)存較小、適用性較高，但運(yùn)用到尋路算法時(shí)，所搜索的鄰居結(jié)點(diǎn)和無用結(jié)點(diǎn)過多，導(dǎo)致搜索效率過低。

導(dǎo)航網(wǎng)格法是建立在多邊形網(wǎng)格地圖基礎(chǔ)上的一種地圖劃分方法[17-18]。利用導(dǎo)航網(wǎng)格法對(duì)地圖進(jìn)行預(yù)處理，需要先利用建模工具對(duì)地圖中的障礙物進(jìn)行剔除，生成多邊形網(wǎng)格模型地圖。利用平面多邊形域快速約束Delaunay三角化的方法，可以對(duì)生成的約束多邊形網(wǎng)格模型進(jìn)行快速三角劃分，生成可運(yùn)用于尋路算法的導(dǎo)航網(wǎng)格地圖[19-21]。因?yàn)閷?dǎo)航網(wǎng)格預(yù)先剔除了障礙物信息，在大面積空白區(qū)域的網(wǎng)格劃分上，導(dǎo)航網(wǎng)格劃分少，所以在路徑搜索時(shí)，不會(huì)考慮障礙物信息，從而搜索的鄰居結(jié)點(diǎn)也大幅減少，提高搜索效率。

1 多邊形導(dǎo)航網(wǎng)格地圖三角剖分

多邊形導(dǎo)航網(wǎng)格是一組多邊形集合，對(duì)地圖進(jìn)行可行走域和不可行走域劃分。利用建模工具對(duì)地圖進(jìn)行處理，剔除障礙物，生成可行走域的多邊形網(wǎng)格地圖。多邊形網(wǎng)格較方格網(wǎng)格地圖更容易劃分不規(guī)則的障礙物，可以有效減少搜索網(wǎng)格的數(shù)量，從而提高搜索效率。尋路算法運(yùn)用于多邊形導(dǎo)航網(wǎng)格之前，還需對(duì)多邊形網(wǎng)格進(jìn)行三角剖分。

如圖1，灰色多邊形為障礙物，首先需要將障礙物以及邊界的邊定義為約束邊，如圖1（a）中實(shí)心線條，完成三角剖分后添加的邊稱為無約束邊，如圖1（b）中的虛線條，由此形成的三角網(wǎng)格即為尋路網(wǎng)格。在尋路過程中，可以穿越無約束的邊界，但不能穿越受約束的邊界。Delaunay三角網(wǎng)具有最大化最小角特性，即Delaunay三角剖分形成三角形的最小角是最大的，因此三角網(wǎng)格是具有規(guī)則化的三角網(wǎng);另一個(gè)是空?qǐng)A特性，即在Delaunay三角網(wǎng)中任一三角形的外接圓內(nèi)不會(huì)有其它點(diǎn)存在。這兩大特性可以有效避免出現(xiàn)“長條”細(xì)長型的三角網(wǎng)格，生成的三角網(wǎng)格趨近于等邊三角形，因此搜索路徑不會(huì)重復(fù)穿越三角網(wǎng)格，保證了三角劃分的唯一性，方便網(wǎng)格管理。Delaunay三角劃分有很多種方法，例如Bowyer-Watson算法、翻邊算法等。在制作多邊形導(dǎo)航網(wǎng)格時(shí)，已確定受約束邊，因此本文在導(dǎo)航網(wǎng)格三角剖分算法上運(yùn)用了一種快速約束Delaunay三角形剖分的算法。算法如下：

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

基于多邊形導(dǎo)航網(wǎng)格與基于傳統(tǒng)方格網(wǎng)格地圖的A*算法，相同點(diǎn)是都需要遍歷大量結(jié)點(diǎn)。為了提高A*算法的搜索效率，減少搜索的網(wǎng)格結(jié)點(diǎn)數(shù)量，介紹了兩種A*搜索結(jié)點(diǎn)優(yōu)化方法：利用二叉堆對(duì)搜索結(jié)點(diǎn)的Open列表進(jìn)行存儲(chǔ);利用目標(biāo)范圍界限的方法對(duì)目標(biāo)點(diǎn)進(jìn)行分區(qū)域查找。

2.1 A*算法簡介

A*尋路算法是基本的啟發(fā)式路徑搜索算法，它通過啟發(fā)式函數(shù)估計(jì)當(dāng)前結(jié)點(diǎn)下一步能到達(dá)鄰居結(jié)點(diǎn)至目標(biāo)點(diǎn)的成本，以進(jìn)行路徑規(guī)劃。A*算法是根據(jù)加權(quán)圖制定：從圖的特定結(jié)點(diǎn)開始，構(gòu)造從該結(jié)點(diǎn)開始的路徑樹，一次一步地?cái)U(kuò)展路徑，直到其一個(gè)路徑在預(yù)定目標(biāo)結(jié)點(diǎn)處結(jié)束為止。在主循環(huán)的每次迭代中，A*需要確定將其部分路徑中的哪一個(gè)擴(kuò)展為一個(gè)或多個(gè)更長路徑。A*算法核心是啟發(fā)式函數(shù)。

其中，n是當(dāng)前結(jié)點(diǎn)，f（n）表示當(dāng)前結(jié)點(diǎn)n的啟發(fā)函數(shù)，g（n）是從起始結(jié)點(diǎn)到n的路徑的實(shí)際代價(jià)，h（n）是估算當(dāng)前結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)最優(yōu)路徑的估計(jì)成本。h（n）值估算需要引入合適的啟發(fā)式函數(shù)。為了保證用A*找到最短路徑，啟發(fā)式h（x）必須滿足結(jié)點(diǎn)x和y的以下屬性：

D（x，y）為X至Y的實(shí)際距離，意味著啟發(fā)式h（x）的值必須小于或等于實(shí)際距離。啟發(fā)式函數(shù)距離估計(jì)有很多種方法，例如曼哈頓距離、切比雪夫距離、歐幾里得距離等，本文A*算法采用的是二維歐幾里得距離。假設(shè)點(diǎn)p1=（x1，y1）和點(diǎn)p2 =（x2，y2），其歐幾里得距離d（p1，p2）為：

A*算法是使用優(yōu)先級(jí)隊(duì)列執(zhí)行要擴(kuò)展的最小估計(jì)成本結(jié)點(diǎn)的迭代過程。該優(yōu)先級(jí)隊(duì)列被稱為開放列表，在算法的每一步，從隊(duì)列中刪除具有最低f（n）值的結(jié)點(diǎn)，相應(yīng)地更新其鄰居結(jié)點(diǎn)的f值和g值，并將該鄰居結(jié)點(diǎn)添加到Open列表中。 該算法一直持續(xù)到目標(biāo)結(jié)點(diǎn)的f值低于隊(duì)列中的任何結(jié)點(diǎn)（或直到隊(duì)列為空），目標(biāo)f值就是最短路徑的長度，因?yàn)閔（n）在目標(biāo)處可接受的啟發(fā)式函數(shù)中為零。A*算法在每次尋路過程中，需要循環(huán)遍歷大量結(jié)點(diǎn)信息，Open列表需要對(duì)結(jié)點(diǎn)進(jìn)行存儲(chǔ)和判斷，進(jìn)而選取F（n）值最小的結(jié)點(diǎn)。

針對(duì)基于多邊形導(dǎo)航網(wǎng)格的A*尋路算法，提出了兩種優(yōu)化方法，分別是利用二叉堆優(yōu)化Open列表與利用目標(biāo)范圍界限方法快速找到目標(biāo)點(diǎn)所在區(qū)域。利用二叉堆對(duì)結(jié)點(diǎn)進(jìn)行數(shù)據(jù)存儲(chǔ)，可以快速對(duì)Open列表中的鄰居結(jié)點(diǎn)進(jìn)行插入、刪除等操作，從而提高A*算法的搜索效率。利用目標(biāo)范圍界限的方法，可以在預(yù)處理地圖信息時(shí)，對(duì)網(wǎng)格進(jìn)行目標(biāo)范圍劃分，生成并保存目標(biāo)范圍界限。當(dāng)運(yùn)用A*算法時(shí)，讀取目標(biāo)范圍界限，即可快速定位目標(biāo)點(diǎn)所在范圍，從而減少搜索的結(jié)點(diǎn)數(shù)量。

2.2 Open列表數(shù)據(jù)結(jié)構(gòu)優(yōu)化

大型地圖中具有數(shù)量巨大的網(wǎng)格結(jié)點(diǎn)，需要反復(fù)搜索數(shù)據(jù)量龐大的Open列表，從而導(dǎo)致搜索效率過低。為了解決這一問題，引入二叉堆對(duì)結(jié)點(diǎn)進(jìn)行數(shù)據(jù)存儲(chǔ)，對(duì)A*算法進(jìn)行優(yōu)化。

二叉堆是一種特殊的堆，特殊之處在于它是完全按照大小順序存儲(chǔ)的完全二叉樹。其有最小二叉堆和最大二叉堆，最大二叉堆的堆結(jié)點(diǎn)即父結(jié)點(diǎn)是最大的，相反最小二叉堆是最小的。二叉堆的堆序性是，任意一個(gè)父結(jié)點(diǎn)中的鍵值總是小于或等于子結(jié)點(diǎn)中的鍵值，這樣就可以快速執(zhí)行數(shù)據(jù)操作。在Open列表中，需要考察F（n）的最小值，因此采用最小二叉堆存儲(chǔ)Open列表中的結(jié)點(diǎn)。圖2為Open列表二叉堆示例圖，圓圈中數(shù)字代表F（n）值。

引入二叉堆后，A*算法每執(zhí)行一次尋路過程，就需要對(duì)Open列表進(jìn)行更新，增加鄰居結(jié)點(diǎn)，刪除Open列表中無用的結(jié)點(diǎn)。

插入數(shù)據(jù)，需要在二叉堆下一個(gè)可用位置創(chuàng)建一個(gè)空穴，如果不會(huì)破壞數(shù)據(jù)順序結(jié)構(gòu)，則插入成功。若不符合數(shù)據(jù)順序則繼續(xù)向上插入，直至成功。

刪除數(shù)據(jù)，只能刪除根結(jié)點(diǎn)，在根結(jié)點(diǎn)處建立一個(gè)空穴，將二叉堆最后一個(gè)值賦予根結(jié)點(diǎn)，自上而下依次調(diào)整，直至滿足二叉堆的堆序性。

利用二叉堆存儲(chǔ)Open列表可快速插入和刪除列表中鄰居結(jié)點(diǎn)，從而提高A*算法的搜索效率。

2.3 基于目標(biāo)范圍界限的優(yōu)化

目標(biāo)范圍界限是一種在預(yù)處理地圖信息時(shí)快速劃分目標(biāo)點(diǎn)的方法，核心思想是預(yù)先計(jì)算一個(gè)邊界框，其中包含所有通過探索其邊達(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ù)量，提高搜索效率。

計(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)格，只有通過標(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)格具有不規(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)的距離。

4 漏斗算法路徑平滑處理

基于多邊形導(dǎo)航網(wǎng)格的優(yōu)化A*算法生成路徑如圖5，實(shí)線為實(shí)際最短路線，虛線為A*算法尋路生成的路徑，是三角形內(nèi)心所連接成的線段，并不能代表其最優(yōu)真實(shí)路徑，需要進(jìn)一步利用漏斗算法進(jìn)行路徑平滑處理，從而生成實(shí)際最優(yōu)路徑。

漏斗算法包括3種結(jié)構(gòu)：路徑、漏斗和頂點(diǎn)。路徑是構(gòu)成算法中已知最短路徑點(diǎn)的一系列線段，漏斗邊分別由順時(shí)針旋轉(zhuǎn)邊和逆時(shí)針旋轉(zhuǎn)邊組成，涵蓋尚未處理的最短路徑區(qū)域。多邊形頂點(diǎn)以順時(shí)針方向保存（見圖6）。

在算法開始時(shí)，路徑為空，頂點(diǎn)設(shè)置為起點(diǎn)S，分別連接內(nèi)部最近的頂點(diǎn)V1和V2，構(gòu)成漏斗進(jìn)行判斷。若接下來的頂點(diǎn)在漏斗邊SV2和SV1內(nèi)部，則更新漏斗，如圖6（a）所示;若V3和V4都在漏斗里面，則更新漏斗邊SV3，漏斗將變得更窄;若頂點(diǎn)在漏斗邊的外邊則無需更新漏斗，如圖6（b）中V5在漏斗邊SV3的右邊;若漏斗上邊的頂點(diǎn)在下邊的下方，如圖6（c）中V8已經(jīng)在下邊漏斗邊的下方，則需要重置漏斗的頂點(diǎn)。由V3作為頂點(diǎn)，分別連接V4、V5重新構(gòu)造漏斗，存儲(chǔ)點(diǎn)V3作為拐點(diǎn)之一。重復(fù)執(zhí)行以上步驟，處理所有最優(yōu)路徑的三角網(wǎng)格頂點(diǎn)，存儲(chǔ)拐點(diǎn)，最終得到V3、V8為拐點(diǎn)，連接所有拐點(diǎn)找到最優(yōu)路徑。圖6（d）中S-g線段即為最優(yōu)路徑。漏斗算法如下：

輸入：s起始點(diǎn)，g終點(diǎn)

輸出：Path Π（ΔS，ΔE）

（1）if （NumEdges（c）<1）

（2）p.Add（s）;p.Add（g）;

（3）return P;

（4）L1← Connect（s，pr） ： L2← Connect（s，Pl）;//構(gòu)造漏斗邊L1和L2，順時(shí)針旋轉(zhuǎn)，在下方的為L1稱為漏斗的右邊。

（5）While （p.rightside ！=null） { //遍歷路徑右側(cè)的點(diǎn)

（6）If（pr+1 in L1.Leftside And pr+1 in L2.Rightside） //判斷下一個(gè)漏斗右邊方向的多邊形頂點(diǎn)是否在漏斗里面，若是，則更新漏斗邊，漏斗邊收窄。

（7）update L1← Connect（s，pr+1 ） ;

（8）else If （pr+1 in L2.Leftside）

（9）update L1← Connect（pr，pr+1） And push pr? in CornerPoint[] ;//重置漏斗頂點(diǎn)以及邊，并存儲(chǔ)頂點(diǎn)作為//拐點(diǎn)。

（10）else If （pr+1 in L2.Leftside ）? do nothing;}

（11）同理處理漏斗左邊的頂點(diǎn)，存儲(chǔ)拐點(diǎn);

（12）Connect （s， CornerPoint[] ，g） ;//連接起始點(diǎn)、拐點(diǎn)和終點(diǎn)形成路徑。

（13）return path P（s，CornerPoint[] ，g）;

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

本文實(shí)驗(yàn)平臺(tái)搭建利用Unity3D游戲引擎，地圖制作利用Blender建模工具，分別制作10×10、20×20、50×50尺寸的實(shí)驗(yàn)地圖，對(duì)應(yīng)尺寸均為Unity單位，制作好的地圖需要對(duì)障礙物進(jìn)行剔除，并刪除內(nèi)部網(wǎng)格線，生成多邊形輪廓的導(dǎo)航網(wǎng)格。在方格地圖的生成上，根據(jù)障礙物尺寸，選擇合適尺寸的網(wǎng)格。為了更精確尋找最優(yōu)路徑，選擇0.1Unity單位的網(wǎng)格地圖，對(duì)地圖進(jìn)行遍歷，確保尋路的準(zhǔn)確性。地圖預(yù)處理生成的目標(biāo)范圍界限以XML形式保存在項(xiàng)目文件夾中（見圖7）。

經(jīng)過實(shí)驗(yàn)對(duì)比分析，在保證最優(yōu)路徑的基礎(chǔ)上，地圖面積越大，基于多邊形導(dǎo)航網(wǎng)格地圖的改進(jìn)A*算法在搜索結(jié)點(diǎn)以及搜索時(shí)間上越優(yōu)于基于傳統(tǒng)方格地圖的A*算法（見圖8）。

6 結(jié)語

本文是針對(duì)不規(guī)則凸多邊形的A*尋路算法研究，對(duì)凸多邊形地圖利用快速約束Delaunay三角剖分的方法進(jìn)行三角剖分，形成可用于尋路的三角網(wǎng)格。為適用于不規(guī)則的三角網(wǎng)格，改進(jìn)統(tǒng)一A*算法中的網(wǎng)格代價(jià)，并給出針對(duì)多邊形導(dǎo)航網(wǎng)格的優(yōu)化A*算法。生成路徑是三角網(wǎng)格中心點(diǎn)的連線，并不是實(shí)際的最優(yōu)路徑，因此需要利用漏斗算法對(duì)路徑進(jìn)行平滑處理。本次實(shí)驗(yàn)地圖采用的是二維地圖，多邊導(dǎo)航網(wǎng)格在三維地圖中也有良好的表現(xiàn)。未來將重點(diǎn)研究如何將優(yōu)化A*算法運(yùn)用于三維多邊形導(dǎo)航網(wǎng)格。

參考文獻(xiàn)：

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

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

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

[4] 張前哨. 基于A算法的地圖尋徑的研究[D]. 武漢：武漢科技大學(xué)， 2005.

[5] HARABOR D，GRASTIEN A. Online graph pruning for pathfinding on grid maps[C].? San Francisco：AAAI Conference on Artificial Intelligence， 2011.

[6] DEMYEN D，BURO M. Efficient triangulation-based pathfinding[J].? Aaai，2007，1338（9）：161-163.

[7] 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.

[8] KALLMANN M. Navigation queries from triangular meshes [C].? The Third International Conference on Motion in Games，2010：230-241.

[9] 王天順，張莉.? 一種基于導(dǎo)航網(wǎng)格的路徑搜索技術(shù)[J]. 電腦知識(shí)與技術(shù)，2010，6（12）：3014-3016.

[10] 陳娜，黃明和，劉清華. 基于DAF算法的地圖尋徑研究[J]. 科學(xué)技術(shù)與工程，2010，10（30）：7536-7540.

[11] 張翰林，關(guān)愛薇，傅珂，等.? Dijkstra最短路徑算法的堆優(yōu)化實(shí)驗(yàn)研究[J]. 軟件，2017， 38（5）：15-21.

[12] 孫玉昕，章瑾. 利用堆排序優(yōu)化路徑搜索效率的分析[J]. 武漢工程大學(xué)學(xué)報(bào)，2013， 35（6）：50-54.

[13] WAGNER D，WILLHALM T，ZAROLIAGIS C. Geometric containers for efficient shortest-path computation[J].? Journal of Experimental Algorithmics，2005，10（10）：1-3.

[14] 韓瑋. 游戲地圖尋路及其真實(shí)性研究[D]. 重慶：西南大學(xué)， 2013.

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

[16] 李立，唐寧九，林濤. 基于地圖分割與以矢量信息描述地圖的A*尋路算法[J]. 四川大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，47（4）：729-734.

[17] 王燁萍. 基于綜合導(dǎo)航網(wǎng)格的智慧旅游動(dòng)態(tài)尋徑方法[D]. 成都：西南交通大學(xué)， 2017.

[18] 林巍凌. 引入導(dǎo)航網(wǎng)格的室內(nèi)路徑規(guī)劃算法[J]. 測繪科學(xué)， 2016，41（2）：39-43.

[19] 趙芳?jí)荆词_，李向前，等. 基于三角形細(xì)分的三角網(wǎng)格模型表面體素化算法[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2017，23（11）：2399-2406.

[20] 嚴(yán)冬明，胡楷模，郭建偉，等. 各向同性三角形重新網(wǎng)格化方法綜述[J]. 計(jì)算機(jī)科學(xué)， 2017， 44（8）：9-17.

[21] 曾薇，孟祥旭，楊承磊，等. 平面多邊形域的快速約束Delaunay三角化[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2005，17（9）：1933-1940.

（責(zé)任編輯：何 麗）