I’ve just developed a new algorithm to do collision detection. I’ve tested it and it works as it should.
With 100 sprites to do collision detection on it takes just over 0.0003 seconds.
With 1000 sprites to do collision detection on it takes just over 0.03 seconds (while the Big-O(n^2) takes well over 20 seconds).
With 10000 (ten thousand yes) it takes 4.6 seconds, while the Big-O(n^2) one takes about, well, I gave up waiting :]
Are there any better ones out there?
Normally just spatially partioning them is enough to cut down the actual number of comparisons going on. In 2D, sort into grid cells and only compare those sprites in the same cell - vary the cell size dependent on the size of the community being collided and their likely proximity to each other.
In your tests - how many collisions are being detected? In the 10000 test… whats the speed if every sprite is colliding with every other sprite?
Kev
The thing is, if you have 3 sprites, and they all intersect each other, then only 2 of the sprites will actually collide since they destroy each other and the other one is left alive. This is logical since, let’s say a bullet hits 2 units, then it destroys the first unit it hits and not the 2nd unit.
Below: 4999 collisions detected, since when 2 sprites collide that’s ONE collision. When 4999*2 = 9998, which means there are 2 sprites left that don’t collide :] good luck finding those.
Thats pretty specific to a game genre - and a particular game - my unit might have health, at that point both bullets count, or I might be making things bounce off each other, in which case I’m interested in all the collisions at a given time.
Not to say it doesn’t look pretty! 
Kev
It’s just a matter of how you implement the algorithm. In my demo I simply kill 2 colliding rectangles, I might decide not to kill both, but only one and withdraw energy from one. (like destroy the bullet and subtract health from unit)
Download the JAR file containing the algorithm and some demos, and tell me your opinion: (ignore the uglyness of the code
Had a quick look, nothing wrong with the “code ugliness” - readable and clean
Your algorithm seems to be your using the collision rectangles x and y coordinates added together as a heuristic to group which sprites need to be checked against each other. Could be just my very quick read failing me - but won’t this mean you’d compare for instance a sprite at (50,1) to a sprite at (1,50)?
Presumably this would have problems with different size objects also in that your heuristic only considers their position and not their size.
As I said, I’ve only got a few minutes between work…
Kev
This is true.
Sprites at (50,1) and (1,50) (group 51) would need to be checked for collision. But the tests I’ve done don’t indicate that that’s much of an overhead.
If those sprites are, let’s say 10x10 pixels in dimension, then groups 41 through 61 need to be checked for collision.
If you add another sprite that is 20x20 in dimension, then you would need to expand the range of what groups to perform collision detection on, from 41-61 to 31-71. It’s better if the sprites are of some similar dimension, 10x10, 20x20 even 100x100 is fine, but as soon as you have a single sprite that is 1000x1000 then the point of the algorithm fades out. So, units, bullets etc. something that is a lot of and relatively similar dimension is very good.
You could look at this as some sort of groupping, but still with a very limited code to implement and also VERY fast, at least the fastest I’ve seen as of yet.
Your first step is to sort, you might find its actually faster to just sort into buckets based on imposing a grid on the play area. At that point you could just compare the sprites in the same grid cell - this would be just as tunable, would prevent 50,1 - 1,50 checks and is probably faster than sorting the whole list based on compareTo, would be a consistent O(n) rather than potentially much worse using standard sorting.
But then really, like most of these things, it ends up being application specific.
Kev
True.
And thanks for discussing this with me. I see now how I can change this to become O(n)
No worries, I’ve enjoyed thinking about it Been a while since I engaged the brain
Kev