Jump to content
  • Advertisement
Sign in to follow this  
lucky6969b

What is the best way to update a Quadtree/Octree?

This topic is 797 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 want to just update the area which is going to be affected.
Say an agent is moving into an area, where he leaves, may be merged,
and where he lands on, will be subdivided.
The algorithm I am coming up now needs to update the tile id very quickly and
re-sort all the id all over again which is very time consuming.
Are there any good examples on how to quickly update a quadtree?
Thanks
Jack

Edited by lucky6969b

Share this post


Link to post
Share on other sites
Advertisement
You could use a 1D or 2D hash for the lowest level of detail and index a cache in which you've allocated you QT/OT nodes directly.

Not only does maintaining a semi-duplicate linear data structure (for each level) help with simple updates, it is much more ergonomic in terms of memory management and most updates/neighbor lookups are bound to be MUCH more cache friendly.

Personally I feel like linear grids are almost always the way to go. If you do need coarse control, it makes more sense to mentally adjust how you think about a quadtree and treat it as a set of tiered linear arrays instead.

Share this post


Link to post
Share on other sites

I believe rebuilding the entire Octree could prove faster then splitting/merging it's child nodes.

void MyEngine::Update()
{
    m_WorldOSP->Clear();
    for (int e = 0; e < getSceneEntityCount(); e ++) {
        setEntityOctant(e, m_WorldOSP->Insert(getEntityBBox(e)));
    }
}

Share this post


Link to post
Share on other sites

This guy is doing it well..... pity is didn't know how he did it...

 

To Christian:

I also tried to refresh the whole quadtree in realtime,

But as you know :), it is just too heavy operation...

The whole application grind to a halt.

Edited by lucky6969b

Share this post


Link to post
Share on other sites

Assuming each child has a reference to its parent, and each quad has a count of how many items it contains (cached for its children):

 

When an item leaves a quad subtract one from the quad's count, and request the quad's parent to check if it should merge (if the sum of all children's count is less than threshold). If it did merge the merged quad should again request its parent to check for merge, etc.

 

Likewise when en item enters a quad you just check if the node should split, if it did split, you check the new quad (the one you entered, not the other three) if it also needs to split, etc.

 

If moving one node from one quad to the other you should do the enter first, to avoid current quad and new quad being first merged and then split, if they have the same parent.

 

This is assuming each quad has a reference to its parent and all its children, not using some array to store quads in. If you do want to store quads in an array, to prevent garbage collection, you could have a stack with unused indexes in the array, so you don't ever need to move items in the array. If your children in the quadtree takes too long to sort through when merging or splitting a quad, you should use a smaller threshold.

Share this post


Link to post
Share on other sites

One more tiny question to ask,
I am wondering if say a tractor of a truck enters a warehouse,
and the floor of the tractor becomes part of the world,
the quad tree is to be extended, I don't really want to extrude
that part of the quad tree in advance and pretend it was there before the truck enters,
I want the new area to be stitched to the original quad tree.
The problem being is where should I seed the pivot point
of the new quads?

BTW, I decided not to store the ids in an array, I store them in a hash map
Anyways, the ids can be reused when required...
Thanks
Jack

Edited by lucky6969b

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!