作者littleshan (我要加入劍道社!)
看板GameDesign
標題Re: [程式] 請問如何計算2D的碰撞預測及碰撞避免
時間Wed Dec 13 15:59:14 2006
: --
:
※ 發信站: 批踢踢實業坊(ptt.cc)
: ◆ From: 140.119.201.20
: 推 chaosrx:可以試試 Bounding Box 12/12
: 推 l314:用bounding box,當Agent數多時,計算的cost會相當大? 12/12
: 推 littleshan:grid + bounding box 12/12
: 推 l314:樓上的前輩能否再給小弟多一點提示或參考網站.. 12/13
: → l314:我有看過一些paper用grid，的確可以大幅降低計算的cost.. 12/13
: → l314:但我實作經驗很不足，請問有沒有推薦的網站可以參考..orz.. 12/13
: → l314:或前輩能多給些detail的指導..謝謝.. 12/13
grid 的概念很簡單
就只是把整個區域切成一塊一塊的小方格
比如說 假設所有 agent 都會在 [0,100]x[0,100] 這個範圍中移動
那就把它切成 10x10 的方格 每個格子的長寬皆為 10
而且每個方格都要儲存所有位置在這個方格中的 agent 清單
這麼一來 假設某 agent 想知道哪些 agent 可能與它碰撞
他只要檢查自己所在的方格 與鄰近方格中的 agent 即可
而不需要和所有其它的 agent 測試
當然 要切多少個方格 就和你要偵測的距離相關
上面所說的做法是拿 20 做為上限
也就是所有距離超過 20 的 agent 都不會進行碰撞測試
方格的大小取決於你希望多近的距離才需要碰撞測試
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.84
1F：推 l314:感恩..orz.. 12/13 16:56
2F：推 hodsala:影像四元樹也是可以~可是查查~我只知道概念 01/02 18:44
3F：→ hodsala: 以 01/02 18:46
4F：推 littleshan:這是動態場景，不適合用 quadtree 01/04 05:53