[程式] 低效能需求的區域性碰撞迴避 AI

[dklassic (DK)]

 
年初接手翻新手上遊戲的 AI 系統，因而實作了一個只依靠區域性碰撞迴避進行移動的
AI 系統。反正當個紀錄都好，想想就決定寫個一篇文章嘗試有系統性地說明。
其實這個名字並不夠說明完整釐清這個 AI 能幹嘛，但至少有涵蓋最重要的主要目的：「
低效能需求」、「區域性」、「碰撞迴避」。而在開始解釋區域性碰撞迴避 AI 之前，不
得不先說明原系統的缺陷，才能夠了解實作碰撞區域性碰撞迴避 AI 的理由以及對應的優
缺點。
 
 
零、原系統缺陷 
原系統基本上是採用 Unity 的 Nav Mesh Agent 為基礎在製作的。在幾個網路上看到的
影片中都顯示 Nav Mesh Agent 可以有傑出的效能表現，就算上千個 Agent 在跑也沒問
題。
Nav Mesh Agent 顧名思義就是藉由預先或動態更新烤起來的 Nav Mesh 來進行移動的存
在。身為 Nav Mesh Agent 擁有完整的空間資訊，對於位置移動來說可以提供非常高精度
結果，無論是要移動到目標地點的能力，還是途中避免撞到其他物件的能力都會好很多。
這件事情對一般遊戲來說是好事，畢竟誰也不想讓自己的遊戲充滿頂著牆壁走路的人物。
本來使用 Nav Mesh Agent 對於關卡結構複雜度高的遊戲應該是好事，而我正在開發的遊
戲《自動混亂》因為涉及隨機生成關卡而容易出現複雜度很高的幾何，若是使用 Nav
Mesh Agent 應該可以有很好的結果。
https://i.imgur.com/JhwXkLk.png
（↑隨便生成的一個關卡版面，由於空間障礙物的種類繁多，還會有比上圖更加難以穿梭
的結構）
壞事呢？
Nav Mesh 能最大化發揮的情境是靜態場景。雖然 Nav Mesh 也能進行動態修改，但是相
關的管理就沒有辦法輕鬆處理。
雖然讓上千個 Nav Mesh Agent 同時跑本身不是個問題，但是前提是這上千個 Nav Mesh
Agent 不會同時要求 CPU 回傳路徑資訊，也不會需要頻繁更新移動目標。
 
《自動混亂》在設計上是個節奏比較快的遊戲，敵我行動能力、擊殺速度都相當的快，為
了要挑戰玩家，我希望讓敵人能相對快速地應對玩家來進行移動。
實際上確實有其他合理的作法，像是降低路徑規劃請求頻率、分散各 AI 請求的時機（參
考：CJ 貓的時域切割 #1OqsJooL ）。
但另一方面這款遊戲也涉及關卡隨機產生的遊戲設計，讓維護 Nav Mesh 本身變成相對麻
煩的事情。
由於當時為了要實作方便管理結果的 AI，包含想要用更正規的指令式行動設計包裝起來
，因此最後決定來實作完全仰賴區域性碰撞迴避執行的 AI。
 
一、區域性碰撞迴避 AI 
區域性碰撞迴避（Local Collision Avoidance），也就是相對於全域（Global）來說並
不知道關卡全貌而嘗試避免碰撞。
我的實作方式基本上是想像成 AI 有 20 個移動方向可以選擇，每個 Frame 都會重新確
認一次自己對於各方向的偏好。根據自己的偏好，盡量往該方向轉。（這部分可以額外最
佳化，參考：CJ 貓的時間切割 #1Wi9bSCE 與延遲蒐集 #1Wf04-GB ）
例如說 AI 可能不偏好往陷阱和障礙物移動，但是偏好往玩家角色移動。
https://i.imgur.com/FzeyW4p.png
這組 AI 的基本運作邏輯包含：
－避免移動中撞上障礙物
－對各個障礙物有偏好
－偏好維持原本的移動方向
－偏好往指定的目標移動
－與指定的目標保持指定距離
 
根據上面幾件事情，我們可以對這 20 個方向進行加減分並且以綠線表示喜歡、紅線表示
不喜歡，以長度表示幅度：
https://i.imgur.com/NbMNkPR.png
接著我們在每個 Frame 都讓敵人盡量轉向他最喜歡的方向前進。如此一來骨幹就算是完
成了，實作出來大概就會長這樣，雖然實作上很簡單但效果其實很好：
https://twitter.com/RandomDevDK/status/1348143680968818688?s=20
 
二、物理性行動 
在偏好方向上基本概念很簡單也很好實作，完成之後 AI 就可以用很低負擔的方式持續在
環境中移動而不會撞牆感覺很笨。但要讓 AI 的移動上讓人有理所當然的感覺就還有待努
力。
其中最重要的就是要讓 AI 的物理性質有某種正確性，才能看起來合理，而這個正確性就
源於加減速。
https://i.imgur.com/tkP7tyU.png
加減速應該很好理解，總之要使力速度才會慢慢變快，使力才能讓速度慢慢減少。如果
AI 會瞬間以最高速度行動的話看起來就會很滑順但是有種異樣性。這類型的物理性質其
實主要就是：
－移動速度的加減速
－旋轉速度的加減速
 
只要進行上兩件事情時都有遵循加減速的性質，AI 的行動就會看起來更煞有其事。
 
三、實作效果 
https://twitter.com/RandomDevDK/status/1436186119666692124?s=20
敵人之間沒有碰撞是故意的，但還不錯吧？
上圖還用到了程序性動畫，但這部分就獨立發一篇應該比較適合。
 
四、限制與解法 
身為一個不知道整體環境的 AI，對應的限制也就很明確：無法確保他能夠移動到指定位
置。
由於《自動混亂》的關卡設計雖然偶爾很複雜，但是基本上不會出現最容易引發局部性碰
撞檢測容易卡死的碗型結構：
https://i.imgur.com/hr5Whlw.png
如上圖情境，雖然當 AI 遠遠地靠近這個結構的時候自然而然會繞過去，但如果因為一些
因素意外造成這樣的情境發生時，AI 就可能會因此卡死在這個結構內，這方面可以仰賴
偏好方向的權重調整來盡量避免，但就無法完美確保。
https://i.imgur.com/9Jt7Wms.jpg
（↑《Hades》中很具參考性的碗型結構情境，如果站在橫跨深淵的位置時，Tiny
Vermin 頭目可能會陷在碗型結構出不來，使用遠程武器可以輕易無傷打贏。官方某次更
新後 Tiny Vermin 傳送離開的頻率增加，我認為應該就是為了解決這個問題）
 
所以在這邊提出幾個假設實作，可以考慮使用：
（一）LOD AI 
這個概念是讓各個 AI 有不同級別的實作，某些 AI 使用低精度的區域性碰撞迴避，某
些 AI 使用高精度的 Nav Mesh Agent。
區分方式包含根據相對於玩家的距離、敵人類型等等都不錯，也可以讓低精度 AI 把高精
度 AI 當成一個指標靠近，就有可能藉由少量高精度 AI 的協助橫跨難以穿梭的空間。
（二）歷史紀錄與迴避 
相較於上一個，這個的實用性還待考證。但我的想法是因為 AI 容易出問題的碗型結構，
結果而論會讓 AI 不斷回去同一個位置，也因此或許可以考慮讓 AI 不傾向於前往曾經去
過的位置。根據權重設計也可能反而讓敵人更深陷碗裡也說不定，就有待測試。
（三）偵錯與錯誤應對 
既然可以設計出大致上堪用的 AI，表示這種錯誤情境相對少見。也因此如果 AI 基本效
果很好的話，就可以讓 AI 單純在特定條件下會「傳送」離開原地，讓 AI 重新開機判斷
邏輯就好。
例如說：
－物理上的傳送、跳躍到其他位置
－暫時性放棄現在追蹤的目標或甚至偏好往反方向的目標移動
 
上面兩個設計甚至在不需要的情境下執行，還是可以被包裝成 AI 在重新審視戰況，反而
看起來更煞有其事。
 
五、結語 
AI 的議題大概有無限種的方式可以實作，甚至多個混在一起判斷。沒有唯一解，只有對
應特定情境適合、好用的解。
例如說上述情境都假設敵人單純地跟目標保持特定距離，但如果是掩體射擊遊戲的話，
對 AI 來說保持指定距離就只是間接目標，真正執行的偏好移動地點就得變成鄰近的掩體
，並且寫一套邏輯去判斷哪個掩體的品質比較好
（參考：《看門狗 2》的 AI 戰鬥邏輯：https://youtu.be/c06DZ81Tbmk）
複雜的關卡會出問題，那麼其實也就可以盡量降低場景複雜度。除了減少物件以外，讓很
多物件只是裝飾品實際上被穿過時會直接被敵人破壞也是種不會讓人覺得場景東西很少很
廉價的手法。
 
但總之這是我現在開發的遊戲中使用的 AI 邏輯，寫篇文章記錄供自己未來備考，也提供
大家做個參考。
 
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.169.78.133 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/GameDesign/M.1631257391.A.E9B.html
推 coolrobin: 未看先推
推 hayluu: 推  長知識了
推 damody: 圖床可以拉到hackmd讓他上傳試試
 
意外有效的 Workaround XD
但可惜我的重點倒不是傳圖片，而是想要能夠直接傳個短影片更方便解釋
※ 編輯: dklassic (1.169.78.133 臺灣), 09/11/2021 00:03:59
推 oopFoo: 你的東西完全可以用NavMesh。問題在如何架構輔助資料結構
→ oopFoo: 在這之上。https://www.redblobgames.com/
→ oopFoo: https://theory.stanford.edu/~amitp/GameProgramming/
→ oopFoo: Amit Patel是google的前10位員工，現在是億萬富翁，對遊戲
→ oopFoo: 有興趣。他也喜歡動態產生地圖，做ai path。
推 oopFoo: https://reurl.cc/43R68D
→ oopFoo: 他有各種Group，Cooperative Path finding的連結。好好看
→ oopFoo: 一下，你碰到的問題，其他人都碰過。
推 oopFoo: 如果你真的不想改，起碼考慮一下Heat Map(Influence Map)
 
我知道可以用 NavMesh 也知道怎麼做，內文也有說只是嫌管理麻煩 XD
又因為改用了資源需求更低的處理方式後，並沒有現在的 AI 設計無法克服的關卡情境，
也可以逆向以關卡設計避免 AI 陷入瓶頸，所以才沒有進一步往下修改實作。
上面的 AI 架構我應該是十個小時內就實作完成設定出效果不錯的權重，這種超級簡便又
好維護的概念。
 
但還是感謝你的分享。
※ 編輯: dklassic (111.240.180.175 臺灣), 09/11/2021 11:01:44
推 wangm4a1: 推
推 oopFoo: 你的AI大致上是Desire-driven AI，Dijkstra Map(Influence
→ oopFoo: 很適合，又簡單寫，可以變化多很多。
→ oopFoo: https://reurl.cc/EZ7Mnm  ，有稍微解釋。
→ oopFoo: https://github.com/marukrap/RoguelikeDevResources
→ oopFoo: AI連結可看
→ oopFoo: 不想用NavMesh就直接鋪2d grid
不是啦，雖然很感謝你的分享，但你說的這些我都知道啦 XDDD（<-顯示為論文就是做最佳

化的人）
如果今天我只要寫 AI 就好的話我就會花更多時間與努力去最佳化成果了，在這邊也只是
寫篇文章紀錄說我大概這樣做、效果意外很好到我不需要寫可靠度更高的版本也沒關係啦
～
 
反之如果想要分享 AI 設計的各方參考資料與手段的話，我也滿建議你可以寫教學、心得
、整理文。
寫這篇的用意是因為我知道中文參考資料難找又不齊全，除了讓未來有人（包含自己）需
要時可以查來參考，也是希望能拋磚引玉讓更多人一起分享 XD

我想說的是：非常感謝你的分享，但只回給我看其實沒有效益。
如果你願意的話可以完整構成一篇給未來需要找資料的人的參考文章會非常有價值！
※ 編輯: dklassic (111.240.180.175 臺灣), 09/12/2021 10:48:13
 
※ 編輯: dklassic (111.240.180.175 臺灣), 09/12/2021 11:07:03
※ 編輯: dklassic (111.240.180.175 臺灣), 09/12/2021 11:14:36
推 oopFoo: 了解。因為以前寫遊戲不知道Dijkstra，作ai蠻痛苦的。後來
→ oopFoo: 會了，超級好用，才會一直囉唆。
※ 編輯: dklassic (1.169.104.198 臺灣), 06/08/2022 19:18:08