• ### Announcements

#### Archived

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

# 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 on other sites
aftermath    100
It depend on your CPU speed.
On mine, it would be nothing at all,
on a celery 100, it will be slow.

[ my engine ][ my game ][ my email ]
SPAM

##### Share on other sites
aftermath    100
ACUALY, i forgot to mention you are dealing with 2^850 check here, that is 7.5075168288047002299711576955093e+255 ... hmm, i sound wrong. well, it will be somthing exponention :?

[ my engine ][ my game ][ my email ]
SPAM

##### Share on other sites
hello_there    122
my computer is a amd k-6-2 400 and i have a voodoo 3.

##### 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 on other sites
aftermath    100
psudocode:
for all cubes as FOCUSCUBE{    for eatch cube as CHECKCUBE{    FOCUSCUBE->check(CHECKCUBE)}}

that looks like 850 loops with eatch loop having 849 loops thats 849*580 }= 721650

[ my engine ][ my game ][ my email ]
SPAM

##### Share on other sites
aftermath    100
and i mean checking each cube against eatch cube.

[ my engine ][ my game ][ my email ]
SPAM

##### 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 Jnext I

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

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

##### Share on other sites
FunkyTune    122
It is FunkyTUNE, but that''s ok

##### Share on other sites
aftermath    100
WTF?!?!?!?!
Thats what I said, not funkytune !!!

[ my engine ][ my game ][ my email ]
SPAM

##### Share on other sites
aftermath    100
... ohh nevermind. Hes from Canada, ehh. It takes a while fot them...

[ my engine ][ my game ][ my email ]
SPAM

##### Share on other sites
FunkyTune    122
Well, ok...

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

/John

##### Share on other sites
aftermath    100
forget the frigin 2^850 calculation!
my new calc was that you will have to have 721650 checks!

[ my engine ][ my game ][ my email ]
SPAM

##### Share on other sites
FunkyTune    122
But that''s almost twice the calculations that are actually needed.

/John

##### Share on other sites
aftermath    100
721650 is twise of 7.5075168288047002299711576955093e+255 ?
o ... k ... ?

or do you mean yours, witch is wrong by the way, cuz it dosent make any sence.

[ my engine ][ my game ][ my email ]
SPAM

##### Share on other sites
aftermath    100
and I got back from Michalson... witch for some reason said that you said that you need 850*849 checks, witch i acualy said!

[ my engine ][ my game ][ my email ]
SPAM

##### 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 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 on other sites
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 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 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 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 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 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.