Kyle Schouviller

A short, post-final follow-up to my previous article about Quadtrees. Includes a nice animation showing how the nodes are structured.

I’ve had some questions about my explanation of Quadtrees, and I must admit, the first time I made one, it was quite an undertaking. However, since I’ve been through 99% of a Computer Science degree, I’ve done a lot of work with data structures. So when I first read about Quadtrees, I noticed that they were very similar to an uneven binary tree. Each node can contain a certain number of items before splitting, items are arranged according to positional value (roughly), and the search time for any item is logarithmic.

The node tree

Before I explain the classes, a picture of how the node tree is constructed in a Quadtree as objects are added and move through the tree (individual frames on click-through):

You can see how the tree evolves as objects are added to the tree, and as an object moves through the tree. You can even see one case where two objects exist in one node since neither can be pushed down.

If you look at the Quadtree I’ve coded, you’ll see that it’s made up of three classes – QuadTree, QuadTreeNode and QuadTreePositionItem. This is pretty standard design for a tree structure (a wrapper class for the tree and then a bunch of nodes) – the only deviation being that I implemented a positional class as well since that data is required for a Quadtree (and since I need to be updated on object movements). Each of these classes contains groups of methods, which I’ll discuss below.

QuadTree

• Constructors – Initializes the head node and stores a little bit of information about the tree.
• Insert – Inserts an item in the head node.
• Query – Labelled “get…” in my methods, these perform queries on the head node and return the result.

QuadTreeNode

• Constructors – Initializes a node.
• Insert – Inserts an item in the node.
• Query – Labelled “get…” in my methods, these query the node.
• Partition – Partitions a node, initializing four child nodes.
• PushItemDown – Pushes an item in the tree down to the proper child node, returning success of the push. Used when item moves.
• PushItemUp – Pushes an item up to the parent node. Used when item goes out of range.
• Remove – Removes an item from the node (cleans up references to items).
• ItemMove / ItemDestroy – Methods called when an item in the node moves or is destroyed.

QuadTreePositionItem
Positional and Size information, all properties.

You might notice that the QuadTree class is really just an interface to the QuadTreeNode class. In fact, if you wanted to, you could just initialize a QuadTreeNode as a head node and perform all of your operations on that. I chose to implement a wrapper class so I could do a few extra things from the top that only the head node needs to do (such as destroy or resize the entire tree), without having all of that extra logic hanging around in child nodes.

Make sure it fits your design

I think the biggest issue in understanding a Quadtree is that there isn’t just a single way to make a Quadtree. There are many variations, and which variation you chose really depends on what your needs are.

If you’re using a Quadtree for a landscape, you’ll probably just be using it for visibility culling. In this case, you won’t care as much about how things move around in the Quadtree, since all of the objects will be set up during initialization. What you’ll want to optimize is searching, so you’re doing it as efficiently as possible every frame.

If you have a lot of balls moving around in a Quadtree, you’re probably going to have a lot of restructuring operations in your Quadtree as balls simultaneously occupy the same spaces. In this case, you might benefit from pre-partioning the Quadtree so it’s all ready to go when you start. You might also benefit from enforcing a maximum object depth, so objects pile up in a node once they reach that depth (so your Quadtree doesn’t grow huge). You could also push items into the top node, and only push them down if the node fills up (as opposed to my tree design, where I push them down automatically).

If you only have a single object moving around and everything else is static, you could do fine with my design. You may also want to keep items at the top level until the level fills up, so you can move items around faster (less pushes means less processing and function jumps).

You might notice that after I query a node for objects I make sure that object is intersecting the query box – this isn’t standard for a Quadtree, but in my case it was more efficient, since I could eliminate more objects with a simple box check and then be sure that all objects returned are at least bounding-box colliding with the query rectangle.

Overall, just make sure that the design fits your needs. If it doesn’t, look for ways you could modify it to fit into your design.

This entry was posted on Thursday, May 10th, 2007 at 11:00 am and is filed under Game Programming, XNA. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.