Jump to content
  • Advertisement
Sign in to follow this  
Scarfy

Quadtrees and Collision Detection

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

I'm trying to use quadtrees for collision detection. Could someone help me with adding objects to Quadtrees? I understand how to create one and have done so, but I'm having problems understanding dealing with the process of adding things too it. Assuming my smallest cell is 64 x 64 and the size of the object I wish to add is 32 x 32 I can happily add it to the cell. However what happens if the object's coordinates make it straddle two or four cells? Do I add it to these cells? What happens if the object is too big to be added to the smallest cell? Do I go to the next cell up..? What happens if the object lies exactly in the center of the quadtree? Does that mean it could potentially collide with everything in the game world..?

Share this post


Link to post
Share on other sites
Advertisement
Adding an item goes recursively: if the item fits in a node, that node checks if it lies completely within one of it's subnodes. If that's the case, it calls that nodes insert function and the process repeats itself. If the item can't be added to a subnode, it's stored in the current node.

So, indeed, an item that's located at the center of the field always gets checked against. Now I've seen a custom type called 'loose quadtree', where every node has an extended bounding box. I haven't experimented with it yet so far but it sounds like an interesting concept if you have to deal with these situations a lot.

Share this post


Link to post
Share on other sites
Lets say that we have a parent node

N

It's subnodes,

12
34

And their subnodes,

xx xx
xx xx

xx xx
xx xx

Where each cluster of x is the subnode of a parent node with the numbers. Now, if the object is in the center of 1234, then it will be tested against the nodes labelled y. (Assuming its not larger than a 3rd level node)

xx xx
xy yx

xy yx
xx xx

Sorry if its a bit crude, but I hope it helps. :)

Share this post


Link to post
Share on other sites
I've experimented with two types of quad trees. In the first scheme, you store each object in the smallest node which entirely contains the object. In the second scheme, you store each object in every leaf node that the object intersects.

It was probably my problem because I did not write my code efficiently, but my implementation spent an inordinate amount of time bookkeeping in the first scheme because I would have to maintain a list of nodes which contained objects so that I could update each object's placement.

The second scheme is working well for me, so far. My process is to reinsert every dynamic object into a static quadtree per frame and perform collision detections during the insertion. I then clear all the nodes where an insertion occured at the end of the frame. The disadvantage is redundancy, so I used a "last checked object" counter to eliminate redundancies.

Share this post


Link to post
Share on other sites
Yeah, there are two basic ways to handle the problem of objects that are too big for a leaf node:

1) put a pointer to the object in all nodes that it touches.

2) put the object in the largest node that completely contains the object.

If you go with #1, you have the already mentioned redundancy issues. If you go with #2, you have to treat every node as a leaf node. I've not benchmarked the two against each other, but i went with #2, personally. It has it's set of issues though: it works good for many small objects (i can track ~500 balls bouncing in a large room and still keep the FPS high), but oblong objects tend to get filed in nodes higher up the tree. Because of that, there tend to be a lot of objects in the higher nodes, or even the root node itself (the entire space) that you have to check against. If you went with #1 and a static tree (as opposed to a dynamic one), you would have a finer grain but would be cleaning up pointers in more nodes.

Quote:
What happens if the object lies exactly in the center of the quadtree? Does that mean it could potentially collide with everything in the game world..?


Yup, if you go with #2. If you went with a static grid though, it would only touch the four squares in the middle. You might consider a grid as opposed to a quadtree.

Share this post


Link to post
Share on other sites
"You might consider a grid as opposed to a quadtree."

Cheers, guys. Sounds like a quadtree could get nasty. I did do a grid once before but I messed it up. However I think I'll be able to do it right this time.

Incase you're wondering what I did wrong,

Imagine my object is, in cells, 4 x 4. I was only adding the object to the cells which its corners lay (if that makes sense).

I'll do a proper fix this time

Thanks!

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!