Sign in to follow this  

How is a quadtree any better for 2D collision detection than an array?

This topic is 4111 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 have written a collision detection engine using the SAT. It have added all of the obvious early escape checks to cut down on calculations (are their centres closer than the sums of their radii, are they traveling towards each other, etc). However, it still has a processing time of x^n, because every object is checked against every other object. To cut down the number of checks I have to make, I will either use a quadtree or a grid. If I was using a grid, then I would loop through my list of objects and assign each a location on the grid based on where it's centre was (eg, if it's coordinates were 10.1, 5.6, then I would allocate it to cell [10][5]), and then test for collisions against objects in the same cell as it and the 8 cells surrounding it. This method sounds very easy to impliment. However, everywhere I look for collision optimisations seems to champion quadtrees as a way to quickly chop out all the objects that the object of interest can't be intersecting with. I read an excellent article on gamedev.net explaining the basic theory of quadtrees. Alhtough I understand the basic theory, it seems much more difficult to impliment, I don't know how exactly I would apply it to collision detection, I would have to make a new data structure, and I can't find any good tutorials on quadtree based collision detection. So, would using quadtrees give me a significant enough performance boost to warrant the extra effort? Or would the grid method be more effort than it appears at first glance, or have other pitfalls that I haven't seen? What would be the advantages of each? And, lastly, does anyone know where I could find tutorials on how to impliment either method?

Share this post


Link to post
Share on other sites
Quote:
Original post by CIJolly
However, it still has a processing time of x^n, because every object is checked against every other object.


That's exactly how a quadtree is better. You won't be checking objects against those that are not in the same area.

Share this post


Link to post
Share on other sites
Quote:
Original post by owl
That's exactly how a quadtree is better. You won't be checking objects against those that are not in the same area.


You answered the question "Why is a quadtree better than no space partitioning at all". The question asked was "Why is a quadtree better than another space partitioning method (a grid)".

In practice, both grids and quadtrees work well and get reasonable performance. Grids work best when the vast majority objects fit within a grid square, and the distribution is fairly homogenous. Conversely, quadtrees work when the objects have variable sizes or are clustered in small areas.

Share this post


Link to post
Share on other sites
Quote:
Original post by owl
Quote:
Original post by CIJolly
However, it still has a processing time of x^n, because every object is checked against every other object.


That's exactly how a quadtree is better. You won't be checking objects against those that are not in the same area.


his grid system covered that.

i havent done a collision system myself but i think a quad tree will work for any size object.
You may have some massive objects and some small objects which need to checked, i think a static grid will have trouble with this.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
Quote:
Original post by owl
That's exactly how a quadtree is better. You won't be checking objects against those that are not in the same area.


You answered the question "Why is a quadtree better than no space partitioning at all". The question asked was "Why is a quadtree better than another space partitioning method (a grid)".


Is true. Besides, I also missed he is talking about 2D. I belive a grid should be enough. Sorrys!

Share this post


Link to post
Share on other sites
Quote:
Original post by CIJollySo, would using quadtrees give me a significant enough performance boost to warrant the extra effort?
Unlikely, but it really depends on the types of objects you have (are they all the same size vs. largely differing sizes) and what type of collision queries you hope to perform on them.

Due to its inherent simplicity, a (uniform) grid tends to have much better cache performance than tree-based structures. The uniform grid breaks down a bit when you have objects of greatly varying sizes, but in those cases you can use a hierarchical grid to address that problem. A hierarchical grid typically always outperforms a quadtree/octree for collision detection purposes.

Share this post


Link to post
Share on other sites

This topic is 4111 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this