FlightAgent #Boid Develop log

紀錄到目前為止的 FlightAgent 開發日誌整理.

Log #1
為了尋找一種可以指定航點並且兼容許物件受到物理碰撞影響的方式, 最後在Unity 中選用 Configurable Joint 來達成飛行 agent 的核心.

影片可見, 以這種方式帶動的 Rigidbody 可以受物理影響而帶動, 並且能覆寫角度部份, 最重要的是這個設定並不需要在 Rigidbody 身上做任何特別處理.

所以概念模型為

Agent (Rigidbody)
Navigation Engine (Rigidbody + HiddenFlag + Configurable Joint – link to “Agent”)

兩個 GameObject 並無層階關係, 以 Configurable Joint 把 Navigation Enginie 及 Agent 連結起來, 導航系統則直接對 Navigation 進行 RigidBody.MovePosition() 寫入, 並以此帶動 Agent 的移動.

Log #2, #3

R&D 後發現, 好像大部份的 stanford university CS student 也喜歡用 Boid 來做 FYP… 所以網絡上也有很多相關的資源及源碼發佈.

這兩個 Log 主要是 Implement 及 optimization 在 boid + flocking 的系統資源上 (網上…大部份的源碼寫得有點吃資源)

Agent 與 Agent 之間的間關係, 及如何進行 flocking 的三大原則等等 (3-simple-rules-of-flocking).

#Log 4

主要是優化 flocking 的朋友認證方式, 以下面的原則進行計算

const 設定 distance bias (sqr), 對比本體與及範圍內的 agent 才開始進行計算
const 設定 angle bias (0f~1f), 對比本體與其它 agent’s velocity direction dot value.
const 設定Speed bias 值, 並比其 velocity (sqr) 是否在誤差範圍內.

滿足以上條件的 Agent 會被列為朋友, 加入到 private List<Agents> m_TaggedBoid 內, 用於 boid 族群運算內.

# Log 5, 6, 7, 8 , 9
是 Agent 的 optimization,

– using Vector4 to store Vector3+weight info.
– re-construct steering factor, using interface to queue up the different steering factor
重寫 Agent 代碼, 使 steering factor 變得可擴展或進行動態加減.

– each boid have their own short term memory, represent in time.
即 Log 4 的族群運算優化, 每只 agent 建構是決定其更新間隔後, 每次檢定後需 cooldown, 減少 agent 進行全域的 distance 運算量, 原本為 O(n ^ n), 因為必需使用其 position, 所以只能用 cache 減小存取 U3D API 的數量, 但基本 logic 不能改變. 故以時間及 Frame lock 錯開 Agent 的運算量.

– using Centroid to calculate the final position.
Agent 每幀的行進角度不再是由 “自己” 及 “路徑” 中計算, 改為族群的質心取得角度值後轉換為 Local 的相對角度.
這修改令 Agent 不會再試圖在長距離及共同目標的情況下, 互相搶佔最佳化路線. 變得更”禮讓/合群”….

# Log 10, 11

正式進行 Octree 建構

Implement realtime bake Octree

Z-order
obstacle shape detect & re-construct

學習一般的 Octree 結構建立, 詳見參考文章.

# Log 12

– Async bake octree, remove all event listener than done in Log 10,11, because fucking slow.
重寫 Octree 建構並支持 runtime async reconstruction, 移除 Log 10, 11 中所有內部 event, 因為超級慢.
Octree 測試中的 node 數量為 6k, 每幀 Add event 的數量達到 60000次, alloc memory約 1MB.
全部改為 Func<> callback

– Based on octree and try to connect the leaf nodes neighbor, to form region, and try to use that for A* pathfinding.
於 octree 的 leaf node 上進行 neighbor 搜索, 並試圖以此減少 A* 搜尋路經時需檢索的 node 數量.

– use Obstacle class to internal handle update position and dispatch event.
所有 Obstacle 於加入 Octree 後會置入紀錄, 並通過內部進行位置更新, (忽略往後所有相同Obstacle 回報)
更新的方式通過檢查 GameObject 的 transform 是否有更改為概念, 於 0.3s ~ 10.0s 間進行.

if position changed, current update interval divide by 2;
if position NOT changed, current update interval doubled.

此修改令 octree 的地形檢測使用之物理 API, BoxOverlap 減少為 1.

# Log 13, 14, 14.1
Path finding logic

– optimize and refactor classes. removed node region. (learn by mistake)
移除整個 node region. 因為很慢.

– implement LazyThetaStar pathfinder,

– dynamic runtime update obstacle and path finding for each agents.

參考資料:

所有影片紀錄 (continue update)

FlightAgent #Boid Develop log

Canis

發佈留言取消回覆

Canis

發佈留言 取消回覆

發佈留言取消回覆