人工智能尋路算法及其在游戲中的應用研究

李志豪 張毅 黃健宇

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

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

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

1.1人工智能

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

1.2 A*搜索算法

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

2.A*搜索算法改進

2.1減少AI角色之間的碰撞

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

2.2未知區域探索

在實際的游戲中，A*搜索算法的應用能夠幫助AI角色進行未知區域的路徑探索。而形成這樣的功能實際上需要游戲系統中為游戲中的每一個角色創建一個"KnownWalkability"數組，在該數組中能夠對角色所探索的路徑進行記憶，避免AI角色在路的死端進行徘徊，并導致路徑選擇上出現問題。在游戲中，一旦地圖的未知區域被其他玩家所探索過了，那么AI角色在進行尋路的環節中就會很容易找到未知[4]。

2.3非方形區域的搜索

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

3.改進后的A*搜索算法應用

3.1盲目搜索

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

3.2 cost的圖搜索

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

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

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

結論：

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

參考文獻：

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

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

[3]沈健.FPS游戲尋路算法的研究與實現[D].華南理工大學，2012.

[4]胡俊.游戲開發中的人工智能研究與應用[D].電子科技大學，2007.

[5]荊東星.人工神經網絡在游戲尋路中的應用研究[D].長沙理工大學，2010.