Jump to content
  • Advertisement
Sign in to follow this  
helloworld922

Quad tree question

This topic is 2895 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

Hi, I was thinking of using a quad-tree to accelerate 2D collision detection so I don't have to check every object against another object, however I've run into an issue with objects at the boundaries of nodes.

So, for example say there's a quad node A bound by the square (0,0) and (16,16), and it's subdivided once into 4 equal square child nodes. Now, if I have an object who's center is located at say (7,2), but has a bounding box of (3,3) (width and height of the box), it would partially over-lap between the child nodes 1 and 2.

I've thought of a two main possible solutions, but there are irreconcilable faults with the following approaches that I can't seem to work past.

Method 1: All objects on node boundaries are added to the parent quad node. However, it is very likely in my game to have many items overlapping the boundaries, so it could quickly become that most objects reside in the top quad node, resulting in very little speedup from the quad tree.

Method 2a: Don't subdivide a node until it contains a certain number of objects (say, 10). Only root nodes contain the object references. This runs into the problem with an object having to be classified as in one node or another, even if it's partially in another node, resulting in a missed collision. This is unacceptable since the game I am writing will require exact collision detection detection (or at least, close to exact).

Method 2b: A variant of method 2a in that the object gets added to all nodes it's in. However, this method would require a considerably larger amount of memory to allow the nodes to keep track of which nodes they are in (especially large objects). Keeping the quad-tree up to date with moving objects would also be a hassle.

Is a quad-tree a good solution for 2d collision detection? If so, how do I solve the problems with any of the methods above, or is there another method I'm missing? If not, what data structure would you recommend using with 2d collision detection?

Share this post


Link to post
Share on other sites
Advertisement
I think you are on the right track with using a quadtree. From what I've heard, a good way to avoid this problem is to use a loose quadtree. Instead of inserting items by their bounding box, you insert them merely by their center. However you restrict the depth of the objects:
An object is only inserted into a deeper node if the object fits into the loose rectangle of the node (that is, a rectangle with twice the length & height of the "actual" rectangle of that node). This way your objects won't stay in the root node when they overlap boundaries (only when they are equally big as the root node, which should never be the case).
The downside of this loose quadtree is that you need to change the culling algorithm. You will need to do a collision detection for all objects that intersect the loose rectangle (and not the "actual" one).

I haven't implemented a loose quadtree yet, only a "classic" one. However there is a paper that explains the details: click.

I hope this helps :)

Share this post


Link to post
Share on other sites
Heya, yes quad trees are good for 2d (:

I personally would do it (and DO do it in my own game) where if it doesnt fit in the child node, it goes into the parent node (method 1)

You are right that doing so makes an object go "shallower" in the tree, and you get most benefit when you have your objects in the deepest parts of the tree.

So, it would make the perf win not quite as big, but it should still be a huge win over not doing any kind of spatial storage of your objects.

There is also something called a "loose quad tree" where basically the childmost nodes are larger than they need to be to account for larger objects to be stored in child nodes (the children then overlap)

of course special logic is needed to test against siblings so it complicates things a little.

Another good thing to use for 2d games is just a straight up grid, and only testing against things in the grid cell (and in neighboring cells when appropriate).

Yet another thing to do is called dimensional reduction.

What you do for this, is make a list of all your objects, sorted by their X position (alternatively, you could have their X begin and X end in the list too)

So basically you can quickly look in this list (binary search) to do an X axis test, and then you can just do a "brute force" (over a much smaller set of objects) for the Y axis test.

(:

Share this post


Link to post
Share on other sites
hmm, I guess you don't get anything for free :P

I'll take a look at the loose quad-trees, they sound pretty promising, though it sounds like it may be easier to resort to a grid.

Thanks for the quick answers!

Share this post


Link to post
Share on other sites
Just FYI, I eventually decided to use method 2b. Adding items took a little bit longer (for my uses, not a significant amount of time), but the memory usage was fairly easy to keep down using a hash map and I could easily have the quad tree only recurse deeper when needed (say, when a node reaches a certain capacity of objects it has). I also managed to keep the number of indices to update down by only updating the indices of nodes that need to be subdivided.

The reason I shy'd away from method 1 was because it was quite likely that an object would have to cross at least one if not multiple boundaries, causing it to be added to a higher level node. This means any items in sub-nodes would have to check if they collided with that item, and that item will have to check a greater set of items in all the sub nodes. For a "one-step up" boundary (the object only gets added one level up than the lowest leaf node), this problem was very minimal, but I found that since the main node containing everything had rather large and inconveniently placed boundaries right across the middles, a lot of objects would get added to the very top node, causing a major slow down.

I decided method 2a simply just unacceptable for my application because there would be large objects and small objects, and I didn't want the small objects to be able to move without a valid collision on the large object.

I also ruled out the loose quad trees because of the variations in size would have drastically reduced the efficiency of this structure and I just couldn't justify the complexity of implementing one.

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!