基于Silverlight網頁游戲的尋徑優化算法

李子強，宋余慶，陳健美，馮 江

江蘇大學 計算機科學與通信工程學院，江蘇 鎮江 212013

基于Silverlight網頁游戲的尋徑優化算法

李子強，宋余慶，陳健美，馮 江

江蘇大學 計算機科學與通信工程學院，江蘇 鎮江 212013

游戲，在國外被稱為“第九藝術”，是一種世界范圍內的通用語言。隨著微軟開發的Silverlight技術快速崛起，使得中國Silverlight網頁游戲迅速發展，越來越多的研究開始側重于如何尋求游戲角色更優的路徑搜索上來[1]。作為一種靈活的、高性價比的尋路算法，A*（A-Star，A*）搜索算法一直被游戲行業廣泛采用[2]。然而在Silverlight游戲這個對尋路實時性和路徑真實性要求較高的應用領域，A*仍有幾點不足之處[3]。諸如：標準的A*算法搜索比較費時，尤其是當尋路規模過大時，其時間消耗令玩家無法忍受；其次，直接利用算法得到的路徑往往曲曲折折，過于機械化。除此之外，游戲地圖中的特殊地形、目標結點可達不可達的判斷、地圖中障礙物位置的動態改變以及當某一狹窄路徑交通堵塞時如何改變尋路策略等都是需要考慮的問題[4]。本文通過分析現有算法應用于Silverlight網頁游戲中存在的不足，結合Silverlight游戲使用網格地圖的特點，在現有研究的基礎上，將光線跨越算法和動態關鍵點尋路技術應用于傳統的A*路徑搜索中，提出了一種基于Silverlight網頁游戲的尋徑優化算法。該算法在現有使用二叉堆存儲開啟列表并引入“父結點”指針的A*算法的基礎上，利用光線跨越算法減小傳統路徑搜索算法的規模，同時引入“動態關鍵點”的概念并結合光線跨越算法優化算法返回的路徑。實驗證明，該算法能夠極大地縮短尋徑時間，提高尋路單位的響應速度，且尋得的路徑更短、更平滑，有效提高了游戲角色的智能性，增強了Silverlight網頁游戲的實時效果，用戶體驗更加良好順暢。

1 啟發式A＊算法

1.1 A＊算法簡介

A*搜尋算法，俗稱A星算法，是一種在圖形平面上有多個結點的路徑，求出最低通過成本的啟發式動態規劃搜索算法[5]。常用于游戲中的NPC（非玩家控制角色）和線上游戲中BOT（機器人）的移動計算上。該算法像Dijkstra算法一樣，可以找到一條最短路徑；也像BFS（Breadth First Search，BFS）算法一樣，可以進行啟發式的搜索[4]。

在此算法中，設g(n)表示從起點到任意頂點n的實際距離，h(n)表示任意頂點n到目標頂點的估算距離。則A*算法的公式可表示為[6]：f(n)=g(n)+h(n)。該公式遵循以下特性：

（1）如果h(n)為0，只需求出g(n)，即求出起點到任意頂點n的最短路徑。此時，該求解轉化為單源最短路徑問題，即用Dijkstra算法可求解。

（2）如果h(n)≤“n到目標的實際距離”，則一定可以求出最優解，而且h(n)越小，需要計算的結點越多，算法效率越低。

1.2 A＊算法流程

本文使用引入了“父結點”指針的A*算法，該指針能夠有效地避免標準A*算法中存在的“回路問題”[7]。具體算法流程描述如下：

步驟1從起點S開始，把它作為待處理的結點存入一個“開啟列表”，開啟列表就是一個等待檢查結點的列表。

步驟2尋找起點S周圍可以到達的結點，將它們放入“開啟列表”，并設置它們的“父結點”為S。

步驟3從“開啟列表”中刪除起點S，并將其加入“關閉列表”。“關閉列表”中存放的都是不需要再次檢查的結點。

步驟4從“開啟列表”中選擇F值最低的結點C，把它從“開啟列表”中刪除，并放到“關閉列表”中。

步驟5檢查它所有相鄰并且可以到達的結點。如果這些結點還不在“開啟列表”里的話，將它們加入“開啟列表”，計算這些結點的G、H和F，并設置它們的“父結點”為C。

步驟6如果某個相鄰結點D已經在“開啟列表”里了，檢查如果用新的路徑（就是經過C的路徑）到達它的話，G值是否會更低一些。如果新的G值更低，那就把它的“父結點”改為目前選中的結點C，然后重新計算它的F值和G值（H值不需要重新計算，因為對于每個方塊，H值是不變的）。如果新的G值比較高，就說明經過C再到達D不是一個明智的選擇，因為它需要更遠的路，這時什么也不做。

步驟7重復步驟4～步驟6，直到目標格G已經在“開啟列表”，這時候路徑被找到，從目標格開始，沿著每一格的父結點移動直到回到起始格，這就是路徑。如若開啟列表已經空了，說明路徑不存在。

1.3 優化開啟列表的方法

A*算法中最緩慢的部分就是在開啟列表中尋找F值最低的結點（或者方格），其速度取決于地圖的大小。而在游戲地圖中可能有成百甚至上千的結點需要在某一時刻使用A*搜索，這樣反復搜索這么大的開啟列表會嚴重拖慢整個A*搜索的過程。然而這些時間在極大程度上受列表存儲方式的影響。在諸多開啟列表的存儲方式中，最簡單的存儲方法就是順序存儲每個結點，然后在每次需要提取最低耗費元素的時候遍歷整個列表。這雖能提供快速的插入速度，但由于每次都需要遍歷整個列表才能確定哪個F值是最低的，使得移除速度可能是最慢的。

對于這一問題的一般處理方法是通過保持開啟列表有序來提高搜索效率。這雖會花費一點預處理的時間，因為每次插入新的元素都需要為之選擇一個合適的位置。但是由于它的F值是最低的，所以只需移除第一個元素就可以，其大大加快了移除元素速度。其中可以保持開啟列表有序的方法有很多，比如選擇排序、冒泡排序和快速排序。以上最簡單的方法是，當需要添加新元素時，從列表頭起，用將要插入元素的F值與每個元素的F值比較，一旦找到相等或者更高的F值，就把新元素插入到列表中該元素的前面。另外，可以通過使用列表中所有元素的平均值來確定是從表頭還是從表尾開始處理。比平均F值低的元素從表頭開始處理，反之則從表尾開始處理，這樣可以節省一半的處理時間。以上方法雖然簡單，但是在時間上卻不如快速排序的時間消耗小。在快速排序中，首先從比較新元素和列表中間元素的F值開始，如果新元素的F值低，就和1/4處元素進行比較；如果還是更低，就比較它和1/8處的元素，以此類推，不斷地折半開啟列表進行比較，直到找到合適的位置為止。

在有序列表中，每個元素都按照由低到高或由高到低的順序保存在恰當的位置。這很有用，但是還不夠。事實上，不用關心數字A是否比B在更低的位置上，只要保證F值最低的元素存放在列表頂端便于訪問即可，至于列表的其他部分即使混亂也沒關系。列表的其他部分只有在需要另一個F值最低的元素的時候，才有必要保持有序。這正是二叉堆所具備的功能。二叉堆是一種特殊的堆，二叉堆是完全二叉樹或者近似完全的二叉樹。二叉堆滿足堆的特性，即父結點的鍵值總是大于或者等于任何子結點的鍵值。在二叉堆上可以進行插入結點，刪除結點，取出值最小的結點等基本操作。二叉堆和快速排序很類似，通常被那些苛求A*搜索速度時使用。實際經驗表明，二叉堆能提高平均尋路速度2～3倍，尤其對擁有大量結點的地圖的（如100×100結點或更多）提高更明顯[8]。鑒于二叉堆在提高A*算法搜索效率上的優勢，本文將采用二叉堆來優化開啟列表。

2 光線跨越算法

實現直線光柵化的方法之一是解直線的微分方程式，即

其有限積分近似解：

式中x1，y1和x2，y2是所求直線的端點坐標，yt是直線上某一步的初值。此公式表示所求直線上 y值的逐次遞歸關系。當此公式用于直線光柵化時，稱為數字微分分析器（Digital Differential Analyzer，DDA）。簡單的DDA選擇Δx或Δy中的較大者為一個光柵單位。

在二維光柵顯示器上，畫線算法在每一行（或列）上選擇最能代表直線的像素顯示，如圖1中的方框所示。而光線跨越算法必須選取光線穿過的每一個像素，新增選取的像素如圖1中的圓圈所示。注意在一些列中選取了多個像素。對DDA算法稍加修改即可用于光線跨越算法[9]。

圖1 光線跨越算法

在圖1中，方框表示由標準的DDA算法提取的像素，圓圈表示光線跨越算法新增的像素。該圖顯示了光線跨越水平（或垂直）平面進入體元的二維示意圖。注意，光線在三維均勻網絡中前進時，它在兩相鄰豎直平面間跨越的距離為常數，在圖2標記為Δx。同樣，它在兩相鄰水平平面間跨越的距離也為常數。在圖2標記為Δy。在三維中還存在第三個常數Δz。當光線在場景中進行時，它通過三個面之一進入體元。

圖2 沿光線兩相鄰體元間的x和y距離增量

在二維情況下，如果dx＜dy，則光線從垂直于x軸的平面進入下一體元；該體元可沿x軸定位，dx=dx+Δx。類似地，如果dy＜dx，則光線從垂直于y軸的平面進入下一體元；該體元可沿 y軸定位，dy=dy+Δy。在圖3中設體元由一個角點的索引(i,j,k)定位，則下一體元的索引為i=i+ix,j=j+jy,k=k+kz，其中ix、jy、kz取+1還是－1取決于光線的方向。

本文所用的二維光線跨越算法描述如下：

初始化ix,jy,Δx,Δy,dx,dy

圖3 沿著光線總的x和y距離

3 基于Silverlight網頁游戲的尋徑優化算法

在利用二叉堆優化開啟列表并引入“父結點”指針優化A*算法的基礎上，本文將之與光線跨越算法相結合并引入“動態關鍵點”的概念，提出了一種基于Silverlight網頁游戲的尋徑優化算法。該尋徑優化算法的具體步驟如下：

步驟1判斷目標結點G是否可達。若不可達，則直接返回路徑不存在，算法結束。

步驟2若目標結點為可達結點，則從起始點S到目標點G之間利用光線跨越算法計算光線經過的結點。若經過的所有結點都為可達結點，則路徑為點S和點G之間的線段，算法結束。

步驟3記錄S到G的第一個不可達結點的前一結點和最后一個不可達結點的后一結點，分別記為S′和G′。把當前結點S′作為起始點，并添加進開始列表Open中。將S′周圍所有可達或可通過結點，添加進Open表，并添加S′作為父結點。從開啟列表Open中刪除結點S′，并將S′添加進關閉列表Close中。

步驟4從二叉堆優化的Open表中選擇F最低結點（第一個），然后對選中的結點做如下處理：首先，將它從Open表刪除，然后添加進關閉列表Close中。然后，檢查所有相鄰結點，跳過那些在Close表中的或不可達的結點，添加進Open表。對還不在Open表中的（即新添加進去的），把選中結點作為新結點的父結點。如果某結點已經在Open表里，檢查現在這條路徑是否更好。即使用新的路徑到達它的話，G值是否會更低一些。如果不是，那就什么都不做；如果新的G值更低，那就把（選中結點）相鄰結點的父結點改為目前選中的結點，重新計算F和G值。F值由以下啟發函數得到，F=G+H。G按當前點相對于父結點的位置得到：若在父結點直角方向，則在父結點G值上加10，對角線方向加14；H采用曼哈頓啟發方式，即當前結點到目標結點之間水平和垂直結點數量之和（忽略對角線）。

步驟5重復步驟4，直到結束點G′被添加進Open表中，轉步驟6；或Open表為空，返回路徑不存在，算法結束。

步驟6從目標點開始，沿著每一結點的父結點移動回起始結點，記錄這條路徑并刪除路徑中方向相同的冗余結點。比如：有路徑結點路徑[0，1]、[0，2]、[0，3]和[1，2]，由于結點[0，1]、[0，2]與[0，1]、[0，2]、[0，3]方向相同，故刪除結點[0，2]。路徑結點可表現為[0，1]，[0，3]，[1，2]。記錄這些動態關鍵點。

步驟7把S和G添加進步驟6所獲得的關鍵點列表的開始和結尾，從S點開始，利用光線跨越算法，進一步過濾動態關鍵點列表。方法是以S點為當前結點，若某動態關鍵點與S間全為光線可達結點，則刪除此關鍵點與S點間的其他關鍵點；若不可達，則把該關鍵點作為當前結點。依次向下過濾，在達到G時結束過濾，則返回路徑為以上剩余關鍵點的折連線，算法結束。

算法的流程圖如圖4所示。

圖4 尋徑優化算法的流程圖

4 實驗結果

為了準確分析改進算法的尋路性能，本文將其與使用二叉堆存儲開啟列表并引入“父結點”指針的標準A*算法進行比較。實驗的硬件環境：CPU Intel?CoreTM2 Duo E7500@2.93 GHz，內存為2 GB。軟件環境：操作系統為Microsoft Windows XP Professional。開發平臺為.NET，語言為C#。測試地圖由地圖編輯器生成，為了更直觀地體現本文改進方案的360°全方位尋徑效果，地圖編輯器保留了結點的網格邊框。

4.1 尋徑效果測試

在地圖編輯器編輯生成的網格地圖上進行尋路實驗，尋路結果如圖5所示。圖5中，左上角S點為尋徑起點，目標點為右下角G點。在圖5中占據大部分地圖結點區域的白色底紋區域為角色可通行結點區域，分布于圖5左下和右上的多邊形結點區域以及處于圖5中心區域的“T”型結點區域為山丘、溝壑或人為設定的障礙物等邏輯占據的不可通行結點區域，相對處于下方的路徑SG為標準A*算法尋得的路徑，點M、N為本文改進算法獲得的動態關鍵點，其和起點S及終點G間的光線路徑SMNG為本文改進的A*算法尋得的路徑。

圖5 算法尋徑效果比較

從圖5可以看出，在尋徑起點和終點相同的前提下，由標準A*算法返回的路徑SG較為曲折，從根本上來講，這是由于現有A*算法從邏輯上限定了尋路方向為4方向（不包括對角）或者8方向（包括對角方向）的局限造成的。本文改進的A*尋路算法返回的路徑SMNG較為平滑，其返回的路徑沒有標準A*尋徑的4方向或8方向局限，為360°全方向路徑，而且路徑SMNG較路徑SG更短，因此本文改進方案的尋徑效果要明顯優于現有的使用二叉堆存儲開啟列表并引入“父結點”指針的標準A*算法。

由于光線跨越算法和動態關鍵點的使用，本文提出的改進的A*算法尋得的路徑沒有傳統A*算法尋徑4個方向或8個方向的局限性，為360°全方位路徑。算法尋得的路徑短，且避免了A*算法存在的回路問題，尋路單位也不會到達不可達區域，所尋路徑更優更貼近現實。在Silverlight網頁游戲中表現為游戲角色智能的提高，游戲玩家游戲體驗的提升。

4.2 尋徑時間測試

表1記錄了圖5中尋徑的時間，為了減小誤差，分別記錄了使用二叉堆存儲開啟列表并引入“父結點”指針的標準A*算法和本文改進算法在圖5上10次尋徑的時間消耗。

表1 算法尋徑消耗時間比較 ms

從表1可計算得知，在同等的硬件條件和軟件環境下，標準A*算法尋徑圖5路徑SG的平均時間為1.4 ms，本文改進算法尋徑圖5路徑SMNG的平均時間為0.4 ms。

圖5的尋徑規模為64×41結點，在本文測試環境下為尋徑屏幕左上角到右下角（飛利浦190CW9顯示器19 in，分辨率為1 440×900），由于單次的尋徑起點和終點一般不會超出整個客戶端屏幕鼠標可點擊區域，因此該測試用例可基本代表Silverlight網頁游戲尋路的需求。從表1的尋路時間分析可以看出，在同等的硬件條件和軟件環境下，改進算法的尋徑時間消耗遠遠小于標準A*算法的時間消耗。在Silverlight游戲通常每秒6幀（每幀166.7 ms）的情況下，尋徑時間消耗遠遠小于幀切換的時間消耗，因此不會出現幀補償導致的畫面跳躍現象（游戲中表現為畫面的卡滯），能夠很好滿足游戲實時性需求。

從上面的實驗結果中可以看出，改進后的算法返回的路徑沒有現有A*算法8方向的局限性，其返回的路徑為360°全方向路徑，較之標準的A*算法返回的8方向路徑短且平滑，可使得Silverlight游戲角色尋徑更加自然，能有效提高游戲角色的智能性。同時，改進后的算法在尋路時間消耗上要遠遠小于現有的使用二叉堆存儲開啟列表并引入“父結點”指針的標準的A*算法，游戲角色尋路時間要遠遠小于游戲畫面的幀切換時間。實驗證明該方法切實可行。

5 結束語

本文在分析Silverlight網頁游戲中尋路算法現有研究的基礎上，結合Silverlight網頁游戲地圖的特點，將光線跨越算法引入傳統路啟發式徑搜索算法并引入“動態關鍵點”對現有的尋路算法進行了改進，提出了一種基于Silverlight網頁游戲的尋徑優化算法。重點解決了現有算法應用于Silverlight網頁游戲尋路時時間消耗大和尋得的路徑不夠平滑優化這兩個問題。實驗結果表明，該路徑搜索算法減少了尋路的時間消耗，尋得的路徑更短更平滑。該算法能夠滿足Silverlight網頁游戲的尋路實時性和路徑真實性需求，提高游戲角色的智能性和游戲的可玩性。且隨著游戲尋路規模的增大，改進后的算法對效率的提升更顯著。

[1]Xu Z G，Van Doren M.A museum visitors guide with the A～* pathfinding algorithm[C]//Proceedingsof2011 IEEE International Conference on Computer Science and Automation Engineering.Shanghai：[s.n.]，2011.

[2]BaiWenfeng，Han Lina.An improvedA～* algorithm in path planning[C]//Proceedings of 2010 International Conference on Computer，Mechatronics，Control and Electronic Engineering.Changchun：[s.n.]，2010.

[3]高曄，邢毅.Vega平臺下三維并行A～*算法的設計與實現[J].計算機工程與應用，2012，48（7）：231-233.

[4]周小鏡.基于改進A*算法的游戲地圖尋徑的研究[D].重慶：西南大學，2011.

[5]Russell S，Norvig P.Artificial intelligence：a modern approach[M]. [S.l.]：Prentice Hall，2002.

[6]龔道雄，劉翔.迷宮搜索算法的比較研究[J].計算機應用研究，2011（28）：4433-4436.

[7]許珂樂.網絡游戲中的尋路算法初探[EB/OL].（2011-09-28）. [2012-04-26].http：//www.cnki.net/kcms/detail/15.1211.f.20110928. 2034.038.html.

[8]詹海波.人工智能尋路算法在電子游戲中的研究和應用[D].武漢：華中科技大學，2006.

[9]Rogers D F.計算機圖形學的算法基礎[M].石教英，彭群生，譯.北京：機械工業出版社，2002.

LI Ziqiang,SONG Yuqing,CHEN Jianmei,FENG Jiang

School of Computer Science and Telecommunication Engineering,Jiangsu University,Zhenjiang,Jiangsu 212013,China

Aimed to the problems of A*algorithm search in Silverlight web games,such as the path optimization problem and the time-consuming problem,this paper associates the light across algorithm with the A*algorithm search that uses the light across algorithm and the parent node pointer,and proposes an advanced algorithm search in Silverlight web games.The algorithm is based on the existing research results and uses the light across algorithm to reduce the A*algorithm search scale.Meanwhile,it introduces the dynamic critical point technique that combined with the light across algorithm to optimize the path.The experiment in the grid map that used in Silverlight web games proves that this algorithm can effectively find out an optimal practical path,according to the prevailing conditions set by the system.It can raise the search efficiency and reduce the complexity of the planning issue and improve the playability.

A*algorithm;light across algorithm;dynamic critical points;heuristic searching;path search;Silverlight web games

為了解決A*路徑搜索算法在Silverlight網頁游戲中的搜索費時和路徑曲折等問題，在結合光線跨越算法和引入父結點指針的二叉堆存儲開啟列表的A*算法的基礎上，提出了一種基于Silverlight網頁游戲的尋徑優化算法。該算法在現有研究的基礎上使用光線跨越算法減小A*算法搜索規模，同時將動態關鍵點技術與光線跨越算法結合來優化算法返回的路徑。將該算法在游戲所使用的網格地圖中進行實驗，實驗結果表明，該算法能夠有效地根據系統設定的通行條件尋找出一條最優的實際可行的路徑，同時縮短尋路的時間消耗和所尋的路徑長度，提高游戲的可玩性。

A*算法；光線跨越算法；動態關鍵點；啟發式搜索；地圖尋徑；Silverlight網頁游戲

A

TP301.6

10.3778/j.issn.1002-8331.1206-0370

LI Ziqiang,SONG Yuqing,CHEN Jianmei,et al.Advanced algorithm search in Silverlight web game.Computer Engineering and Applications,2013,49（5）：59-63.

教育部博士點基金（No.20113227110010）；江蘇省高校自然基金（No.10KJB520004）；江蘇省軟件與集成電路專項基金（No.2009[100]）；江蘇省普通高校研究生科研創新計劃（No.CXZZ11_0575）。

李子強（1987—），男，碩士研究生，主要研究方向：網絡游戲設計與開發、醫學圖像處理；宋余慶（1959—），男，教授，博士生導師，主要研究方向：網絡游戲設計與開發、醫學圖像處理；陳健美（1962—），女，教授，主要研究方向：數據挖掘、醫學圖像；馮江（1987—），男，碩士研究生，主要研究方向：網絡游戲設計與開發、醫學圖像。E-mail：nano_li@126.com

2012-06-25

2012-10-12

1002-8331（2013）05-0059-05

CNKI出版日期：2012-10-31 http://www.cnki.net/kcms/detail/11.2127.TP.20121031.0947.014.html