衛(wèi)　敏

(山西職業(yè)技術(shù)學(xué)院，山西 太原 030006)

?

3D游戲中AI自動(dòng)尋路機(jī)制的算法與優(yōu)化策略研究

衛(wèi)敏

(山西職業(yè)技術(shù)學(xué)院，山西 太原 030006)

摘要：隨著3D游戲的日趨流行，在復(fù)雜的3D游戲環(huán)境中如何能使非玩家控制角色準(zhǔn)確實(shí)現(xiàn)自動(dòng)尋路功能成為了3D游戲開發(fā)技術(shù)中一大研究熱點(diǎn)。本文針對(duì)3D游戲開發(fā)中的AI自動(dòng)尋路功能的A*算法進(jìn)行了基于Unity3D游戲開發(fā)平臺(tái)的優(yōu)化與實(shí)現(xiàn)，優(yōu)化后的A*算法較之傳統(tǒng)的路徑規(guī)劃算法，實(shí)時(shí)性更高、靈活性更強(qiáng)，尋路結(jié)果更加接近人工選擇的路徑結(jié)果。

關(guān)鍵詞：3D游戲；AI人工智能系統(tǒng)；尋路算法

現(xiàn)今隨著手機(jī)3D游戲開發(fā)技術(shù)的日漸成熟，游戲玩家對(duì)游戲品質(zhì)的要求也越來(lái)越高。玩家對(duì)游戲品質(zhì)的評(píng)價(jià)一般主要取決于游戲的操控性是否靈活、游戲的虛擬環(huán)境是否逼真以及游戲的運(yùn)行是否流暢等方面。設(shè)計(jì)開發(fā)3D游戲，怎樣在各個(gè)性能指標(biāo)間實(shí)現(xiàn)平衡，則屬于核心問(wèn)題。

1AI自動(dòng)尋路功能概述

在游戲中，AI(即人工智能)系統(tǒng)主要是用于實(shí)現(xiàn)游戲角色的某種智能行為，使用戶的游戲體驗(yàn)更加逼真，增加游戲的趣味性[1]。例如在射擊游戲中敵人的子彈可以自動(dòng)追蹤攻擊玩家；在NPC游戲中敵人可以自動(dòng)的避開障礙物尋找最短路徑到達(dá)玩家所在目的地對(duì)玩家進(jìn)行攻擊，這些智能行為的實(shí)現(xiàn)就是通過(guò)AI系統(tǒng)中的智能尋路功能來(lái)完成的。

在技術(shù)實(shí)現(xiàn)方面，本文所研究的尋路算法設(shè)計(jì)主要是基于一種經(jīng)過(guò)變異的貪心算法——A Star算法框架構(gòu)建的[2]。通過(guò)對(duì)游戲場(chǎng)景中預(yù)先設(shè)置的路徑節(jié)點(diǎn)進(jìn)行分析計(jì)算找出最優(yōu)路線，實(shí)現(xiàn)游戲角色的智能尋路。

23D游戲中AI算法的設(shè)計(jì)原理

A Star算法簡(jiǎn)稱A*算法，其基本原理是通過(guò)創(chuàng)建的開放式列表與封閉式列表對(duì)游戲場(chǎng)景中的所有路徑節(jié)點(diǎn)進(jìn)行比對(duì)和篩選，從而計(jì)算出最短的路徑，為了節(jié)省游戲在這方面的計(jì)算開銷，該算法采取的是模糊比對(duì)，省略了貪心算法中的回溯計(jì)算部分。

2.1A*算法的基本原理

如圖1所示，將游戲角色的起始位置設(shè)為開始節(jié)點(diǎn)，要到達(dá)的目的地設(shè)為目標(biāo)節(jié)點(diǎn)，黑色區(qū)域是障礙物標(biāo)志，白色區(qū)域?yàn)榭赏ㄐ新窂健?/p>

圖1　路徑節(jié)點(diǎn)設(shè)置示意圖

圖2　A*算法基本原理

A*算法的基本設(shè)計(jì)原理如圖2所示，首先將所有需要檢測(cè)的路徑節(jié)點(diǎn)讀入到開放式列表，從起始節(jié)點(diǎn)開始中選取距離目的節(jié)點(diǎn)最近的節(jié)點(diǎn)依次與目標(biāo)節(jié)點(diǎn)進(jìn)行比對(duì)，所得到路徑即為最優(yōu)路徑。該算法通過(guò)一定的擇優(yōu)策略選擇場(chǎng)景中節(jié)點(diǎn)進(jìn)行比對(duì)，例如將圖1中的路徑起始節(jié)點(diǎn)設(shè)為A，目標(biāo)節(jié)點(diǎn)設(shè)為B，當(dāng)前計(jì)算出的最優(yōu)路徑節(jié)點(diǎn)為C，在僅考慮節(jié)點(diǎn)間的幾何距離前提下其節(jié)點(diǎn)代價(jià)的計(jì)算可由公式(1)得出：

(A-C)2+(B-C)2.

(1)

通過(guò)計(jì)算的各個(gè)節(jié)點(diǎn)代價(jià)，選擇代價(jià)最小的節(jié)點(diǎn)優(yōu)先進(jìn)行比對(duì)。最壞的情況是遍歷了所有的節(jié)點(diǎn)才得到結(jié)果，因此該算法的計(jì)算效率與游戲場(chǎng)景中的節(jié)點(diǎn)數(shù)量有直接關(guān)系，如果游戲場(chǎng)景較為復(fù)雜，包含有大量的路徑節(jié)點(diǎn)信息，會(huì)嚴(yán)重增加算法開銷，要解決這些問(wèn)題就需要對(duì)A*算法做進(jìn)一步的優(yōu)化。

2.2A Star尋路算法的優(yōu)化

首先，從節(jié)點(diǎn)列表的結(jié)構(gòu)優(yōu)化上著手，改進(jìn)A*算法的性能。主要是將所有節(jié)點(diǎn)按照計(jì)算出的節(jié)點(diǎn)代價(jià)由小到大進(jìn)行排序并建立相應(yīng)的結(jié)構(gòu)列表，根據(jù)節(jié)點(diǎn)的變化動(dòng)態(tài)維護(hù)該數(shù)據(jù)結(jié)構(gòu)，從開放式列表中選擇最優(yōu)節(jié)點(diǎn)時(shí)可直接通過(guò)該數(shù)據(jù)列表讀取到當(dāng)前的最優(yōu)節(jié)點(diǎn)，該方法適用于復(fù)雜的游戲場(chǎng)景尋路，以增加游戲占用的系統(tǒng)存儲(chǔ)空間為代價(jià)減少尋路算法的系統(tǒng)開銷。

其次是在動(dòng)態(tài)場(chǎng)景中對(duì)尋路算法進(jìn)行優(yōu)化調(diào)整。當(dāng)在游戲中有多個(gè)對(duì)象同時(shí)進(jìn)行尋路移動(dòng)時(shí)，優(yōu)化策略可分為以下幾步來(lái)實(shí)現(xiàn)動(dòng)態(tài)的路徑調(diào)整：

1) 為每個(gè)對(duì)象建立一個(gè)碰撞列表用于記錄該對(duì)象發(fā)生過(guò)碰撞的路徑信息；

2) 根據(jù)各個(gè)對(duì)象之間的優(yōu)先級(jí)進(jìn)行排序，當(dāng)檢測(cè)到碰撞后，將選擇優(yōu)先級(jí)別最高的對(duì)象重新進(jìn)行節(jié)點(diǎn)定位和路徑選擇，同時(shí)停止其他對(duì)象的移動(dòng)，直到優(yōu)先級(jí)最高的對(duì)象通過(guò)再繼續(xù)原路徑的移動(dòng)；

3) 將上一步碰撞檢測(cè)到的路徑信息記錄到碰撞列表中，每次檢測(cè)到碰撞后，都先在碰撞列表中進(jìn)行查詢。如果路徑信息是重復(fù)的則要更新路徑選擇策略，如果路徑信息無(wú)重復(fù)則要對(duì)碰撞列表進(jìn)行更新。這主要是為了避免對(duì)象的路徑重復(fù)，反復(fù)與同一對(duì)象發(fā)生碰撞。

33D游戲開發(fā)中AI尋路算法的具體實(shí)現(xiàn)

本文采用了目前在移動(dòng)平臺(tái)上較為流行的一款游戲開發(fā)引擎——Unity3D來(lái)進(jìn)行AI尋路算法的設(shè)計(jì)。

3.13D游戲開發(fā)軟件——Unity3D游戲引擎中AI系統(tǒng)的設(shè)計(jì)框架

Unity3D游戲引擎本身就提供有AI尋路系統(tǒng)，主要采用的是路徑節(jié)點(diǎn)(WayPoint)算法進(jìn)行路徑選擇。WayPoint算法是基于A*算法框架由Unity3D引擎自行開發(fā)的尋路策略，其設(shè)計(jì)框架可以簡(jiǎn)述為：

首先通過(guò)調(diào)用Unity3D游戲引擎中的Navigation路徑導(dǎo)航系統(tǒng)對(duì)場(chǎng)景中的地形進(jìn)行分析計(jì)算，建立節(jié)點(diǎn)信息列表；

其次進(jìn)行尋路者的設(shè)置，為尋路者添加AI尋路組件(Nav Mesh Agent)計(jì)算尋路者的節(jié)點(diǎn)位置、運(yùn)動(dòng)速度、旋轉(zhuǎn)速度等信息；

初始化節(jié)點(diǎn)信息，通過(guò)WayPoint算法在游戲場(chǎng)景中標(biāo)記出所有的路徑節(jié)點(diǎn)，并在各個(gè)節(jié)點(diǎn)間建立連接路徑，在確定了的起始節(jié)點(diǎn)與目的節(jié)點(diǎn)之間每次任取兩個(gè)分別與起始節(jié)點(diǎn)和目的節(jié)點(diǎn)臨近的節(jié)點(diǎn)計(jì)算路徑代價(jià)，并優(yōu)先選擇其中代價(jià)最小者來(lái)獲取最短路徑；

編寫尋路控制腳本用于實(shí)現(xiàn)尋路者的動(dòng)態(tài)尋路控制，當(dāng)目的節(jié)點(diǎn)發(fā)生改變，通過(guò)尋路腳本控制可動(dòng)態(tài)更新追蹤目的節(jié)點(diǎn)并進(jìn)行路徑的調(diào)整控制。

3.2三維游戲場(chǎng)景中AI尋路功能的實(shí)現(xiàn)與控制

Unity3D游戲引擎主要支持C#、Java及boo三種腳本的編程開發(fā)，這里對(duì)自動(dòng)尋路的控制實(shí)現(xiàn)編程采用的是C#腳本，其核心代碼示例如下：

Public class NavMA:MonoBehaviour{

Transformm_object;//定義尋路者對(duì)象組件變量

Player m_MyPlay;//定義玩家變量

NavMeshAgentm_MeshA;//定義尋路組件變量

voidStart(){

m_object=this.transform;//將尋路者對(duì)象實(shí)例化

m_MyPlay=GameObject.FindGameObjectWithTag(“Player”).GetComponent();//實(shí)例化玩家對(duì)象，通過(guò)m_MyPlay的位置屬性可鎖定動(dòng)態(tài)目標(biāo)節(jié)點(diǎn)

m_MeshA=GetComponent();//導(dǎo)入游戲地形的節(jié)點(diǎn)計(jì)算信息

m_MeshA.SetDestination(m_MyPlay. m_object.position);//實(shí)時(shí)鎖定尋路的目標(biāo)節(jié)點(diǎn)位置為玩家所在位置}

void Update(){

MoveCon();//調(diào)用控制函數(shù)}

voidMoveCon(){

m_MeshA.Move(m_object.TransformDirection((new Vector3(0.0f,0.0f,0.3f))));//控制尋路者動(dòng)態(tài)追蹤玩家坐標(biāo)節(jié)點(diǎn)，計(jì)算最短路徑，并按照設(shè)置的速度進(jìn)行尋路移動(dòng)}}

4結(jié)論

本文針對(duì)目前3D游戲開發(fā)中的研究熱點(diǎn)——AI尋路功能的優(yōu)化進(jìn)行了一些研究和嘗試。通過(guò)對(duì)A Star尋路算法的應(yīng)用分析，再進(jìn)一步優(yōu)化了算法，并通過(guò)Unity3D平臺(tái)進(jìn)行了實(shí)現(xiàn)。但為了兼顧游戲的運(yùn)行效率，算法設(shè)計(jì)中未能提高現(xiàn)有尋路機(jī)制的精確性，在一些特殊情況下會(huì)影響到用戶的游戲體驗(yàn)，在這一方面還有待進(jìn)行更加深入的研究。

參考文獻(xiàn)

[1]梁毅，周剛.基于定位點(diǎn)和路徑復(fù)用的大型多人在線游戲?qū)ぢ匪惴╗D].成都：四川大學(xué)，2013.

[2]楊科選.人工智能尋路算法及其在游戲中的應(yīng)用研究[D].長(zhǎng)沙：中南大學(xué)，2013.

收稿日期：2015-12-31

作者簡(jiǎn)介：衛(wèi)敏(1979- )，女，山西太原人，助講，大學(xué)本科，研究方向：計(jì)算機(jī)應(yīng)用。

文章編號(hào)：1674- 4578(2016)02- 0091- 02

中圖分類號(hào)：TP391.41

文獻(xiàn)標(biāo)識(shí)碼：A

3D Games AI Algorithms Automatically Find Its Way Mechanism and Strategy Research

Wei Min

(DepartmentofComputerScience,ShanxiVocationalandTechnicalCollege,TaiyuanShanxi030006,China)

Abstract:With the increasingly popular spreading of 3D game, how to make non-player to control characters and exactly realize the automatic pathfinding function becomes one major research focus in the 3D game development technology under the complex 3D game environment. Aiming at the A* algorithm of AI automatic pathfinding function, this paper makes optimization and realization for it based on Unity 3D game development platform. Compared to the traditional algorithm of route planning, the optimized A* algorithm is more real-time and flexible, and its pathfinding result is closer to that of artificial selection.

Key words:D games; AI artificial intelligence system; pathfinding algorithm