孫玉霞，樊質(zhì)軍

(湖北師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 ，湖北 黃石 435002)

一種基于A星算法的游戲路徑優(yōu)化應(yīng)用

孫玉霞，樊質(zhì)軍

(湖北師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 ，湖北 黃石 435002)

A*算法作為游戲中解決尋路問(wèn)題的主要搜索算法，本文討論了A*算法的基本原理，交代了其在游戲?qū)ぢ愤^(guò)程中的作用及缺陷，并在A*算法基礎(chǔ)上添加了一個(gè)對(duì)障礙預(yù)處理的方案，用一個(gè)destination集合，使角色能順利地繞開(kāi)障礙，減少搜索不必要的障礙所用的額外內(nèi)存空間和運(yùn)行時(shí)間，從而更加智能地到達(dá)目標(biāo)結(jié)點(diǎn)。實(shí)驗(yàn)仿真證明了該算法的有效性和可行性。

A*算法；啟發(fā)式函數(shù)；路徑優(yōu)化；預(yù)處理功能

尋路作為游戲中的基本問(wèn)題之一，即角色按照程序指定的合適的路徑從地圖的A點(diǎn)抵達(dá)B點(diǎn)，根據(jù)角色對(duì)周?chē)h(huán)境了解程度的不同，可分為兩種類型：全局路徑規(guī)劃方法和完全未知或部分未知的局部路徑規(guī)劃方法[1]。而在此基礎(chǔ)上，發(fā)展了許多以啟發(fā)式算法為核心的智能算法，包括A*算法、D*算法、遺傳算法、模擬退火算法和蟻群算法[2～5]。

啟發(fā)式的A*搜索算法作為路徑優(yōu)化和路徑搜索的經(jīng)典方法，在戰(zhàn)略性游戲中都是以此為基礎(chǔ)來(lái)進(jìn)行尋路的，雖然相對(duì)于那些老式的搜索算法，比如深度優(yōu)先搜索算法，廣度優(yōu)先搜索算法，Dijkstra搜索算法[6～8]，在時(shí)間復(fù)雜度和空間復(fù)雜度要好的很多，但是A*搜索算法本身也存在不足，尤其是在搜索過(guò)程中出現(xiàn)前方障礙的問(wèn)題，雖然啟發(fā)式A*搜索算法可以在搜索的過(guò)程中有“方向”地往終點(diǎn)尋路過(guò)去，但是當(dāng)遇到障礙時(shí)，也會(huì)在障礙周?chē)M(jìn)行搜索，即做了許多無(wú)用功的結(jié)點(diǎn)搜索，因?yàn)檎系K阻擋了前方A*搜索的道路，國(guó)內(nèi)外的學(xué)者也對(duì)此進(jìn)行了大量的研究，例如：王善坤等[9]根據(jù)改進(jìn)的人工勢(shì)場(chǎng)法讓繞過(guò)障礙的曲線更加平滑，但是依然需要在障礙周?chē)M(jìn)行搜索；蔡方方等[10]根據(jù)雙層A*算法進(jìn)行二次搜索來(lái)繞過(guò)障礙，雖然可以避開(kāi)了障礙，但是增加了額外A*算法搜索時(shí)間；高慶吉等[11]引入了“人工搜索標(biāo)記”，起到預(yù)先判斷或者逃離障礙物的作用，但是依然需要對(duì)障礙周?chē)M(jìn)行無(wú)用功結(jié)點(diǎn)的搜索預(yù)處理。綜上所述，雖然目前學(xué)者們做出了許多研究，但是依然存在搜索過(guò)程中無(wú)用功結(jié)點(diǎn)的出現(xiàn)，本文在A*算法的基礎(chǔ)上，并在A*算法搜索的過(guò)程中，添加了一個(gè)對(duì)障礙預(yù)處理的方案，并且額外添加一個(gè)destination集合，使角色能順利地繞開(kāi)障礙，減少搜索所用的額外內(nèi)存空間，從而更加智能地到達(dá)目標(biāo)結(jié)點(diǎn)。所做的仿真實(shí)驗(yàn)結(jié)果中也證明了改進(jìn)后算法的合理性和可行性。

1 基于A*算法的搜索規(guī)劃

1.1 A*搜索算法

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

為了達(dá)到啟發(fā)的目的，與一般的搜索算法不同，可以看圖1和圖2對(duì)比，在A*算法中，十分奇妙的設(shè)計(jì)了一個(gè)估價(jià)函數(shù)，這是最主要的部分：

f(n)=g(n)+h(n)

其中f(n)是從當(dāng)前結(jié)點(diǎn)展開(kāi)(一般在網(wǎng)格中是八個(gè)方向)搜索出來(lái)的結(jié)點(diǎn)的估價(jià)值，g(n)表示從當(dāng)前結(jié)點(diǎn)到預(yù)處理搜索點(diǎn)的估價(jià)值，h(n)則表示預(yù)處理的結(jié)點(diǎn)中與目標(biāo)點(diǎn)的估價(jià)值。

A*算法的尋路步驟如下(其中open集合列表表示預(yù)處理但未訪問(wèn)的結(jié)點(diǎn)，close集合列表則表示已經(jīng)訪問(wèn)過(guò)的結(jié)點(diǎn))：

1)從起點(diǎn)start開(kāi)始, 把它作為一個(gè)結(jié)點(diǎn)首先放入open集合列表中。

2)同時(shí)預(yù)處理start起點(diǎn)的周?chē)Y(jié)點(diǎn)，一般在網(wǎng)格中是8個(gè)方位，并且把這8個(gè)方位的父節(jié)點(diǎn)設(shè)置為該start結(jié)點(diǎn)。

3) 當(dāng)周?chē)Y(jié)點(diǎn)搜索完畢后，將start結(jié)點(diǎn)從open集合列表中刪除，同時(shí)放入close集合列表中。

4)先檢查預(yù)處理的這些點(diǎn)，是否是“可用結(jié)點(diǎn)”(不是障礙或者不在close集合列表中)，當(dāng)確認(rèn)是可用結(jié)點(diǎn)，則計(jì)算那些預(yù)處理結(jié)點(diǎn)的f，g，h的值，同時(shí)在計(jì)算的過(guò)程中比較大小，將最小的結(jié)點(diǎn)排在open集合列表中，方便下一步使用。

5)如果某個(gè)預(yù)處理結(jié)點(diǎn)已經(jīng)在open集合列表中了, 檢查如果用新的路徑時(shí)此時(shí)的估價(jià)函數(shù)是否更低，如果是，則更新，更新的同時(shí)也需要適當(dāng)調(diào)整下大小排序，否則不更新。

6)判斷該相鄰方格是否為終點(diǎn)，不是的話重復(fù)第4,5步，是的話就結(jié)束程序，并且根據(jù)之前每個(gè)結(jié)點(diǎn)存在的父節(jié)點(diǎn)，回溯標(biāo)記，找到終點(diǎn)，并且輸出路徑，結(jié)束程序。

圖1 一般搜索算法的預(yù)處理搜索范圍

1.2 傳統(tǒng)啟發(fā)式A*搜索算法的不足

在A*中算法中，最重要的就是啟發(fā)式函數(shù)的選取，不同的啟發(fā)式函數(shù)會(huì)造成不同搜索范圍，搜索范圍越小，搜索路徑越精確，造成的誤差就會(huì)越少。但是當(dāng)前方存在障礙時(shí)，會(huì)出現(xiàn)許多無(wú)意義的搜索，引起繞道或者原路返回，則花費(fèi)大量不必要的時(shí)間和空間，如圖3 .

圖3 A*算法遇障礙時(shí)搜索范圍

2 針對(duì)A*算法不足的改進(jìn)方案及思路

基本思路：在小人尋路的過(guò)程中，自動(dòng)繞開(kāi)前方的障礙物，避免走進(jìn)復(fù)雜或者特殊地形，從而避免搜索更多無(wú)意義的結(jié)點(diǎn)，達(dá)到搜索范圍更小，確定目標(biāo)更精確的效果。具體思路如下：

1)利用局部障礙檢測(cè)方法對(duì)最近障礙物進(jìn)行預(yù)處理

在搜索過(guò)程中將可能遇到的障礙進(jìn)行預(yù)處理功能，從而使小人在尋路過(guò)程中，自動(dòng)避開(kāi)障礙物，避免無(wú)意義的搜索。在障礙物的預(yù)處理上，為避免浪費(fèi)大量時(shí)間，采用目標(biāo)點(diǎn)局部障礙檢測(cè)方法，即當(dāng)朝向目標(biāo)點(diǎn)的前方出現(xiàn)障礙的時(shí)候(如圖4，圖5)，取最近的障礙并且檢測(cè)，在程序中，可以將小人和目標(biāo)點(diǎn)連成。

圖4 小人尋路時(shí)所遇障礙

一條直線，從小人這個(gè)點(diǎn)往目標(biāo)點(diǎn)作一個(gè)射線，一旦該射線有障礙，那么就檢測(cè)到了障礙，并且將該障礙物做預(yù)處理，如果該射線沒(méi)有遇到障礙，就說(shuō)明前方通暢無(wú)阻，就可以筆直地往目標(biāo)點(diǎn)走去了。

2) 以兩個(gè)邊界結(jié)點(diǎn)坐標(biāo)確定障礙位置并進(jìn)行存儲(chǔ)

為了用盡可能小的內(nèi)存來(lái)存儲(chǔ)障礙的坐標(biāo)結(jié)點(diǎn)，只需要存下兩個(gè)邊界點(diǎn)的坐標(biāo)(當(dāng)然，也可以存下大于兩個(gè)的邊界點(diǎn)坐標(biāo))，其中邊界點(diǎn)的特點(diǎn)就是，除了一個(gè)方向，其他方向都沒(méi)有相應(yīng)的障礙。

3) 添加destination列表，表示目標(biāo)結(jié)點(diǎn)集合

確定了障礙的邊界點(diǎn)以后(邊界點(diǎn)可以有多個(gè)點(diǎn)，為了方便起見(jiàn)，設(shè)兩個(gè)障礙邊界點(diǎn)為A點(diǎn)和B點(diǎn)，并且O點(diǎn)為小人所在點(diǎn)，C點(diǎn)是最終的終點(diǎn))，然后需要計(jì)算OA+AC和OB+BC的繞行距離，但是無(wú)論是曼哈頓距離，還是對(duì)角線距離，或者是歐幾里得距離，都比繞行距離要小，并且距離差會(huì)隨著目標(biāo)障礙物的增大而增大。此時(shí)增加一個(gè)destination目標(biāo)節(jié)點(diǎn)列表，表示目標(biāo)節(jié)點(diǎn)集合，此列表操作的順序是先進(jìn)先出，利用此方法會(huì)優(yōu)先找到繞開(kāi)障礙的一個(gè)出口點(diǎn)，出口點(diǎn)就是當(dāng)前的目標(biāo)點(diǎn)。假設(shè)此時(shí)B點(diǎn)是出口點(diǎn)即目標(biāo)點(diǎn)，那么將B點(diǎn)先壓入destination列表中，由于到B點(diǎn)的路暢通無(wú)阻，所以小人將迅速找到B點(diǎn)，并且完美地繞開(kāi)了障礙物，此時(shí)B點(diǎn)出棧，目標(biāo)點(diǎn)變?yōu)榱嗽K點(diǎn)C點(diǎn)，再繼續(xù)搜索找到C點(diǎn)，將C點(diǎn)出棧，此時(shí)destination列表中沒(méi)有任何集合，小人尋路完成，至此程序結(jié)束。

圖6 傳統(tǒng)A*算法搜索范圍

3 實(shí)驗(yàn)仿真分析

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

實(shí)驗(yàn)仿真環(huán)境為仿真軟件生成的50×50的網(wǎng)格地圖，如圖6和如圖8所示。其中s代表起點(diǎn)，A代表所預(yù)處理搜索的結(jié)點(diǎn)，x代表障礙，小點(diǎn)則代表可通行的路徑，d代表終點(diǎn)。首先，圖6中，仿真實(shí)驗(yàn)很好的驗(yàn)證了前文1.2中A*算法在遇到障礙時(shí)的不足，即雖然有啟發(fā)式地向目標(biāo)點(diǎn)尋去，但是也要在阻礙它的障礙周?chē)M(jìn)行預(yù)處理搜索。圖7中運(yùn)用了改進(jìn)后的方法，可以明顯看出預(yù)處理搜索的范圍減少了。圖8中，加入了多種復(fù)雜障礙，也能很明顯的看出，當(dāng)障礙復(fù)雜，起始點(diǎn)與目標(biāo)點(diǎn)距離遠(yuǎn)時(shí)，A*算法這一不足突出地更加明顯，為了讓讀者分辨清楚，用紅色框框著的區(qū)域代表障礙。圖9中，當(dāng)我們運(yùn)用了改進(jìn)后的A*算法時(shí)，更加可以明顯地看出，搜索預(yù)處理的結(jié)點(diǎn)數(shù)大大減少，并且也同時(shí)更加智能地繞開(kāi)了障礙，最終達(dá)到目標(biāo)點(diǎn)。從上面的仿真實(shí)驗(yàn)結(jié)果可以看出，該改進(jìn)后的A*算法較傳統(tǒng)的A*算法，預(yù)處理的搜索范圍明顯減少，也更加智能地繞開(kāi)了障礙，大大提升了性能。

圖8 傳統(tǒng)A*算法在多障礙下的搜索范圍

4 結(jié)語(yǔ)

本文在基于A*算法的基礎(chǔ)上，添加了對(duì)就近障礙預(yù)處理找出邊界出口的方案，并且結(jié)合一個(gè)destination集合，結(jié)合這三種方法，改進(jìn)了傳統(tǒng)A*算法在游戲中的運(yùn)用，即解決了前方出現(xiàn)障礙時(shí)(特別在障礙擁有特殊地形的情況下),出現(xiàn)許多無(wú)用功搜索結(jié)點(diǎn)，從而消耗額外內(nèi)存,大大減少了對(duì)額外內(nèi)存的消耗；同時(shí)，也為游戲中小人在尋找較遠(yuǎn)目標(biāo)點(diǎn)時(shí)，減少了所消耗的額外時(shí)間(如轉(zhuǎn)向問(wèn)題)，仿真實(shí)驗(yàn)也證明了該改進(jìn)算法的可行性和真實(shí)性。從而使小人在繞開(kāi)障礙時(shí)變得更加智能化，同時(shí)也讓游戲變得更加流暢，大大提升了游戲的品質(zhì)，也給玩家在游戲中帶來(lái)更好的體驗(yàn)。

[1]莊慧忠,社樹(shù)新,吳鐵軍.機(jī)器人路徑規(guī)劃及相關(guān)算法研究[J].科技通報(bào),2004,20(3):210～215.

[2]陳和平,張前哨.A*算法在游戲地圖尋徑中的應(yīng)用與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用與軟件,2005, 22(12):118～120.

[3]Stentz A.Optimal and efficient path planning for partially-known environments[C].Proceedings of the IEEE International Conference on Robotics and Automation. San Diego, Carlifonia, USA,1994:3310～3317.

[4]Gemeinder M,Gerke M.GA-based path planning for mobile robot systems employing an active search algorithm[J].Applied Soft Computing, 2003, A3:149～158.

[5]Dorigo M,Maniezzo V,Colorni A. Ant system:optimization by a colony of cooperating agent[J].IEEE Transactions on Systems Man and Cybernetics, 1996,26(1):29～41.

[6]田翠華,許衛(wèi)平,陳玉明.深度優(yōu)先遍歷算法、隨機(jī)布點(diǎn)法及回溯法在迷宮游戲中的應(yīng)用[J].河北北方學(xué)院學(xué)報(bào)(自然科學(xué)版), 2013, 29(3):19～24.

[7]盧啟衡,馮曉紅.基于寬度優(yōu)先搜索的路徑生成算法[J].現(xiàn)代計(jì)算機(jī):專業(yè)版,2006(12):87～89.

[8]蔚潔,楊懷雷,成汝震.基于Dijkstra算法的最優(yōu)路徑搜索方法[J]. 河北師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2008,32(5):590～593.

[9]王善坤,張治海.一種混合算法在游戲?qū)街械膽?yīng)用[J].電子設(shè)計(jì)工程，2016(19)：22～24.

[10]蔡方方,楊士穎,張小鳳等.雙層A_算法在游戲?qū)ぢ贩矫娴难芯縖J].微電腦應(yīng)用,2010,6(1):26～28.

[11]高慶吉,于詠生,胡丹丹.基于改進(jìn)A*算法的可行性路徑搜索及優(yōu)化[J].中國(guó)民航學(xué)院學(xué)報(bào)，2005,23(4):42～45.

A game path optimization application based on A* algorithm

SUN Yu-xia,FAN Zhi-jun

(College of Computer Science and Technology, Hubei Normal University,Huangshi 435002, China)

A* algorithm is the main search algorithm to solve the problem of pathfinding in the game, this paper discusses the basic principle of A* algorithm, explains its functions and defects in the process of finding the game, and based on A* algorithm adds a scheme of obstacle pretreatment, with a collection of destination, the role can avoid obstacles successfully, to reduce the extra memory space and run time used to search for unnecessary obstacles, and thus more intelligently to reach the target node. The simulation results show the effectiveness and feasibility of the algorithm.

A* algorithm; heuristic function; path optimization; preprocessing function

湖北省教育廳重點(diǎn)項(xiàng)目(D20162501)

2017—01—05

孫玉霞(1976— )，湖北黃岡人，碩士，副教授。

TP301.6

A

2096-3149(2017)02- 0072-05

10.3969/j.issn.2096-3149.2017.02.016