How do you update QuadTree after moving an object in C ++?
The easiest way is to delete and insert an object, but there are probably faster methods. (If I overdo it and I should just do it the easy way, let me know)
Here are some notes on my QuadTree
- The objects that move are AABBs and can be larger than the smallest QuadTree node.
- Objects are not deleted when child QuadTrees are created. Which means that the root of the QuadTree has a pointer to every object within the QuadTree.
- Objects are stored as pointers in a vector outside the QuadTree.
So far, every time the object is moved, it calls the Update () function on the root QuadTree. It includes its past bounding box, too, before it moves to options. I'm not sure how to make the function.
Posting all the code to my QuadTree here will make my post quite long, so I created a GitHub repository for readability.
Edit: For anyone looking for an answer, this seems to be updating objects by deleting and deleting them and is pretty efficient judging by the test he did in the comments.
source to share
There are several solutions for this: You can recreate the entire tree for each update. You can also just delete and paste the object as you move it.
Another solution (in my case it gives me better performance) is to store only static objects in a square tree. I kept dynamic objects in the list (my game has a lot less dynamic objects than static ones).
Also you can read about other spatial data structures like grid, it is much easier to move objects between cells.
It will be very difficult to do better than delete and re-insert, especially in your case, since:
- Deleting seems super cheap (remove the pointer from the corresponding vector node)
- When you are looking for which node to move the object to, you need to traverse the tree in the same way as when inserting, after which:
- The insert is pretty cheap
The only thing I'd like to try if performance is really an issue is some kind of leaf insertion. Let's say your tree is quite large and objects usually move to immediately adjacent nodes, you can request an insert in the parent node, which would pass it on to the parents if necessary. 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);
}
In principle, it may be more efficient to walk the tree from the leaf from which the object originates than always starting from the root, since neighboring nodes tend to share a close ancestor.
In the worst case, you end up doing the work twice, because you will go back all the way to the root. At best, both sources and destinations have an immediate parent.
How good the gain will be will depend entirely on the layout of your particular tree, its size, and a host of other factors, so you should measure the performance of your code before and after implementing something like this.
source to share