網(wǎng)絡(luò)游戲中的尋路算法

韓宇澤

摘 要

近年來伴隨網(wǎng)絡(luò)游戲產(chǎn)業(yè)的全面進(jìn)程，游戲設(shè)計環(huán)節(jié)對人工智能的要求已不可同日而語。作為網(wǎng)絡(luò)游戲設(shè)計的基礎(chǔ)，人工智能引擎是實(shí)現(xiàn)高品質(zhì)現(xiàn)實(shí)模擬的先決條件，但是在人工智能引擎中，移動系統(tǒng)即為基礎(chǔ)因素，在尋路系統(tǒng)的實(shí)現(xiàn)上，現(xiàn)階段大多使用迪克斯特拉算法及以決策樹概念為核心的A*算法，而我在對現(xiàn)階段主流算法予以對比基礎(chǔ)上，深化了算法的優(yōu)化概念。

【關(guān)鍵詞】網(wǎng)絡(luò)游戲 尋路算法

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

1 Static path method

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

2 常規(guī)A-Star算法

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

W即為本步代價的權(quán)值。期核心理念即為，把全部的中間環(huán)節(jié)與權(quán)值放置于最優(yōu)隊(duì)列之中，每次都選擇加權(quán)代價最小的節(jié)點(diǎn)，在此基礎(chǔ)上通過此節(jié)點(diǎn)拓展下屬子節(jié)點(diǎn)，亦為計算出代價后放置于最優(yōu)隊(duì)列，直至搜尋到目的地為止。

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

3 A-Star優(yōu)化算法

本人在常規(guī)A-Star算法基礎(chǔ)上進(jìn)行了相應(yīng)的優(yōu)化，予以優(yōu)化后的主要搜索步驟如下所述：

構(gòu)建兩個表，OPEN表存儲至已生成但沒有被考察的節(jié)點(diǎn)，CLOSED表內(nèi)錄入曾到達(dá)過的節(jié)點(diǎn)。

把起點(diǎn)存儲至OPEN表內(nèi)；

While （OPEN！=NULL）

{

從OPEN表內(nèi)取估價參數(shù)f最小的節(jié)點(diǎn)n；

if （n節(jié)點(diǎn)==終點(diǎn)）break；

else

{

按序列獲取n的8個方向節(jié)點(diǎn)X；

if （X不可到達(dá)或X在CLOSE表內(nèi)）無需在意X：

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

if（ X的估價參數(shù)不超過OPEN表的估價參數(shù)）

調(diào)節(jié)OPEN表內(nèi)的估價參數(shù)； //取最小路徑的估價參數(shù)

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

在此基礎(chǔ)上把X放置于OPEN表內(nèi)；

此時//并未排序

}

把n節(jié)點(diǎn)放置于CLOSE表內(nèi)；

依附于估價參數(shù)把OPEN表內(nèi)的節(jié)點(diǎn)予以整體排序；

}

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

4 總結(jié)

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

參考文獻(xiàn)

[1]姚雪梅.人工智能中A～*算法的程序?qū)崿F(xiàn)——八數(shù)碼問題的演示程序[J].電腦與信息技術(shù)，2013（02）.

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

[3]Michi Henning；Mark Spruiell；馬維達(dá).Hello World——ICE分布式應(yīng)用開發(fā)入門[J].程序員，2014（09）.

作者單位

太原市知達(dá)常青藤中學(xué)校 山西省太原市 030000endprint