基于A星算法的游戲路徑優化的仿真分析

樊質軍+楊朋英+孫玉霞

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

關鍵詞：A*算法；啟發式函數；尋路；預處理

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

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

1 A*算法的不足與改進

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

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

2 仿真實驗

2.1 實驗環境及設備

實驗仿真的硬件設備：Inter（R） Core（TM） i5-4200 CPU @ 1.60GHz 2.30GHz，內存為4GB；操作系統為Microsoft Windows 8.1；仿真系統開發平臺環境為：Dev-cpp5.4.0；

2.2 實驗基本流程及技術難點

2.2.1 實驗基本流程

圖1為實驗整體流程圖。

2.2.2 技術難點

（1） 目標結點選取

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

（2） 障礙的內存存儲

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

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

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

（4） 預處理障礙

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

2.2.3 結果數據分析

（1） 內存結點的分析

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

（2） 消耗時間的分析

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

3 結束語

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

參考文獻：

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

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