问如何在对象在QuadTree中移动之后更新C++？

EN

很难做得比删除和重新插入更好，特别是在您的情况下，因为：

• 删除似乎非常便宜(从相应节点的向量中删除指针)
• 在查找要将对象移动到哪个节点时，需要以与插入时完全相同的方式遍历树，然后：
• 插入很便宜

如果性能确实是一个问题，我会尝试的唯一一件事就是从叶子中插入一些东西。假设您的树非常大，并且对象通常移动到相邻的节点，您可以请求插入父节点，如果需要，它将传递给其父节点。类似于：

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);
}

基本上，从对象来自的叶子走树可能比从根开始的效率更高，因为相邻的节点倾向于共享一个相近的祖先。

在更糟糕的情况下，您将完成两倍的工作，因为您将一直返回到根。在最好的情况下，源和目标共享一个直接父级。

这将完全取决于特定树的布局、它的大小以及一系列其他因素，因此您应该在实现类似的东西之前和之后度量代码的性能。

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

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

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