Jump to content
  • Advertisement
Sign in to follow this  
mb108

Quick Quadtree Question(s)

This topic is 3611 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm considering using a quadtree for collision detection and decision-making for boids. I came across a couple of questions: At what point do you split a quad? I've seen two approaches: one is to split on a certain bucket size, another is to split until you reach the smallest quad that will contain the child (or your level limit). Or is this a judgment call based on the application? How do you keep the tree updated for dynamic objects? My current stab at it is to require children to inherit this:
class QuadTreeChild
{
public:
    virtual const std::vector<int>& getAABB() const = 0;
};

The quadtree can then query it's children and adjust/reinsert only as necessary. I'm not thrilled about this solution, but neither am I thrilled about the prospect of rebuilding the tree every frame. Wisdom welcome.

Share this post


Link to post
Share on other sites
Advertisement
Yes, your best bet would be to build the quad-tree based on a minimal number of "scene nodes" that it must contain. Then just set that to a sensible value based on your application needs.

And you definitely don't want to build the quad-tree every frame. So make a flag that your "scene nodes" have that labels them as STATIC or DYNAMIC. Then just build the quad-tree from the nodes that are labeled STATIC.

Or you could come up with another method to distinguish between the two. At any rate, you only want to build a quad-tree from nodes that are STATIC.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!