用C++游戏的Quadtree vs Red-Black树？

Question

我一直在寻找网上的四叉树/四叉树节点实现多年.有一些基本的东西,但没有什么我可以真正使用它的游戏.

我的目的是将对象存储在游戏中以处理诸如碰撞检测之类的事情.我不是100%确定四叉树是最好的数据结构,但我从它所读到的是.我已经编写了一张红黑树,但我真的不知道我的游戏性能是否足够好(这将是像Ankh这样的冒险第三人称游戏).

如何在C++中编写基本但完整的四叉树类(或八叉树)？你会如何使用四叉树进行碰撞？

Answer 1

当您只需要存储有效在飞机上的东西时,使用四叉树.像经典RTS中的单位一样,它们都在地面上或者只是稍微高一点.基本上每个节点都有4个子节点的链接,这些子节点将节点的空间划分为均匀分布的区域.

八分相同但是在所有三个维度而不是仅仅两个维度,因此它们具有8个子节点并将空间划分为八个.当游戏实体在所有三个维度中更均匀地分布时,应该使用它们.

如果您正在寻找二叉树 - 如红黑树 - 那么您希望使用称为二进制空间分区树(BSP树)的数据结构或称为KD树的版本.这些使用平面将空间分成两半,在KD树中平面是正交的(在XZ,XY,ZY轴上),因此有时它在3D场景中效果更好.BSP树在任何方向上使用平面划分场景,但它们可能非常有用,并且它们可以像Doom一样被使用.

现在因为你已经对游戏空间进行了划分,所以你现在不必测试每个游戏实体与其他所有游戏实体的对比,看看它们是否发生冲突,最好是O(n ^ 2)算法.相反,您查询数据结构以返回游戏空间的子区域内的游戏实体,并且仅对这些节点执行相互碰撞检测.

这意味着所有游戏实体的碰撞检测应该是n O(nlogn)操作(最坏的情况).

还有几件需要注意的事项:

• 确保从相邻节点测试游戏实体,而不仅仅是当前节点中的游戏实体,因为它们仍然可能会发生冲突.
• 实体移动后重新平衡数据结构,因为您现在可能在数据结构中有空节点,或者包含太多实体以获得良好性能的数据(也是所有实体在同一节点中的退化情况).

Answer 2

红黑树不是空间索引; 它只能对单个序号键进行排序.四叉树(用于二维)是空间索引,允许快速查找和消除点.八叉树对三个维度做同样的事情.

Answer 3

使用四叉树的原因是因为您可以在x和y坐标上分割,在x,y和z上分割八叉树,使碰撞检测变得微不足道.

四叉树:如果一个元素不在topleft中,它就不会与topright,bottomleft或bottomright中的元素碰撞.

这是一个非常基础的类,所以我不明白你找到的实现中缺少什么.

我不会写这样的课程,我只是从具有合适许可证的项目中借用它.