fast search technique for collision detection

[r691175002]

You could always use a quadtree to filter the number of full collision tests you need to perform.

[shaon]

quadtree? what is that? I have read somewhere on google about octatrees and the likes but never really saw any article expand on it. Care to be the first one?

For this part I'm assumming people understand what the "sort by reference position" is.

It seems the idea of pre-processing and then only checking with the neighbours which have at max 2*radius might or might not be better than O(nC2). The initial sort algorithm would take O(n log n), assuming the standard sort is the merge sort, plus going through the list and checking the possible collision based on the 2*radius idea. If the distance between the first and the last item is less then 2*radius of the first object then the 2nd part of our algorithm would take us n C 2. Thus the worst case time for this algorithm is O(n log n + n C 2). However if the coordinates were such that the each coordinate neighbor in the sorted list was at max 2*radius distance (example given below):
sorted_coordinates = [ (0,0,2) , (0,0,4), (0,0,6), (0,0,8) ] <== the radius of the object is 1.0000
or even this:
sorted_coordinates = [ (0,0,20000000) , (0,0,400000000), (0,0,6000), (0,0,800000000000000) ] <== the radius of the object is 1.0000

In such a situation the amount of time that would take would be O(n) for the 2nd part of the algorithm since we only have to look one index down from each one.
Thus the best case scenario is O( n log n + n) or O( n[ log + 1] ). The best possible case has a good chance of occuring or atleast the worst case has an extremely high chance of not happening. I'm sure in most games you don't have 1500 objects all in other's radius so this method in practical use, according to the calculations, actually has a good chance of being faster then the standard O(n^2) and O(n C 2).

2nd thing that I found was very awkard about Python:

I did a series of test using a time measuring function from pygame, to see how long it takes to calculate square roots and squares of 1,000,000 numbers. The results were very suprising. math.sqrt(i) took about 532 ms to go complete 1,000,000 square roots. Using (i)^(.5) took about 350 ms, significantly less. I then tried to see how long it takes to do (i)^2 which takes about 1500 ms!! (i)^2.0 takes 350 ms!!!

It seems (i)^(.5) and (i)^(2.0) takes the same time but (i)^(2) and math.sqrt(i) are terribly slow. As to why i to the power of an integer is so slow is weird... you'd think it would actually be faster.

[r691175002]

Wikipedia has a pretty good picture of a quadtree (http://en.wikipedia.org/wiki/Quadtree).
I haven't ever implemented a quadtree before but I would use it to eliminate half the possible collisions in each step, reducing your preprocessing to log N (best case) time. It is basically a binary tree in two spatial dimensions.

I have done a significant amount of coding in flash (both slow and very graphics centric) and generally collision detection isn't a massive problem. If you take reasonable steps to filter out sprites that aren't on the screen etc there shouldn't be too many problems. Big O notation isn't extremely telling either, it is rare to get more than a few thousand objects at the same time, and the time spent on a pixel perfect detection vs a simple bounding box comparison will make a much bigger difference.