網絡游戲中的尋路算法

韓宇澤

摘 要

近年來伴隨網絡游戲產業的全面進程，游戲設計環節對人工智能的要求已不可同日而語。作為網絡游戲設計的基礎，人工智能引擎是實現高品質現實模擬的先決條件，但是在人工智能引擎中，移動系統即為基礎因素，在尋路系統的實現上，現階段大多使用迪克斯特拉算法及以決策樹概念為核心的A*算法，而我在對現階段主流算法予以對比基礎上，深化了算法的優化概念。

【關鍵詞】網絡游戲 尋路算法

眾所周知，人工智能即為現階段快速發展的一門學科，其側重于分析、開發模擬人的智能。當今網絡游戲產業化發展迅速，人工智能也將從根本促進虛擬游戲的發展，為游戲中的人物賦予“生命”，這將從根本深化游戲場景的真實性及游戲的可玩性。人工智能引擎即為網絡游戲的主要構成因子，人工智能會影響游戲的可玩性與玩家對游戲的認可，優秀的智能系統可以讓游戲中的角色在建設及戰爭等特定狀態下具備比人更優異的處理能力，因此可以讓玩家有擁有更好的游戲體驗。目前，人工智能得到了游戲設計人員的重視，并慢慢成為深化游戲品質的主要切入點。人工智能在游戲中一般體現于非玩家角色的行為表現，一些即時戰略游戲，人工智能可以在全范圍內予以智能化尋路行為，其中涵蓋了單個人物的智能尋路，而且還具有群體的編隊尋路、碰撞協調及多單位智能路徑分配能力，而尋路的目的即怎樣找到從起點到達終點的最短途徑。因為網絡游戲需要一定的實時性，因此要在最短的時間范圍內尋求一條相對較短的途徑。現階段，常規的尋路模式主要包括A*算法（A-Star算法）與靜態路徑法（Static path method）兩種。

1 Static path method

在相對小的地圖內，通過Static path method去查找路徑能夠達到精準的效果。Static path method生成算法較為多見的包括迪克斯特拉算法。在使用Static path method時，我們要預先計算地圖內各節點到達其他節點的路徑參數，在物體要到達特定目標點時，只要依附于指定的路徑走就能夠到達目的地。但是Static path method的最大缺點即為要占用很多的內存資源，而且大地圖中不適合使用Static path method。對于256*256的地圖而言，所有結點均需儲存其他結點的方向，因此其大小即256*256*256*256=4GB；同時運算量大，在處理地圖上節點時，均需進入一次隊列，共256*256個目標點需予以計算，因此需要進行256*256*256*256*8*2次！我們不難看出，Static path method是無法直接應用于尋路系統的。不論是計算時間亦或內存占用率，對于一臺普通電腦而言都是不可承受的，所以從游戲設計層面予以分析，單純擇取Static path method尋路并非明智之舉。

2 常規A-Star算法

A-Star算法即為人工智能中較為多見的基本方法，設一件事要分成很多環節才能夠完成，所完成環節的代價均可算出，而且通過估值函數計算從本步直至最終目的所需的代價，而總代價為：本步代價*W十最終目的代價*（1-w）

W即為本步代價的權值。期核心理念即為，把全部的中間環節與權值放置于最優隊列之中，每次都選擇加權代價最小的節點，在此基礎上通過此節點拓展下屬子節點，亦為計算出代價后放置于最優隊列，直至搜尋到目的地為止。

A-Star算法已然存在其相應的缺點：啟發式搜索靈活性較低，程序每次加入取出兩個隊列時，都要予以大量的內存分配，這在一定程度上浪費了大量的時間；同時，要檢測有無處于隊列中，這也會消耗一定的時間；而且，保存動態規劃參數的數組還要還原，每進行一次尋路均需還原大量的數組，在很大程度上影響了其速率。特別是在大地圖亦或在特定地形狀態下，搜索效率會呈幾何形遞減，若對A-Star的最長尋找步長予以限定，那么物體無法在指定步驟內完成尋路任務，此狀態下物體通常會走出不符客觀規律的路線。

3 A-Star優化算法

本人在常規A-Star算法基礎上進行了相應的優化，予以優化后的主要搜索步驟如下所述：

構建兩個表，OPEN表存儲至已生成但沒有被考察的節點，CLOSED表內錄入曾到達過的節點。

把起點存儲至OPEN表內；

While （OPEN！=NULL）

{

從OPEN表內取估價參數f最小的節點n；

if （n節點==終點）break；

else

{

按序列獲取n的8個方向節點X；

if （X不可到達或X在CLOSE表內）無需在意X：

if（X in OPEN）在此步驟，需要對比X的估價參數f；//即為想用節點的兩個差異化路徑估價值

if（ X的估價參數不超過OPEN表的估價參數）

調節OPEN表內的估價參數； //取最小路徑的估價參數

if（X未被訪問）計算X的估價參數；

在此基礎上把X放置于OPEN表內；

此時//并未排序

}

把n節點放置于CLOSE表內；

依附于估價參數把OPEN表內的節點予以整體排序；

}

各更新估價值的過程中，需錄入節點的主節點，完成搜索后，根據終點倒推至起點，若完成倒推就可證明最終路徑有效。

4 總結

綜上所述，目前，人工智能得到了游戲設計人員的重視，并慢慢成為深化游戲品質的主要切入點。人工智能在游戲中一般體現于非玩家角色的行為表現，一些即時戰略游戲，人工智能可以在全范圍內予以智能化尋路行為，其中涵蓋了單個人物的智能尋路，而且還具有群體的編隊尋路、碰撞協調及多單位智能路徑分配能力，而尋路的目的即怎樣找到從起點到達終點的最短途徑。目前的尋路算法基本滿足了游戲設計的需要，不過這些算法存在著無法避免的問題，所以需要在對比各種方法的基礎上，有指向性的開發匹配于游戲設計需求的尋路算法。

參考文獻

[1]姚雪梅.人工智能中A～*算法的程序實現——八數碼問題的演示程序[J].電腦與信息技術，2013（02）.

[2]牛兵，陳誼.二維GIS與三維視景仿真技術的結合及其在視景仿真中的應用[J].北京工商大學學報（自然科學版），2015（02）.

[3]Michi Henning；Mark Spruiell；馬維達.Hello World——ICE分布式應用開發入門[J].程序員，2014（09）.

作者單位

太原市知達常青藤中學校 山西省太原市 030000endprint