求助！关于四叉树碰撞检测。。。。。

zmcdn

  如果要弄一个等轴视角的游戏，在室外场景，四叉树碰撞检测好，还是将场景分成许多个网格的方法好？

小小C

分成许多个网格什么意思呢?

OSFG

最好是四叉树之类的。貌似你的地形都要分把。不明白你第二句话啥意思。

zmcdn

对不起，我的语言表达能力不大好。
第二句话说的就是最传统的那个办法。
就是将地形分成很多方格，每个方格保存位于这个方格里的物体，一个物体只要检测他所在的方格的所有物体就能检测碰撞。

游戏视界

3D场景里的碰检和渲染一般都用四叉树、8叉数吧，你说的第二种方法应该已经很少有人用了吧~

zmcdn

问题就在这里。总觉得在动态物体碰撞检测的时候，四叉树不如传统方法好。
每个物体虽然不是必须从树根开始遍历，但是如果动态物体正好在树根的时候，会不会很慢。
我看网上还有个办法，就是把叶子连起来，但这样跟传统办法不就一样了吗。。。。

游戏视界

zmcdn: Re:求助！关于四叉树碰撞检测。。。。。

问题就在这里。总觉得在动态物体碰撞检测的时候，四叉树不如传统方法好。
每个物体虽然不是必须从树根开始遍历，但是如果动态物体正好在树根的时候，会不会很慢。
我看网上还有个办法，就是把叶子连起来，但这样跟传统办法不就一样了吗...

实质这是一个搜索效率的问题，

四叉树的搜索仅为lgN次，效率是很高的；

而后面的一种实质上就是对链表的遍历，如果同样是上百万个数据，那后面的这种方法搜索的效率低了就不是一点半点~

zmcdn

游戏视界: Re: Re:求助！关于四叉树碰撞检测。。。。。


实质这是一个搜索效率的问题，

四叉树的搜索仅为lgN次，效率是很高的；

而后面的一种实质上就是对链表的遍历，如果同样是上百万个数据，那后面的这种方法搜索的效率低了就不是一点半点~

您好！您所说的链表是动态物体链表么？四叉树也应该遍历所有物体吧。

游戏视界

"把叶子连起来"的"遍历"是使用step+1的算法来实现目标结果的搜索，所以效率极低；

而使用四叉树算法后，对同样数据的搜索就仅lgN次，不同的算法间的效率区别就体现在这里。

两种算法的所谓“遍历”的概念是根本不同的。

为了方便你理解，举个不恰当的比喻就是就像采用数组进行数据的搜索与采用hash算法对同样数据的搜索，两者执行效率之间的差别会很悬殊。

OpenGPU

学习了!!

---------------------------------------------------------------------

开源图形处理器体系结构论坛(OpenGPU论坛)  
http://www.opengpu.org/bbs/

OpenGPU Graphics Open Source community（ 图形开源社区），聚焦领域(focus domain)包括：
  * GPU Architecture（图形处理器体系结构）.
  * Graphics Algorithm（图形算法).
  * Open Source Rendering Engine（开源渲染器）.
  * Open Source GPU Simulator/RTL Implement（开源GPU模拟器）.
  * GPGPU Programming （ 面向通用的图形处理器编程）
  * GPU General-purposed Computing （ GPU通用计算）.
.