遊戲程式設計中的尋路算法研究

近年來，遊戲産業的快速發展帶動了遊戲中人工

智能（Artificial Intelligence，簡稱AI）的發展，越來越

多的遊戲采用人工智能技術提高遊戲的可玩性。在電

子遊戲中，玩家操控主要角色，而其他角色的行為邏

輯由人工智能操縱，這些角色我們稱之為NPC（Non-

Player Character，非玩家控制角色）。大部分遊戲在開

發過程中都會遇到路徑探索問題，快速、準确地計算

出遊戲角色從地圖中的A點到達B點的一條路徑，一

直是遊戲開發者追求的目标，同時也是遊戲人工智能

研究的一個重要方面。

1　遊戲程式設計中的簡單尋路算法

在遊戲關卡中常常會放置一些怪物（即NPC），這

些怪物通常在一個區域内走來走去，這個區域被稱為

“巡邏區域”；一旦玩家的角色進入怪物的“視野”，怪

物就會發現玩家角色，并主動向其所在的位置移動，

這個區域稱為“警戒區域”；當玩家角色和怪物更加靠

近時，會進入到怪物的“攻擊區域”，這時怪物會對玩

家角色進行傷害。在某些RPG（Real-Time Strategy

Game，即時戰略遊戲）中，NPC在不利的情況下還會

選擇主動逃跑。如何模拟這些行為邏輯，目前遊戲業

已經有一些比較成熟的方法。

1.1　随機尋路算法

随機尋路算法适合模拟遊戲中那些沒有什麼頭腦

的生物，它們總是在場景中漫無目的地走來走去。可

以用以下的代碼進行模拟：

npc_x_velocity=-5+rand()%10；

npc_y_velocity=-5+rand()%10；

int npc_move_count=0；

while(++npc_move_count<num){第4期8 5

npc_x+=npc_x_velocity；

npc_y+=npc_y_velocity；

}//endwhile

在上例中，NPC會選取一個随機方向和速率運動

一會兒，然後再選取另一個。當然，還可以加上更多

的随機性，如，改變運動方向的時間不是固定的num

個周期，或者更傾向于朝某個方向等。實際程式設計中還

必須考慮到碰撞檢測，當NPC遇到障礙物後，會随機

選取一個前進的方向，繼續行走。

1.2　跟蹤算法

當遊戲中的主角進入到NPC的“警戒區域”後，遊

戲的AI可輕易獲得目标的位置，然後控制NPC對象

移向被跟蹤的對象。跟蹤算法可以模拟這一行為：

voidBat_AI(void)

{

if(ghost.x>bat.x)

bat.x++；

else

if(ghost.x<bat.x)

bat.x--；

if(ghost.y>bat.y)

bat.y++；

else

if(ghost.y<bat.y)

bat.y--；

……

}//end Bat_AI

這段代碼放到程式中實際運作時不難發現，N P C

會迅速地追蹤到目标。這種跟蹤非常精确，但是在遊

戲中過于精确卻不一定是一件好事，因為這會使NPC

的行為看上去顯得有點假。一種更自然的跟蹤方式是

使跟蹤者的方向矢量與從跟蹤目标的中心到跟蹤者的

中心所定義的方向矢量靠攏。

這個算法可以這樣設計：假設AI控制的對象稱作

跟蹤者（tracker）并有以下屬性：

Position：(tracker.x，tracker.y)

Velocity：(tracker.xv，tracker.yv)

被跟蹤對象稱作跟蹤目标（target），有如下屬性：

Position：(target.x，target.y)

Velocity：(target.xv，target.yv)

基于上面的定義，下面是調整跟蹤者的速度向量

的常用邏輯循環：

1）計算從跟蹤者到跟蹤目标的向量：

TV=(target.x-tracker.x，target.y-tracker.y)=(tvx，

tvy)，規格化TV——也就是說(tvx，tvy)/Vector_Length

(tvx，tvy)使得最大長度為1.0，記其為TV*。記住

Vector_Length()隻是計算從原點(0，0)開始的矢量長度。

2）調整跟蹤者目前的速度向量，加上一個按rate

比例縮放過的TV*：

tracker.x+=rate*tvx；

tracker.y+=rate*tvy；

注意：當rate>1.0時，跟蹤向量會合得更快，跟蹤

算法對目标跟蹤得更緊密，并更快地修正目标的運動。

3）跟蹤者的速度向量修改過之後，有可能向量的

速度會溢出最大值，就是說，跟蹤者一旦鎖定了目标的

方向，就會繼續沿着該方向加速。是以，需要設定一個

上界，讓跟蹤者的速度從某處慢下來。可做如下改進：

tspeed=Vector_Length(tracker.xv，tracker.yv)；

if(tspeed>max_SPEED){

tracker.xv*=0.7；

tracker.yv*=0.7；

}

也可以選擇其它的邊界值0.5或0.9等均可。如果

追求完美，甚至可以計算出确切的溢出，并從向量中

縮去相應的數量。追蹤過程中同樣也會遇到障礙物，

是以，碰撞檢測是必不可少的。程式員可以根據不同

的遊戲類型設計碰撞後的行為邏輯。

1.3　閃避算法

這個技術是讓遊戲的N P C能避開玩家角色的追

擊，跟前面的跟蹤代碼很相似，跟蹤算法的對立面就

是閃避算法，隻要把上例中的等式翻轉，閃避算法就

成了，下面是轉換後的代碼：

if(ghost.x>bat.x)

bat.x--；

else

if(ghost.x<bat.x)

bat.x++；

if(ghost.y>bat.y)

bat.y--；

else

if(ghost.y<bat.y)

bat.y++；

……

以上介紹的3個算法可以模拟NPC的一些簡單的尋

路、跟蹤和閃避行為，在小遊戲中會經常用到。但是，

在較大型的遊戲中使用這樣簡單的算法就會大大影響遊

戲效果了。是以，大型遊戲的人工智能算法都較複雜。

2　遺傳算法在路徑探索中的應用

改進優化後的A*算法可以很好地勝任遊戲中的路

徑搜尋[1]，一直以來被遊戲界認為是最好、最成熟的尋

路算法之一，因而被廣泛應用。由于A*算法是按照尋

找最低耗費的路徑來設計，A*尋路會找到最短，最直接

付朝晖，丁夢，喻昕　遊戲程式設計中的尋路算法研究8 6 湖南工業大學　學　報2007年

的路徑，當算法具體實作後，得到的這條路徑也是唯一

的路徑[2]。于是，當遊戲重來時，玩家會發現NPC總是

隻有一條路可走，這樣就顯得不夠真實。玩家希望NPC

有足夠的智力能找到一條适合的路徑，也要有不同的選

擇。如果能夠為遊戲中的角色設定一個智能系統來進行

控制，這個系統能通過自身不斷地學習，逐漸适應複雜

的環境，自己找到一條“較好”的路徑，并且有較高的

效率，就會使遊戲角色的行為邏輯看上去更真實一些。

這樣就需要借助人工智能的一些技術，如遺傳算法等。

2.1　遺傳算法

遺傳算法是模拟生物進化的步驟，将繁殖、雜交、

變異、競争和選擇等概念引入到算法中，通過維持一

組可行解，并通過對可行解的重新組合，改進可行解

在多元空間内的移動軌迹或趨向，最終走向最優解。

它克服了傳統優化方法容易陷入局部極值的缺點，是

一種全局優化算法[3，4]。

遺傳算法的步驟如下：

1）對待解決問題進行編碼——生物的性狀是由生

物遺傳基因的編碼所決定的，使用遺傳算法時，需要

把問題的每一解編碼成一個基因編碼，一個基因編碼

就代表問題的一個解，每個基因編碼有時被稱作是一

個個體，有時也把基因編碼稱作染色體[5]；

2）随機初始化群體X(0)=(x1，x2，…，xn)；

3）對目前群體X(t)中每個個體xi計算其适應度

F(xi)，适應度表示了該個體的性能好壞；

4）從目前群體選出2個成員，選出的機率正比于

染色體的适應性，适應分愈高，被選中機率也愈大；

5）按照預先設定的雜交率，從每個選中染色體的

一個随機确定的點上進行雜交；

6）按照預定的變異率，通過對被選染色體的位的

循環，把相應的位實行翻轉；

7）如果不滿足終止條件繼續3）。

2.2路徑探索的遺傳算法實作

在這個路徑探索例子中，首先建立1個地圖，它

有1個入口，1個出口。地圖中放置一些障礙物，在入

口處放置1個NPC。地圖可以用1個二維整數數組Map

[][]來表示，其中用0來表示可以通行的空間，1代表

牆壁或障礙物，8為入口，9為出口。遊戲開發者通常

是借助地圖編輯器之類的工具來生成這個數組。

接下來要使它能找到出口，并避免與所有障礙物相

碰撞。這種地圖設計方法被封裝在一個稱為CNpcMap

的類中，隻需要以常量的形式來儲存地圖數組以及起點

和終點就行了。除了存儲地圖，這個CNpcMap類中需

要1個數組NpcPath[][]，用來記錄NPC在地圖中行走的

路徑。可以用由1（UP）、2（DOWN）、3（LEFT）、4（RIGHT）

所組成的動作方向序列來檢測NPC走了多遠，并計算出

NPC能到達的最遠位置，然後傳回1個适應性分數，它

正比于NPC最終位置離出口的距離。NPC所到達的位置

與出口越近，給NPC的适應性分數就越高。如果NPC實

際已到達了出口，将得到滿分1，這時，循環就會自動

結束，此時得到問題的一個解。

根據遺傳算法的步驟，第1步是為染色體編碼，染

色體把NPC的每一個動作方向編入代碼中。NPC有上、

下、左、右4個動作方向，編碼後的染色體是代表這4

個動作方向的一個數組DirAction[]。首先通過程式生成

由1234組成的整型随機數數組，就能根據它得到NPC

行動時的方向。例如染色體{3，2，1，2，4，3，2，1，…}。

第2步要做的是将NPC置于地圖的入口，然後指

示NPC根據DirAction[]數組中所列的方向指令序列一

步步地走。如果有一個方向使NPC碰到了牆壁或障礙

物，則忽略該指令序列并繼續按下一條指令序列去走

就行了。這樣不斷走下去，直到用完所有方向或NPC

到達出口為止。遺傳算法以整型随機數數組作為初始

群體，一般要求産生幾百個這樣的随機染色體，測試

它們每一個能讓NPC走到離出口有多麼近，然後讓其

中最好的那些作為種子産生後代，期望它們的“子孫”

中能有走得離出口更近一點。這樣繼續下去，直到找

出一個解。是以，需要定義一種結構，其中包含一個

染色體，以及一個與該染色體相聯系的适應性分數。

這個結構的定義如下：

struct Chromosome

{

int DirAction[]；

double FitnessScore；

Chromosome()：FitnessScore(0){}

Chromosome(int num)：FitnessScore(0)

{

for(int i=0；i<num；++i)

{

//創造随機字元數組

}

}

}

在建立Chromosome對象時，把一個整型數作為參

數傳遞給構造函數，則它就會自動建立一個以此整數

為長度的随機數字數組，并将其适應性分數初始化為

零，完成對基因組的設定。

第3步，也是遺傳算法類中最為關鍵的一步，就

是測試染色體群中每一個體的适應性分數，數。函數

CalFitSco()根據代表上、下、左、右4個方向的數組

DirAction[]，計算出NPC離開出口的最終距離，傳回

一個适應性分數。計算适應性分數程式如下：

int Dist_X=abs(Npc_X-End_X)；

int Dist_Y=abs(Npc_Y-End_Y)；第4期8 7

return 1/(Dist_X+Dist_Y+1)；//加1避免分子為0

這裡的Dist_X和Dist_Y就是NPC所在的位置相對

于地圖出口的水準和垂直偏離值。如果N P C到達出

口，則Dist_X+Dist_Y=0。CalFitSco()保持對每一代

中适應性分數最高的基因組以及與所有基因組相關的

适應性分數的跟蹤。每當一個新的基因組群被建立出

來時，需要将它們儲存下來。

第4步，從目前群體選出2個個體以備雜交。賭

輪選擇是常用的一種方法，被選中的幾率和它們的适

應性分數成比例，适應性分數愈高的染色體，被選中

的機率也愈大。但這不是說适應性分數最高的成員一

定能選入下一代，它隻是有最大的機率被選中。

while(Parents<V_Num)

{

//用賭輪法選擇

Chromosome Parent1=RSele()；

Chromosome Parent2=RSele()；

……

}

在每次疊代過程中，需選擇2個染色體作為“後

代”染色體的“父輩”，一個染色體的适應性分數越高，

其被賭輪方法選擇作為“父輩”的機率就越大。

第5步雜交操作

Chromosome Cbaby1，Cbaby2；

Hybridize　　(Parent1.DirAction，　

Parent2.DirAction　，　Cbaby1.DirAction　，

Cbaby2.DirAction)；

建立2個新的染色體，它們與所選的父輩一起傳

遞給雜交函數Hybridize()。這一函數執行了雜交，并把

新的染色體的二進制位串存放到Cbaby1和Cbaby2中。

第6步變異操作

Differentiation(Cbaby1.DirAction)；

Differentiation(Cbaby2.DirAction)；

以上這2步實作對染色體後代雜交變異，完成後

把2個後代染色體加入新的群體，這樣就完成了一次

疊代過程。該過程不斷重複，原有的群體由新生一代

所組成的群體代替，直到染色體收斂到了一個解。

程式運作中有可能不是總能找到一條通往出口的

路徑，這時有可能會導緻NPC會在一個角落不确定地

走來走去，原因是群體太快地收斂到一個特殊類型的

染色體，由于群體中的成員變得相似，Hybridize算子

的優勢這時實際上已經不能發揮作用，隻有很少的變

異操作在起作用。但變異率設定得很低，當染色體類

型的差異消失後，僅僅依靠變異本身已不能去發現一

個解[6]。選擇适當的參數可以改善這個問題，但是目

前還沒有一個有效的規則，不同的問題需要不同的

值，使用者隻能通過自己的實踐選取合适的值，在具體

實作中把雜交率選為0.6，變異率取為0.05，而基因組

數目取為染色體長度的2倍，可得到較理想的解。

2.3　遺傳算法尋路的優缺點

與其他尋路算法相比，遺傳算法具有如下優點：

1）在搜尋中用到的是随機的變換規則，而不是确

定的規則。它在搜尋時采用啟發式的搜尋，而不是盲

目的窮舉，因而具有很高的搜尋效率。

2）遺傳算法給出的是一組優化解，而不是一個優

化解，這樣，在遊戲中可表現出更多的行為空間。

3）遺傳算法具有很強的可并行性，可通過并行計

算來提高計算速度，因而更适用于大規模複雜問題的

優化。

但是，遺傳算法畢竟是一種較新的算法，實際運

用中存在一些問題，主要集中在以下幾個方面：

1）遺傳算法的理論研究較滞後。由于遺傳算法本

身是一種仿生的思想，盡管實踐效果較好，但理論證

明比較困難，而且，這種算法提出來的時間還不是太

長，是以，其理論和實踐的研究幾乎是平行進行的。

2）算法本身的參數還缺乏定量的标準，目前采用

的都是經驗數值，而且，不同編碼、不同遺傳技術都會

影響到遺傳參數的選取，因而會影響到算法的通用性。

3）遺傳尋路算法還算不上真正的實時算法，在遊

戲中的應用會受到一些限制，在實時性很強的遊戲中

不宜使用。

3　結語

近年來，遊戲的AI發展很快，各種AI技術被引

入到遊戲中，如遺傳算法、人工神經網絡計算、地形

分析技術、團隊尋徑算法、A*算法等，這些技術出色

地解決了遊戲中一些基本問題。有理由相信，未來遊

戲的AI将會給玩家帶來更多的驚喜。

參考文獻：

[1]　何國輝，陳家琪.遊戲開發中智能路徑搜尋的算法研究[J].

計算機工程與設計，2006，27（13）：2334-2337.

[2]　陳和平，張前哨.A*算法在遊戲地圖尋徑中的應用與實作

[J].計算機應用與軟體，2005，22（10）：118-120.

[3]　王小平，曹立明.遺傳算法－理論、應用與軟體實作[M].

西安：西安交通大學出版社，2002.

[4]　閻平凡，張長水.人工神經網絡與模拟進化計算[M].北

京：清華大學出版社，2000.

[5]　王淑琴.神經網絡和遺傳算法在遊戲設計中的應用研究[D].

長春：東北師範大學，2004.

[6]　金朝紅，吳漢松，李臘梅，等.一種基于自适應遺傳算法

的神經網絡學習算法[J].微型機資訊，2005，2（110-11）：

49-51.