李子涵，孫建紅，王永利

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

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

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

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

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

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

2 障礙物膨脹處理

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

圖1 原始路徑

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

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

圖2 膨脹處理結果

3 射線法簡化冗余節(jié)點

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

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

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

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

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

圖3 射線法簡化冗余節(jié)點

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

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

運行尋路程序，統(tǒng)計3 個場景中路徑轉折點的個數(shù)，如表1 所示。

表1 場景中路徑轉折點數(shù)量

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

4 擬曲線路徑平滑方法

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

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

圖5 使用貝塞爾曲線平滑

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

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

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

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

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

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

圖6 使用擬曲線平滑

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

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

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

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

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

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

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

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

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

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

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

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

6 仿真測試參數(shù)及客觀評價

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

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

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

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

7 結論

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