作者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