Quadtrees and Collision Detection
Author
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..?
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.
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.
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. :)
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. :)
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.
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.
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.
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.
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.
Author
"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!
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!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
