A*算法的改進(jìn)及其在移動(dòng)端游戲中的運(yùn)用

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

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

中圖分類號：TP311.52

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

1 A*算法簡介

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

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

FindPath（）

{

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

while（OPEN！=NULL）

{

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

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

{

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

}

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

{

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

if（M in OPEN）

{

if（M的估價(jià)值

{

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

重新計(jì)算OPEN表中的估價(jià)值；//取最小路徑的估價(jià)值

}

}

if（M in CLOSE）

{

continue；

}

if（M not in both）

{

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

求出M的估計(jì)值；

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

}

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

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

通過估價(jià)值將OPEN表中的每個(gè)節(jié)點(diǎn)進(jìn)行排序；

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

Print（CLOSE）；//輸出路徑

}//方法結(jié)束

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

2 二叉堆（BinaryHeap）簡介

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

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

圖1

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

圖2

為了讓我們的堆有效，我們把最底層之上的每一行都進(jìn)行填充?？梢园讶我鈹?shù)值的元素填在最底層，同時(shí)將新的元素按照從左到右的順序依次添加。

3 基于二叉堆的A*算法

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

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

Typedefstuct node

{

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

float nodeCost；//估價(jià)值

}NODE；

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

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）；//重新生成堆

}

}

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

4 實(shí)驗(yàn)結(jié)果分析與評價(jià)

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

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

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

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

傳統(tǒng)

A*46.75110.752046158389

78.4831.4863284157

改進(jìn)

A*46.75110.752046158168

78.4831.486328496

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

5 結(jié)束語

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

參考文獻(xiàn)：

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

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

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

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

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

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

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