Archived

This topic is now archived and is closed to further replies.

hello_there

sloooooowwwwwwww

Recommended Posts

hello_there    122
how much would it downgrade speed drawing 850 cubes to the screen and checking for collisions with all of them? i mean would it be heaps or just a little?

Share this post


Link to post
Share on other sites
FunkyTune    122
Excuse me, I don''t know much about collision checking, and maybe I''m totally wrong, but:

Wouldn''t the number of checks be

850+849+848...+1 = (850+1)*(850/2) = 361675 ?

That''s a little bit less than 2^850...

/John

Share this post


Link to post
Share on other sites
Michalson    1657
FunkyTUNE!!! is correct. By doing 850*849 you're repeating *alot* of checks. Take this example, you have objects A, B and C.

What your loop will do is this:
1st interation of outer loop:
(A,B), (A,C)
2d interation of outer loop:
(B,A), (B,C)
3rd interation of outer loop:
(C,A), (C,B)

However notice that in the 2nd interation we've already checked AB, and in the third interation we've already checked AC and BC.

You want to do this:

1st
(A,B), (A,C)
2nd
(B,C)

This can be accomplished with this code (Assuming areas are Low to High):

for I=Low to High-1
for J=I+1 to High
Compare(I,J)
next J
next I


[EDIT]: Correct horrible insult to FunkyToon, ...eer tune

[edited by - michalson on May 6, 2002 8:27:08 AM]

Share this post


Link to post
Share on other sites
FunkyTune    122
Well, ok...

If you want to do 2^850 calculations every frame, do it.

But don''t come complaining to me about your low framerate...

/John

Share this post


Link to post
Share on other sites
FunkyTune    122
Ok, then:

Each cube has to be checked against every other cube, right?

So if you check Cube1 against Cube2, you don't have to check Cube2 against Cube1, right?

This means that you only have to check the cubes that has an index bigger that the cube being checked against.


  
CUBE cube[NUM_CUBES];
for (int i=0; i<NUM_CUBES-1; i++)
{
for (int j=i+1; j<NUM_CUBES; j++)
{
if (collision(cube[i], cube[j]))
cout << "Kaboom!";
}
}


EDIT: source-tag

[edited by - FunkyTune on May 6, 2002 7:38:19 AM]

[edited by - FunkyTune on May 6, 2002 7:39:35 AM]

Share this post


Link to post
Share on other sites
phueppl1    122
FunkyTUNE ( ) is correct..

It doesn''t matter if you check A against B or B against A... it will give you the same result ( if not, there''s some serious bug in your CD code *g*)...

So you''re doublechecking quite a bit if you''re not going for Michalsons algo.. (It''s the same runoff as in the bubble sort).

Still, to get that fluently, I''d suggest some kind of hierachy or so, where you group boxes together to bigger groups.. that way you''ll only have to test boundings first, and if that gives a hit you''ll have to test further..

There are a lot of papers about that around..
hope that helped..
cya,
Phil

Visit Rarebyte!
and no!, there are NO kangaroos in Austria (I got this questions a few times over in the states )

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
AfterMath simply seems unable to accept there are people who can see a possible optimizion of problems...
I guess he still uses BubbleSort...

Share this post


Link to post
Share on other sites
taratr98    122
Okay. You can do 850*849 calculations = 721650. But it is true that this redundantly checks about half of the time. (If you''ve already checked A colliding with B, there''s no need to check B colliding with A.)

The number of calculations for FunkyTune''s code is defined as

(849+848+847+846+ ... +1) - think about it for a minute, you''ll see that this is true.

(849+ ... +1) is defined as a summation: adding up from 1 to 849. The calculation for that is n(n-1)/2. That gives us that (849+ ... +1) is about 359976. (The math is right on this, believe me.)

So, FunkyTune''s code is about twice as efficient as the "check everything with everything" algorithm. Okay?

If you want to do the extra 361674 calculations, that''s your business. But imagine how much worse this difference would be at 10,000 cubes!

This small algorithm analysis and complexity lesson brought to you by

-ATR-

Share this post


Link to post
Share on other sites
TheMuuj    122
Of course, when dealing with cubes, there are ways of getting even better efficiency. But I suggest the programmer with the question try the (n)+(n-1)+(n-2)+...(1) method first. This is the basic outline for a lot of searching algorithms.

--TheMuuj

[edited by - TheMuuj on May 6, 2002 12:23:55 PM]

Share this post


Link to post
Share on other sites
a person    118
how about using sectors to further reduce the number of checks? if two cubes are not in neighboring sectors, its impossible for them to collide (assuming your sectors are larger then a cube can move per frame). of course you need to sort the cubes first. but once they are initially sorted you never have to do it again since when a cube crosses a sector, you just pop it from the previous sector and push it to the new sector. straddling cubes might be slightly tricky, but some research will solve things pretty well.

hello_there: why dont you ust do some research and try it out?

Share this post


Link to post
Share on other sites
Zipster    2359
Just wanted to point out that the number of checks would actually be 850 "combination" 2, which is 850!/2!(850 - 2)! , or 360825 checks. That's using the fact that A to B = B to A. Gotta love statistics

[edited by - Zipster on May 6, 2002 7:15:53 PM]

Share this post


Link to post
Share on other sites
Mulligan    378
Assuming that the cubes are all of the same size, a simple distance check could allow you to avoid checking for a collision all together. This wouldnt change the big-O, but would drastically reduce the calculating. Plus, there are a million other things you could do to cut down on extra processing. Thats my two cents.

Share this post


Link to post
Share on other sites