Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I am developing a quadtree to keep track of moving objects for collision detection. Each object has a bounding shape, let's say they are all circles. (It's a 2D top-down game)

I am unsure whether to store only the position of each object, or the whole bounding shape.

If working with points, insertion and subdivision is easy, because objects will never span multiple nodes. On the other hand, a proximity query for an object may miss collisions, because it won't take the objects' dimensions into account. How to calculate the query region when you only have points?

Collision between objects from neighboring nodes

If working with regions, how to handle an object that spans multiple nodes? Should it be inserted in the nearest parent node that completely contains it, even if this exceeds the node's capacity?

Which node should contain the red object?

Thanks.

share|improve this question
add comment

2 Answers

You must store it in the smallest node that completely contains it- even if this exceeds capacity (use a resizable container).

share|improve this answer
    
Yeah, I can tell, and I did. –  DeadMG Jun 25 '12 at 18:30
add comment

If storing extended objects (regions) in a quadtree, the object should be referenced from all the leaf nodes it touches. I wouldn't try to find the least common ancestor and store it there, because then e.g. a small object that happens to cross a high-level boundary will end up in a very high node, and must be tested against everything else in that large, high-level node when you do collision queries and suchlike.

However, you also have to be careful because large objects could end up being referenced from many nodes, making them expensive to update when they move around, and causing them to be re-checked many times for collisions etc. Depending on your use case it might be worth using some kind of heuristic to store large objects at a higher level in the tree, but this would complicate the algorithms, so I probably woudn't bother unless you establish that it's really a performance problem in your particular case.

Similarly, to query a region, the query should look at all the leaf nodes the queried region touches.

These basically use the same algorithm, which is to start with a region and push it down through the tree to find the leaf nodes it touches. It's a depth-first traversal, but at each node you can prune any children that don't touch the region. You'll need to maintain a stack to keep track of where you are in the traversal.

share|improve this answer
    
Thanks, this makes sense. Sure, processing cross-node objects would be slower than objects that are completely inside a node, but I can't see any way around that. I could increase the node capacity to keep the fragmentation down, but this would increase the number of objects included in collision detection. I'll play around with that to find a good balance. –  alekop Jun 26 '12 at 19:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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