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

This topic is 4412 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites
Quote:
 Original post by CIJollyHowever, 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 on other sites
Quote:
 Original post by owlThat'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 on other sites
Quote:
Original post by owl
Quote:
 Original post by CIJollyHowever, 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 on other sites
Quote:
Original post by ToohrVyk
Quote:
 Original post by owlThat'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 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.

1. 1
2. 2
3. 3
Rutin
17
4. 4
5. 5

• 14
• 9
• 10
• 12
• 17
• ### Forum Statistics

• Total Topics
632906
• Total Posts
3009155
• ### Who's Online (See full list)

There are no registered users currently online

×