游戲開發(fā)中智能路徑搜索算法的研究
2008-12-31 00:00:00潘建生
電腦知識與技術(shù) 2008年36期
摘要：在游戲軟件中，人工智能是一個(gè)重要而又復(fù)雜的模塊，而尋路算法是人工智能運(yùn)用于電子游戲中的最基本問題之一。針對游戲中路徑搜索的特點(diǎn)，在對一般搜索算法、常見搜索算法和啟發(fā)式搜索技術(shù)進(jìn)行詳細(xì)地分析與研究的基礎(chǔ)之上，結(jié)合實(shí)際應(yīng)用情況，對A*算法進(jìn)行了一些優(yōu)化與改進(jìn)。
關(guān)鍵詞：游戲開發(fā)；人工智能；A*算法；路徑搜索
中圖分類號：TP18文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2008)36-2739-03
Research on Algorithm of AI Pathfinding in Game Development
PAN Jian-sheng
(School of Computer Science Technology， Nantong University， Nantong 226001， China)
Abstract: In game software，Artificial Intelligence is an important and complicated module.Shortest-Path Search is one of the most basic questions in which artificial intelligence applied to electronic games.The characteristics of the search path in the general search algorithm，commom heuristic search algorithm and technology on the basis of a detailed analysis and study，the combination of practical application，for a number of A* algorithm optimization and improvement.
Key words: game development; artificial intelligence; A* algorithm; pathfinding
1 引言
人工智能（Artificial Inteligence）在電子游戲中運(yùn)用已經(jīng)有很多年了，并且在發(fā)展中變得越來越完善。如果在游戲中不加入完善的游戲AI控制系統(tǒng)，那么游戲玩家就認(rèn)為該游戲缺乏可玩性。一個(gè)在市場上暢銷的成功游戲，必須既要有華麗的畫面視覺效果和悅耳的聽覺感受，又要有高超逼真的人工智能控制系統(tǒng)。游戲開發(fā)者把AI應(yīng)用在游戲中，就會使廣大玩家感到他們所面對的由電腦AI系統(tǒng)控制的敵人（即NPC）跟現(xiàn)實(shí)中的敵人一樣擁有人類智能，讓玩家留下如臨實(shí)境的體驗(yàn)。在游戲術(shù)語中，AI是用來描述游戲角色的行為表現(xiàn)的。如在角色扮演類游戲（RPG）中去模擬人作為某個(gè)角色的行為，在即時(shí)戰(zhàn)略游戲（RTS）中進(jìn)行路徑搜索算法，包括簡單的AI找路和群體AI找路，還有策略AI，戰(zhàn)術(shù)AI，建筑布置，危險(xiǎn)估計(jì)，地形分析等多方面。一般游戲AI系統(tǒng)都是從搭建最基本的尋路系統(tǒng)開始，一步步修改和完善后而成的。所以本文重點(diǎn)闡述了游戲AI開發(fā)中最基本最核心的人工智能尋路算法。
2 主要路徑搜索算法
最短路徑搜索，就是根據(jù)游戲地圖中的地形和障礙，尋找一條從起點(diǎn)到終點(diǎn)的最近、最直接的路徑的算法。搜索通常有盲目搜索（也稱非啟發(fā)式搜索）和啟發(fā)式搜索兩種不同的方法，盲目搜索的特點(diǎn)是不考慮給定問題所具有的特定知識，系統(tǒng)根據(jù)事先確定好的某種固定排序，依次調(diào)用規(guī)則或隨機(jī)調(diào)用規(guī)則，這種搜索具有盲目性，效率不高，一般統(tǒng)稱為無信息引導(dǎo)的搜索策略；啟發(fā)式搜索的特點(diǎn)是在搜索中加入了與問題有關(guān)的啟發(fā)性信息，這些信息可以指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問題的求解過程并找到最優(yōu)解。它是動態(tài)地確定規(guī)則的排序，并優(yōu)先調(diào)用較合適的規(guī)則使用。
2.1 非啟發(fā)式的Dijkstra算法
Dijkstra算法是最基本的非啟發(fā)式最短路徑搜索，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法能得出最短路徑的最優(yōu)解。
路徑上的開始頂點(diǎn)(出發(fā)點(diǎn))稱為源點(diǎn)，路徑上的最后一個(gè)頂點(diǎn)稱為終點(diǎn)，并假定討論的權(quán)值不能為負(fù)數(shù)。單源點(diǎn)到其他頂點(diǎn)的最短路徑是指：給定一個(gè)出發(fā)點(diǎn)(單源點(diǎn))和一個(gè)有向網(wǎng)G=(V，E)，求出源點(diǎn)到其它各頂點(diǎn)之間的最短路徑。迪杰斯特拉算法的基本思想是:設(shè)置并逐步擴(kuò)充一個(gè)集合S，存放已求出其最短路徑的頂點(diǎn)，則尚未確定最短路徑的頂點(diǎn)集合是V-S，其中V為網(wǎng)中所有頂點(diǎn)集合。按最短路徑長度遞增的順序逐個(gè)以V-S中的頂點(diǎn)加到S中，直到S中包含全部頂點(diǎn)，而V-S為空。具體做法是：設(shè)源點(diǎn)為Vl，則S中只包含頂點(diǎn)Vl，令W=V-S，則W中包含除Vl外圖中所有頂點(diǎn)，Vl對應(yīng)的距離值為0，W中頂點(diǎn)對應(yīng)的距離值是這樣規(guī)定的：若圖中有弧
在Dijkstra算法中，求一條最短路徑所花費(fèi)的時(shí)間：從V-S中選取具有最小距離的頂點(diǎn)Vk花費(fèi)時(shí)間O(n)；修改V-S中頂點(diǎn)的距離花費(fèi)時(shí)間O(n)；輸出最短路徑花費(fèi)時(shí)間O(n)。因此求出n-1條最短路徑的時(shí)間復(fù)雜度為O(n2)。頂點(diǎn)對之間的最短路徑是指：對于給定的有向網(wǎng)G=(V，E)，要對G中任意一對頂點(diǎn)有序?qū)、W(V≠W)，找出V到W的最短距離和W到V的最短距離。解決此問題的一個(gè)有效方法是:輪流以每一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行Dijkstra算法n次，即可求得每一對頂點(diǎn)之間的最短路徑，總的時(shí)間復(fù)雜度為O(n3)。但由于Dijkstra算法遍歷計(jì)算的節(jié)點(diǎn)很多，所以效率較低。非啟發(fā)式路徑搜索實(shí)際上是一種窮舉法，通過固定順序依次搜索尋路者周圍的路點(diǎn)，直到找到目的路點(diǎn)為止。搜索點(diǎn)在計(jì)算機(jī)模擬圖象上呈現(xiàn)的是一個(gè)不斷擴(kuò)大的矩形。如此窮舉直接導(dǎo)致搜索速度過慢且不符合人類一般的尋路邏輯。
2.2 啟發(fā)式的A*算法
啟發(fā)式搜索的核心是估價(jià)函數(shù)f(n)，所謂的估價(jià)函數(shù)就是用來估計(jì)節(jié)點(diǎn)重要性的函數(shù)。函數(shù)f(n)被定義為從初始節(jié)點(diǎn)A出發(fā)，約束經(jīng)過節(jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)B的所有路徑中最小路徑代價(jià)的估計(jì)值。即f(n)的值由兩部分組成，一部分是從起始節(jié)點(diǎn)A到該結(jié)點(diǎn)的代價(jià)，用函數(shù)g(n)表示。一般而言，g(n)的值計(jì)算是讓父結(jié)點(diǎn)的該值和從父結(jié)點(diǎn)到本身的代價(jià)和相加而得，所以它的值是能夠確定的；另外一部分則是從該結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的估計(jì)代價(jià)，用函數(shù)h(n)表示。對h(n)的值一般需要根據(jù)問題自身的特性來確定，它體現(xiàn)的是自身的啟發(fā)性信息，因此也稱為啟發(fā)函數(shù)。對一般的地圖尋路問題，h(n)的值通過水平和垂直位置的差距結(jié)合而算出的效果比較好。例如:設(shè)B(dx，dy)是終點(diǎn)，n(sx，sy)是當(dāng)前點(diǎn)，則:h(n)=|dx-sx|+|dy-sy|那么函數(shù)f(n)則可以表示為:f(n)=g(n)+h(n)
A*算法是一種典型的啟發(fā)式搜索算法，它除了利用上述的啟發(fā)函數(shù)來對搜索過程中的每一個(gè)節(jié)點(diǎn)進(jìn)行評估，另外它還保持著兩個(gè)表:Open表和Close表.Open表由未考察的結(jié)點(diǎn)組成，而Close表由已考察的結(jié)點(diǎn)組成。當(dāng)算法已經(jīng)檢查過與某個(gè)結(jié)點(diǎn)相連的所有子結(jié)點(diǎn)，計(jì)算出這些子結(jié)點(diǎn)的g(n)，h(n)和f(n)值，并把它們放入Open表以待考察，那么該點(diǎn)就是已考察的結(jié)點(diǎn)，通常都是放在 Close表里面。因?yàn)樵贏*算法計(jì)算的過程中，會經(jīng)常從Open表或者Close表中取出一個(gè)最小值的元素，所以這兩個(gè)表所用的數(shù)據(jù)結(jié)構(gòu)通常要便于排序，常見的是使用堆數(shù)據(jù)結(jié)構(gòu)，該結(jié)構(gòu)每次都能夠把最小值的元素放到最上面。A*算法就是利用估價(jià)函數(shù)對地圖中的每個(gè)結(jié)點(diǎn)進(jìn)行評估，并結(jié)合Open表和Close表的操作來完成路徑的搜索。假設(shè)起始結(jié)點(diǎn)為A，終止結(jié)點(diǎn)為B，下面代碼是A*算法實(shí)現(xiàn)過程的偽代碼描述，其中n是每次被考察的結(jié)點(diǎn)，臨時(shí)結(jié)點(diǎn)m代表n的每個(gè)有效子結(jié)點(diǎn)，所謂有效子結(jié)點(diǎn)就是指在地圖中能夠到達(dá)的結(jié)點(diǎn)。當(dāng)n等于B時(shí)那么該次搜索也就完成了。
A*算法偽代碼:
計(jì)算A的g，h和f值，并把A放入Open表中；
wh1le(Open表非空)
{
取Open表里f值最小的元素n，將其放入Close表里；
if(n等于B)
搜索完成，返回；
for(n的每個(gè)有效子結(jié)點(diǎn)m)
{
計(jì)算m的g，h和f值；
if(m未被訪問過)//說明不在Open表和Close表里
將其放入Open表里；
e1seif(m在Open表里)
{if(m該次計(jì)算的f值比上次更小)
重新設(shè)置m的g，h和f值為該次計(jì)算的值；
}}}
根據(jù)中間的搜索標(biāo)記求出路徑；
A* 算法具備很多優(yōu)點(diǎn)。首先，如果起點(diǎn)和終點(diǎn)之間存在有效路徑，A* 就一定能夠找到。其次，只要h ( n)是可納的，它就一定能找到一條最短路徑。第三，A* 算法是啟發(fā)式搜索算法中搜索狀態(tài)最少的一種算法，它使啟發(fā)式函數(shù)得到了最有效的應(yīng)用。A*算法是一個(gè)利用某個(gè)估價(jià)函數(shù)可以找出最短路徑的最好優(yōu)先算法。我們選取的估價(jià)函數(shù)越好，則路徑搜索時(shí)排除的節(jié)點(diǎn)就越多，這個(gè)A*算法就越好越有效率。但在實(shí)際游戲開發(fā)中由于實(shí)時(shí)性的問題，估價(jià)函數(shù)中的啟發(fā)信息越多，它的計(jì)算量就越大，耗費(fèi)的時(shí)間就越多。所以又要適當(dāng)?shù)臏p少h(n)啟發(fā)信息，即減小約束條件，可是算法的準(zhǔn)確性就差了，這就是個(gè)全局平衡取舍的問題了。
通過該算法偽代碼可以看出，一次搜索任務(wù)是通過兩個(gè)循環(huán)計(jì)算來完成的。另外當(dāng)一次路徑搜索正在計(jì)算的過程中，是不能夠被外界中斷的。但是如果當(dāng)搜索規(guī)模很大時(shí)，則通常一次計(jì)算會耗費(fèi)大量的時(shí)間，而此時(shí)主程序的其它模塊就不得不等待該次計(jì)算的完成。這種同步尋路算法所導(dǎo)致的結(jié)果在某些需要實(shí)時(shí)響應(yīng)的系統(tǒng)中可能會是致命的。對于游戲的特殊要求，A* 還有幾個(gè)不得不改進(jìn)的缺點(diǎn)：標(biāo)準(zhǔn)A* 搜索比較費(fèi)時(shí)，當(dāng)多個(gè)單位同時(shí)應(yīng)用算法進(jìn)行尋徑時(shí)，其耗時(shí)會令游戲玩家無法忍受；直接利用算法得到的路徑雖然是最短路徑，但往往曲曲折折，過于機(jī)械化。因此，還要對它進(jìn)行平滑處理；除此以外，游戲地圖中的特殊地形、目標(biāo)節(jié)點(diǎn)可達(dá)不可達(dá)的判斷、地圖中障礙物位置的動態(tài)改變，以及當(dāng)某一狹窄路徑交通堵塞時(shí)，如何改變尋路策略，都是需要考慮的問題。針對這些問題，本文下面將對該算法進(jìn)行優(yōu)化和改進(jìn)。
3 A*算法的改進(jìn)、優(yōu)化策略
3.1 避免AI角色之間的碰撞
在前述的A*算法描述中，完全忽略了其他AI角色對尋路的干擾。這種的情況下AI尋路者之間表現(xiàn)出來的是可以相互穿越。這種現(xiàn)象在大多數(shù)的實(shí)際游戲中是不允許的。如果希望AI角色之間能互相繞開，則對于相互靠近的運(yùn)動著的AI角色，可以通過懲罰它們各自路徑上的節(jié)點(diǎn)，來鼓勵(lì)這些AI角色找到各自不同的路徑.如果選擇了把其他正在移動并且遠(yuǎn)離當(dāng)前尋路者的那些AI角色也考慮在內(nèi)，將需要實(shí)現(xiàn)一種方法及時(shí)預(yù)測在何時(shí)何地碰撞可能會發(fā)生，以便恰當(dāng)?shù)谋苊猓駝t極有可能得到一條怪異的路徑，單位突然轉(zhuǎn)彎試圖避免和一個(gè)已經(jīng)不存在的單位發(fā)生碰撞。當(dāng)然我們也需要寫一段碰撞檢測的代碼，因?yàn)闊o論計(jì)算的時(shí)候路徑有多完美，它也會因時(shí)間而改變。當(dāng)碰撞發(fā)生時(shí)，一個(gè)AI尋路者必須尋找一條新路徑，或者，如果將要碰撞到的另一個(gè)AI角色正在移動，則原AI尋路者等待那個(gè)AI角色離開后再繼續(xù)沿當(dāng)前路徑前進(jìn)。
3.2 各種地形的不同損耗
在前述的A*算法描述中，地形分為可通過的和不可通過的兩種。但在實(shí)際游戲設(shè)計(jì)中，我們會遇到一些不同種類的可通過的地形。他們的移動耗費(fèi)各異如沼澤，山坡，沙漠，樓梯等等，這些都是可通過但比平坦的自然道路移動耗費(fèi)更高的地形。同樣我們也需要比自然道路移動耗費(fèi)更低的地形，如平滑的下坡道等等。對這個(gè)問題，我們只要在計(jì)算任何地形G值的時(shí)候增加或減少地形損耗就可以了。由于A*搜索算法已經(jīng)按照尋找最低耗費(fèi)的路徑來設(shè)計(jì)，所以很容易處理這種情況。
3.3 平滑搜索路徑
盡管A*算法提供了最短、最低代價(jià)的路徑，但這條路徑常常看起來AI角色走起來顯得比較突兀，不是很平滑。有兩種方法可以解決這個(gè)問題。當(dāng)計(jì)算路徑的時(shí)候可以對改變方向的格子施加不利影響，即對G值增加額外的數(shù)值。也可換另一種方法，可以在路徑計(jì)算完之后沿著它跑一遍，找出那些會讓路徑看起來更平滑的相鄰格替換原先路徑上的格子。
3.4 預(yù)計(jì)算最短路徑
利用Dijkstra算法計(jì)算最短路徑樹，將其存儲在一個(gè)最短路徑查找表中。在游戲運(yùn)行時(shí)，不再執(zhí)行路徑查找算法，而是查表。
3.5 分層次尋路
利用不同細(xì)致級別的搜索空間圖，首先計(jì)算一個(gè)較粗糙的路徑，在到達(dá)具體的區(qū)域時(shí)再使用更細(xì)致的搜索空間（可以是該區(qū)域的局部搜索空間）來計(jì)算更精確的路徑。
4 結(jié)束語
A*算法作為一種計(jì)算最短路徑的算法，它結(jié)合了啟發(fā)式方法和形式化方法，為許多即時(shí)戰(zhàn)略游戲所用到. 通過對A*算法的優(yōu)化改進(jìn)后，A* 算法可以很好地勝任游戲中的路徑搜索，提高了原算法的執(zhí)行效率，并使路徑的選擇更加人性化.但在減少搜索時(shí)間的同時(shí)也增加了空間的消耗.隨著A *算法在游戲的設(shè)計(jì)開發(fā)領(lǐng)域廣泛應(yīng)用，電腦游戲中人工智能A *的算法會發(fā)展得越來越完善。
參考文獻(xiàn)：
[1] Rabin S.人工智能游戲編程真言[M].莊越挺，吳飛，譯.北京:清華大學(xué)出版社，2005.
[2] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版)[M].北京:清華大學(xué)出版社，1997.
[3] 何國輝，陳家琪.游戲開發(fā)中智能路徑搜索的算法研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2006，27(13).
[4] 朱福喜，湯怡群，傅建明.人工智能原理[M].武漢:武漢大學(xué)出版社，2002.
[5] 陳剛，付少鋒，周利華.A*算法在游戲地圖尋徑中的幾種改進(jìn)策略研究[J].科學(xué)技術(shù)與工程，2007，7(15).
