人工智能尋路算法及其在游戲中的應(yīng)用研究

李志豪 張毅 黃健宇

摘要：近年來，大型網(wǎng)絡(luò)游戲逐漸開發(fā)，游戲開發(fā)中所用到的技術(shù)大部分為智能化、自動(dòng)化技術(shù)。其中基于人工智能的尋路算法在游戲開發(fā)中比較突出，A*搜索算法是尋路算法中反映速度最快的一種，能夠在短時(shí)間內(nèi)遍歷諸多地點(diǎn)，并找尋出最短的路徑。基于此，本文將對游戲中的人工智能尋路算法中的A*搜索算法進(jìn)行分析，研究其實(shí)際算法的改進(jìn)，并將改進(jìn)后的智能算法應(yīng)用到實(shí)際游戲開發(fā)中。

前言：隨著游戲的開發(fā)與應(yīng)用，人工智能A*搜索算法占據(jù)了游戲設(shè)計(jì)是重要部分。其中A*搜索算法是一種被廣泛應(yīng)用的最短路徑搜索算法之一，在廣度優(yōu)先搜索模式的啟發(fā)之下，進(jìn)行路徑搜索，其搜索函數(shù)所針對的對象是對當(dāng)前搜索位置。在實(shí)際的路徑遍歷中，A*搜索算法經(jīng)常會走彎路，為了提升路徑搜索效率，需要對A*搜索算法進(jìn)行改進(jìn)，并保障A*搜索算法下所搜索的路徑為最優(yōu)。

1.人工智能尋路算法概述

1.1人工智能

人工智能的簡稱為AI，是一種的應(yīng)用于模擬場景開發(fā)、延伸以及拓展等的智能理論，是目前比較時(shí)尚的技術(shù)科學(xué)。人工智能所包含的內(nèi)容比較多，其中主要包括思維過程模擬，以及智能型我的模擬。總體來說，人工智能所研究的對象是使得計(jì)算機(jī)能夠運(yùn)用專業(yè)知識去解決實(shí)際問題，模擬人類的部分智能行為。基于人工智能尋路算法在游戲中的應(yīng)用，推動(dòng)了游戲的開發(fā)[1]。

1.2 A*搜索算法

A*搜索算法實(shí)際上是一種啟發(fā)式的算法，在很多領(lǐng)域中得以應(yīng)用。A*搜索算法能夠在地圖上的兩點(diǎn)間找到一條路徑，這條路徑是兩點(diǎn)間的最短路徑。在搜索路徑之前，該算法首先需要判斷，所要計(jì)算的兩點(diǎn)間是否存在著路徑。除了A*搜索算法還有很多搜索路徑的計(jì)算方式，但是A*搜索算法對于路徑的計(jì)算以及搜索速度是最快的，且其算法比較靈活多變。A*搜索算法在路徑搜索環(huán)節(jié)中不會盲目，有時(shí)也能進(jìn)行回溯嘗試。A*搜索算法的搜索過程，主要是通過在地圖中創(chuàng)建與位置相對應(yīng)的節(jié)點(diǎn)，并在地圖上以移動(dòng)的方式來實(shí)現(xiàn)。這些節(jié)點(diǎn)有不同的屬性，g代表著起始節(jié)點(diǎn)到該節(jié)點(diǎn)的代價(jià)，h代表著該節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的估計(jì)代價(jià)，f代表著是經(jīng)過該節(jié)點(diǎn)的路徑估計(jì)值[2]。

2.A*搜索算法改進(jìn)

2.1減少AI角色之間的碰撞

在大型的網(wǎng)絡(luò)游戲中，AI角色之間不允許碰撞，如果不同的AI角色之間出現(xiàn)了碰撞，將會出現(xiàn)節(jié)點(diǎn)怪異。但是在進(jìn)行A*搜索算法搜索路徑環(huán)節(jié)中，不能忽視游戲中不同的AI角色之間的相互干擾，如果不能對以上情況進(jìn)行避免將會出現(xiàn)不同的尋路者之間的穿越。為了避免不同角色之間的碰撞，需要對靠近一個(gè)正在運(yùn)動(dòng)的AI角色時(shí)，需要系統(tǒng)對其各自路徑上的節(jié)點(diǎn)進(jìn)行懲罰，并對另辟蹊徑的AI尋路著進(jìn)行獎(jiǎng)勵(lì)，在這樣的模式下就能夠避免AI角色之間的碰撞。在 游戲開發(fā)時(shí)，為了避免不同角色之間發(fā)生碰撞，需要在后臺編寫一段代碼，當(dāng)角色之間發(fā)生碰撞時(shí)，一個(gè)AI尋路者需要找到新路徑，如果一個(gè)被碰撞的AI角色處于移動(dòng)的狀態(tài)時(shí)，則原AI尋路者需要等待，待其離開之后，在就行移動(dòng)[3]。

2.2未知區(qū)域探索

在實(shí)際的游戲中，A*搜索算法的應(yīng)用能夠幫助AI角色進(jìn)行未知區(qū)域的路徑探索。而形成這樣的功能實(shí)際上需要游戲系統(tǒng)中為游戲中的每一個(gè)角色創(chuàng)建一個(gè)"KnownWalkability"數(shù)組，在該數(shù)組中能夠?qū)巧剿鞯穆窂竭M(jìn)行記憶，避免AI角色在路的死端進(jìn)行徘徊，并導(dǎo)致路徑選擇上出現(xiàn)問題。在游戲中，一旦地圖的未知區(qū)域被其他玩家所探索過了，那么AI角色在進(jìn)行尋路的環(huán)節(jié)中就會很容易找到未知[4]。

2.3非方形區(qū)域的搜索

A*搜索算法在以前的圖形搜索中，一般使用的2D環(huán)境的方形圖，但是隨著游戲技術(shù)的不斷開發(fā)，可以對非規(guī)則形狀的圖形區(qū)域進(jìn)行探索。例如在《英雄聯(lián)盟》、《夢三國》等游戲中，游戲開發(fā)可以設(shè)計(jì)出與角色路徑探索相關(guān)的尋路關(guān)卡。首先需要設(shè)計(jì)者在地形圖中確立一個(gè)路徑點(diǎn)系統(tǒng)，該路徑點(diǎn)一般是道路的轉(zhuǎn)折點(diǎn)，在地形圖中如果兩個(gè)點(diǎn)之間沒有障礙，就視為兩個(gè)點(diǎn)是相鄰的，在以上競技類的游戲中，需要相鄰位置安排在表格中，并記錄地圖上兩個(gè)點(diǎn)之間的直線距離，進(jìn)而實(shí)現(xiàn)非方形的區(qū)域搜索。

3.改進(jìn)后的A*搜索算法應(yīng)用

3.1盲目搜索

將改進(jìn)了的A*搜索算法在實(shí)際游戲中的應(yīng)用，能夠?qū)崿F(xiàn)地圖的盲目搜索，盲目搜素實(shí)際上需要是在準(zhǔn)確搜索的基礎(chǔ)上，確定AI角色的大致位置，在實(shí)際游戲中的應(yīng)用效果比較明顯。盲目搜索是在一個(gè)圖的搜索之下，對相關(guān)邊的全部關(guān)系進(jìn)行遍歷。同時(shí)該種搜索模式能夠針對不區(qū)域內(nèi)部的節(jié)點(diǎn)和邊進(jìn)行分析，能夠及時(shí)發(fā)現(xiàn)已經(jīng)遍歷過的目標(biāo)節(jié)點(diǎn)，并迅速的將其排除在外。盲目搜索與其他種搜索模式相比，存在著很多差異，也有很多優(yōu)勢，一方面在搜索環(huán)節(jié)中所需要的信息都比較小，另一方面所搜索的深度和廣度都比較大。

3.2 cost的圖搜索

在很多游戲圖搜索環(huán)節(jié)中，要想搜索一條路徑，都需要具有一個(gè)開銷，開銷實(shí)際上就是權(quán)--cost。在游戲者想要尋找到兩點(diǎn)之間的最短路徑，首先需要考慮開銷，在開銷理念中，沿著兩條比較短路徑進(jìn)行遍歷，會比兩條長邊進(jìn)行遍歷便捷的多?；贏*搜索算法就屬于開銷中的一種。將A*搜索算法進(jìn)行改進(jìn)，能夠?qū)蓚€(gè)節(jié)點(diǎn)之間的距離進(jìn)行判斷，一方面提升了A*搜索算法實(shí)際效率，另一方面也對開銷進(jìn)行充分利用[5]。

3.3以游戲Gauntlet為例分析A*搜索算法的實(shí)際應(yīng)用

Gauntlet游戲是在歐洲開發(fā)，以奇幻世界為游戲背景的角色扮演類游戲。在實(shí)際游戲中有以下四個(gè)角色，分別為英雄、女神、魔法師以及精靈。在該游戲中包含了五大實(shí)體模塊，分別為行動(dòng)、行為、感知、代理、視覺等。在 A*搜索算法下，該游戲的AI尋路過程如下：首先將游戲啟動(dòng)，在游戲登陸者按鍵之后進(jìn)入到游戲環(huán)節(jié)中，游戲背景啟動(dòng)。然后游戲主程序進(jìn)行AI角色遍歷，在角色遍歷環(huán)節(jié)中，所消耗的時(shí)間比較長。因此基于這樣的背景，游戲開發(fā)者為了減少游戲啟動(dòng)的時(shí)間，在游戲人物遍歷環(huán)節(jié)中，改變幀速。一般情況下普遍采用每幀只允許一個(gè)AI人物進(jìn)行尋路的模式，對整體幀速進(jìn)行控制。這樣的設(shè)計(jì)能夠使得整體的游戲畫面能夠更加的流暢。當(dāng)AI角色進(jìn)入時(shí)，角色大腦需要對問題進(jìn)行思考，找到游戲中需要考慮的問題。然后開始正式的對游戲世界進(jìn)行探索，對游戲中不同的帶來進(jìn)行合理調(diào)用。最先需要調(diào)用的就是感知類--AIPerception：：Perceive（），然后感知類的函數(shù)將搜索信息傳遞到行動(dòng)類中，調(diào)用行動(dòng)類的表現(xiàn)--AIBehavior：：Behave（），在行動(dòng)類的驅(qū)使下，對游戲中具體的人物行為進(jìn)行控制，然后進(jìn)行游戲路徑探索，調(diào)用函數(shù)--AINodeManager：：DoPathFinding（），函數(shù)調(diào)用之后，系統(tǒng)后臺自動(dòng)計(jì)算出路徑距離，驅(qū)動(dòng)AI人物開始尋路表現(xiàn)。

結(jié)論：

綜上所述，在本文中對人工智能尋路算法進(jìn)行介紹，著重分析了A*搜索算法的實(shí)際應(yīng)用。為了提升游戲中尋路效率，對當(dāng)前的A*搜索算法進(jìn)行改進(jìn)，首先需要避免AI角色之間的碰撞，提升算法對未知區(qū)域的探索，并優(yōu)化A*搜索算法對非方形區(qū)域的搜索。將改進(jìn)了的A*搜索算法在實(shí)際游戲中應(yīng)用，通過實(shí)際的游戲進(jìn)行路徑尋路分析。

參考文獻(xiàn)：

[1]詹海波.人工智能尋路算法在電子游戲中的研究和應(yīng)用[D].華中科技大學(xué)，2006.

[2]何文雅.3D游戲場景中虛擬角色的智能尋徑應(yīng)用研究[D].華中師范大學(xué)，2009.

[3]沈健.FPS游戲?qū)ぢ匪惴ǖ难芯颗c實(shí)現(xiàn)[D].華南理工大學(xué)，2012.

[4]胡俊.游戲開發(fā)中的人工智能研究與應(yīng)用[D].電子科技大學(xué)，2007.

[5]荊東星.人工神經(jīng)網(wǎng)絡(luò)在游戲?qū)ぢ分械膽?yīng)用研究[D].長沙理工大學(xué)，2010.