Re: [程式] 關於碰撞偵測的初期簡化

看板GameDesign作者NDark (K1下次要買搖滾區)時間15年前 (2008/10/21 11:39)推噓7(7推 0噓 5→)

留言12則, 7人參與討論串2/3 (看更多)

※ 引述《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

推

gpmm

10/21 11:45, , 1^F

10/21 11:45, 1^F

※ 編輯: NDark 來自: 140.96.76.147 (10/21 12:25)

推

GALINE

10/21 13:25, , 2^F

10/21 13:25, 2^F

推

sdk

10/21 13:34, , 3^F