A*算法在游戲尋路中的應用

胡正紅，張俊花

(太原師范學院計算機系，山西 太原 030012)

隨著科技的發(fā)展，人工智能技術應用在許多游戲開發(fā)過程中以提高游戲的可玩性。路徑探索是游戲開發(fā)過程中經(jīng)常遇到的問題，通?？梢圆捎脧V度優(yōu)先搜索算法或深度優(yōu)先搜索算法來實現(xiàn)路徑搜索，但這些常用搜索算法在“連連看”游戲尋路中存在數(shù)據(jù)冗余、運行時間長的缺點。針對該游戲路徑搜索的特點，首先我們對常見的廣度優(yōu)先搜索算法進行詳細分析與研究，結合游戲中的應用情況，研究A* 搜索算法和啟發(fā)式搜索技術，設計估價函數(shù)，改進A*算法用于游戲尋路。

1 廣度優(yōu)先搜索算法在游戲中的應用

“連連看”游戲規(guī)則是:在有限的時間內，將圖案相同的兩張牌用三根以內的直線連在一起就可以消除，只要把所有的圖案全部消完即可獲得勝利［1］。

采用廣度優(yōu)先搜索，將目標函數(shù)修改為從一個點到另一個點的轉彎次數(shù)，首先把圖形Start (x1，y1)壓入隊列。然后擴展圖形Start(x1，y1)可以直線到達的節(jié)點，用集合S0=Find(x1，y1)表示這些節(jié)點都可通過轉彎數(shù)為0的路徑到達，如果圖形Target(x2，y2)包含在集合S0 中，結束搜索。

否則，繼續(xù)擴展集合S0 中空格可以直線到達的節(jié)點，用集合S1={Find(p)|p∈S0}表示，令S1’=S1－S0(S1 包含了S0)，表示S1’中的節(jié)點和圖形Start(x1，y1)之間可以通過轉彎數(shù)目為1的路徑連起來。如果圖形B(x2，y2)在S1’中，則圖形S，T 之間可以用轉彎數(shù)目為1的路徑連接，結束搜索。

否則，繼續(xù)展開S1’集合中的空格可以直線到達的節(jié)點，用集合S2=Find{Find(p)|p∈S1’}表示，令S2’=S2－S0－S1=S2－S0－S1’(S2 包含了S0和S1)，集合S2’是圖形A(x1，y1)可以通過轉彎數(shù)目為2的路徑到達的格子。如果圖形T(x2，y2)在集合S2’中，則圖形A，B 之間可以用轉彎數(shù)目為2的路徑連接，否則圖形A，B 之間不能通過轉彎小于3的路徑連接。

2 A*算法的估價函數(shù)設計

A*算法具備很多優(yōu)點。首先，如果起點和終點之間存在有效路徑，A* 就一定能夠找到;其次，只要H(n)是可納的，它就一定能找到一條最短路徑;第三，A*算法是啟發(fā)式搜索算法中搜索狀態(tài)最少的一種算法，它使啟發(fā)式函數(shù)得到了最有效的應用［2］。

啟發(fā)式搜索的核心是估價函數(shù)F(n)，“連連看”中連線不能從尚未消去的圖案上經(jīng)過，節(jié)點只能在四個方向移動，兩個相同圖案之間的連線不能超過兩個彎。

因此估價函數(shù)中，需要考慮當前格Current 到目標格Target的移動耗費，當前格Current 與開始格Start的轉彎數(shù)，用估價函數(shù)表示為［3］:

在“連連看”游戲中，格子S的移動方向分水平上、水平下、豎直上、豎直下四個方向，每個格子對應著有圖案、無圖案兩種狀態(tài)。

設計二維數(shù)組map［Rows］［Cols］表示對應的方格是否有圖狀態(tài)，當數(shù)組元素值取1 表示該位置有圖，取0 表示無圖。

估價函數(shù)F(n)的取值設定:

G(n):移動的距離。結合游戲的要求，這里設定沿著四個方向移動，移動位置上有圖則距離值為無窮大，這樣的格子不考慮擴展，如果無圖距離值為1，如圖1所示。

圖1 G值的設定

H(n):指定格子到目標格橫向走的步數(shù)與縱向走的步數(shù)和;例如T(Tx，Ty)是終點，C(Cx，Cy)是當前點，則:h(n)=|Tx－Cx|+ |Ty－Cy|。

C(n):起點Start 到指定格子的轉彎數(shù)，直線連接C 取值為0，轉一次彎，C值為1;轉兩次彎，C值為2;轉彎數(shù)為3，估價函數(shù)無窮大。

例如:開始點S 與終點T 在一條橫線上，周圍的格子狀態(tài)如圖1所示;計算S 點的四方向節(jié)點的F(n)，上方和左方的節(jié)點估價函數(shù)無窮大，右方節(jié)點的f(n)=1+3+0，下方節(jié)點的f(n)=1+5+0;計算過程如圖2－圖4所示。

圖2 初始狀態(tài)

圖3 G值的計算

圖4 H值的計算

展開右方F值=4的點，計算其右節(jié)點估價函數(shù)f=4+(1+2+0)=7，如圖5所示。

展開F值=7的節(jié)點，計算出其右節(jié)點估價函數(shù)f=7+(1+1+0)=9，如圖6所示。

展開F=9的節(jié)點，終點就在它的展開節(jié)點中了，完成了最短路徑工作。

圖5 估價表示

圖6 展開f=4的節(jié)點

圖7 展開f=7的節(jié)點

3 A*算法的應用設計

A*算法是一種典型的啟發(fā)式搜索算法，它除了利用上述的啟發(fā)函數(shù)來對搜索過程中的每一個節(jié)點進行評估，另外它還必須有兩個表:Open 表和Close 表［4］。

Open 表由未考察的結點組成，保存了打開節(jié)點的F值;每次從Open 表中取F值最小的節(jié)點展開后續(xù)節(jié)點。

Close 表由已考察的結點組成，將已展開的節(jié)點加入其中(不包括終點)。

結合“連連看”的要求，A*算法實現(xiàn)的過程可以用偽代碼描述，假設起始節(jié)點為Start，目標節(jié)點為Target，其中Current是每次被考察的節(jié)點，臨時節(jié)點Temp 代表Current的四方向上的有效子結點，所謂有效子結點就是指在“連連看”中沒有圖案的格子。當Current 等于Target 時搜索成功。

A*算法作為“連連看”中的尋路算法，用偽代碼表示如下:

4 A*算法在“連連看”中的應用

4.1 數(shù)字化運動方向

A*算法的數(shù)據(jù)結構設置，程序設計有其一定的模式，這里針對“連連看”，給出A*算法的實現(xiàn)代碼。

“連連看”中節(jié)點的運動方向是4個，可以設置一個常量數(shù)組，把每個方向的移動坐標變動量存入數(shù)組，定義類的方法，傳入?yún)?shù):起始點坐標和目標點坐標:

圖8 數(shù)字化方向

4.2 計算轉彎

“連連看”中計算節(jié)點的轉彎數(shù)很關鍵，因此定義類方法GetCrossing，傳遞節(jié)點的ID 號，返回起點到節(jié)點的轉彎數(shù)。

4.3 尋路設計

展開節(jié)點后，定義類方法FindPath 傳遞相關參數(shù)計算節(jié)點坐標，記錄節(jié)點ID 號，增加節(jié)點到OpenList，計算G、H、E、F值，然后把展開的節(jié)點加入到whichNode 中。

5 算法分析

假設游戲地圖n 行m 列，設N=m* n，由于每個節(jié)點做為擴展節(jié)點進入Open 表最多一次，因此Open 表中最多處理N個展開節(jié)點。擴展每個節(jié)點需要O(1)的時間，因此算法最多耗時O(N)。構造相應的最短路徑需要O(L)的時間，L是最短路徑的長度。當節(jié)點數(shù)為N 時，廣度優(yōu)先搜索算法的復雜度為O(N* N)，A*算法的復雜度為O(N+L)，計算量不會隨著節(jié)點的展開迅速增加，只要起點和終點之間存在有效路徑，A*算法就能夠快速找到。

6 總結

本文將A*算法應用在“連連看”游戲尋路搜索上，給出了改進的估價函數(shù)、算法運行流程，能夠用O(N+L)的時間完成最短路徑搜索，很好地適應游戲的要求。A*算法結合了啟發(fā)式方法和形式化方法，為許多即時戰(zhàn)略游戲所用到，可以修改方向參數(shù)，對于游戲中八方向移動搜索路徑也具有一定的實際應用價值。

［1］胡正紅.一種尋路算法在游戲中的應用［J］.山西電子技術，2009(6):53－54.

［2］陳和平，張前哨.A算法在游戲地圖尋徑中的應用與實現(xiàn)［J］.計算機應用與軟件，2005(12):118－120.

［3］Hu zhenhong，Jinli.Application and Implementation of A* Algorithm in Picture Matching Path－finding［G］.In:2010 International Conference on Computer Application and System Modeling(ICCASM 2010)，Taiyuan，China，2010:224－227.

［4］陳煉，鄧少波，萬芳.A算法在梵塔問題中的應用［J］.計算機工程，2005(4):168－170.