用于2D碰撞检测的四叉树 [英] Quadtree for 2D collision detection
问题描述
我正在尝试使用四叉树进行2D碰撞检测，但是我对如何实现它有一点疑虑。首先，我会有一个四叉树，其中包含四个子树（一个表示每个象限），以及不适合单个子树的一组对象。
I'm trying to use a quadtree for 2D collision detection, but I'm a little stumped on how to implement it. First of all, I'd have a quadtree which contains four subtrees (one representing each quadrant), as well as a collection of objects which don't fit into a single subtree.
在树中检查对象进行碰撞时，我会执行此操作（感谢用于2D碰撞检测的四叉树）：
When checking an object for collisions in the tree, I would do something like this (thanks to QuadTree for 2D collision detection):
- 检查对象与当前节点中任何对象的冲突。
- 对于空间重叠对象的任何子树，递归。
要查找四叉树中的所有冲突：
To find all collisions within a quadtree tree:
- 检查当前节点中每个对象与当前节点中的每个对象。
- 检查每个对象在当前节点中针对每个子树。
插入四叉树：
- 如果对象适合多个子树，则将其添加到th中当前节点，并返回。
- 否则，递归到任何子树包含它。
要更新四叉树：
- 重新进入每个子树。
- 如果当前节点中有任何元素
- 如果当前节点中的任何元素适合于子树，请将其插入到子树中。
这样没事吗？可以改进吗？
Is this alright? Can it be improved?
推荐答案
您的四叉树结构不是最佳的。你是正确的，每个节点存储4个子树，但实际的对象只能存储在叶子内部，而不是内部节点。因此，持有实际对象的集合需要移动到叶子。
Your quadtree structure isn't optimal. You're right to store 4 subtrees per node, but actual objects should only be stored inside the leaves, not inner nodes. Therefore the collection holding the actual objects needs to be moved to the leaves.
我们来看看操作的实现：
- 将对象插入四叉树中：
检查对象是否与当前节点相交。如果是这样，递归。如果您已达到叶级别，请将对象插入到集合中。 - 从四叉树中删除对象：
执行完全相同的步骤，如果插入对象，但是当你已经达到叶级别从集合中删除它。 - 测试一个对象是否与四叉树内的任何对象相交：_
执行与插入对象完全相同的步骤，但是当您到达叶子级别时检查与集合中所有对象的冲突。 - 测试四叉树内所有对象之间的所有冲突：
对于四叉树中的每个对象执行单个对象碰撞测试。 - 更新四叉树：_
从已修改位置的四叉树中删除所有对象，并再次插入。
- Insert an object into the quadtree:
Check if the object intersects the current node. If so, recurse. If you've reached the leaf level, insert the object into the collection. - Delete an object from the quadtree:
Execute the exact same steps as if inserting the object, but when you've reached the leaf level delete it from the collection. - Test if an object intersects any object inside the quadtree:
Execute the exact same steps as if inserting the object, but when you've reached the leaf level check for collision with all the objects in the collection. - Test for all collisions between all objects inside the quadtree:
For every object in the quadtree execute the single object collision test. - Update the quadtree:
Delete all objects from the quadtree whose position has been modified and insert them again.
这有几个优势：
This has several advantages:
- 只存储对象叶子很容易处理四叉树的操作（更少的特殊情况）
- 四叉树可以具有不同深度的叶子，从而允许您根据四叉树的密度来调整四叉树的密度它涵盖的空间区域。这种适应可以在运行时发生，从而保持对象/节点比例的最优。
只有不利于：
- 对象可以属于quadtree内的几个集合。您将需要在四叉树之外的额外的线性集合来枚举每个对象而不重复。
这篇关于用于2D碰撞检测的四叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
