祁 悅 ，趙 洋 ，楊 帆

（南京理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,江蘇 南京 210094）

一種基于A*算法的分層路徑規(guī)劃在3D游戲中的應(yīng)用研究

祁 悅1，趙 洋2，楊 帆3

（南京理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,江蘇 南京 210094）

以3D游戲中智能體的路徑規(guī)劃為研究背景，對(duì)于如何生成3D游戲的地形網(wǎng)格以及如何進(jìn)行高速、準(zhǔn)確的路徑規(guī)劃進(jìn)行了研究。提出了一種分層的解決方案，首先通過(guò)建立導(dǎo)航網(wǎng)格劃分狀態(tài)空間；接著使用引入地形估價(jià)因子的 算法進(jìn)行網(wǎng)格尋路，并通過(guò)拐角點(diǎn)法生成路徑，同時(shí)對(duì) 算法的OPEN表進(jìn)行了二叉堆的優(yōu)化；最后介紹了基于射線(xiàn)透射的局部 算法對(duì)動(dòng)態(tài)障礙物的處理。實(shí)驗(yàn)分析表明該算法的有效性。

導(dǎo)航網(wǎng)格； 算法；地形因子；二叉堆；拐角點(diǎn)法；射線(xiàn)透射

隨著游戲產(chǎn)業(yè)的快速發(fā)展，每年都有很多不同種類(lèi)的游戲產(chǎn)品推出，形成了一項(xiàng)數(shù)十億美元的產(chǎn)業(yè)。盡管游戲的名目眾多，但游戲的類(lèi)型卻十分有限。開(kāi)發(fā)者們正在致力于尋找任何可能找到的方式來(lái)使他們的游戲受到關(guān)注，而游戲人工智能[1]無(wú)疑是一個(gè)很好的方向。

在游戲人工智能中，路徑規(guī)劃是角色動(dòng)作選擇的一個(gè)重要表現(xiàn)。出于對(duì)用戶(hù)體驗(yàn)的考慮，不同游戲?qū)PC(Non-Player Character,非玩家控制角色)人工智能化程度的設(shè)計(jì)要求不同，使得不同角色對(duì)尋路的要求也不盡相同。對(duì)于小型游戲以及對(duì)尋路時(shí)間要求不高的NPC可以采用基于盲目搜索的路徑規(guī)劃，例如寬度優(yōu)先搜索便能夠保證角色可以到達(dá)目標(biāo)地點(diǎn)，但對(duì)于大規(guī)模的路徑規(guī)劃，如在需要考慮眾多物理因素的3D游戲環(huán)境下，啟發(fā)式搜索可以有效地節(jié)約內(nèi)存資源并且快速達(dá)到目標(biāo)狀態(tài)。目前，A*算法是應(yīng)用最為廣泛的一種啟發(fā)式搜索算法。

本文針對(duì)3D游戲的物理環(huán)境以及特殊性，采用了一種分層次的路徑規(guī)劃解決方案。首先，游戲環(huán)境處理層負(fù)責(zé)根據(jù)地形、靜態(tài)障礙物的規(guī)劃以及關(guān)卡設(shè)計(jì)信息生成導(dǎo)航網(wǎng)格圖；接著，路徑規(guī)劃層負(fù)責(zé)選擇合適的尋路算法對(duì)不同角色進(jìn)行路徑規(guī)劃,本文采用引入地形估價(jià)因子的A*算法；最后，動(dòng)態(tài)障礙物規(guī)避層則負(fù)責(zé)處理碰撞檢測(cè)、局部規(guī)避、群體角色尋路優(yōu)先級(jí)等問(wèn)題。

1 導(dǎo)航網(wǎng)格的生成

在早期的2D游戲中，游戲開(kāi)發(fā)者們多采用柵格法或可見(jiàn)點(diǎn)法[2]劃分搜索空間。然而當(dāng)面對(duì)大型的3D游戲，柵格法和可見(jiàn)點(diǎn)法的缺點(diǎn)就顯現(xiàn)出來(lái)了。它們需要大量細(xì)化的柵格或路點(diǎn)來(lái)描述多障礙的大地圖，內(nèi)存占用率高，尋路效率低，且在面對(duì)動(dòng)態(tài)障礙物以及不同角色的不同尋路參數(shù)時(shí)表現(xiàn)不盡人意。導(dǎo)航網(wǎng)格[3](NavMesh)是一種越來(lái)越受游戲開(kāi)發(fā)商歡迎的方法。它使用凸多邊形的網(wǎng)來(lái)描述游戲環(huán)境中的可訪(fǎng)問(wèn)區(qū)域。凸多邊形有個(gè)很重要的特性，就是它允許從多邊形的任一點(diǎn)到網(wǎng)格中的其他點(diǎn)都可以保證暢通無(wú)阻。

在游戲環(huán)境預(yù)處理層，我們可以將三維空間表示成由相互連接的多邊形構(gòu)成的網(wǎng)格，并將多邊形數(shù)據(jù)存儲(chǔ)為結(jié)點(diǎn)應(yīng)用于尋路中。導(dǎo)航網(wǎng)格非常接近于三維場(chǎng)景空間，根據(jù)地圖不同區(qū)域的特點(diǎn)，網(wǎng)格可以是三角形或凸多邊形。生成導(dǎo)航網(wǎng)格的方法很多，可以選擇用中間件生成，例如Xaitment、NavPower、 PathEngine、 Kynapse等[2]。現(xiàn)在很多的集成游戲開(kāi)發(fā)引擎也都包含了生成導(dǎo)航網(wǎng)格的組件。如圖1所示，此圖是在unity 3D游戲開(kāi)發(fā)引擎中生成的一個(gè)導(dǎo)航網(wǎng)格圖，在圖中可看出在較為寬闊的平地導(dǎo)航網(wǎng)格較稀疏，而在周?chē)o態(tài)障礙物的區(qū)域，網(wǎng)格密度較稠密。

圖1 導(dǎo)航網(wǎng)格圖Fig.1 Navmesh implementation

自動(dòng)生成的導(dǎo)航網(wǎng)格具有一定的局限。在NPC較多或是關(guān)卡設(shè)計(jì)較復(fù)雜的狀態(tài)空間中，關(guān)卡設(shè)計(jì)師需要在某個(gè)區(qū)域設(shè)置更多的網(wǎng)格以便使地圖能夠處理該區(qū)域可能發(fā)生的碰撞或者其它動(dòng)態(tài)障礙。例如在FPS（First-Person Shooter Game, 第一人稱(chēng)射擊類(lèi)游戲，簡(jiǎn)稱(chēng)FPS）游戲或者RTS（Real-Time Strategy,實(shí)時(shí)策略游戲，簡(jiǎn)稱(chēng)RTS）游戲中，某個(gè)區(qū)域會(huì)有許多NPC埋伏，此時(shí)PC(Player Character,玩家控制角色)需要對(duì)該區(qū)域進(jìn)行動(dòng)態(tài)檢測(cè)，若需要重新進(jìn)行尋路，該區(qū)域則需要較多的網(wǎng)格以確保尋路算法的實(shí)現(xiàn)。因此針對(duì)關(guān)卡設(shè)計(jì)較復(fù)雜的區(qū)域，使用手動(dòng)方式繪制導(dǎo)航網(wǎng)格比較合理。

2 基于導(dǎo)航網(wǎng)格的A?算法

傳統(tǒng)A*算法可以看作是在Dijkstra算法的基礎(chǔ)上加入了啟發(fā)式搜索，啟發(fā)信息的確定原理是引入一個(gè)估價(jià)函數(shù)[4]，對(duì)狀態(tài)空間中需要搜索的每個(gè)結(jié)點(diǎn)進(jìn)行估價(jià)，將估價(jià)最小的結(jié)點(diǎn)取出并繼續(xù)向下搜索。A*算法估價(jià)函數(shù)的基本形式是f(n)=g(n)+h(n)，其中f(n)表示從起始結(jié)點(diǎn)經(jīng)過(guò)當(dāng)前結(jié)點(diǎn)并且到達(dá)目標(biāo)結(jié)點(diǎn)的估價(jià)花費(fèi)，g(n)表示從初始結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的實(shí)際花費(fèi)，h(n)表示當(dāng)前結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的估價(jià)花費(fèi)。當(dāng)估價(jià)花費(fèi)h(n)越接近真實(shí)值，算法的效率就越高[5-6]，越有可能找到最優(yōu)解。A*算法流程如圖2所示。

在游戲開(kāi)發(fā)中用于尋路的A*算法根據(jù)導(dǎo)航網(wǎng)格密度、網(wǎng)格邊數(shù)以及跨越網(wǎng)格邊界的權(quán)值不同，估價(jià)花費(fèi)f(n)的選取也不同。因此，首先對(duì)導(dǎo)航網(wǎng)格內(nèi)每一個(gè)多邊形結(jié)點(diǎn)的定義如下：

圖2 A*算法流程Fig.2 A*algorithm processes

其中，point_array表示網(wǎng)格頂點(diǎn)位置信息，edge_array表示邊的信息，factor表示當(dāng)前網(wǎng)格的地形因子，f和g分別代表啟發(fā)函數(shù)中的f(n)和g(n)。兩個(gè)布爾變量inOpen和inClose分別表示當(dāng)前網(wǎng)格結(jié)點(diǎn)是否存在于 算法中的OPEN表或者CLOSED表中。

其次需要研究的就是如何確定一個(gè)合適的估價(jià)函數(shù)。簡(jiǎn)單地圖多采用歐幾里德距離法[7]、曼哈頓距離法[8]或者對(duì)角線(xiàn)距離法定義估價(jià)函數(shù)，但這些方法僅僅考慮了距離而忽略了地形代價(jià)，在多障礙的大型復(fù)雜地圖中往往不太適用。這里我們引入一個(gè)地形因子factor，針對(duì)不同代價(jià)的地形因子可以更準(zhǔn)確地反映角色尋路的花費(fèi)。對(duì)于估價(jià)函數(shù)中的代價(jià)g值，這里定義為網(wǎng)格結(jié)點(diǎn)穿入邊和穿出邊中點(diǎn)的曼哈頓距離；估價(jià)花費(fèi)h值取該三角形的中心點(diǎn)（三頂點(diǎn)的中值）到路徑終點(diǎn)B的x和y方向的曼哈頓距離，化簡(jiǎn)后的公式為：

其中g(shù)0表示起始結(jié)點(diǎn)到第一條穿出邊的g值花費(fèi)，gn為第n個(gè)結(jié)點(diǎn)網(wǎng)格的g值花費(fèi)，s.x, s.y為起始結(jié)點(diǎn)的二維坐標(biāo)值；p[1].x, p[1].y為第一條穿出邊的中點(diǎn)二維坐標(biāo)值；p[n].x, p[n].y為第n條穿入邊的中點(diǎn)二維坐標(biāo)值；p[m].x, p[m].y為n所在網(wǎng)格穿出邊中點(diǎn)的二維坐標(biāo)值；hn表示網(wǎng)格結(jié)點(diǎn)n到終點(diǎn)的估計(jì)花費(fèi)； m[n].x, m[n].y表示第n個(gè)多邊形網(wǎng)格結(jié)點(diǎn)中點(diǎn)的二維坐標(biāo)值；fn則表示為n結(jié)點(diǎn)的總花費(fèi)；最后factor表示地形因子。地形因子的影響因素有很多，因素如地形坡度、粗糙度等，這些因素不能直接作為路徑規(guī)劃的信息，需要對(duì)其進(jìn)行一定的轉(zhuǎn)化。這里簡(jiǎn)單的以坡度α和粗糙度β作為因素提出一種地形因子的解決方案，公式如下：

估價(jià)函數(shù)確定后，就可以根據(jù)A*算法的算法流程，找到最優(yōu)網(wǎng)格路徑。考慮到算法引入了地形估價(jià)因子，對(duì)算法的效率產(chǎn)生了一定的影響，這里可以對(duì)OPEN表進(jìn)行一個(gè)二叉堆[7]的優(yōu)化處理。二叉堆是一棵排序樹(shù)，它的父親結(jié)點(diǎn)總是小于或大于 它所有的孩子結(jié)點(diǎn)，但各個(gè)孩子結(jié)點(diǎn)之間是無(wú)序的，因?yàn)樗⒉皇峭耆行虻臉?shù)，但在算法中我們僅需將OPEN表中最小的一個(gè)結(jié)點(diǎn)取出即可，即只需將二叉堆的頂點(diǎn)取出放入CLOSED表。因此，使用二叉堆可以減少比較次數(shù)和排序的時(shí)間。在此我們?cè)贗nter Core i3 2.93 GHz/ Windows 7 32 bit/Visual C++ 2008環(huán)境下對(duì)二叉堆優(yōu)化OPEN表的A*算法和傳統(tǒng)A*算法對(duì)運(yùn)行時(shí)間進(jìn)行簡(jiǎn)單對(duì)比試驗(yàn)，地形因子factor值取1，即在光滑的二維平面進(jìn)行，h(n)取十倍的曼哈頓距離，對(duì)比結(jié)果如表1所示。結(jié)果表明使用二叉堆存放OPEN表是可以提高算法效率的。

表1 算法的對(duì)比結(jié)果Tab.1 Test result of the algorithm

最后進(jìn)行網(wǎng)格內(nèi)路徑點(diǎn)的生成。如圖3左邊網(wǎng)格點(diǎn)圖所示，5個(gè)相鄰的多邊形為A*算法求出的最優(yōu)網(wǎng)格路徑。其中S表示起點(diǎn)，P表示終點(diǎn)，其余C到G各點(diǎn)為網(wǎng)格公共邊的交點(diǎn)。本文定義多邊形頂點(diǎn)的存儲(chǔ)均為順時(shí)針順序，如圖可以看出每條公共邊均為起點(diǎn)穿出該多邊形區(qū)域的邊，故以下稱(chēng)該邊為穿出邊。首先，將起點(diǎn)S所在穿出邊的兩個(gè)交點(diǎn)A、B分別設(shè)為左點(diǎn)和右點(diǎn)。如圖3右邊網(wǎng)格線(xiàn)圖所示，由起點(diǎn)S分別連接A和B并延長(zhǎng)，定義線(xiàn)段SA和SB為左線(xiàn)和右線(xiàn)，查找下一條穿出邊的兩個(gè)端點(diǎn)C和D，若C點(diǎn)在左線(xiàn)和右線(xiàn)之間，記C點(diǎn)為新的左點(diǎn)，并且更新SC為新的左線(xiàn)；同理，若頂點(diǎn)D在新的左線(xiàn)SC和右線(xiàn)SB之間，則更新D點(diǎn)為右點(diǎn)，且記新的右線(xiàn)為SD。

圖3 網(wǎng)格點(diǎn)與網(wǎng)格線(xiàn)圖Fig.3 Maps with navmesh points and navmesh lines

繼續(xù)查找，如圖4左邊拐點(diǎn)圖所示，若下一條穿出邊的頂點(diǎn)E不在左線(xiàn)和右線(xiàn)之間，則不更新左點(diǎn)和左線(xiàn)，而F點(diǎn)則在左線(xiàn)SC和右線(xiàn)SD之間，則更新F點(diǎn)為右點(diǎn)，SF為右線(xiàn)。若下一條穿出邊的兩個(gè)頂點(diǎn)均不在當(dāng)前左線(xiàn)和右線(xiàn)之間，如圖H點(diǎn)和G點(diǎn)均在右線(xiàn)SF之外，則當(dāng)前的右點(diǎn)為右線(xiàn)的終點(diǎn)，記該右點(diǎn)為路徑的一個(gè)拐點(diǎn)。拐點(diǎn)確定后，將其視為新的起點(diǎn)，循環(huán)以上步驟，當(dāng)終點(diǎn)出現(xiàn)在左線(xiàn)和右線(xiàn)之間時(shí)，從起點(diǎn)開(kāi)始，連接所有的拐點(diǎn)和終點(diǎn)，則找到了一條完整的路徑。如圖4右邊最終路徑圖所示，連接SF和FP，即生成了從起點(diǎn)到終點(diǎn)的路徑。

圖4 拐點(diǎn)與最終路徑圖Fig.4 Maps with corner points and final path

3 動(dòng)態(tài)障礙物處理

在游戲中，如果PC遇到障礙物，游戲操作者本身可以通過(guò)觀察和操作對(duì)障礙物進(jìn)行規(guī)避，而對(duì)于沒(méi)有學(xué)習(xí)能力的NPC，當(dāng)遇到游戲場(chǎng)景動(dòng)態(tài)的變化，例如一個(gè)較大的爆炸碎片堵住了尋得的路線(xiàn)上的某結(jié)點(diǎn)或是一群NPC突然出現(xiàn)在了某個(gè)需要通過(guò)的結(jié)點(diǎn)，此時(shí)如果重新進(jìn)行路徑規(guī)劃是十分不明智的。因此，在路徑規(guī)劃的最后引入動(dòng)態(tài)障礙物規(guī)避層，該層主要負(fù)責(zé)處理碰撞檢測(cè)[9]、局部規(guī)避、群體角色尋路優(yōu)先級(jí)[10]等問(wèn)題。

游戲世界眾多的NPC都是具有物理屬性的，即可能發(fā)生碰撞，那么就需要一個(gè)碰撞檢測(cè)子系統(tǒng)能夠監(jiān)聽(tīng)到此類(lèi)情況的發(fā)生。在3D場(chǎng)景里，碰撞檢測(cè)可以通過(guò)射線(xiàn)透射實(shí)現(xiàn)。射線(xiàn)是以智能NPC自身所在坐標(biāo)為起點(diǎn)向前進(jìn)方向發(fā)射的一條或多條無(wú)終點(diǎn)的線(xiàn)，一旦檢測(cè)出射線(xiàn)存在終點(diǎn)坐標(biāo)，則可判斷其將遇到障礙物。此時(shí)，可以向游戲狀態(tài)獲取障礙物詳細(xì)信息，即可以判斷其是否將發(fā)生碰撞。如若角色在移動(dòng)過(guò)程中接收到的碰撞子系統(tǒng)的決策告知下一個(gè)或是多個(gè)結(jié)點(diǎn)將發(fā)生碰撞，則將其標(biāo)記為阻塞結(jié)點(diǎn)，此時(shí)需要改變尋路策略。對(duì)此可以引入一種基于射線(xiàn)投射的局部A*尋路方法。

定義從阻塞結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)開(kāi)始到阻塞結(jié)點(diǎn)后一個(gè)結(jié)點(diǎn)進(jìn)行局部尋路，然后將新的路徑覆蓋阻塞的部分。這么做的好處是，原先A*算法已經(jīng)求得的路徑花費(fèi)可以重用，提高尋路的效率。對(duì)于NPC群體尋路，可以采取設(shè)置優(yōu)先級(jí)的方法，若高優(yōu)先級(jí)的角色和其他角色發(fā)生碰撞，可以默認(rèn)將其他角色視為靜態(tài)障礙物，等待高優(yōu)先級(jí)的角色走過(guò)后再進(jìn)行尋路。通常優(yōu)先級(jí)的確定是與角色的移動(dòng)力和反應(yīng)速度等因素相關(guān)的。

4 結(jié)束語(yǔ)

文中針對(duì)3D游戲中的路徑規(guī)劃問(wèn)題，提出了分層次的解決方案。首先采用導(dǎo)航網(wǎng)格對(duì)大地圖的狀態(tài)空間進(jìn)行劃分，避免了存儲(chǔ)大量的路點(diǎn)，節(jié)約了內(nèi)存空間。接著使用基于導(dǎo)航網(wǎng)格的A*算法實(shí)現(xiàn)了最優(yōu)網(wǎng)格路徑并對(duì)A*算法的OPEN表進(jìn)行了二叉堆的優(yōu)化，實(shí)驗(yàn)分析表明該方案能夠提高算法的工作效率。接著采用拐角點(diǎn)法生成了網(wǎng)格內(nèi)部的路徑，完成角色的路徑搜索。最后，給出了一種基于局部A*算法的智能NPC的障礙物規(guī)避算法。本文介紹的層次化路徑規(guī)劃解決方案正用于3D游戲運(yùn)動(dòng)模型系統(tǒng)的研發(fā)，初步效果令人滿(mǎn)意。

[1]方約翰, 李睿凡, 郭燕慧, 等. 游戲人工智能: 計(jì)算機(jī)游戲中的人工智能[M]. 北京郵電大學(xué)出版社, 2007.

[2]Buckland M. 游戲人工智能編程案例精粹[M].羅岱,譯. 人民郵電出版社, 2008.

[3]Sturtevant N R,Buro M. Improving Collaborative Pathfinding Using Map Abstraction[C]//AIIDE. 2006: 80-85.

[4]Leigh R, Louis S J, Miles C. Using a genetic algorithm to explore A*-like pathfinding algorithms [C]//Computational Intelligence and Games, 2007. CIG 2007. IEEE Symposium on. IEEE, 2007:72-79.

[5]Graham R, McCabe H, Sheridan S. Pathfinding in computer games[J]. ITB Journal, 2003,8:57-81.

[6]Bj?rnsson Y, Enzenberger M, Holte R C, et al. Fringe search:beating at path-finding on game maps[J]. CIG, 2005, 5: 125-132.

[7] Ballinger C, Louis S. Comparing heuristic search methods for finding effective real-time strategy game plans[C]//2013 IEEE Symposium Series on Computational Intelligence. 2013:122-128.

[8]徐翔, 黃敏. 一種改進(jìn)的群體智能尋路算法[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2012, 29(5): 139-142.

XU Xiang，HUANG Ming.An improved group intelligence pathfinding algorithm[J]. Computer Applications and Software,2012,29(5):139-142.

[9] Bakkes S C J, Spronck P H M, van Lankveld G. Player behavioural modelling for video games[J]. Entertainment Computing, 2012,3(3): 71-79.

Application of a A* algorithm-based hierarchical path planning in 3D games

QI Yue1, ZHAO Yang2, YANG Fan3
（College of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China）

This paper focuses on how to generate a 3D navmesh and implement high-speed path-finding for autonomous characters in 3D games. We proposed a hierarchical solution to meet the requirement. Firstly, a navmesh is used to divide the state space. Then we used the A* algorithm to find the path of the navmesh with making use of binary heaps to optimize the OPEN table. We also proposed a method of corner points to find the final path. At last, we used ray transmission to detect the dynamic obstacles. The initial experimentation shows that our solution is able to be used in some 3D games.

navmesh; A* Algorithm; terrain factor; binary heaps; corner points; ray transmission

TN919.32

A

1674-6236(2014)11-0037-03

2013-10-24 稿件編號(hào)：201310166

祁 悅(1989 —），女，江蘇揚(yáng)州人，碩士。研究方向：游戲人工智能。