Sign in to follow this  
a1programmer

Simple Quadtree question

Recommended Posts

Guys, It has been a little while since I've looked into working with a Quadtree. I've gotten so far as creating a simple GUI which will let me click to add more nodes, and the space would divide if necessary, etc (the subdivision lines were also drawn as well). I'm getting back into the details of implementing the data structure, but there have always been a few things that have sort of boggled my mind regarding them. Hopefully you guys can help me out. For this discussion, assume that everything in in 2D, of course, and that objects are bound by a 10 x 10 box, with a (0,0) origin. What happens when an "item" straddles a division line, and effectively exists in two different divisions. For example, suppose we have a limit of 4 items per bucket, where there was one in each quadrant, and we add a new item exactly in the middle, at 0,0. There are two ways that I can think this is approached, but I haven't seen it documented in most tutorials I've seen. 1) When we check to see what items are in quadrant 1,1 (top right (tr) child) , we also check the parent. 2) We actually place a pointer to the newly added item to all four children of the tree. I have also heard of "loose" quad trees, which seem like they could also address this problem, but in that instance, items are added to multiple buckets (I think). [Edited by - a1programmer on March 3, 2010 1:26:27 PM]

Share this post


Link to post
Share on other sites
I solved this by putting the object in all the colliding tree nodes. Otherwise I would need to keep track of whether a parent node contains objects as well.
In the update of the tree I iterate through each node. I check if there are subnodes under the current checked node. If there are, I call their update. If there are none, I execute the collision checks of the current node. That way I always only check the deepest nodes, which is the reason why I never keep objects in parent nodes. But I believe it's up to your own likes or dislikes.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this