孫玉霞，樊質(zhì)軍

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

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

孫玉霞，樊質(zhì)軍

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

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

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

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

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

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

1.1 A*搜索算法

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

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

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

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

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

1)從起點start開始, 把它作為一個結(jié)點首先放入open集合列表中。

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

3) 當(dāng)周圍結(jié)點搜索完畢后，將start結(jié)點從open集合列表中刪除，同時放入close集合列表中。

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

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

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

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

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

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

圖3 A*算法遇障礙時搜索范圍

2 針對A*算法不足的改進方案及思路

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

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

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

圖4 小人尋路時所遇障礙

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

2) 以兩個邊界結(jié)點坐標(biāo)確定障礙位置并進行存儲

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

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

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

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

3 實驗仿真分析

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

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

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

4 結(jié)語

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

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

[2]陳和平,張前哨.A*算法在游戲地圖尋徑中的應(yīng)用與實現(xiàn)[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)先遍歷算法、隨機布點法及回溯法在迷宮游戲中的應(yīng)用[J].河北北方學(xué)院學(xué)報(自然科學(xué)版), 2013, 29(3):19～24.

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

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

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

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

[11]高慶吉,于詠生,胡丹丹.基于改進A*算法的可行性路徑搜索及優(yōu)化[J].中國民航學(xué)院學(xué)報，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

湖北省教育廳重點項目(D20162501)

2017—01—05

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

TP301.6

A

2096-3149(2017)02- 0072-05

10.3969/j.issn.2096-3149.2017.02.016