logo标签列表

用于C++游戏的四叉树与红黑树哪个更好？

c++quadtree
8

我已经在网上寻找四叉树/四叉树节点的实现很长时间了。有一些基础知识，但没有什么东西可以真正用于游戏。

我的目的是为了在游戏中存储对象，以处理诸如碰撞检测之类的事情。 我不确定四叉树是否是最好的数据结构，但从我所读到的来看，它是最好的。我已经编写了一个红黑树，但我不确定性能是否足够好，因为我的游戏将是像《Ankh》这样的第三人称冒险游戏。

如何编写一个基本但完整的C++四叉树类（或八叉树）？ 如何使用四叉树进行碰撞检测？

这有点含糊不清。我认为树的实现需要知道你想要存储什么类型的数据，因为这会影响插入操作的细节（如分裂等）。 - unwind
6个回答
18

四叉树(Quadtrees)通常用于存储平面上的物体，例如类似于经典实时战略游戏中所使用的单位，它们都在地面上或者仅仅浮在地面之上。每个节点连接着四个子节点，将该节点的空间均匀地分成四个部分。

八叉树(Octrees)同样可以进行相同的操作，但是在三维空间中而非只有两维，所以有8个子节点并将空间分成了八份。如果3D场景中的游戏实体在三个维度上分布更加均匀，则应使用它们。

如果您正在寻找类似于红黑树的二叉树结构，则应使用称为二进制空间分割树(BSP tree)或其版本之一——KD树(KD Tree)的数据结构。它们使用平面将空间划分为两个部分，在KD树中，这些平面是正交的(在XZ、XY、ZY轴上)，因此在3D场景中有时效果更好。BSP树可以使用任意方向的平面来划分场景，虽然它们可能很有用，但早在Doom时期就已经被使用过了。

现在，由于已经将游戏空间分区，您不必针对每一个游戏实体测试其是否与其他游戏实体碰撞，这是一个最好的O(n^2)算法。相反，您可以查询数据结构以返回游戏空间子区域内的游戏实体，仅对这些节点相互之间进行碰撞检测。

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

还有一些额外需要注意的问题：

  • 确保测试相邻节点中的游戏实体，而不仅仅是当前节点中的游戏实体，因为它们仍然可能会发生碰撞。
  • 在实体移动后重新平衡数据结构，因为现在数据结构中可能存在空节点或包含太多实体以至于性能不理想(还有一种情况是所有实体都在同一个节点中)。
10

红黑树不是空间索引，它只能对单个序数键进行排序。Quadtree是（对于二维），它可以快速查找和消除点的空间索引。Octree则是对于三维做同样的事情。

5
使用四叉树的原因是可以在x和y坐标上进行分割，而八叉树则在x、y和z上进行分割，使得碰撞检测变得微不足道。
四叉树：如果一个元素不在左上角，则不会与右上角、左下角或右下角中的元素发生碰撞。
这是一个非常基本的类，所以我不明白你在找到的实现中缺少什么。
我不会写这样的类，我只会从具有适当许可证的项目中借用它。
四叉树的关键不在于快速遍历树，而是尽可能避免进行遍历。 - Jimmy
3

我强烈建议您使用渲染引擎，例如Ogre3D。据我所知，它支持八叉树进行场景管理。但是您可以根据自己的需要扩展基于八叉树的类。我曾经自己编写所需的代码，但对于复杂的项目来说，这并不是正确的方式。

0

总的来说，树对于这个问题是有问题的，因为任何插入的项都可能位于边界上，而处理该情况的所有方法都相当不令人满意。

您很可能希望将对象分为可移动和静态，并检查给定帧上移动的任何内容与静态对象是否匹配。

BSP树是静态几何的接受解决方案（通过将对象分割成两个部分来处理边界情况），对于动态尝试使用类似Sort and Sweep（也称为Sweep and Prune）的东西。

0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接