7
\$\begingroup\$

I currently have a QuadTree that contains all my Entities. It works well and I've optimized it pretty decently, but the one thing that hurts is that I am removing from and inserting to it almost every frame. A little code:

    entityMap.remove(it->second, it->second->getLastAABB()); // Removes the entity, getLastAABB is it's last location

    QuadTree* nearest = entityMap.getLowestRoot(moved);
    std::unordered_set<Locatable*> entities = nearest->getAll();
    for (auto itt = entities.begin(); itt != entities.end(); itt++) {
        AABB aabb = (*itt)->getAABB();
        if (aabb.collides(moved)) {
            // COLLISION
        }
    }

    entityMap.insert(it->second);

That code gets run 30 times a second. I use a dirty flag so that only entities that have moved are dealed with. entityMap is the QuadTree itself.

Any advice to decrease insert and remove calls is appreciated.

\$\endgroup\$
2
\$\begingroup\$

Contrary to the common belief you can optimize the quad tree function insert. The common implementation of insert, is to traverse from root to the leafs and find the most fit node, in Game programming gems 2 there is an article that details how you can instantly find that node, if you know the extents of the quatree(can be extended to octree) and the extents of the object bounding box. This way you can instantly determine the level and the node that contains the box. Fortunately you find full explanation in this article.

You can also track the neighbors of each node, hence, when an object moves you know where it's going, this work especially when you have a complete quatree, otherwise I suggest the first approach.

\$\endgroup\$
1
\$\begingroup\$

I'm guessing that insert and remove traverse the quad tree from root to leaf, and that's why you are concerned about its performance?

(By the way, rule of thumb is never perform any optimisations unless you've asked "have I measured a real performance problem" and can answer in the affirmative.)

In games, the vast majority of movement would be continuous, that is, your entities will be moving from one leaf node to a neighbour. You would have a tree with linked leaves, so even if the leaves share a very distant ancestor, you only need to follow the local links instead of all the way up the tree.

\$\endgroup\$
  • \$\begingroup\$ So you suggest a linked list of QuadTree's? \$\endgroup\$ – Tips48 Mar 25 '14 at 16:02
  • \$\begingroup\$ @Tips48 no, I mean a tree where the leaves have links to their neighbours, like a B+ tree \$\endgroup\$ – congusbongus Mar 25 '14 at 23:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.