用于二维碰撞检测的四叉树 [英] 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 碰撞检测的 QuadTree):

When checking an object for collisions in the tree, I would do something like this (thanks to QuadTree for 2D collision detection):

1. 检查对象是否与当前节点中的任何对象发生碰撞.
2. 对于空间与对象重叠的任何子树，递归.

要查找四叉树中的所有碰撞:

To find all collisions within a quadtree tree:

1. 根据当前节点中的其他对象检查当前节点中的每个对象.
2. 根据每个子树检查当前节点中的每个对象.

插入四叉树:

1. 如果对象适合多个子树，则将其添加到当前节点，然后返回.
2. 否则，递归到任何包含它的子树中.

更新四叉树:

1. 递归到每个子树中.
2. 如果当前节点中的任何元素不再完全适合当前树，请将其移至父节点.
3. 如果当前节点中的任何元素适合子树，则将其插入子树.

这样好吗?可以改进吗?

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.

我们来看看操作的实现:

1. 在四叉树中插入一个对象:
   检查对象是否与当前节点相交.如果是这样，递归.如果您已达到叶级别，请将对象插入到集合中.
2. 从四叉树中删除一个对象:
   执行与插入对象完全相同的步骤，但是当您到达叶级别时，将其从集合中删除.
3. 测试一个对象是否与四叉树内的任何对象相交:
   执行与插入对象完全相同的步骤，但是当您到达叶级别时，检查与集合中的所有对象是否发生碰撞.
4. 测试四叉树内所有对象之间的所有碰撞:
   对四叉树中的每个对象执行单个对象碰撞测试.
5. 更新四叉树:
   从四叉树中删除位置已被修改的所有对象，然后重新插入.

这有几个优点:

• 通过只在叶子中存储对象，很容易处理四叉树上的操作(较少的特殊情况)
• 四叉树可以有不同深度的叶子，因此您可以根据四叉树覆盖的空间区域调整四叉树的密度.这种适应可以在运行时发生，从而使对象/节点比率保持最佳.

只有缺点:

• 对象可以属于四叉树内的多个集合.您将需要在四叉树之外使用一个额外的线性集合来枚举每个对象而没有重复项.

这篇关于用于二维碰撞检测的四叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！