基于A星算法的游戲路徑優(yōu)化的仿真分析

樊質(zhì)軍+楊朋英+孫玉霞

摘要：路徑搜索是許多游戲的核心組成部分，路徑搜索的算法有很多，不同的搜索算法有不同的搜索效率。A*算法是游戲中解決尋路問題的主要搜索算法，該文通過對A*算法的分析與研究，找出不足并進行優(yōu)化和改進。在A*算法基礎(chǔ)上添加了一個對障礙預處理的方案，使角色能順利地繞開障礙，減少搜索不必要的障礙所用的額外的空間和時間。并進行了尋路仿真實驗，對比分析了傳統(tǒng)算法和改進算法的性能。實驗結(jié)果表明改進A*算法的可行性與有效性。

關(guān)鍵詞：A*算法；啟發(fā)式函數(shù)；尋路；預處理

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2018）01-0195-02

尋路作為游戲中的基本問題之一，即角色按照程序指定的合適的路徑從地圖的A點抵達B點，根據(jù)角色對周圍環(huán)境了解程度的不同，分為全局路徑規(guī)劃方法和完全未知或部分未知的局部路徑規(guī)劃方法兩種。目前網(wǎng)絡游戲、手機增值等業(yè)務迅猛發(fā)展，尋路技術(shù)已成為游戲的一個核心組成部分。物體按照某種指定方式移動，就要求程序必須能夠找到一條從起點到目標點的最佳路徑，這條路徑應該是繞過障礙物并且到達目的地最短的路徑，而A*算法就是完成這個任務的最好的算法。

1 A*算法的不足與改進

啟發(fā)式A*搜索算法，顧名思義，就是有啟發(fā)地尋找目標結(jié)點，并且在基于最小的成本下，盡可能地找到通向目標點的最合適并且最短的路徑。

在《一種基于A星算法的游戲路徑優(yōu)化應用》的文章中，講述了傳統(tǒng)A*算法的不足，即在面對障礙時進行了許多無用功結(jié)點的搜索，并對此不足作出了相應的改進，添加了一個對障礙預處理的方案，并且額外添加一個destination集合，使角色能順利地繞開障礙，減少搜索所用的額外內(nèi)存空間，從而更加智能地到達目標結(jié)點，并且對此改進方法作了仿真分析。

2 仿真實驗

2.1 實驗環(huán)境及設(shè)備

實驗仿真的硬件設(shè)備：Inter（R） Core（TM） i5-4200 CPU @ 1.60GHz 2.30GHz，內(nèi)存為4GB；操作系統(tǒng)為Microsoft Windows 8.1；仿真系統(tǒng)開發(fā)平臺環(huán)境為：Dev-cpp5.4.0；

2.2 實驗基本流程及技術(shù)難點

2.2.1 實驗基本流程

圖1為實驗整體流程圖。

2.2.2 技術(shù)難點

（1） 目標結(jié)點選取

在傳統(tǒng)的A*算法中，目標點只有一個，為了讓角色優(yōu)先到達障礙邊界出口點，根據(jù)堆棧的思想，將此作為一個destination目標集合，將邊界出口點作為最先到達的臨時目標點。

（2） 障礙的內(nèi)存存儲

為了用盡可能少的內(nèi)存存儲障礙，運用了一個邊界出口點方法，即存儲障礙邊界點的障礙，這里的方法可以有很多，本文的方法是將障礙再加一層屏障。

（3） 多個邊界出口點的選取

一個障礙可能會有多個邊界出口點，為了選取最近以及最可靠的出口點，根據(jù)角色到出口點加上出口點到終點的距離來進一步判斷出口點的選取。

（4） 預處理障礙

在角色尋路的過程中，從角色到目標點或者臨時目標點的連線中，如果檢測到存在障礙，那么立刻停止檢測，就該障礙作進一步處理。

2.2.3 結(jié)果數(shù)據(jù)分析

（1） 內(nèi)存結(jié)點的分析

添加了改進方案的A*算法在搜索的過程中，搜索無用功的結(jié)點明顯減少，例如表1中哈曼頓的結(jié)點從51減少到了16，搜索范圍變小，例如多障礙的結(jié)點由643減少到了143，并且根據(jù)圖2可知，結(jié)點減少率大約在80%左右，綜上所述，改進以后的算法能更精確且快速地繞開障礙并尋找路徑，直至抵達終點。

（2） 消耗時間的分析

在實際游戲中，游戲在生成地圖的時候已經(jīng)預處理了障礙，又因為A*算法是基于靜態(tài)網(wǎng)格下的，即障礙都是靜態(tài)的，針對5種不同的地形實驗進行A*算法改進前和改進后消耗時間的精確測試，如表2和表3，可以清楚地看出每組實驗測試了5組數(shù)據(jù)，并且從中去掉一個最高值和最低值，取剩下三組數(shù)據(jù)求平均值[1]，使最終的平均值數(shù)據(jù)更加精確，而5種不同的實驗（實驗一到實驗五）中改進前和改進后結(jié)點的個數(shù)分別對應為：73，29，730，121，858和14，22，110，52，173，結(jié)合這些數(shù)據(jù)繪制出隨著結(jié)點個數(shù)變化時間消耗分析預測圖，如圖3，可以明顯地看出，雖然在結(jié)點很少的情況下，改進后的A*算法所需時間高于傳統(tǒng)的A*算法，但是隨著結(jié)點個數(shù)增加，并且根據(jù)線性預測分析法[2]可以明顯看出，改進的A*算法要優(yōu)于傳統(tǒng)的A*算法，綜上所述，在基于改進A*算法上預處理所需內(nèi)存明顯減少的情況下，游戲所運行的的時間也有一定的優(yōu)化，從而驗證了改進A*算法的真實性和可行性。

3 結(jié)束語

本文在A*算法的基礎(chǔ)上，添加了對就近障礙預處理找出邊界出口的方案，結(jié)合一個destination集合，對傳統(tǒng)A*算法進行了改進，并進行仿真實驗，由圖2的減少率圖和圖3的耗時預測分析圖可以明顯地看出，該改進方法在預處理搜索的內(nèi)存大大減少，并且基于此在時間上也有一定的優(yōu)化，綜上所述，根據(jù)仿真實驗結(jié)果，驗證了改進的A*算法的可行性和真實性。

參考文獻：

[1] 周世健. 截尾均值與平尾均值[J]. 地球科學與環(huán)境學報， 1996（4）：84-90.

[2] Aitchison J， Dunsmore I R. Statistical prediction analysis[M]. Cambridge University Press， 1975.endprint