基于A*算法的電子游戲路徑優化處理

李子涵，孫建紅，王永利

（1.南京理工大學電子工程與光電技術學院，江蘇南京 210094；2.南京理工大學計算機科學與工程學院，江蘇 南京 210094）

當今，游戲人工智能可為游戲產品獲取更高的用戶粘性[1]。A*尋路算法作為一種啟發式算法[2-3]，在電子游戲編程中獲得了廣泛使用，其與盲目式算法相比，有運算速度較快、搜尋精度較高[4]等優點；以此為基礎，后人還發展出D*算法等動態路徑規劃算法[5-6]。為解決傳統A*算法中尋路質點無體積[7]的問題，膨脹處理障礙物，為路徑留出緩沖，再使用射線法簡化冗余節點。為克服貝塞爾曲線平滑法不適用的問題，現提出一種擬曲線平滑方法，在關鍵節點間插值后，使用多段線段模擬曲線，克服了貝塞爾曲線平滑法產生的刺狀畸變，使平滑后的路徑具有良好的視覺效果。

1 A*算法與柵格地形劃分法簡介

A*算法是一種在智能尋路中常用的啟發式算法，其原理是使用開啟列表和關閉列表，通過求取式（1）啟發函數的函數值，找出開啟列表中當前啟發值最小的路徑點，獲取其相鄰節點，以此引導路徑搜索，最終得到一條關于當前啟發值最優的路徑[8]，式（1）如下所示：

柵格法是模擬地形環境的一種常用方法，它使用相互連接的單位柵格覆蓋復雜地形，設置可通過坡度角和可通過高度，將柵格劃分為可通過區域與不可通過區域，簡化不規則地形。

在尋路柵格中使用A*算法，所得原始路徑是由目標節點到初始節點的一系列父節點回溯構成，因此原始路徑是充滿冗余和鋸齒的，如果在可視化實現中直接使用原始路徑，視覺效果將會非常差，并且鋸齒拐角處的速度突變并不符合物體運動的實際情況。

2 障礙物膨脹處理

在場景中設置尋路起點與終點，使用A*尋路算法完成尋路，可以得到原始路徑，如圖1 所示。

圖1 原始路徑

可以看出，原始路徑中的確存在大量冗余轉折點和鋸齒狀路徑，且由于啟發函數的貪心性質[9]，導致大量局部路徑段緊貼障礙物延伸，又因尋路物體的模型存在可產生物理碰撞的體積，在仿真動畫中，將會出現尋路物體的部分模型鑲嵌進障礙物模型中，可能引起難以預測的系統漏洞[10]，因此應當引入障礙物膨脹算法，獲得安全路徑。

在尋路算法尋找最優路徑的計算過程中，并不對當前真實地形進行考察，只依賴于已經預先生成的尋路網絡[11]，故在進行障礙物膨脹算法時，只需考慮路徑點的可通過性與不可通過性即可。根據用戶需要，調節膨脹半徑R，遍歷路徑節點以R為半徑做球體碰撞檢測，若檢測到碰撞物為非地面的碰撞事件，則將該節點設置為不可通過節點，即將障礙物向外膨脹一個安全距離R，之后生成尋路網絡，可以看到障礙物周圍被設置為不可通過的緩沖區域，如圖2（a）所示，此時運行尋路算法得到安全路徑，如圖2（b）所示。

圖2 膨脹處理結果

3 射線法簡化冗余節點

在得到安全路徑后，可將路徑中的冗余節點進行簡化。從初始節點開始遍歷路徑中的所有節點：

1）假設當前節點編號為i0，那么其后兩個路徑節點編號分別為i0+1 與i0+2，如圖3（a）所示。

2）以節點i0為起點，為方向發射射線，進行碰撞檢測，若該射線在節點i0與節點i0+2 之間未檢測到碰撞事件，則i0+1 節點為冗余節點，移除之,如圖3（b）所示。此時存儲路徑節點的列表元素從第i0+2 號元素開始，全體向前移動一位補位，先前的i0+2 節點變為當前的i0+1 節點，同理先前的i0+3 節點變為當前的i0+2 節點。

3）重復上述射線碰撞檢測，直到當前io節點與io+2 節點間檢測到碰撞事件，則io+1 節點不為冗余節點，如圖3（c）所示；此時使用賦值語句i=i+1，將射線檢測的起始節點由io移至io+1。

4）重復上述射線碰撞檢測，直到io+1 值大于等于節點列表元素數，跳出循環，簡化完成，如圖3（d）所示。

圖3 射線法簡化冗余節點

為了保證測試結果的客觀性，如圖4 建立以下3 個場景，通過調整場景中障礙物的多寡來控制場景的復雜程度（圖4（a）障礙物稀疏，環境簡單；圖4（b）障礙物較多，環境較為復雜；圖4（c）障礙物眾多且相互交錯，環境復雜），以測試該方法在不同復雜程度環境中的運行效果。

圖4 3種不同復雜程度的場景

運行尋路程序，統計3 個場景中路徑轉折點的個數，如表1 所示。

表1 場景中路徑轉折點數量

從表1 可以看出，射線簡化算法顯著簡化了路徑中的冗余轉折點。

4 擬曲線路徑平滑方法

選取圖4 中最復雜的測試場景圖4（c）。如圖5（a）所示，在簡化路徑冗余轉折點后，可以看出原路徑中鋸齒狀抖動已經全部消失，但路徑折轉處仍是尖銳的。三次樣條曲線[12]與貝塞爾曲線[13]是生成曲線的常見算法。三次樣條曲線的繪制過程需要多次求導數[14]，計算量較大，且該文涉及的仿真中路徑點均為離散點，故該文不適用此法。貝塞爾曲線基于伯恩斯坦多項式在閉區間上的一致收斂性，可以通過少量的點，去控制生成復雜的曲線[15]。

考慮直接使用貝塞爾曲線進行路徑平滑，但運行程序后發現系統溢出報錯。究其原因，由于場景中路徑點過多，求取高階貝塞爾曲線是一個占用大量資源的計算過程，以至于產品難以正常運行，為了克服此問題，現將原路徑進行分段貝塞爾曲線平滑，但貝塞爾曲線的生成是一個連續的過程，路徑中任何一個節點的變化都會對整條路徑產生影響[16]，分段進行貝塞爾曲線平滑后，每兩段曲線間的連接處無法保證平滑。通過分段生成三階貝塞爾曲線，得到圖5（b），對比圖5（a）可以看出，路徑中部分尖銳拐彎處變得平滑，但某些路徑段卻出現刺狀畸變，平滑效果不理想。

圖5 使用貝塞爾曲線平滑

由于貝塞爾曲線平滑方法與產品要求不相符，故棄之不用，現另提出一種擬曲線平滑方法。由于在平滑前使用射線法簡化冗余節點時，刪去了大量節點，而擬曲線平滑處理的本質是用多段線段去模擬曲線，所以在平滑處理前仍需進行路徑點插值處理。將存儲路徑點的向量列表nodes 的可用長度擴展為列表中當前節點數量的4 倍，再使用Vector3.Lerp 方法在每兩個相鄰路徑點的1/4、1/2 與3/4 處插入新的路徑點。插值完畢后，從初始節點后一個節點開始遍歷路徑中的所有節點。

1）假設當前節點編號為ib，其前后兩個路徑節點編號分別為ia、ic，使用式（2），取節點ia與節點ic的中點，記為點iac。

2）設置平滑強度strength(0 ≤strength≤1)，使用式（3），得到節點（當strength=0 時，節點即為節點ib，當strength=1 時，節點即為節點iac）。

再將路徑點向量列表中的節點ib替換為節點，完成節點ib的平滑。

3）使用賦值語句ib=ib+1，將當前節點后移一位，循環上述平滑過程，直到ic大于等于節點列表元素數，跳出循環，平滑完成。

設置平滑強度strength=0.8，執行此算法后得到如圖6 所示路徑，可以看出此時路徑拐彎處的視覺效果已經接近曲線。

圖6 使用擬曲線平滑

5 改進分段擬曲線路徑平滑方法

在擬曲線平滑得到的路徑中，總體上消除了路徑拐彎處的尖銳轉折，但可以看出在局部路徑中出現了“急彎”，如圖7（a）所示，以及在無障礙物的空曠區域處，原本為直線段的路徑產生了弧形畸變，如圖7（b）所示。

圖7 擬曲線平滑所得局部路徑

究其原因，在擬曲線平滑之前使用了射線簡化，導致路徑中原本間距均勻的節點被大量刪除，只剩下轉折處的關鍵節點，而關鍵節點分布不均勻，在環境復雜處關鍵節點密集，環境空曠處關鍵節點稀疏，擬曲線平滑使用簡單插值，在關鍵節點密集處產生冗余插值，導致平滑后產生“急彎”，而環境空曠處由于插值點數量不夠，導致無需平滑的直線路徑段產生弧形畸變，為解決此問題，現對擬曲線平滑方法進行改進，提出改進分段擬曲線平滑方法。

設置段長值SegmentLength，從初始節點開始遍歷路徑中的所有節點。

1）假設當前節點編號為i，代入式（4），得到節點i與節點i+1 之間的距離length。

2）將length代入式（5），得到節點i與節點i+1之間需要插值點的個數num。

由于段長SegmentLength可能無法被節點距離length整除，而式（5）使用取整函數，得到的段長舍去了余數，遍歷整個路徑將產生積累誤差，因此引入段長余數rem，使用式（6）更新rem值，同時修改num賦值語句為式（7）。

3）使用賦值語句i=i+1，將當前節點后移一位，循環上述平滑過程，直到i+1 大于等于節點列表元素數，跳出循環，插值完成。

設置段長值SegmentLength=1，平滑強度strength=0.8，將當前節點列表中的元素代入擬曲線平滑函數，得到如圖8 所示路徑。

圖8 使用改進分段擬曲線平滑所得路徑

從圖8 可看出，此時路徑中已無“急彎”和弧形畸變。

6 仿真測試參數及客觀評價

現考慮使用曲率對平滑效果進行客觀評價，取路徑曲線L拐彎處弧，其切線轉角為Δα，弧長為Δs，則該段弧平均曲率為，使點M′沿弧趨向于點M，若弧平均曲率的極限存在，則稱其為曲線L在點M處的曲率，記為K,即由于使用擬曲線路徑平滑法所得路徑并非真實的曲線，而是由若干線段組成，故無法直接用曲率進行客觀平滑效果考量，但因平滑后路徑視覺效果非常接近曲線，故該實驗可使用與該路徑彎道處視覺效果重合的曲率圓在彎道中點臨近的一段圓弧來近似代替原路徑，使考量簡化。若曲率半徑,那么可以將曲率考量簡化為路徑拐彎處的曲率半徑考量。

通過統計轉折處的曲率半徑與弧形畸變數量，得到表2（表中貝塞爾曲線平滑法簡稱“貝塞爾”，擬曲線平滑法簡稱“擬曲線”，改進分段擬曲線平滑法簡稱“改進”）。

表2 3種平滑方法下各轉折處曲線的曲率半徑

剔除畸變值，使用貝塞爾曲線平滑法得到的平均曲率半徑為8.58 mm，畸變率為45.45%，使用擬曲線平滑法得到的平均曲率半徑為6.50 mm，畸變率為13.64%，使用改進分段擬曲線平滑法得到的平均曲率半徑為9.59 mm，無畸變?？梢钥闯?，改進分段擬曲線路徑平滑法對比貝塞爾曲線平滑法，無路徑畸變，且路徑拐彎處平均曲率半徑增大11.77%。

7 結論

該文以傳統A*算法得到的原始路徑為基礎，針對原始路徑冗余節點多、美觀度不足的問題，提出了射線簡化冗余點與擬曲線路徑平滑兩種路徑處理方法。首先將原尋路環境中的障礙物進行安全膨脹處理，然后通過節點插值、射線法檢測障礙物、冗余點刪除操作，得到化簡后的路徑，再以此為基礎，進行節點插值后，使用擬曲線平滑，得到較美觀的路徑，之后在擬曲線平滑的基礎上做出改進，提出改進分段擬曲線平滑法，使平滑效果得到提升。仿真結果表明，該方法效果顯著。