Original Post
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?
