> For example if we have 'n' objects then the first object could collide with n-1 objects (since we don't check if an object has collided with itself) the second object could collide with (n-2) additional objects not counting the possible collisions we have already counted. If we keep going like this we get the number of possible collisions is: (n-1) * (n-2) * (n-3) ... 1 This is equivalent to n! / 2! * (n-2)!
Seems to me like it should be more like the handshake problem, which comes out to n * (n-1)/2. n^2 is still bad, but not nearly as bad as n!.
Actually, n! / (2! * (n-2)!) comes out exactly at n * (n-1)/2. It's just one form of the general formula for combinations.
However, multiplying the possible situations is, of course, wrong. A case of a wrong explanation of the final result I'd imagine (permutations instead of combinations),
Hrmm. For some reason whenever graphics/game programming related articles get posted on HN, the quality seems to be ridiculously low. For example, no discussion of discrete vs. continuous, temporal coherence, sweep and prune, separating axis, etc. I think even if you assume this article was written in 1998 it still strikes me as a bit behind the times. The fact that this article has 15 points at the moment is disturbing...
Why doesn't Octopus just stop posting horrible articles and whenever people point out how horrible the articles are, why don't other stop telling them to post something better?
Because I haven't been involved in game development professionally since 2002. Even though my knowledge is now 9 years out of date, I know that this article is low quality.
That's a sign you should submit better articles or write them yourself (then submit). If you have a bunch of links handy why not post them here as well?
When I learned about sweep and prune I was amazed at how simple and obvious it should have been, but I don't recall the first books I read on game programming ever mentioning it, I'd hope a book dedicated to collision detection topics would but I don't own one.
The quality of most such articles really is extremely low. Apart from a few books from experts like the Ericson "Real-Time Collision Detection," and the codebase for open source engines, public knowledge about this stuff is basically missing from the Web.
At least these days there are good books. Ten years ago, AFAIK, your best options for the cutting-edge concepts were GDC session notes and academic papers.
9 comments
[ 0.20 ms ] story [ 17.5 ms ] threadSeems to me like it should be more like the handshake problem, which comes out to n * (n-1)/2. n^2 is still bad, but not nearly as bad as n!.
However, multiplying the possible situations is, of course, wrong. A case of a wrong explanation of the final result I'd imagine (permutations instead of combinations),
In other words, STFU GTFO.
When I learned about sweep and prune I was amazed at how simple and obvious it should have been, but I don't recall the first books I read on game programming ever mentioning it, I'd hope a book dedicated to collision detection topics would but I don't own one.
At least these days there are good books. Ten years ago, AFAIK, your best options for the cutting-edge concepts were GDC session notes and academic papers.