分層路徑搜索算法研究

呂龍輝+靳紅霞

摘要：自動(dòng)尋路算法是智能游戲中的重要組成部分，通過(guò)對(duì)現(xiàn)有自動(dòng)尋路算法的分析，了解目前已有自動(dòng)尋路算法所存在的不足。基于地圖劃分的思想設(shè)計(jì)分層路徑搜索算法，通過(guò)將地圖細(xì)分，計(jì)算細(xì)分區(qū)域中抽象節(jié)點(diǎn)的最短路徑，在地圖加載過(guò)程中，實(shí)現(xiàn)地圖的預(yù)處理，從而在確定了路徑起始點(diǎn)和結(jié)束點(diǎn)之后，快速實(shí)現(xiàn)自動(dòng)尋路。

關(guān)鍵詞：自動(dòng)尋路算法；地圖細(xì)分；抽象圖

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）30-0066-02

1 概述

隨著信息技術(shù)的發(fā)展，游戲的畫(huà)面質(zhì)量不斷提高，角色技能越來(lái)越豐富，當(dāng)游戲的畫(huà)面質(zhì)量和角色技能發(fā)展到一定階段之后，單純的提高游戲畫(huà)面效果和角色已經(jīng)難以滿足玩家的需求，而游戲的難易程度、趣味性和操作游戲就成為了智能游戲的研究熱點(diǎn)。

自動(dòng)尋路是智能游戲中非常重要的組成部分，傳統(tǒng)的A*自動(dòng)尋路算法通過(guò)剪枝優(yōu)化自動(dòng)尋路搜索進(jìn)程，最終找到一條路徑起點(diǎn)和終點(diǎn)之間的最短路徑。但A*的空間復(fù)雜度較高，在大地圖上的自動(dòng)尋路效果較差。而M-A*、HPA*算法通過(guò)對(duì)地圖的多尺度劃分來(lái)縮小搜素空間，提高了自動(dòng)尋路算法效率，但是降低了所尋路徑的最優(yōu)程度。

2 自動(dòng)尋路算法優(yōu)化思路

目前，大多數(shù)的自動(dòng)尋路算法都未考慮地圖中障礙物的分布問(wèn)題，而且相同自動(dòng)尋路算法的性能在不同障礙物分布地圖上的差別較大。Dijkstra和A*算法的難以滿足大地圖自動(dòng)尋路算法的性能要求；HPA*算法未考慮地形信息，降低最終路徑的最有程度；M-A*僅的分區(qū)僅考慮起點(diǎn)和終點(diǎn)的區(qū)域信息，導(dǎo)致每一次自動(dòng)尋路都需要重新分區(qū)，造成性能降低；Quadtree算法的抽象節(jié)點(diǎn)較多，終止條件過(guò)于嚴(yán)格，內(nèi)存耗費(fèi)嚴(yán)重。

針對(duì)目前主流自動(dòng)尋路算法所存在的不足，提出一種考慮地圖分布信息的分層路徑搜索算法，通過(guò)對(duì)地圖的分區(qū)，根據(jù)區(qū)域中障礙物的分布情況來(lái)選擇合適的自動(dòng)尋路算法來(lái)設(shè)計(jì)尋找路徑，進(jìn)而提高整個(gè)自動(dòng)尋路算法的性能。

3 分層路徑搜索算法設(shè)計(jì)

分層路徑搜索算法根據(jù)大地圖中障礙物的分布情況，將大地圖分為不均等的若干區(qū)域，并根據(jù)每個(gè)區(qū)域的障礙物信息來(lái)設(shè)置區(qū)域狀態(tài)，并將區(qū)域邊界的空白節(jié)點(diǎn)看做抽象節(jié)點(diǎn)來(lái)構(gòu)建地圖的抽象圖；并依據(jù)區(qū)域的狀態(tài)，選擇曼哈頓距離或者向上融合算法來(lái)獲得抽象節(jié)點(diǎn)間的最短路徑；使用A*算法在抽象圖上實(shí)現(xiàn)抽象尋路，依據(jù)相關(guān)節(jié)點(diǎn)在所在區(qū)域的狀態(tài)來(lái)選擇對(duì)應(yīng)的自動(dòng)尋路算法進(jìn)行細(xì)化；最終得到實(shí)際的最短路徑。

3.1 相關(guān)系數(shù)設(shè)計(jì)

在分層路徑搜索算法中，引入了區(qū)域障礙物比例[α]，區(qū)域狀態(tài)標(biāo)記[λ]和閾值[β]三個(gè)系數(shù)。

1）區(qū)域障礙物比例

區(qū)域障礙物比例[α]用于計(jì)算區(qū)域的障礙物多少，為是否需要繼續(xù)細(xì)分提供依據(jù)，其計(jì)算公式如式（1）所示。

[α=當(dāng)前分區(qū)障礙物總數(shù)當(dāng)前分區(qū)的節(jié)點(diǎn)總數(shù)] （1）

2）區(qū)域狀態(tài)標(biāo)記

區(qū)域狀態(tài)標(biāo)記[λ]取值0或1，對(duì)分區(qū)過(guò)程中所構(gòu)建四叉樹(shù)上不再細(xì)分的葉子及節(jié)點(diǎn)狀態(tài)進(jìn)行標(biāo)記。如果區(qū)域內(nèi)的障礙物較多，那么[λ]取值0，在該區(qū)域中使用A*算法實(shí)現(xiàn)自動(dòng)尋路；如果[λ]取值1表示當(dāng)前區(qū)域的障礙物較少，可以使用Bresenham直線方法尋找最優(yōu)路徑。

3）閾值

閾值[β]為是否需要對(duì)區(qū)域繼續(xù)進(jìn)行劃分的邊界值，[β]值越大，那么區(qū)有的劃分就越細(xì)，地圖中的抽象節(jié)點(diǎn)額越多，擴(kuò)展節(jié)點(diǎn)越少，耗費(fèi)時(shí)間越少，但耗費(fèi)的內(nèi)存越多；[β]值越小，區(qū)域劃分越粗糙，抽象節(jié)點(diǎn)越小，耗費(fèi)的內(nèi)存越小。

3.2 地圖區(qū)域劃分

將大地圖根據(jù)障礙物信息細(xì)分成多個(gè)區(qū)域是分層路徑搜索算法的核心思想。其區(qū)域劃分思想與同樣進(jìn)行地圖劃分的Quadtree算法不同，在算法中首選將地圖劃等分為四份，然后根據(jù)每個(gè)分區(qū)的區(qū)域障礙物比例[α]和閾值[β]的關(guān)系來(lái)設(shè)置區(qū)域狀態(tài)標(biāo)記[λ]。根據(jù)三個(gè)參數(shù)的定義，地圖區(qū)域劃分分為如下三種情況。

1）[α=0]，表明當(dāng)前區(qū)域沒(méi)有障礙物，設(shè)置[λ=1]，設(shè)置為葉子節(jié)點(diǎn)，表明該分區(qū)沒(méi)有障礙物，不再進(jìn)行細(xì)分，該區(qū)域使用Bresenhhan直線方法來(lái)尋找最短路徑。

2）[0?α?β]，區(qū)域內(nèi)障礙物較多，繼續(xù)細(xì)分。

3）[α?β?1]，區(qū)域內(nèi)障礙物較少，設(shè)置[λ=0]，設(shè)置為葉子節(jié)點(diǎn)，表明該分區(qū)有障礙物，在該區(qū)域內(nèi)使用A*算法進(jìn)行自動(dòng)尋路。

分層路徑搜索算法的分區(qū)算法流程圖設(shè)計(jì)如圖1所示。

在按照如上的思路進(jìn)行地圖區(qū)域劃分，最終得到一個(gè)包含地圖區(qū)域信息的一個(gè)四叉樹(shù)。

3.3 抽象圖構(gòu)造

在完成地圖區(qū)域劃分之后，需要將所得到的四叉樹(shù)葉子節(jié)點(diǎn)上邊界上的非障礙物節(jié)點(diǎn)作為抽下點(diǎn)，來(lái)構(gòu)造地圖的抽象圖。根據(jù)區(qū)域的狀態(tài)分別采用曼哈頓距離或者自底向上融合算法來(lái)計(jì)算子區(qū)域抽象節(jié)點(diǎn)的最短距離。

如果子區(qū)域的[λ=1]，則表明該區(qū)域內(nèi)沒(méi)有障礙物，直接使曼哈頓算法計(jì)算兩個(gè)抽象節(jié)點(diǎn)之間的距離；否則，改區(qū)域中含有障礙物，使用自底向上融合的方法計(jì)算區(qū)域內(nèi)抽象節(jié)點(diǎn)之間的最短距離。其中曼哈頓距離計(jì)算公式如式（2）所示。

[DisP1，P2=X1-X2+Y1-Y2] （2）

在得到區(qū)域內(nèi)抽象節(jié)點(diǎn)的最短路徑之后，最終完成地圖的抽象圖。

3.4 自動(dòng)尋路設(shè)計(jì)

在獲得地圖完整的抽象圖之后，根據(jù)玩家所設(shè)定的路徑起始點(diǎn)和目標(biāo)點(diǎn)，找到其所在的區(qū)域進(jìn)行插入操作。首先，判斷路徑的起始點(diǎn)或目標(biāo)點(diǎn)是否為抽象點(diǎn)，如果是抽象點(diǎn)，那么可以在抽象圖上進(jìn)行自動(dòng)尋路；其次，判斷起始點(diǎn)和目標(biāo)點(diǎn)是否在同一個(gè)分區(qū)內(nèi)，如果是，則根據(jù)所在分區(qū)的[λ]值，選擇Bresenhhan直線或A*算法實(shí)現(xiàn)自動(dòng)尋路；最后，如果起始點(diǎn)和目標(biāo)點(diǎn)不再同一個(gè)分區(qū)，則分別連接起始點(diǎn)和目標(biāo)點(diǎn)與其所在區(qū)域的抽象節(jié)點(diǎn)的連接，完成起始點(diǎn)和目標(biāo)點(diǎn)的插入操作。

在完成了相關(guān)系數(shù)的設(shè)計(jì)、地圖區(qū)域的劃分和獲得抽象圖之后，最終的自動(dòng)尋路設(shè)計(jì)如圖2所示。

4 結(jié)束語(yǔ)

分層路徑搜索算法是一種考慮了地圖內(nèi)部障礙物分布情況的地圖分層路徑搜索算法，在算法中根據(jù)障礙物分布信息將地圖劃分為一系列不均等的子區(qū)域，并將子區(qū)域邊界上的所有非障礙物節(jié)點(diǎn)看成是抽象節(jié)點(diǎn)構(gòu)造地圖的抽象圖，并根據(jù)區(qū)域內(nèi)的障礙物分布情況，選擇Bresenhhan直線或A*算法實(shí)現(xiàn)自動(dòng)尋路計(jì)算區(qū)域中抽象節(jié)點(diǎn)之間的最路徑；最終根據(jù)玩家所設(shè)定的路徑起始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)實(shí)現(xiàn)路徑細(xì)化，得到實(shí)際的最優(yōu)路徑。分層路徑搜索算法在地圖加載過(guò)程中，完成的預(yù)處理，可以提高玩家在使用時(shí)的最優(yōu)路徑選擇，完成自動(dòng)尋路。

參考文獻(xiàn)：

[1] 李艷，周振華，趙文舉，等.一種考慮地圖分布信息的分層路徑搜索算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2013，11：2607-2611.

[2] 李艷，李鐵松.一種基于相對(duì)海明距離的地圖復(fù)雜性度量[J].計(jì)算機(jī)工程，2012，38（7）：10-12.

[3] 馮林，紫紅霞.基于動(dòng)態(tài)閾值啟發(fā)式圖搜索的SLAM算法[J].計(jì)算機(jī)工程，2011，37（17）：185-187.

[4] 李艷，陳彩，李文亮，等.KM-A*：一種基于A*和K-means聚類的計(jì)算機(jī)游戲?qū)ぢ匪惴╗C].2010年第三屆計(jì)算智能與工業(yè)應(yīng)用國(guó)際學(xué)術(shù)研討會(huì)，2010，7：291-294.