C++ 游戏中的四叉树与红黑树？
我多年来一直在网上寻找四叉树/四叉树节点实现。 有一些基本的东西，但没有什么是我能够真正将其用于游戏的。
我的目的是在游戏中存储对象以进行碰撞检测等处理。 我不能 100% 确定四叉树是最好使用的数据结构，但从我读到的内容来看，它是最好的。 我已经编写了红黑树代码，但我真的不知道性能是否足以满足我的游戏（这将是像 Ankh 这样的冒险第三人称游戏）。
我如何用 C++ 编写一个基本但完整的四叉树类（或八叉树）？ 您将如何使用四叉树进行碰撞？
I have been looking for a quadtree/quadtree node implementation on the net for ages. There is some basic stuff but nothing that I would be able to really use it a game.
My purpose is to store objects in a game for processing things such as collision detection.
I am not 100% certain that a quadtree is the best data structure to use, but from what I have read it is. I have already coded a Red-Black tree, but I don't really know if the performance would be good enough for my game (which will be an adventure 3rd person game like Ankh).
How would I write a basic but complete quadtree class (or octree) in C++?
How would you use the quad tree for collisions?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
当您只需要存储有效地位于平面上的内容时，可以使用四叉树。 就像经典 RTS 中的单位一样，它们都在地面上或仅在地面上方一点点。 本质上，每个节点都有到 4 个子节点的链接，这些子节点将节点的空间划分为均匀分布的部分。
八叉树做同样的事情，但在所有三个维度上，而不仅仅是两个维度，因此它们有 8 个子节点，并将空间划分为八个。 当游戏实体在所有三个维度中分布更均匀时，应该使用它们。
如果您正在寻找二叉树（例如红黑树），那么您需要使用一种称为二元空间分区树（BSP 树）的数据结构或其称为 KD 树的版本。 这些使用平面将空间分成两半，在 KD 树中，平面是正交的（在 XZ、XY、ZY 轴上），因此有时它在 3D 场景中效果更好。 BSP 树使用任意方向的平面来划分场景，但它们非常有用，早在 Doom 中就已使用它们。
现在，因为您已经对游戏空间进行了分区，所以您不必针对每个其他游戏实体来测试每个游戏实体以查看它们是否发生冲突，这最多是一个 O(n^2) 算法。 相反，您查询数据结构以返回游戏空间子区域内的游戏实体，并且仅对这些节点彼此执行碰撞检测。
这意味着所有游戏实体的碰撞检测应该是 n O(nlogn) 操作（最坏的情况下）。
需要注意的一些额外事项：
Quadtrees are used when you only need to store things that are effectively on a plane. Like units in a classic RTS where they are all on the ground or just a little bit above it. Essentially each node has links to 4 children that divide the node's space up into evenly distributed quarters.
Octrees do the same but in all three dimensions rather than just two, and thus they have 8 child nodes and partition the space up into eights. They should be used when the game entities are distributed more evenly among all three dimensions.
If you are looking for a binary tree - like a red-black tree - then you want to use a data structure called a binary space partitioning tree (BSP tree) or a version of it called the KD Tree. These partition space into halves using a plane, in the KD tree the planes are orthogonal (on the XZ, XY, ZY axes) so sometimes it works better in a 3D scene. BSP trees divide the scene up using planes in any orientation, but they can be quite useful, and they were used as far back as Doom.
Now because you've partitioned the game space you now don't have to test every game entity against every other game entity to see if they collide, which is an O(n^2) algorithm at best. Instead you query the data structure to return the game entities within a sub-region of the game space, and only perform collision detection for those nodes against each other.
This means that collision detection for all game entities should be n O(nlogn) operation (at worst).
A couple of extra things to watch out for:
红黑树不是空间索引； 它只能对单个序数键进行排序。 四叉树（对于二维）是一种空间索引，允许快速查找和消除点。 八叉树在三个维度上做同样的事情。
A red-black tree is not a spatial index; it can only sort on a single ordinal key. A quadtree is (for two dimensions) a spatial index that allows fast lookup and elimination of points. An Octree does the same thing for three dimensions.
使用四叉树的原因是因为您可以在 x 和 y 坐标上进行分割，即 x、y 和 z 上的八叉树，从而使碰撞检测变得微不足道。
四叉树：如果一个元素不在左上角，它不会与右上角、左下角或右下角的元素发生碰撞。
这是一个非常基本的课程，所以我不明白您在找到的实现中缺少什么。
我不会写这样的类，我只是从具有合适许可证的项目中借用它。
The reason to use a quadtree is because you can then split on x- and y-coordinates, an octree on x, y and z, making collision detection trivial.
Quadtree: if an element is not in the topleft, it wont collide with one in topright, bottomleft or bottomright.
It is a very basic class, so I don't understand what you are missing in implementations you found.
I would not write such a class, I'd just borrow it from a project with a suitable license.
我强烈建议您使用渲染引擎，例如 Ogre3D。 据我所知它支持八叉树进行场景管理。 但您可以根据需要扩展基于八叉树的类。 我曾经自己编写我需要的东西，但对于复杂的项目，这不是正确的方法。
I warmly suggest you to use a rendering engine, Ogre3D for instance. As far as I know it supports Octrees for scene management. But you can extend the Octree-based class as you wish. I used to code the stuff I needed by myself, but for complex projects, it's just not the right way.
一般来说，树在这方面存在问题，因为插入的任何项目都可能位于边界上，并且处理这种情况的所有方法都相当不令人满意。
您很可能希望将对象分为可移动和静态，并根据静态对象检查给定帧上移动的任何内容。
BSP 树是静态几何的公认解决方案（通过将对象分成两部分处理边界情况），对于动态尝试诸如排序和扫描（也称为扫描和修剪）之类的解决方案。
Trees in general are problematic for this in that any item inserted can lie on a boundary, and all the methods of dealing with that situation are fairly unsatisfactory.
You'll most likely want to sort your objects into moveable and static, and check anything that moved on a given frame against the static objects.
BSP Trees are the accepted solution for static geometry (boundary cases handled by splitting the object into two pieces), for dynamic try something like Sort and Sweep (also known as Sweep and Prune).
目前 STANN 是最好的开源实现。
http://sites.google.com/a/compgeom.com/stann/< /a>
Right now STANN is the best open source implementation.
http://sites.google.com/a/compgeom.com/stann/