碰撞用的四叉树的搜索效率如何才能体现出来？

zlcnkkm · 发表于 2005-10-16 12:19:00

场景中的物体在每一个计算周期的位置都不相同，那么是不是每个周期都重新历遍？

无影无踪 · 发表于 2005-10-16 12:35:00

这种遍历还是比较快的，而且不一定都要从根节点开始遍历。

zlcnkkm · 发表于 2005-10-16 13:28:00

我也想不通究竟如果判断从哪一层开始遍历

无影无踪 · 发表于 2005-10-16 15:52:00

如果物体已在节点n中，那么可以认为与该物体发生潜在碰撞可能的物体为n节点中的其他物体以及n以下的所有节点中的物体，还有n的所有祖先节点中的物体。也就是说需要向下遍历搜索和向上的寻根搜索。

zlcnkkm · 发表于 2005-10-16 22:08:00

那么还是要在每个计算周期开始时，都要重新生成树，判断每个物体在哪个节点上

游戏之家 · 发表于 2005-10-16 22:35:00

矩形判断我有很好的办法,  不占用资源

AX > A And AX < A+100 And  BX > B And BX < B+ 100 Then  到击中程序

AX,BX=子弹坐标
A,B=敌人坐标
现在是 100 x 100 的矩形  , 我的打击者1940里用的这个方法.

无影无踪 · 发表于 2005-10-16 22:37:00

不可以完全这样想，因为基本上游戏中静态的物体都会比动态的多得多，而且动态的也不一定每时每刻都在移动，即使移动，大多速度也不会达到每秒钟几百米（子弹可以）。因此静态的物体无需update，对于动态的，我们可以根据物体原来所在的节点比较快速地找出新位置时的节点，这种速度其实是非常快的。

zlcnkkm · 发表于 2005-10-16 22:59:00

游戏之家: Re:碰撞用的四叉树的搜索效率如何才能体现出来？

矩形判断我有很好的办法, 不占用资源

AX > A And AX < A+100 And BX > B And BX < B+ 100...

这方法在2D游戏里比较常用，简单兼方便

不过我发这贴主要是学习叉树

zlcnkkm · 发表于 2005-10-16 23:07:00

无影无踪: Re:碰撞用的四叉树的搜索效率如何才能体现出来？

不可以完全这样想，因为基本上游戏中静态的物体都会比动态的多得多，而且动态的也不一定每时每刻都在移动，...

一言惊醒啊~！感谢一个！

在3D场景应该是用六叉树吧？这个不太好理解

无影无踪 · 发表于 2005-10-16 23:10:00

zlcnkkm: Re: Re:碰撞用的四叉树的搜索效率如何才能体现出来？

一言惊醒啊~！感谢一个！

在3D场景应该是用六叉树吧？这个不太好理解

3D中的是8叉树，其实4叉树在3D中也是经常用到的，例如地形(terrian)。8叉树的道理和4叉树是一样的。

账号		自动登录	找回密码
密码			立即注册

Re:碰撞用的四叉树的搜索效率如何才能体现出来？