在 C++ 中移动对象后，如何更新 QuadTree? [英] How do you update a QuadTree after an object has moved in C++?

问题描述

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

The easiest method is removing and inserting the object, but there are probably faster methods. (If I'm overthinking this and I should just do it the simple way, let me know)

这是关于我的四叉树的一些注意事项

Here are some notes about my QuadTree

• 正在移动的物体是 AABB，可能比最小的四叉树节点.
• 创建子四叉树时不会移除对象.那意味着根四叉树有一个指向内部每个对象的指针四叉树.
• 对象作为指针存储在四叉树外部的向量中.

到目前为止，每次对象移动时，它都会调用根四叉树上的一个名为 Update() 的函数.它在参数中移动之前包括自身及其过去的边界框.我不知道如何制作这个功能.

So far, each time an object moves it calls a function called Update() on the root QuadTree. It includes itself and its past bounding box before it moved in the parameters. I'm not sure how to make the function though.

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

Posting the entire code to my QuadTree here would make my post quite long, so I've created a GitHub repository for easier reading.

对于任何寻找答案的人this 似乎通过删除和删除对象来更新对象，并且很漂亮从他在评论中所做的测试来看，效率很高.

For anyone looking for an answer this seems to update objects by removing and deleting them and is pretty efficient judging by the test he did in the comments.

推荐答案

确实很难比删除和重新插入做得更好，尤其是在您的情况下，因为:

It'll be really hard to do better than remove and re-insert, especially in your case, since:

• 删除看起来超级便宜(从相应节点的向量中删除指针)
• 在寻找要将对象移动到哪个节点时，您需要以与插入时完全相同的方式遍历树，然后:
• 插入非常便宜

如果性能真的是一个问题，我唯一会尝试的是从叶子中进行某种插入.假设您的树非常大并且对象通常移动到紧邻的节点，您可以请求插入父节点，如果需要，它将传递给它的父节点.类似的东西:

The only thing I would try if performance is really an issue is some sort of insertion from the leaves. Let's say your tree is pretty large and that objects usually move to immediately adjacent nodes, you could request insertion in the parent node, which would pass it to its parent if needed. Something like:

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

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

Basically, it might be more efficient to walk the tree from the leaf the object is coming from than always starting from the root since adjacent nodes tend to share a close ancestor.

在更糟糕的情况下，您最终会做两倍的工作，因为您会一直返回到根目录.在最好的情况下，源和目标共享一个直接父级.

In the worse case, you'll end up doing twice the work because you'll go back all the way to the root. In the best case, both source and destination share an immediate parent.

这将带来多大的收益完全取决于您的特定树的布局、它的大小以及一系列其他因素，因此您应该在实施此类之前和之后衡量代码的性能.

How good a gain this would be entirely depends on the layout of your particular tree, its size, and a bunch of other factors so you should measure the performance of your code before and after implementing something like this.

这篇关于在 C++ 中移动对象后，如何更新 QuadTree?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！