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

祁 悅 ，趙 洋 ，楊 帆

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

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

祁 悅1，趙 洋2，楊 帆3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖4 拐點與最終路徑圖Fig.4 Maps with corner points and final path

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

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

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

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

4 結(jié)束語

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

[1]方約翰, 李睿凡, 郭燕慧, 等. 游戲人工智能: 計算機(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ī)應(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 稿件編號：201310166

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