淺談人工智能尋路算法在電子游戲中的研究和應(yīng)用

唐李順

摘 要：在電子游戲設(shè)計與開發(fā)中，人工智能（AI）作為提升與改善游戲質(zhì)量核心技術(shù)，其發(fā)展需求越來越高。尋路算法是人工智能系統(tǒng)中最基本也是最重要的部分，目前應(yīng)用最為廣泛的AI尋路算法為A*算法，該算法在一定程度上實現(xiàn)了游戲人工智能系統(tǒng)的優(yōu)化?；诖?，本文有相關(guān)概念出發(fā)，對A*算法在電子游戲中的應(yīng)用進(jìn)行了分析。

關(guān)鍵詞：人工智能；電子游戲；尋路算法

1 人工智能尋路算法的相關(guān)概述

1.1 人工智能

人工智能（Artificial Intelligence簡稱“AI”），是基于計算機(jī)與機(jī)器人技術(shù)研發(fā)的基礎(chǔ)上形成的用于模擬、擴(kuò)展以及延伸人智能行為與邏輯的技術(shù)、方法、理論以及應(yīng)用系統(tǒng)的新興知識學(xué)科[1]。人工智能涉及范圍廣泛，包括計算機(jī)科學(xué)、語言學(xué)、哲學(xué)、數(shù)學(xué)、自然科學(xué)、心理學(xué)以及社會科學(xué)等等。在電子游戲產(chǎn)業(yè)發(fā)展中，運用人工智能為游戲的虛擬環(huán)境以及游戲各種人物角色整填靈動性與真實性，進(jìn)一步提升了游戲的可玩性，有利于游戲產(chǎn)業(yè)的優(yōu)化發(fā)展。

1.2 最短路徑算法

最短路徑算法是游戲AI尋路算法中應(yīng)用最為廣泛的路徑搜索算法。在數(shù)學(xué)、運籌學(xué)、數(shù)據(jù)算法分析中具有普遍分析與介紹。非啟發(fā)式最短路徑算法（Dijkstra算法）和啟發(fā)式最短路徑算法（A*算法）是最短路徑算法中的典型代表。其中非啟發(fā)式Dijkstra算法是在基于某點的基礎(chǔ)上，由起點（中心點）向外逐漸拓展至終點，從而找到最短路徑的算法。該算法由于計算的節(jié)點相對較多，在運算構(gòu)成中其速度以及效率不高。啟發(fā)式A*算法是在基于優(yōu)先搜索的基礎(chǔ)上進(jìn)行啟發(fā)式搜索的一種算法，即，在游戲路網(wǎng)圖的一個起點位置，線進(jìn)行廣度搜索，用以確定搜索區(qū)域，在利用函數(shù)估價方法對路圖網(wǎng)進(jìn)行評估式啟發(fā)式搜索，通過確定最佳路徑，在搜索確定，從而逐漸發(fā)現(xiàn)搜索目標(biāo)，A*算法是游戲設(shè)計與開發(fā)中較為常用的一種路徑搜索法。

2 人工智能尋路算法在電子游戲中的應(yīng)用

2.1 電子小游戲中簡單尋路算法的應(yīng)用

在電子小游戲中，人們對于游戲效果的要求并不高，尤其是簡單的動作型電子小游戲，在設(shè)計構(gòu)成中注重游戲人物角色側(cè)重于尋路、閃避以及跟蹤行為的編程設(shè)計。例如，對于小游戲中的非玩家控制角色（Non-Player Character簡稱“NPC”），常常處于既定的區(qū)域范圍中行走，當(dāng)玩家操作角色進(jìn)入到其范圍內(nèi)時，NPG將進(jìn)行一定的攻擊或躲避行為。在這一構(gòu)成中所應(yīng)用的尋路算法主要有隨機(jī)尋路算法、追蹤算法以及閃避算法。

2.2 大型電子游戲中AI啟發(fā)式A*算法的應(yīng)用

在大型電子游戲中，對游戲音效、視覺效果以及人物角色的要求更高也更為嚴(yán)格。游戲玩家操作角色以及非玩家操作角色的人性化需求，是保證游戲質(zhì)量的關(guān)鍵所在。目前，在大型電子游戲中應(yīng)用最為廣泛的尋路算法為A*算法，對包括攻擊、躲避、尋路、阻擊、轉(zhuǎn)向、跳躍等行為以及虛擬空間的感知進(jìn)行了設(shè)定與編程。因此，在大型電子游戲人工智能尋路算法的應(yīng)用通常由5個基本框架構(gòu)成，包括Behavior（角色行為）、Brain（腦思維）、Agent（非玩家操作角色代理）、Perception（非玩家操作角色感知）、Physical（RPG Model）（NPC物理模型）。

游戲AI控制系統(tǒng)的運轉(zhuǎn)由非玩家操作角色（NPC）開始，非玩家操作角色通過大腦（Brain）的思考，基于A*算法，針對玩家操作角色的物理模型（RPG Model）信息數(shù)據(jù)搜索游戲場景，并從命令列表中（Command Que）選用所要執(zhí)行的行為（Behavior），并將信息傳遞給非玩家操作角色代理（Agent），人工智能控制系統(tǒng)對RPG Model進(jìn)行行為操作，在此過程中其尋路算法流程如下圖。

2.3 對游戲人工智能A*算法優(yōu)化思考

在游戲設(shè)計過程中，需對人工智能A*算法進(jìn)行一定的測試與調(diào)試，從而提升AI尋路系統(tǒng)的優(yōu)化性。在測試過程中，往往會遇到諸多問題，對此游戲設(shè)計人員需進(jìn)行及時而有效的處理，用以保證游戲的可玩性。例如，在大型電子游戲AI尋路系統(tǒng)中，由于游戲內(nèi)容復(fù)雜，游戲中的點數(shù)量相對較多，因此NPC在盡心尋路搜索時，所達(dá)到的具體位置會出現(xiàn)集中與密集的現(xiàn)象。但是如果，路點數(shù)量過多，在一定程度上降低了NPC尋路速度；路點數(shù)量較少，又會在一定程度上使得NPC尋路尋路速度過快，并在一定程度上降低游戲的真實性。因此，在游戲設(shè)計與測試過程中需運用尋路算法進(jìn)行反復(fù)而全面的測試與考慮。

3 結(jié)論

基于人工智能系統(tǒng)在游戲軟件開發(fā)與設(shè)計中的應(yīng)用與完善，電子游戲AI尋路算法的優(yōu)化與改進(jìn)成為人們關(guān)注的重點，對電子游戲質(zhì)量的提升與創(chuàng)新發(fā)展具有重要意義。

參考文獻(xiàn)

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

（作者單位：成都理工大學(xué)）