李志豪 張毅 黃健宇

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

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

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

1.1人工智能

人工智能的簡稱為AI，是一種的應(yīng)用于模擬場景開發(fā)、延伸以及拓展等的智能理論，是目前比較時尚的技術(shù)科學(xué)。人工智能所包含的內(nèi)容比較多，其中主要包括思維過程模擬，以及智能型我的模擬?？傮w來說，人工智能所研究的對象是使得計算機能夠運用專業(yè)知識去解決實際問題，模擬人類的部分智能行為?；谌斯ぶ悄軐ぢ匪惴ㄔ谟螒蛑械膽?yīng)用，推動了游戲的開發(fā)[1]。

1.2 A*搜索算法

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

2.A*搜索算法改進

2.1減少AI角色之間的碰撞

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

2.2未知區(qū)域探索

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

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

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

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

3.1盲目搜索

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

3.2 cost的圖搜索

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

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

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

結(jié)論：

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

參考文獻：

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

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

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

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

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