樊質(zhì)軍+楊朋英+孫玉霞

摘要：路徑搜索是許多游戲的核心組成部分，路徑搜索的算法有很多，不同的搜索算法有不同的搜索效率。A*算法是游戲中解決尋路問(wèn)題的主要搜索算法，該文通過(guò)對(duì)A*算法的分析與研究，找出不足并進(jìn)行優(yōu)化和改進(jìn)。在A*算法基礎(chǔ)上添加了一個(gè)對(duì)障礙預(yù)處理的方案，使角色能順利地繞開障礙，減少搜索不必要的障礙所用的額外的空間和時(shí)間。并進(jìn)行了尋路仿真實(shí)驗(yàn)，對(duì)比分析了傳統(tǒng)算法和改進(jìn)算法的性能。實(shí)驗(yàn)結(jié)果表明改進(jìn)A*算法的可行性與有效性。

關(guān)鍵詞：A*算法；啟發(fā)式函數(shù)；尋路；預(yù)處理

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

尋路作為游戲中的基本問(wèn)題之一，即角色按照程序指定的合適的路徑從地圖的A點(diǎn)抵達(dá)B點(diǎn)，根據(jù)角色對(duì)周圍環(huán)境了解程度的不同，分為全局路徑規(guī)劃方法和完全未知或部分未知的局部路徑規(guī)劃方法兩種。目前網(wǎng)絡(luò)游戲、手機(jī)增值等業(yè)務(wù)迅猛發(fā)展，尋路技術(shù)已成為游戲的一個(gè)核心組成部分。物體按照某種指定方式移動(dòng)，就要求程序必須能夠找到一條從起點(diǎn)到目標(biāo)點(diǎn)的最佳路徑，這條路徑應(yīng)該是繞過(guò)障礙物并且到達(dá)目的地最短的路徑，而A*算法就是完成這個(gè)任務(wù)的最好的算法。

1 A*算法的不足與改進(jìn)

啟發(fā)式A*搜索算法，顧名思義，就是有啟發(fā)地尋找目標(biāo)結(jié)點(diǎn)，并且在基于最小的成本下，盡可能地找到通向目標(biāo)點(diǎn)的最合適并且最短的路徑。

在《一種基于A星算法的游戲路徑優(yōu)化應(yīng)用》的文章中，講述了傳統(tǒng)A*算法的不足，即在面對(duì)障礙時(shí)進(jìn)行了許多無(wú)用功結(jié)點(diǎn)的搜索，并對(duì)此不足作出了相應(yīng)的改進(jìn)，添加了一個(gè)對(duì)障礙預(yù)處理的方案，并且額外添加一個(gè)destination集合，使角色能順利地繞開障礙，減少搜索所用的額外內(nèi)存空間，從而更加智能地到達(dá)目標(biāo)結(jié)點(diǎn)，并且對(duì)此改進(jìn)方法作了仿真分析。

2 仿真實(shí)驗(yàn)

2.1 實(shí)驗(yàn)環(huán)境及設(shè)備

實(shí)驗(yàn)仿真的硬件設(shè)備：Inter（R） Core（TM） i5-4200 CPU @ 1.60GHz 2.30GHz，內(nèi)存為4GB；操作系統(tǒng)為Microsoft Windows 8.1；仿真系統(tǒng)開發(fā)平臺(tái)環(huán)境為：Dev-cpp5.4.0；

2.2 實(shí)驗(yàn)基本流程及技術(shù)難點(diǎn)

2.2.1 實(shí)驗(yàn)基本流程

圖1為實(shí)驗(yàn)整體流程圖。

2.2.2 技術(shù)難點(diǎn)

（1） 目標(biāo)結(jié)點(diǎn)選取

在傳統(tǒng)的A*算法中，目標(biāo)點(diǎn)只有一個(gè)，為了讓角色優(yōu)先到達(dá)障礙邊界出口點(diǎn)，根據(jù)堆棧的思想，將此作為一個(gè)destination目標(biāo)集合，將邊界出口點(diǎn)作為最先到達(dá)的臨時(shí)目標(biāo)點(diǎn)。

（2） 障礙的內(nèi)存存儲(chǔ)

為了用盡可能少的內(nèi)存存儲(chǔ)障礙，運(yùn)用了一個(gè)邊界出口點(diǎn)方法，即存儲(chǔ)障礙邊界點(diǎn)的障礙，這里的方法可以有很多，本文的方法是將障礙再加一層屏障。

（3） 多個(gè)邊界出口點(diǎn)的選取

一個(gè)障礙可能會(huì)有多個(gè)邊界出口點(diǎn)，為了選取最近以及最可靠的出口點(diǎn)，根據(jù)角色到出口點(diǎn)加上出口點(diǎn)到終點(diǎn)的距離來(lái)進(jìn)一步判斷出口點(diǎn)的選取。

（4） 預(yù)處理障礙

在角色尋路的過(guò)程中，從角色到目標(biāo)點(diǎn)或者臨時(shí)目標(biāo)點(diǎn)的連線中，如果檢測(cè)到存在障礙，那么立刻停止檢測(cè)，就該障礙作進(jìn)一步處理。

2.2.3 結(jié)果數(shù)據(jù)分析

（1） 內(nèi)存結(jié)點(diǎn)的分析

添加了改進(jìn)方案的A*算法在搜索的過(guò)程中，搜索無(wú)用功的結(jié)點(diǎn)明顯減少，例如表1中哈曼頓的結(jié)點(diǎn)從51減少到了16，搜索范圍變小，例如多障礙的結(jié)點(diǎn)由643減少到了143，并且根據(jù)圖2可知，結(jié)點(diǎn)減少率大約在80%左右，綜上所述，改進(jìn)以后的算法能更精確且快速地繞開障礙并尋找路徑，直至抵達(dá)終點(diǎn)。

（2） 消耗時(shí)間的分析

在實(shí)際游戲中，游戲在生成地圖的時(shí)候已經(jīng)預(yù)處理了障礙，又因?yàn)锳*算法是基于靜態(tài)網(wǎng)格下的，即障礙都是靜態(tài)的，針對(duì)5種不同的地形實(shí)驗(yàn)進(jìn)行A*算法改進(jìn)前和改進(jìn)后消耗時(shí)間的精確測(cè)試，如表2和表3，可以清楚地看出每組實(shí)驗(yàn)測(cè)試了5組數(shù)據(jù)，并且從中去掉一個(gè)最高值和最低值，取剩下三組數(shù)據(jù)求平均值[1]，使最終的平均值數(shù)據(jù)更加精確，而5種不同的實(shí)驗(yàn)（實(shí)驗(yàn)一到實(shí)驗(yàn)五）中改進(jìn)前和改進(jìn)后結(jié)點(diǎn)的個(gè)數(shù)分別對(duì)應(yīng)為：73，29，730，121，858和14，22，110，52，173，結(jié)合這些數(shù)據(jù)繪制出隨著結(jié)點(diǎn)個(gè)數(shù)變化時(shí)間消耗分析預(yù)測(cè)圖，如圖3，可以明顯地看出，雖然在結(jié)點(diǎn)很少的情況下，改進(jìn)后的A*算法所需時(shí)間高于傳統(tǒng)的A*算法，但是隨著結(jié)點(diǎn)個(gè)數(shù)增加，并且根據(jù)線性預(yù)測(cè)分析法[2]可以明顯看出，改進(jìn)的A*算法要優(yōu)于傳統(tǒng)的A*算法，綜上所述，在基于改進(jìn)A*算法上預(yù)處理所需內(nèi)存明顯減少的情況下，游戲所運(yùn)行的的時(shí)間也有一定的優(yōu)化，從而驗(yàn)證了改進(jìn)A*算法的真實(shí)性和可行性。

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

本文在A*算法的基礎(chǔ)上，添加了對(duì)就近障礙預(yù)處理找出邊界出口的方案，結(jié)合一個(gè)destination集合，對(duì)傳統(tǒng)A*算法進(jìn)行了改進(jìn)，并進(jìn)行仿真實(shí)驗(yàn)，由圖2的減少率圖和圖3的耗時(shí)預(yù)測(cè)分析圖可以明顯地看出，該改進(jìn)方法在預(yù)處理搜索的內(nèi)存大大減少，并且基于此在時(shí)間上也有一定的優(yōu)化，綜上所述，根據(jù)仿真實(shí)驗(yàn)結(jié)果，驗(yàn)證了改進(jìn)的A*算法的可行性和真實(shí)性。

參考文獻(xiàn)：

[1] 周世健. 截尾均值與平尾均值[J]. 地球科學(xué)與環(huán)境學(xué)報(bào)， 1996（4）：84-90.

[2] Aitchison J， Dunsmore I R. Statistical prediction analysis[M]. Cambridge University Press， 1975.endprint