多年来，我一直在网上寻找四叉树/四叉树节点实现。有一些基本的东西，但没有什么能让我真正用它来玩游戏。
我的目的是将对象存储在游戏中以处理诸如碰撞检测之类的事情。我不能 100% 确定四叉树是最好的数据结构，但从我所读到的数据来看。我已经编写了一个红黑树，但我真的不知道性能是否足以适合我的游戏（这将是像 Ankh 这样的冒险第三人称游戏）。
我将如何用 C++ 编写一个基本但完整的四叉树类（或八叉树）？您将如何使用四叉树进行碰撞？
Brock Woolf
问问题
10435 次
6 回答
18
当您只需要存储有效地在平面上的东西时，使用四叉树。就像经典 RTS 中的单位一样，它们都在地面上或略高于地面。本质上，每个节点都有到 4 个子节点的链接，这些子节点将节点的空间分成均匀分布的四分之一。
八叉树做同样的事情，但在所有三个维度上，而不仅仅是两个维度，因此它们有 8 个子节点并将空间划分为八个。当游戏实体在所有三个维度中分布更均匀时，应使用它们。
如果您正在寻找二叉树（例如红黑树），那么您希望使用称为二叉空间分区树（BSP 树）的数据结构或称为 KD 树的版本。这些使用平面将空间分成两半，在 KD 树中，平面是正交的（在 XZ、XY、ZY 轴上），因此有时它在 3D 场景中效果更好。BSP 树使用任何方向的平面来划分场景，但它们可能非常有用，并且早在 Doom 时就已使用它们。
现在因为您已经划分了游戏空间，所以您现在不必针对每个其他游戏实体测试每个游戏实体以查看它们是否发生碰撞，这充其量是 O(n^2) 算法。相反，您查询数据结构以返回游戏空间子区域内的游戏实体，并且仅对这些节点执行碰撞检测。
这意味着所有游戏实体的碰撞检测应该是 n O(nlogn) 操作（最坏的情况）。
需要注意的一些额外事项：
- 确保从相邻节点测试游戏实体，而不仅仅是当前节点中的实体，因为它们仍然可能发生碰撞。
- 在实体移动后重新平衡数据结构，因为现在数据结构中可能有空节点，或者包含太多实体以获得良好性能的节点（也是所有实体位于同一节点中的退化情况）。
于 2008-12-16T16:25:38.170 回答
10
红黑树不是空间索引；它只能对单个序号键进行排序。四叉树是（对于二维）允许快速查找和消除点的空间索引。八叉树对三个维度做同样的事情。
于 2008-12-16T16:10:03.553 回答
5
使用四叉树的原因是因为您可以在 x 和 y 坐标上进行拆分，在 x、y 和 z 上使用八叉树，从而使碰撞检测变得微不足道。
四叉树：如果一个元素不在左上角，它不会与右上角、左下角或右下角的元素发生碰撞。
这是一个非常基本的类，所以我不明白你在找到的实现中缺少什么。
我不会写这样的课程，我只是从具有合适许可证的项目中借用它。
于 2008-12-16T16:02:00.743 回答
3
我强烈建议您使用渲染引擎，例如 Ogre3D。据我所知，它支持八叉树进行场景管理。但是您可以根据需要扩展基于八叉树的类。我以前自己编写需要的东西，但对于复杂的项目，这不是正确的方法。
于 2008-12-16T17:11:31.993 回答
0
通常，树对此存在问题，因为插入的任何项目都可能位于边界上，并且处理这种情况的所有方法都相当不令人满意。
您很可能希望将对象分类为可移动对象和静态对象，并检查在给定框架上移动的任何对象与静态对象。
BSP 树是静态几何（通过将对象分成两部分来处理边界情况）的公认解决方案，对于动态尝试类似排序和扫描（也称为扫描和修剪）的方法。
于 2008-12-16T17:09:31.170 回答
0
目前 STANN 是最好的开源实现。
于 2010-07-05T20:14:51.047 回答