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

看板GameDesign (遊戲設計)作者dklassic (DK)時間3年前 (2021/09/10 15:03)推噓9(9推 0噓 12→)

留言21則, 5人參與討論串1/1

年初接手翻新手上遊戲的 AI 系統，因而實作了一個只依靠區域性碰撞迴避進行移動的 AI 系統。反正當個紀錄都好，想想就決定寫個一篇文章嘗試有系統性地說明。其實這個名字並不夠說明完整釐清這個 AI 能幹嘛，但至少有涵蓋最重要的主要目的：「低效能需求」、「區域性」、「碰撞迴避」。而在開始解釋區域性碰撞迴避 AI 之前，不得不先說明原系統的缺陷，才能夠了解實作碰撞區域性碰撞迴避 AI 的理由以及對應的優缺點。然後因為不知道為什麼我現在上傳圖片到 Imgur 都會傳不上去，所以圖片是上傳巴哈後的小屋網址 QQ 零、原系統缺陷原系統基本上是採用 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

09/10 22:30, 3年前 , 1^F

09/10 22:30, 1^F

推

hayluu

09/10 22:41, 3年前 , 2^F

09/10 22:41, 2^F

推

damody

09/10 23:50, 3年前 , 3^F

09/10 23:50, 3^F

意外有效的 Workaround XD 但可惜我的重點倒不是傳圖片，而是想要能夠直接傳個短影片更方便解釋 ※ 編輯: dklassic (1.169.78.133 臺灣), 09/11/2021 00:03:59

推