游戏AI研究（三）：路径规划
目錄
使用路徑點（Way Point）作為節點
洪水填充算法創建路徑點
使用導航網格（Navigation Mesh）作為節點
預計算
?
- 路徑查詢表
- 路徑成本查詢表
- 擴展障礙碰撞幾何體
- 可視點尋徑
尋路的改進
?
- 平均幀運算
- 路徑平滑
- 雙向搜索
- 路徑拼接
- 節點評估
參考
在了解路徑規劃之前必須先了解基本的尋路算法。
可參考A*尋路算法：A*尋路算法-KillerAery-博客園
使用路徑點（Way Point）作為節點
大部分討論A*算法使用的節點是網格點（也就是簡單的二維網格），但是這種內存開銷往往比較大。
實際上A*尋路算法，對于圖也是適用的，實現只要稍微改一下。
因此我們可以把地圖看作一個圖而不是一個網格，使用預先設好的路徑點而不是網格來作為尋路節點，則可以減少大量節點數量。
?
使用路徑點的好處：
?
- 減少大量節點數量，順帶也就減少了尋路的運算速度開銷。
- 相比網格節點，路徑點的路徑更加平滑。
洪水填充算法創建路徑點
倘若一個地圖過大，開發人員手動預設好路徑點+路徑連接的工作就比較繁瑣，而且很容易有錯漏。
這時可以使用洪水填充算法來自動生成路徑點，并為它們鏈接。
算法步驟：
1.以任意一點為起始點，往周圍八個方向擴展點（不能通行的位置則不擴展）
?
2.已經擴展的點（在圖中被標記成紅色）不需要再次擴展，而擴展出來新的點繼續擴展
?
3.直到所有的點都被擴展過，此時能得到一張導航圖
?
自動生成的導航圖可以調整擴展的距離，手游賬號交易平臺從而得到合適的節點和邊的數量。
使用導航網格（Navigation Mesh）作為節點
導航網格將地圖劃分成若干個凸多邊形，每個凸多邊形就是一個節點。
使用導航網格更加可以大大減少節點數量，從而減少搜尋所需的計算量，同時也使路徑更加自然。
?
然而該如何建立地圖的導航網格，一般有兩種方法：
?
- 手工劃分導航網格往往工作量巨大。
- 程序化生成導航網格則實現稍微復雜。
導航網格是目前3D游戲的主流實現，例如《魔獸世界》就是典型使用導航網的游戲，Unity引擎也內置了基于導航網格的尋路系統。
如果你對如何將一個區域劃分成多個凸多邊形作為導航網格感興趣，可以參考空間劃分的數據結構(網格/四叉樹/八叉樹/BSP樹/k-d樹/BVH/自定義劃分)-KillerAery-博客園里面的BSP樹部分，也許會給你一些啟發。
預計算
主要方式是通過預先計算好的數據，然后運行時使用這些數據減少運算量。
可以根據自己的項目權衡運行速度和內存空間來選擇預計算。
?
路徑查詢表
借助預先計算好的路徑查詢表，可以以O(|v|)的時間復雜度極快完成尋路，但是占用空間為O(|v|2)。
（|v|為頂點數量）
?
實現：對每個頂點使用Dijkstra算法，求出該頂點到各頂點的路徑，再通過對路徑回溯得到前一個經過的點。
路徑成本查詢表
有時候，游戲AI需要考慮路徑的成本來決定行為，
則可以預先計算好路徑成本查詢表，以O（1）的時間復雜度獲取路徑成本，但是占用空間為O(|v|2)。
?
實現：類似路徑查詢表，只不過記錄的是路徑成本開銷，而不是路徑點。
擴展障礙碰撞幾何體
?
在尋路中，一個令游戲AI程序員頭疼的問題是碰撞模型往往是一個幾何形狀而不是一個點。
這意味著在尋路時檢測是否碰到障礙，得用幾何形狀與幾何形狀相交判斷，而非幾何形狀包含點判斷（毋庸置疑前者開銷龐大）。
一個解決方案是根據碰撞模型的形狀擴展障礙幾何體，此時碰撞模型可以簡化成一個點，這樣可以將問題由幾何形狀與幾何形狀相交問題轉換成幾何形狀包含點問題。
這里主要由兩種擴展思路：
?
- 碰撞模型的各個頂點與障礙幾何體頂點重合，然后掃過去錨點形成的邊界即是擴展的邊界（實際上就是讓碰撞模型緊挨著障礙幾何體走一圈）
?
- 碰撞模型的錨點與障礙幾何體頂點重合，然后掃過去最外圍頂點形成的邊界即是擴展的邊界（實際上就是讓碰撞模型沿著原幾何體邊界走一圈）
?
這些擴展障礙幾何形狀的計算完全可以放到預計算（離線計算），不過要注意：
?
- 各個需要尋路的碰撞模型最好統一形狀，這樣我們只需要記錄一張（或少量）擴展過的障礙圖。
- 碰撞模型不可以是圓形，因為這樣擴展出的障礙幾何體將是圓曲的，很難計算。一個解決方案是用正方形近似替代圓形來生成擴展障礙幾何體。
- 當遇到非凸多邊形障礙時，在凹處可能會出現擴展出的頂點重復（交點），簡單的處理是凹角處不插入新的點。
可視點尋徑
尋路的改進
平均幀運算
有時候，大量物體使用A*尋路時，CPU消耗比較大。
我們可以不必一幀運算一次尋路，而是在N幀內運算一次尋路。
（雖然有所緩慢，但是就幾幀的東西，一般實際玩家的體驗不會有大影響）
所以我們可以通過每幀只搜索一定深度=深度限制/N（N取決于自己定義多少幀內完成一次尋路）。
路徑平滑
基于網格的尋路算法結果得到的路徑往往是不平滑的。
很容易看出來，尋路算法的路徑太過死板，只能上下左右+斜45度方向走。
這里提供兩種平滑方式：
?
- 快速而粗糙的平滑
它檢查相鄰的邊是否可以無障礙通過，若可以則刪除中間的點，不可以則繼續往下迭代。
它的復雜度是O（n）,得到的路徑是粗略的平滑，還是稍微有些死板。
?
- 精準而慢的平滑
它每次推進一位都要遍歷剩下所有的點，看是否能無障礙通過，推進完所有點后則得到精準平滑路徑。
它的復雜度是O（n2）,得到的路徑是精確的平滑。
?
雙向搜索
與從開始點向目標點搜索不同的是，你也可以并行地進行兩個搜索：
一個從開始點向目標點，另一個從目標點向開始點。當它們相遇時，你將得到一條路徑。
雙向搜索的思想是：單向搜索過程生成了一棵在地圖上散開的大樹，而雙向搜索則生成了兩顆散開的小樹。
一棵大樹比兩棵小樹所需搜索的節點更多，所以使用雙向搜索性能更好。
?
不過實驗表明，在A*算法往往得到的不會是一棵像BFS算法那樣散開的樹。
因此無論你的路徑有多長，A*算法只嘗試搜索地圖上小范圍的區域，而不進行散開的搜索。
若地圖是復雜交錯多死路的（例如迷宮，很多往前的路實際上并不通往終點），A*算法便會容易產生散開的樹，這時雙向搜索會更有用。
路徑拼接
游戲世界往往很多動態的障礙，當這些障礙擋在計算好的路徑上時，我們常常需要重新計算整個路徑。但是這種簡單粗暴的重新計算有些耗時，一個解決方法是用路徑拼接替代重新計算路徑。
首先我們需要設置拼接路徑的頻率K：
例如每K步檢測K步范圍內是否有障礙，若有障礙則該K步為阻塞路段。
接著，與重新計算整個路徑不同，我們可以重新計算從阻塞路段首位置到阻塞路段尾的路徑：
假設p[N]..P[N+K]為當前阻塞的路段。為p[N]到P[N+K]重新計算一條新的路徑，并把這條新路徑拼接（Splice）到舊路徑：把p[N]..p[N+K]用新的路徑值代替。
一個潛在的問題是新的路徑也許不太理想，下圖顯示了這種情況(褐色為障礙物)：
?
最初正常計算出的路徑為紅色路徑（1 ->2- ->3 ->4）。
如果我們到達2并且發現從2到達3的路徑被封鎖了，路徑拼接技術會把（2 ->3）用（2 ->5 ->3）取代，結果是尋路體沿著路徑（1 ->2 ->5 ->3 ->4）運動。
我們可以看到這條路徑不是這么好，因為藍色路徑（1 ->2 ->5 ->4）是另一條更理想的路徑。
一個簡單的解決方法是，設置一個閾值最大拼接路徑長度M：
如果實際拼接的路徑長度大于M，算法則使用重新計算路徑來代替路徑拼接技術。
M不影響CPU時間，而影響了響應時間和路徑質量的折衷：
?
- 如果M太大，物體的移動將不能快速對地圖的改變作出反應。
- 如果M太小，拼接的路徑可能太短以致于不能正確地繞過障礙物，出現不理想的路徑，如（1 ->2 ->5 ->3 ->4）。
路徑拼接確實比重計算路徑要快，但它可能算出不怎么理想的路徑：
?
- 若經常發現這種情況出現，那么重新計算整條路徑也不失為一個解決辦法。
- 嘗試使用不同的M值和不同的拼接頻率K(如每34M34M步)以用于不同的情形。
- 此外應該使用棧來反向保存路徑，因為刪除和拼接都是在路徑尾部進行的。
節點評估
在A*尋路算法里，一個節點的預測函數最直觀的莫過于歐幾里得距離。
然而對于復雜的游戲世界來說，特別是對于需要復雜決策的AI來說，節點的預測值可不僅僅就距離一個影響因素：
?
- 地形優勢：例如平地節點走得更快而山地節點走得更慢。
- 視野優勢：某些地方具有良好的視野（例如高地），AI需要準備戰斗時應該傾向占領視野優勢點。
- 戰術優勢：一些地方（例如刷出醫療包的地點，可操控機槍）提供了戰術優勢，AI應傾向占領這些戰術優勢地點。
- 其他...
因此，我們可以自定義尋路的預測函數，以調整成為適應復雜游戲世界的AI尋路。
總結
以上是生活随笔為你收集整理的游戏AI研究（三）：路径规划的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 从零开始做一个SLG游戏（三）：用uni
- 下一篇： 从零开始做一个SLG游戏（二）：用mes