我一直在寻找网络上的四叉树/四叉树节点实施年龄。有一些基本的东西，但没有什么能够真正使用它的游戏。Quadtree vs Red-Black树在C++中的游戏？
我的目的是在游戏中存储对象，以处理诸如碰撞检测等事情。 我不是100％确定四叉树是最好的数据结构，但从我读过的是。我已经编了一棵红黑树，但我不知道这个表现对我的游戏是否足够好（这将是一个像安赫一样的冒险第三人称游戏）。
我该如何在C++中编写一个基本的但完整的四叉树类（或八叉树）？ 如何使用四叉树进行碰撞？
当你只需要存储在飞机上有效的东西时，就会使用四叉树。就像经典RTS中的单位一样，它们都在地面上，或者只是稍微高出一点。本质上，每个节点都有4个孩子的链接，将节点的空间分成均匀分布的宿舍。
八叉树做相同的，但在所有三个方面，而不是只有两个，因此，他们有8个节点和最多分区空间分割成八分。当游戏实体在所有三个维度中更均匀地分配时，应该使用它们。
如果您正在寻找一棵二叉树 - 就像一棵红黑树 - 那么您想要使用一种名为二进制空间分区树（BSP树）或称为KD树的一种版本的数据结构。这些分区使用一个平面分成两半，在KD树中平面是正交的（在XZ，XY，ZY轴上），所以有时它在3D场景中效果更好。 BSP树使用任何方向的飞机将场景分开，但它们可能非常有用，而且它们早在Doom后面使用。
现在，因为你已经划分的游戏空间，你现在不必测试每个游戏的实体对所有其他游戏实体，看看他们是否发生碰撞，这是一个为O（n^2）算法的最好的。相反，您查询数据结构以在游戏空间的一个子区域内返回游戏实体，并且仅对这些节点执行碰撞检测。
这意味着，碰撞检测所有游戏实体应该是n O（nlogn）操作（在最坏的情况）。
一些额外的事情需要注意的：
使用四叉树的原因是因为你可以然后在X和Y坐标，对x，y和z中的一个八叉树分割，使得碰撞检测微不足道。
四叉树：如果一个元素不处于左上，它不会与一个在topright，BOTTOMLEFT或bottomright碰撞。
这是一个非常基础的类，所以我不明白你发现的实现中缺少什么。
我不会写这样的课程，我只是从具有合适许可证的项目中借用它。
正好。四叉树的点不是树的快速遍历，而是首先避免遍历。 – Jimmy 2008-12-16 16:03:51
红黑树不是空间索引;它只能对一个序号进行排序。四叉树（二维）是一种空间索引，允许快速查找和消除点。八叉树在三个维度上做同样的事情。
树木一般来说是有问题的，因为插入的任何物品都可能位于边界上，并且处理这种情况的所有方法都不太令人满意。
您很可能希望将对象排序为可移动和静态，并检查给定框架上相对于静态对象移动的任何内容。
BSP树是静态几何（通过将对象拆分为两部分来处理的边界情况）的可接受解决方案，用于动态尝试诸如Sort和Sweep（也称为Sweep和Prune）之类的东西。
我热烈地建议您使用渲染引擎，例如Ogre3D。据我所知它支持Octrees进行场景管理。但是你可以根据需要扩展基于八叉树的类。我曾经自己编写我需要的东西，但对于复杂的项目，这不是正确的方法。
现在STANN是最好的开源实现。
这个有点含糊。我认为树实现需要知道你想要存储什么样的数据，因为这会影响插入工作的细节（分割等）。 – unwind 2008-12-16 14:29:10