基于Silverlight網(wǎng)頁游戲的尋徑優(yōu)化算法

李子強(qiáng)，宋余慶，陳健美，馮 江

江蘇大學(xué) 計算機(jī)科學(xué)與通信工程學(xué)院，江蘇 鎮(zhèn)江 212013

基于Silverlight網(wǎng)頁游戲的尋徑優(yōu)化算法

李子強(qiáng)，宋余慶，陳健美，馮 江

江蘇大學(xué) 計算機(jī)科學(xué)與通信工程學(xué)院，江蘇 鎮(zhèn)江 212013

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

1 啟發(fā)式A＊算法

1.1 A＊算法簡介

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

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

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

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

1.2 A＊算法流程

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

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

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

步驟3從“開啟列表”中刪除起點S，并將其加入“關(guān)閉列表”?！瓣P(guān)閉列表”中存放的都是不需要再次檢查的結(jié)點。

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

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

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

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

1.3 優(yōu)化開啟列表的方法

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

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

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

2 光線跨越算法

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

其有限積分近似解：

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

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

圖1 光線跨越算法

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

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

在二維情況下，如果dx＜dy，則光線從垂直于x軸的平面進(jìn)入下一體元；該體元可沿x軸定位，dx=dx+Δx。類似地，如果dy＜dx，則光線從垂直于y軸的平面進(jìn)入下一體元；該體元可沿 y軸定位，dy=dy+Δy。在圖3中設(shè)體元由一個角點的索引(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網(wǎng)頁游戲的尋徑優(yōu)化算法

在利用二叉堆優(yōu)化開啟列表并引入“父結(jié)點”指針優(yōu)化A*算法的基礎(chǔ)上，本文將之與光線跨越算法相結(jié)合并引入“動態(tài)關(guān)鍵點”的概念，提出了一種基于Silverlight網(wǎng)頁游戲的尋徑優(yōu)化算法。該尋徑優(yōu)化算法的具體步驟如下：

步驟1判斷目標(biāo)結(jié)點G是否可達(dá)。若不可達(dá)，則直接返回路徑不存在，算法結(jié)束。

步驟2若目標(biāo)結(jié)點為可達(dá)結(jié)點，則從起始點S到目標(biāo)點G之間利用光線跨越算法計算光線經(jīng)過的結(jié)點。若經(jīng)過的所有結(jié)點都為可達(dá)結(jié)點，則路徑為點S和點G之間的線段，算法結(jié)束。

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

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

步驟5重復(fù)步驟4，直到結(jié)束點G′被添加進(jìn)Open表中，轉(zhuǎn)步驟6；或Open表為空，返回路徑不存在，算法結(jié)束。

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

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

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

圖4 尋徑優(yōu)化算法的流程圖

4 實驗結(jié)果

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

4.1 尋徑效果測試

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

圖5 算法尋徑效果比較

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

由于光線跨越算法和動態(tài)關(guān)鍵點的使用，本文提出的改進(jìn)的A*算法尋得的路徑?jīng)]有傳統(tǒng)A*算法尋徑4個方向或8個方向的局限性，為360°全方位路徑。算法尋得的路徑短，且避免了A*算法存在的回路問題，尋路單位也不會到達(dá)不可達(dá)區(qū)域，所尋路徑更優(yōu)更貼近現(xiàn)實。在Silverlight網(wǎng)頁游戲中表現(xiàn)為游戲角色智能的提高，游戲玩家游戲體驗的提升。

4.2 尋徑時間測試

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

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

從表1可計算得知，在同等的硬件條件和軟件環(huán)境下，標(biāo)準(zhǔn)A*算法尋徑圖5路徑SG的平均時間為1.4 ms，本文改進(jìn)算法尋徑圖5路徑SMNG的平均時間為0.4 ms。

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

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

5 結(jié)束語

本文在分析Silverlight網(wǎng)頁游戲中尋路算法現(xiàn)有研究的基礎(chǔ)上，結(jié)合Silverlight網(wǎng)頁游戲地圖的特點，將光線跨越算法引入傳統(tǒng)路啟發(fā)式徑搜索算法并引入“動態(tài)關(guān)鍵點”對現(xiàn)有的尋路算法進(jìn)行了改進(jìn)，提出了一種基于Silverlight網(wǎng)頁游戲的尋徑優(yōu)化算法。重點解決了現(xiàn)有算法應(yīng)用于Silverlight網(wǎng)頁游戲?qū)ぢ窌r時間消耗大和尋得的路徑不夠平滑優(yōu)化這兩個問題。實驗結(jié)果表明，該路徑搜索算法減少了尋路的時間消耗，尋得的路徑更短更平滑。該算法能夠滿足Silverlight網(wǎng)頁游戲的尋路實時性和路徑真實性需求，提高游戲角色的智能性和游戲的可玩性。且隨著游戲?qū)ぢ芬?guī)模的增大，改進(jìn)后的算法對效率的提升更顯著。

[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～*算法的設(shè)計與實現(xiàn)[J].計算機(jī)工程與應(yīng)用，2012，48（7）：231-233.

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

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

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

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

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

[9]Rogers D F.計算機(jī)圖形學(xué)的算法基礎(chǔ)[M].石教英，彭群生，譯.北京：機(jī)械工業(yè)出版社，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網(wǎng)頁游戲中的搜索費時和路徑曲折等問題，在結(jié)合光線跨越算法和引入父結(jié)點指針的二叉堆存儲開啟列表的A*算法的基礎(chǔ)上，提出了一種基于Silverlight網(wǎng)頁游戲的尋徑優(yōu)化算法。該算法在現(xiàn)有研究的基礎(chǔ)上使用光線跨越算法減小A*算法搜索規(guī)模，同時將動態(tài)關(guān)鍵點技術(shù)與光線跨越算法結(jié)合來優(yōu)化算法返回的路徑。將該算法在游戲所使用的網(wǎng)格地圖中進(jìn)行實驗，實驗結(jié)果表明，該算法能夠有效地根據(jù)系統(tǒng)設(shè)定的通行條件尋找出一條最優(yōu)的實際可行的路徑，同時縮短尋路的時間消耗和所尋的路徑長度，提高游戲的可玩性。

A*算法；光線跨越算法；動態(tài)關(guān)鍵點；啟發(fā)式搜索；地圖尋徑；Silverlight網(wǎng)頁游戲

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]）；江蘇省普通高校研究生科研創(chuàng)新計劃（No.CXZZ11_0575）。

李子強(qiáng)（1987—），男，碩士研究生，主要研究方向：網(wǎng)絡(luò)游戲設(shè)計與開發(fā)、醫(yī)學(xué)圖像處理；宋余慶（1959—），男，教授，博士生導(dǎo)師，主要研究方向：網(wǎng)絡(luò)游戲設(shè)計與開發(fā)、醫(yī)學(xué)圖像處理；陳健美（1962—），女，教授，主要研究方向：數(shù)據(jù)挖掘、醫(yī)學(xué)圖像；馮江（1987—），男，碩士研究生，主要研究方向：網(wǎng)絡(luò)游戲設(shè)計與開發(fā)、醫(yī)學(xué)圖像。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