作者NDark (K1下次要買搖滾區)
看板GameDesign
標題Re: [程式] 關於碰撞偵測的初期簡化
時間Tue Oct 21 11:39:52 2008
※ 引述《GALINE (我是CQD，不是cqd)》之銘言：
: 假設我的3D空間中有大量的物件可能彼此碰撞（EX:300架飛機）
: 是否只能用窮舉法去偵測全部的物件是否有彼此碰撞呢？
: 還是說，有辦法利用資料結構讓程式能快速找出彼此比較接近的物件，再來作碰撞嗎？
: 或者，用單純的碰撞球來作偵測的效率就夠高，可以用窮舉法硬上呢？
問一個好的問題,就解決了問題的一半...
碰撞偵測是一個很深的問題.
端看有多少資源,有多少時間.
是要做到夠完美,還是做到夠有效率.
Flocking 跟 格鬥 的要求是天差地遠...
窮舉(all pairs)搭配3D距離
不見得比 3D粒子動態范諾圖搭配三角形碰撞計算 慢
端看需求在哪裡.
a) 如果距離死線只有一天
我就會使用窮舉法.
然後記錄下每個物件最近的 鄰居 及 最近距離 ,
依照 最近距離 跟 速度 來判斷這個物件需要抓來碰撞的機率是多少,
機率越低,我就把他歸類到孤鳥區,
1秒(30frames)才去跑一次孤鳥區的碰撞計算.更新上面的數據即可.
同理如果是暴民區,我就每個frame去算一次.而且暴民只跟暴民比.
不過如果全部物件速度都很快,都往同一點飛.最後還是會crash掉的.
如果晚上還有時間,勢必要作一個延遲計算的上限來避免crash.
結論:不精準沒關係,FPS不要掉比較重要,因為老闆根本不會用心看哪隻鳥碰到了
b) 如果距離死線還有一個禮拜
我還是使用窮舉法.
只是會搭配比較高級的判斷方式,
用一個regular grid把我的場景分好,
寫一個位置速度的快查表函式來決定物件的速度方向 可能會碰的區域
對物件的位置是在那些區域的物件來查.
因此那些速度慢的孤鳥,理想上幾乎就可以完全省略他們的碰撞計算了.
結論:說實話,總體上這樣不見得比a方案來的快,
但是比較有學術性,比較可以騙得過喜歡技術的老闆
c) 如果死線還有一個月
首先我會先把b方案在一個禮拜implement出來.
然後花一個禮拜用來調劑身心.看看PTT,抓抓影片,找人出來吃點好料.
然後第二個禮拜尾端survey一下OCTREE是什麼鬼東西
剩下兩個禮拜把它implement出來,然後寫個好看的demo,
如果demo沒寫完,或是OCTREE作不出來,死線的時候我就把方案B交出去
結論:至少你有在做一個大家都聽過的技術了.只是還需要一點時間"測試"而已.
d) 如果死線還有半年
我會依照方案c然後慢慢刻我的OCTREE,
然後多加一些demo,跟編輯器讓大家玩.
然後我會把我做的source code跟demo+編輯器,外加謝金 寄給NDark的實體地址
(記得附上授權.)
--
"May Balance be with U"(願平衡與你同在)
歡迎參觀 NDark的網站
http://vision.twbbs.org/~ndark/
NDark的MSN LIVE
http://ndark.spaces.live.com/
＊最新期待遊戲:
Soul Calibur 4
＊最新專案 : 代客
拼圖宣傳區
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.96.76.147
1F：推 gpmm:頭推！！！ 10/21 11:45
※ 編輯: NDark 來自: 140.96.76.147 (10/21 12:25)
2F：推 GALINE:第四點我笑了 XD 看來我可以慢慢來研究octree，感謝 10/21 13:25
3F：推 sdk:e) 直接拿現成的物理引擎來用...XD 10/21 13:34
4F：推 GALINE:我只會用到一片地形跟碰撞球，不想搞這麼大 XD 10/21 13:54
5F：推 IJS:推 10/21 14:16
6F：推 reizarc:看到這篇想起以前跟你用 octree 做碰撞處理的往事 XD 10/21 23:37
7F：→ reizarc:找了一下 那時用來前處理場景的 octree code 還留著喔 XD 10/21 23:38
8F：→ reizarc:不過圖形介面是用 BCB 寫的 現在不知道還 build 的起來嗎 10/21 23:39
9F：→ NDark:那時候是用BCB摳的?code應該都有留啦.只要片子不要陣亡 10/22 00:21
10F：推 yoco315:推推 XD 10/22 00:30
11F：→ reizarc:有一個有套 GUI 的工具程式是用 bcb 的 10/23 00:01
12F：→ reizarc:核心的部分還是在 VC 中完成 10/23 00:01