摘 要：本文依據(jù)A*算法的特點分析了影響A*效率的因素，通過分析二叉堆的特點并且結(jié)合實際應(yīng)用情況，在A*算法中引入二叉堆算法，以此達到提高A*算法效率的目的。實驗結(jié)果最后證明了基于二叉堆的A*算法比初始的A*具有更快的執(zhí)行速度。

關(guān)鍵字：A*算法；二叉堆優(yōu)化；地圖尋路；人工智能

中圖分類號：TP311.52

游戲在業(yè)界被稱為第九藝術(shù)，成功的游戲更會受到全球玩家推崇。隨著移動互聯(lián)網(wǎng)技術(shù)的應(yīng)用以及和中國移動網(wǎng)絡(luò)3G、4G增值等業(yè)務(wù)迅速發(fā)展，手機游戲行業(yè)開始進入了高速發(fā)展時期。在游戲軟件開發(fā)中，人工智能的設(shè)計是一個重要而又復(fù)雜的模塊，將基于人工智能的尋路算法運用于電子游戲則是現(xiàn)階段游戲開發(fā)中最基本問題之一。物體按照某種指定目的地的方式移動其就要求程序必須能夠找到一條從起點到目標(biāo)點的最佳路徑，這條路徑應(yīng)該是繞過障礙物并且到達目的地的最短的路徑，完成這個任務(wù)最常用的算法就是A*算法。A*作為一種高性價比的尋路算法一直被游戲行業(yè)所廣泛使用[1]，很多客戶端游戲和大型網(wǎng)頁游戲中的尋路算法都基于A*算法如：英雄聯(lián)盟，魔獸世界，夢幻飛仙等。但是由于手機游戲運行軟件條件和硬件不佳等原因，傳統(tǒng)的A*算法也急需改進，以此提高尋路效率。

1 A*算法簡介

A*算法是把常規(guī)方法如Dijkstra算法和啟發(fā)式算法結(jié)合在一起的折中算法。相比于Dijkstra算法，A*算法是啟發(fā)式搜索算法中的一種典型算法。f′（n）=g′（n）+h′（n）是A*算法估價函數(shù)表示方法[2]。在這個函數(shù)里面，g′（n）是起點到節(jié)點n的最短路徑值，h′（n）是n到目標(biāo)節(jié)點的最佳路徑的估價值，f（n）是從初始點經(jīng)由節(jié)點n到目標(biāo)點的估價函數(shù)。由于f′（n）是無法預(yù)先知道的，所以我們通過用h′（n）做h（n）近似值和g′（n）做g（n）的近似值方式去求得f（n）的近似值，其中必須滿足g′（n）

A*算法基本執(zhí)行過程可以如下表示：

FindPath（）

{

初始化兩個表，OPEN表用于保存已經(jīng)探知卻還沒有搜索的節(jié)點，CLOSE表保存已訪問過的節(jié)點。將最開始的初始節(jié)點放入OPEN表中；

while（OPEN！=NULL）

{

在OPEN表中選擇估價值最小的節(jié)點n；

if（n節(jié)點==目標(biāo)節(jié)點）

{

break；//尋路成功，方法結(jié)束

}

for（當(dāng)前節(jié)點n的每個子節(jié)點M）

{

通過估計函數(shù)計算M的估價值；

if（M in OPEN）

{

if（M的估價值

{

把n設(shè)置為M的父節(jié)點；

重新計算OPEN表中的估價值；//取最小路徑的估價值

}

}

if（M in CLOSE）

{

continue；

}

if（M not in both）

{

把n設(shè)置為M的父節(jié)點；

求出M的估計值；

將M插入OPEN表中；//還沒有排序

}

}//for循環(huán)結(jié)束

將n節(jié)點插入CLOSE表中；

通過估價值將OPEN表中的每個節(jié)點進行排序；

}//while輪詢結(jié)束

Print（CLOSE）；//輸出路徑

}//方法結(jié)束

通過A*算法，只要有一條有效路徑存在于起點和終點之間，A*算法能夠有效的幫助我們將它找到。A*算法是現(xiàn)有啟發(fā)式搜索中搜索狀態(tài)最少算法之一，人們通過它，讓啟發(fā)式函數(shù)得到了最有效的應(yīng)用[3]。在分析了上述算法的復(fù)雜度后，可以知道：A*算法不得不頻繁對OPEN表中節(jié)點估價值進行排序，并且維護OPEN表和CLOSE表，尤其每次都要對OPEN表中的節(jié)點再次進行新的排序，其中最緩慢的部分就是在OPEN列表中尋找F值最低的節(jié)點或者方格。當(dāng)?shù)貓D更大時，反復(fù)搜索這么大的列表會嚴(yán)重拖慢整個過程。這顯然無法滿足游戲?qū)崟r性要求較高的特點。在這一需求下，本文將在算法中引入二叉堆（BinaryHeap），再進行節(jié)點排序，從而提高算法尋找F值的效率。

2 二叉堆（BinaryHeap）簡介

二叉堆，其本質(zhì)就是二叉樹以“堆”的形式存在，這種特殊的二叉樹結(jié)構(gòu)是A*算法的最佳拍檔，它能和A*算法形成優(yōu)勢互補，更好的滿足開啟列表的排序需求。二叉堆和快速排序（Quick Sort）很像。平均來說，二叉堆可以提高尋路執(zhí)行效率的2-3倍，對于一個包含大量節(jié)點的地圖（200×200節(jié)點或者更多）來說，優(yōu)化效果尤為明顯。

二叉堆是由一組元素組成的數(shù)據(jù)結(jié)構(gòu)，其中最大或者最?。ㄈQ于需要）的元素在堆頂端。一般情況，我們把最小元素放在堆頂端[4]。頂端的元素有兩個子節(jié)點，每個節(jié)點的F值等于，或者略高于這個元素。依次類推。一個堆結(jié)構(gòu)可能是下面這個樣子：

圖1

當(dāng)然，從二叉堆的存儲結(jié)構(gòu)上講，我們可以簡單的把它存儲在一個一維數(shù)組中。在這個數(shù)組中，數(shù)組的第一個元素（是下標(biāo)1而不是0）就是堆頂端的元素。數(shù)組中下標(biāo)為2和3的位置將存放堆頂端元素的兩個子節(jié)點。4-7的位置將存放這梁節(jié)點的4個子節(jié)點，以此類推。

圖2

為了讓我們的堆有效，我們把最底層之上的每一行都進行填充。可以把任意數(shù)值的元素填在最底層，同時將新的元素按照從左到右的順序依次添加。

3 基于二叉堆的A*算法

通過之前的解釋，我們用數(shù)組的存儲結(jié)構(gòu)去維護堆，則對于堆Heap[1…n]有：Heap[i]≤Heap[2i]，Heap[i]≤Heap[2i+1]。

在C語言中，將數(shù)組當(dāng)中的元素定為一個NODE結(jié)構(gòu)體：

Typedefstuct node

{

char*nodeName；//節(jié)點名

float nodeCost；//估價值

}NODE；

因此，將改進后的用“二叉堆”進行節(jié)點排序算法可以用一下偽代碼表示：

buildHeap（NODEnode[]，inti，intnodeNum）//建堆

{

int t=node[i].nodeCost，j=i+1；

while（j<=nodeNum）

{

if（j

if（t

{

node[j/2]=node[j]；node[j]=t；j=j*2；}

}

}

HeapSort（NODEa[]，intnum）//堆排序

{

inti；NODEtempNode；

for（i=num；i>0；i--）

{

tempNode=a[i]；a[i]=a[1]；a[1]=tempNode；

buildHeap（a，1，i-1）；//重新生成堆

}

}

總所周知，堆排序的平均時間復(fù)雜度在所有排序算法中是最低的，僅為O（nlogn）。將二叉堆引入A*算法之后，對OPEN表的操作也就變成了對二叉堆的排序操作，通過利用二叉堆進行排序，這樣將對傳統(tǒng)的A*算法效率有很大程度上的提高。

4 實驗結(jié)果分析與評價

本文為了便于分析和比較兩種方法的優(yōu)劣，并且保持同等條件，在同一電腦下（Intel CORE i5.2G內(nèi)存）中，對算法進行多次測試，取其平均值。主應(yīng)用程序先加載地圖資源和游戲角色文件，地圖文件由自主開發(fā)的地圖編輯器（MapEditor）產(chǎn)生，在調(diào)用地圖編輯器之后，圖片每一個像素均被切割成一個單元格，該地圖共有1000000（1百萬）個單元格。在程序中，用一個字節(jié)表示一個單元格。按照常用的計算方法，對于估價函數(shù)，選取h′（n）為節(jié)點到目標(biāo)點之間的曼哈頓距離（ManhattanDistance）[5]乘以10，得到以下公式：Mij=10（|xi-xj|+|yi-yj|）。

優(yōu)化前后的運行時間數(shù)據(jù)如下表（C語言）：

表1 優(yōu)化前后的結(jié)果對比

算法起點終點搜索節(jié)點數(shù)路徑長消耗時間（ms）

傳統(tǒng)

A*46.75110.752046158389

78.4831.4863284157

改進

A*46.75110.752046158168

78.4831.486328496

由表中數(shù)據(jù)可知，在引入二叉堆后的A*算法較之于傳統(tǒng)方法，在同等路徑的情況下能夠提高1-2倍左右的執(zhí)行效率。很明顯，二叉堆更加適合用于游戲地圖尋路。

5 結(jié)束語

在分析傳統(tǒng)A*算法在尋路算法的運用情況下，本文將二叉堆數(shù)據(jù)結(jié)構(gòu)引入到該算法中。通過大量實驗結(jié)果來證實：原算法的執(zhí)行效率在改進后得到了大幅提高，能夠滿足現(xiàn)在移動端游戲?qū)Φ貓D自動尋路的高性能要求?？紤]到遇到多個同時發(fā)生尋路需求的情況，還可以通過將多個尋路需求通過形成線性隊列，并且結(jié)合多線程的方法對線性隊列進行壓棧（Push），彈出（Pop），計算操作，便可以滿足當(dāng)下大型多人在線角色扮演游戲（MMORPG）的實際應(yīng)用要求。而如何提高在多線程和網(wǎng)絡(luò)環(huán)境下改進算法的執(zhí)行效率是下一步研究方向[6]。

參考文獻：

[1]RabinS，莊越挺.吳飛，譯.人工智能游戲編程真言[M].北京：清華大學(xué)出版社，2005.

[2]馬少平.人工智能[M].北京：清華大學(xué)出版社，2004：32-34.

[3]李遠靜，莫誠生.Windows游戲編程[M].北京：清華大學(xué)出版社，2004.

[4]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）（第二版）[M].北京：清華大學(xué)出版社，2005.

[5]閻平凡，張長水.人工神經(jīng)網(wǎng)絡(luò)與模擬進化計算[M].北京：清華大學(xué)出版社，2000.

作者簡介：馮俊翔（1993.03-），四川達州人，本科，研究方向：數(shù)字媒體研究與應(yīng)用。

作者單位：重慶郵電大學(xué)軟件工程學(xué)院，重慶 400065