在 C++ 中移动对象后如何更新四叉树？

Question

最简单的方法是删除和插入对象，但可能还有更快的方法。（如果我想太多了，我应该用简单的方法来做，请告诉我）

这是关于我的四叉树的一些注释

• 正在移动的对象是 AABB，并且可能比最小的四叉树节点还要大。
• 创建子四叉树时，不会删除对象。这意味着根四叉树有一个指向四叉树内每个对象的指针。
• 这些对象作为指针存储在四叉树外部的向量中。

到目前为止，每次对象移动时，它都会调用根四叉树上名为 Update() 的函数。它包含其自身以及在移入参数之前的过去的边界框。但我不确定如何实现该功能。

将整个代码发布到我的 QuadTree 会使我的帖子变得很长，因此我创建了一个GitHub 存储库以便于阅读。

编辑：对于任何寻找答案的人来说，这似乎是通过删除和删除对象来更新对象，并且从他在评论中所做的测试来看，这是相当有效的。

Answer 1

除了删除并重新插入之外，真的很难做得更好，尤其是在您的情况下，因为：

• 删除似乎超级便宜（从相应节点的向量中删除指针）
• 当寻找将对象移动到哪个节点时，您需要以与插入时完全相同的方式遍历树，然后：
• 插入相当便宜

如果性能确实是一个问题，我唯一会尝试的就是从叶子中进行某种插入。假设您的树非常大，并且对象通常移动到紧邻的节点，您可以请求插入父节点，如果需要，父节点会将其传递给其父节点。就像是：

void insert_from_leaf(object* o) {
  if (!is_in_this_subtree(o)) {
    parent->insert_from_leaf(o);
    return;
  }
  find_child_node_for_object(o)->insert(0);
}

基本上，从对象所在的叶子开始遍历树可能比总是从根开始遍历树更有效，因为相邻节点往往共享一个紧密的祖先。

在最坏的情况下，你最终会做两倍的工作，因为你会一直回到根源。在最好的情况下，源和目标共享一个直接父级。

增益效果有多大完全取决于特定树的布局、其大小以及许多其他因素，因此您应该在实现此类操作之前和之后测量代码的性能。

Answer 2

解决方案很少：您可以在每次更新时重新创建整个树。您还可以在对象移动时简单地删除和插入对象。

另一个解决方案（在我的例子中它给了我最好的性能）是只在四叉树中存储静态对象。我将动态对象存储在列表中（在我的游戏中，动态对象比静态对象少得多）。

您还可以阅读其他空间数据结构，例如网格，在单元格之间移动对象要简单得多。