11
\$\begingroup\$

I've been told that a quad tree is the ideal data structure for my game, but I'm having trouble understanding how exactly shapes work within quad trees.

I'm doing this in JavaScript, but I think these questions could apply to quad trees in any language.

I think I mostly understand how basic (x,y) points and point insertion works in quad trees, and that I could do it on paper.

Here is a JSfiddle of my experimenting with points.

quad tree points

Aside from one case, my tests with points are working as expected.

But my confusion starts when shapes like rectangles are involved. When you are retrieving from a quad tree with shapes, does it check each point of the shape, and what nodes they fall into? And how do shape insertions even work, when it accepts (x,y,width,height) parameters for each shape? Does it use the width/height from the starting point to calculate other corner points, which are then dispensed into appropriate nodes? If an inserted shape spans into four nodes, is that shape's data saved into all four nodes?

And when a retrieval method accepts a shape as the parameter(x,y,width,height), what is actually going on? Is it first seeing what nodes the shape would span to if it were to be inserted, and then retrieve all the objects of those nodes?

I have a JSfiddle working with shapes, but I am utterly confused on the results of my testing. I am getting duplicate objects being returned!

quad tree shapes

For example, the red square is a drawn equivalent of the parameters I am entering into my retrieval method. I would think that since this red square spans all four nodes, it should return every object in the quad tree! But it doesn't, and I am having trouble rationalizing what it does return. I have a number of other tests that are currently commented out, but you can un-comment and run them to see more confusing results!

As say, if I want to return all points in a quad tree, how would I do that? A retrieve method using a shape the entire size of the bounds? In example, retrieve(0, 0, canvas.width, canvas.height)?

The JavaScript QuadTree library I am using has been referred to by various other sources, so I assume the actual implementation is correct and reputable.

I think a lot of my confusion may stem from a misunderstanding of quad tree terminology. Like, why do they say bounds instead of dimensions, when a "point" has width/height parameters as well? Is it a matter of convention/short-hand, or are they completely different concepts?

Thanks for your time!

\$\endgroup\$
  • \$\begingroup\$ They're stored in the quad tree as normal, by their position. Typically those are at the center, but can be in the corner as you've defined. Your question may be a duplicate of this one: QuadTree: store only points, or regions? \$\endgroup\$ – MichaelHouse Oct 14 '13 at 20:56
  • \$\begingroup\$ I've read that question, but I still don't completely understand the answers :(. "You must store it in the smallest node that completely contains it- even if this exceeds capacity (use a resizable container)." - When he says the smallest node that COMPLETELY contains it, if the object is very large, wouldn't that node often be a non-leaf node? As in a higher-up node that consists of only other nodes? That doesn't seem right to me, since that would mean the containing node would have 1 leaf and the 4 smaller nodes within it. \$\endgroup\$ – user2736286 Oct 14 '13 at 21:03
  • 1
    \$\begingroup\$ @user2736286 If you look at the code for the quadtree lib (it's not very long), you can see it does store rectangles in higher-level nodes to keep them from straddling node borders. See the references to the _stuckChildren field in the code. You can also see this in the "retrieving items with bounds" sample - it always highlights red the nodes that straddle the borders of the nodes you clicked in, all the way up to the root node. \$\endgroup\$ – Nathan Reed Oct 14 '13 at 21:10
  • \$\begingroup\$ @user2736286 Also, the quadtree lib appears to have a bug in retrieving items with bounds - if you give it a query rect that straddles some node borders, it doesn't return all the rects in nodes the query touches. You can see this easily in the "retrieving items with bounds" as well, by clicking near node borders. \$\endgroup\$ – Nathan Reed Oct 14 '13 at 21:14
  • \$\begingroup\$ @NathanReed Earlier I tried to comprehend the code, but I am not skilled enough to understand it without a conceptual foundation. Thanks to John McDonald's pseudo-code I now understand how rectangles are inserted into nodes, but I think I am still unclear on how retrieval works. As for the "retrieving items with bounds" - I am flat out confused by the example. Like, when I click a rect that cleanly fits into one of the smallest nodes, why are all these other rects outside that node highlighted as well? \$\endgroup\$ – user2736286 Oct 14 '13 at 21:33
11
\$\begingroup\$

Quadtrees typically store and retrieve rectangles. A point is a specific case where width and height are zero. The following logic is used to find home for new rectangles in the tree, starting with the root node:

void Store(Rectangle rect)
{
    if(I have children nodes)
    {
        bool storedInChild = false;
        foreach(Node childNode in nodes)
        {
            if(this rectangle fits entirely inside the childNode bounds)
            {
                childNode.Store(rect);   // Go deeper into the tree
                storedInChild = true;
                break;
            }
        }
        if(not storedInChild)
        {
            Add this rectangle to the current node
        }
    }
    else
    {
        Add this rectangle to the current node
    }
}

Note that rectangles can be stored at any depth, it does not have to be a leaf quad. If the rectangle straddles the boundary right at the root level, the root quad will store the rectangle.

For example, the red square is a drawn equivalent of the parameters I am entering into my retrieval method. I would think that since this red square spans all four nodes, it should return every object in the quad tree! But it doesn't, and I am having trouble rationalizing what it does return.

When querying the quadtree, it will only return rectangles that are contained by the query. In your example, you force each of the 4 child quads to be looked at in further detail because the red query rectangle intersects each child quad. Since the children have no further children, each of the rectangles in these child quads will be compared with the red rectangle. Since none of the rectangles in the tree collide with the red query rectangle, nothing should be returned.

You really start to see benefits of quadtrees when you have lots of objects, and lots of space for the objects to exist in compared with the query area(s). In these cases, a small query area can quickly eliminate vast chunks of the quad tree from consideration. Only quads that intersect with the query rectangle will ever be looked at in more detail.

EDIT

Retrieval is usually done like the following:

List<Rectangle> Query(Rectangle queryRect)
{
    List<Rectangle> results;
    foreach(Node childNode in children)
    {
        if(queryRect intersects with childNode bounds)
        {
            results += childNode.Query(queryRect);   // Dig deeper into the tree
        }
    }

    foreach(Rectangle I have stored in this quad)
    {
        if(queryRect intersects with rect)  // Your library doesn't do this
        {
            results += rect;
        }
    }

    return results;
}

In your library however, it doesn't seem to check if if the rectangles it's returning intersect with the query, so you'll need to add that yourself.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ After looking at your library in more detail, your library is returning a list of all possible collision candidates for the query rectangle you specify. It appears that it is your job to compare your query rectangle to each candidate to see if there's an actual collision. Most libraries do that last step for you and just return the actual collisions with the query area. So, all you need to do is add some logic in your retrieve method to prune the list. You can see what it's doing a bit more clearly here: mikechambers.com/html5/javascript/QuadTree/examples/… \$\endgroup\$ – John McDonald Oct 14 '13 at 21:29
  • 1
    \$\begingroup\$ @user2736286 In case you hadn't picked up on it, it is important to take note of the recursion in the Query and Store functions that JohnMcDonald wrote. It's not going to make much sense if you don't get that part. For both, each recursion goes deeper into the tree, ie out on branches and finally into leaves. \$\endgroup\$ – TASagent Oct 14 '13 at 21:56
  • \$\begingroup\$ Thanks John, your pseudo-code is very helpful. When you say "if(queryRect intersects with childNode bounds)", does that basically mean if the queryRect is contained within the bounds - partially or fully? Just want to be 100% clear. Also, in the "retrieve item by bounds" example being discussed, I have an image of the result of my click. Pic The blue dot is where I clicked. So why aren't only the two rectanges inside that node hightlighted? Why are rectangles far away from it highlighted as well? I think that is what is really confusing me. \$\endgroup\$ – user2736286 Oct 14 '13 at 21:58
  • \$\begingroup\$ Part or full. If the two touch, or either is completely contained by the other. You want to read the wiki on Quadtrees, but I have taken your pic, and colour coded it to represent the different child boundaries. All of the blue rectangles are intersecting with the boundaries of the first child quads, then magenta being one layer deeper, and green one layer deeper still. Red rectangles intersect with the clicked quad. You library returns all rects on child boundaries plus all contained in the final child quad (red): i.imgur.com/InB8KBj.png \$\endgroup\$ – John McDonald Oct 14 '13 at 22:14
  • \$\begingroup\$ Ok, so I've tried my best to go over the lib's source code and I finally understand the behavior of stuckChildren, and that all those extra rect's in my pic are simply the stuckChildren. Originally I thought that any rects spanning multiple nodes would just have its data duplicated and inserted in each smaller node. Now I realize that stuckChildren does not get inserted in nodes it spans, but simply stays in the one node containing it, which is why I have to also check all parent nodes, and not just the smallest node containing my query rect. Thanks for pic; it makes a lot more sense now :) \$\endgroup\$ – user2736286 Oct 15 '13 at 22:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.