Archived

This topic is now archived and is closed to further replies.

Quadtree for 2d collision detection

This topic is 5021 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 have decided to use a quadtree collision system for my 2d game, but I can''t exactly figure out the best way to go about implementing this. I was planning on splitting my sprite up into nodes recursively in a quadtree, where if there were visible pixels in the node, the node''s nodes would be included in the next check, and if empty, discarded. Then, when checking for collision between 2 sprites, after doing the usual spacial partition checking and AABB overlap checking, I''d check each of the nodes in turn for overlap with something in the other sprite. This is the part I''m stuck at, what should I be checking each of the nodes against? Should it be the other nodes in the same level in the other sprite, or should it be the whole AABB, or something else? And for when I am at a satisfactory level of detail, how would I detect a collision? Would I check to see if the majority of the node(or leaf as it would be called) was filled with visible pixels? Oh yeah, I also have to be able to scale and rotate the quadtree. Thanks in advance for the advice.

Share this post


Link to post
Share on other sites
First: you can put all collision data in the quad tree. Just keep splitting until you have sufficient resolution, and then store whether the node is full or empty in the tree.

Second: you don''t scale the quad tree, you scale and rotate whatever you put INTO the quad tree (i e, the coordinates), before you put them in. If the "tree object" is scaled by 2 and rotated +30 degrees, you should scale the input data by 0.5 and rotate it by -30, before passing to the tree. Trying to make scale/rotate work well while traversing the tree is an excercise in frustration.

Third: how big are your sprites? Have you really determined that sprite collision is a noticeable performance problem for you? Have you run a profiler? Or do you know from experience that it''s really slow on your current hardware?

On a PC, colliding two 256x256 one-bit sprites against each other is Pretty Darn Quick; you can do tens of thousands of these per second just using overlap test and brute force. Don''t write complicated code if you don''t have to.

Share this post


Link to post
Share on other sites
Thanks for your reply.

quote:

On a PC, colliding two 256x256 one-bit sprites against each other is Pretty Darn Quick; you can do tens of thousands of these per second just using overlap test and brute force. Don''t write complicated code if you don''t have to.



The problem is that I need to scale and rotate these in real time, therefore the pixels actually get larger than just pixels (and therefore equality checks) and I have to do rectangle intersection tests instead, which are considerably more computationally expensive.

quote:

you don''t scale the quad tree, you scale and rotate whatever you put INTO the quad tree (i e, the coordinates), before you put them in.



Does this mean that I''ll need to re-compute which coords go in each quadtree for every frame that i rotate (planning on rotating/scaling every frame if needed)? I was hoping I could rotate/scale the quadtree instead so that the data could stay inside it. Sounds like your solution is a lot simpler though.

I plan on making this an engine, therefore it should be flexible, eg I can use any size of sprite.

How would I actually go about detecting a collision? Would I just check each of the "full" nodes in each sprite''s quadtree against each other (ie, the 4 top level nodes that are full in sprite A will get tested against the 4 top level full nodes of sprite B, and if they intersect, they are passed to the next iteration of collision checking, if not, discarded)?

Share this post


Link to post
Share on other sites