Well at our scene have a number of objects present. They are all moving around. Obviously we need to check for intersection. But currently we have to check for each object versus each object. This is not a good solution.
Is there an efficient datastrukture for this?. Can we store the objects in a way so we quickly can determine wich objects to checj for intersection and wich we shouldent. Oct-trees?, for instance?
What are you doing in your project?
When dealing object collisions you’ve got a triangular number; for n objects you have to deal with n^2 - ((n-1)^2)/2 collisions. This is an O(n^2) algorithm then, that being the largest term. As n grows, it gets slower and slower for each n.
To divide and conquer this using a binary space partition you will, for every reduction in n by half, reduce the algorithmic time of collision by 4. However - you then have to add the cost of classifying each object into its appropriate space.
Cas 
The objetcs are moving i (random) directions. So a maintenance of a BSP tree would have to happen each tick. That takes O(n^2) as well and would probably leave use where we started (probably even more work)
Idea
We want to know if ONE objects collides wth others(the sip the player moves around in). Maybe Range trees combined with a sort of bounding box would do it?
A quad or oct tree tends to work pretty well for moving objects I’ve found, perhaps a loose one if things are moving quite rapidly.
Before you go all wandering off and creating some wacky and clever algorithm just exactly how many objects are there anyway and what’s your time budget to do a collision test? If we’re talking only 100 objects then that’s only 5,000 collision tests per frame - or about 5,000,000 clock cycles at a guess - less than 1% of your typical CPU horsepower. At 1,000 objects it’s more like 500m cycles which is likely to end up being 100% CPU bound on slower chips. But then - how often do you need to check for collisions? Can it be done every other frame?
(I wonder how many cycles a simple sphere-radius collision actually costs?)
If you’re dealing with over 200 objects per frame I’d at least classify them into an octree first. The octree depth is the important number to consider here. Maybe use a depth equal to the number of 0’s (100-999 objects, use depth=2, 1000-9999, use depth=3, etc). Worth a shot.
Cas
Yes, Cosmic Trip checks collision for every object against every object in every frame and time spent there is minimal.
I usually implement things the unclever way and only try to think of clever things when they turn out to be too slow
It all depends on your needs I guess, as Cas pointed out.
[quote](I wonder how many cycles a simple sphere-radius collision actually costs?)
[/quote]
float dx = this.center.x - circle.getX();
float dy = this.center.y - circle.getY();
float separationSquared = dx*dx + dy*dy;
if (separationSquared < radius*radius)
return true;
else
return false;
Hmm…
4 memory reads
7(?) register stores
3 mults
2 subtract
1 add
1 compare
Assuming a 1Ghz CPU and 200Mhz memory a memory read turns out to be 5 ticks. Floating point multipy is what, 3 or 4 cycles? Call it 5 to be on the safe side. Add/sub can probably be done in a couple, call it 3. Total of 45 + 7 + 35 + 23 + 13 + 1 = 52 cycles total.
Probably quite wrong actually but worth a guess (and I’m not even going to attempt to think about pipelining 
). And I think I’ve probably missed a few register moves and stores to reshuffle things mid flow, but they should be pretty cheap.
Memory access cost will vary depending if data is in cache. If it is inside, it can be almost free . If not, you will pay a lot more that just 5 CPU cycles - we are talking about 6-8 MEMORY cycles for reading random place in memory - in your example, it translates to 30-40 cpu cycles, can be a lot more on faster CPU. Hopefully x and y will be near each other, so second read will be already from cache - but we are talking about variance from 0 to 80 cpu cycles for memory access alone. Mispredicted branch at end can easily cost 10-20 cycles depending on CPU type.
Depending on code layout, computations in code can go in parallel, fitting well in pipelines (but I would maybe try to move dx*dx into temp variable before executing second memory access?). Anyway, cost of rest of code can be in 10-30 cycles range - plus 0-80 cycles penalty for possible main memory access and mispredicted branching.
If somebody cares to write such code in C (working on realistic data set), it is easy to see cache missed with AMD Codeanalyst. It should be also possible to see actual pairing/pipeline stalls with it. Too bad it doesn’t work with jitted java code…
cas is prolly right. We are talking below a 100 objects. This was nice. A problem solved that werent a problem at all