Ok, so I'm trying to figure out one last problem before I implement a spacial partitioning quadtree (used primarily for visibility determination and collision detection). My problem comes with dynamic objects that can change what sector of the quadtree they are in during any given frame. Lets say my world is divided up like this, and the red circle is some sort of AI opponent: And here is what the corresponding quadtree would look like: You can see that the AI opponent is currently in node 2, but is moving east and will shortly transition to node 5. What is the best way to facilitate such transitions between nodes in a quadtree? I want to keep dynamic objects classified in the appropriate sections of the quadtree at all times. Atleast one assumption can be made: all leaf nodes will be on the same "level" in the tree. And, the way I'm thinking of implementing it, a leaf will be able to hold multiple entities inside of it -- leaves are purely chunks of the world. Should I figure out what new sector bounding box the AI opponent resides in through a top-down search through the tree, locate the new appropriate leaf, and then place it there? Or should I have some way of iterating across all of the leaves from the current one, so that I don't have to do a top-down traversal of the tree? Or should all nodes have pointers to their neighbors to make this even faster? Or something else? It seems like a top down traversal would be best, as this is what quadtrees are made for! But am I missing something? What if I have hundreds of entities transitioning every frame? ( not likely! ) How has everyone else implemented the handling of dynamic entities in their quadtree partitioning schemes? ANY input will be helpful and is appreciated!! :)

I'm no expert or anything but here it goes-

The red dot is actually just bairly on the root nodes vertical divider. Since it's on the line it really belongs to two squares, not just square #2. So the dot would at that instant belong to the root node, not node #2.

Only if an object is contained *entierly* in a square do you traverse to the child nodes. You do this until you reach the last node, or it intersects a divider line.

So if the dot was on the line between square #2 and #4, the dot would belong to the parent node of leaves 1,2,3,4 (the left child of the root node). If the dot was entierly in square #4, it would belong to square #4.

So for placing the object on the right node, you simply traverse the quadtree until an intersections occues. If one occures it belongs to that node. If no intersections occure when it belongs to the the last node you're in. If you did this every frame it would automatically handle transitioning from node 2-5.

Hope that helps

Ah makes perfect sense :) I didn't think of the possibility of it belonging to a higher level node. Thanks for the good explanation!

I'm no expert on this subject, but as I see it there's two methods to recalculate the node an object (AI or not) is in:

1) Top down.
Obviously, the object must exist in the world for us to enter it into the tree. Calculate the node as per normal.

2) Bottom up then top down.
This (hopes to) take advantage of the fact that objects have some locality - they won't warp from one side of the screen to the other every frame.

Basically, you start with the node the object was in previously. If the object is not within that node, you navigate to that node's parent node. You repeat this process ("while (!that_node->covers( object.coordinates )) that_node = that_node->parent;") until you reach a node covering that area. You then transverse back down as per the top down approach.

In the worst case scenario, this method will take twice as long as the top down approach, to navigate all the way to the top node then back down. Best case scenario it will preform at a constant speed, e.g. when transfering to a neighboring node which shares the immediate parent of "that_node".

No problem!