一種基于A星算法的游戲路徑優化應用

孫玉霞，樊質軍

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

一種基于A星算法的游戲路徑優化應用

孫玉霞，樊質軍

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

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

A*算法；啟發式函數；路徑優化；預處理功能

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

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

1 基于A*算法的搜索規劃

1.1 A*搜索算法

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

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

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

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

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

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

2)同時預處理start起點的周圍結點，一般在網格中是8個方位，并且把這8個方位的父節點設置為該start結點。

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

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

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

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

圖1 一般搜索算法的預處理搜索范圍

1.2 傳統啟發式A*搜索算法的不足

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

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

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

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

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

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

圖4 小人尋路時所遇障礙

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

2) 以兩個邊界結點坐標確定障礙位置并進行存儲

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

3) 添加destination列表，表示目標結點集合

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

圖6 傳統A*算法搜索范圍

3 實驗仿真分析

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

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

圖8 傳統A*算法在多障礙下的搜索范圍

4 結語

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

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

[2]陳和平,張前哨.A*算法在游戲地圖尋徑中的應用與實現[J].計算機應用與軟件,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]田翠華,許衛平,陳玉明.深度優先遍歷算法、隨機布點法及回溯法在迷宮游戲中的應用[J].河北北方學院學報(自然科學版), 2013, 29(3):19～24.

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

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

[9]王善坤,張治海.一種混合算法在游戲尋徑中的應用[J].電子設計工程，2016(19)：22～24.

[10]蔡方方,楊士穎,張小鳳等.雙層A_算法在游戲尋路方面的研究[J].微電腦應用,2010,6(1):26～28.

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