Quadtree和红黑树的游戏在C + +？ [英] Quadtree vs Red-Black tree for a game in 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.

我的目的是存储对象在游戏中处理的事情，如碰撞检测。
我不是100％确定一个quadtree是最好的数据结构使用，但从我所读的是。我已经编写了一个红黑树，但我不知道是否对我的游戏（这将是一个冒险第三人称游戏像安克）的表现是否足够。

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).

我如何在C ++中编写一个基本但完整的quadtree类（或octree）？
如何使用四叉树进行碰撞？

How would I write a basic but complete quadtree class (or octree) in C++? How would you use the quad tree for collisions?

推荐答案

当你只需要存储有效地在飞机上。像经典RTS中的单位，他们都在地上或只是一点点上面。基本上每个节点都有到4个子节点的链接，这些子节点将节点的空间分成均匀分布的季度。

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.

八叉树是相同的，但在所有三个维度而不是两个，他们有8个子节点，并将空间分割成八个。

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.

如果你正在寻找一个二叉树 - 像一个红黑树，那么你应该使用它。想要使用称为二进制空间分区树（BSP tree）的数据结构或其称为KD树的版本。使用平面将这些分区空间分成两半，在KD树中，平面是正交的（在XZ，XY，ZY轴上），因此有时它在3D场景中更好地工作。 BSP树使用任何方向上的平面来划分场景，但是它们可以是非常有用的，并且远远用于Doom。

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.

现在，游戏空间，你现在不必测试每个游戏实体对每个其他游戏实体看它们是否碰撞，这是一个O（n ^ 2）算法。而是查询数据结构以返回游戏空间的子区域内的游戏实体，并且只对这些节点彼此进行冲突检测。

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.

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

This means that collision detection for all game entities should be n O(nlogn) operation (at worst).

需要注意的几件事情：

• 确保您从相邻节点测试游戏实体，而不只是当前节点中的游戏实体，因为它们仍然可能发生冲突。


• 在实体移动之后重新平衡数据结构，因为您现在可能在数据结构中具有空节点，或者包含过多实体以获得良好性能（也是所有实体在同一节点中的退化情况）的数据结构。 / li>
  

• Make sure you test game entities from adjacent nodes, not just the ones in the current node, since they could still collide.
• Rebalance the data structure after the entities have moved since you may have empty nodes in the data structure now, or ones that contain too many entities for good performance (also the degenerate case of all entities being in the same node).

这篇关于Quadtree和红黑树的游戏在C + +？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！