More efficient 360 degree movement + distance formula?

[tyuo9980]

So for i got the collision on my geo wars clone but its really slow when it goes higher than 50 shapes, and I have a core i5 @ 4ghz!

so is there anyway to make this code below more efficient?
i am currently using arctand to find degrees and use x := speed * cosd (degrees). or is there a substitute or trick to removing the trig involved?
also is there another way to simplify the distance equation even further? i am using x^2 + y^2 = dist^2

code:

procedure enemycollide     for a : 1 .. enemynum                                                               %enemy self collision         for b : 2 .. enemynum             if ((ex (a) - ex (b)) ** 2) + ((ey (a) - ey (b)) ** 2) < 900 then           %calculates distance to check collision. 30x30 = 900 to remove sqrt                 ecdeg := slopeang (ey (a) - ey (b), ex (a) - ex (b))                    %calculates slopeang                 if ((x - ex (a) + 14) ** 2) + ((y - ey (a) + 14) ** 2) < ((x - ex (b) + 14) ** 2) + ((y - ey (b) + 14) ** 2) then %if distance of a < b                     if ey (a) < ey (b) then                                             %if enemy b is above enemy a                         if ecdeg > 0 and ecdeg < 180 then                               %for positive slope                             ex (b) += cosd (ecdeg)                             ey (b) += sind (ecdeg)                         elsif ecdeg > 180 and ecdeg < 360 then                          %for negative slope                             ex (b) -= cosd (ecdeg)                             ey (b) -= sind (ecdeg)                         end if                     elsif ey (a) > ey (b) then                         if ecdeg > 0 and ecdeg < 180 then                               %for positive slope                             ex (b) -= cosd (ecdeg)                             ey (b) -= sind (ecdeg)                         elsif ecdeg > 180 and ecdeg < 360 then                          %for negative slope                             ex (b) += cosd (ecdeg)                             ey (b) += sind (ecdeg)                         end if                     end if                 elsif ((x - ex (b) + 14) ** 2) + ((y - ey (b) + 14) ** 2) < ((x - ex (a) + 14) ** 2) + ((y - ey (a) + 14) ** 2) then %if distance of a > b                     if ey (b) < ey (a) then                                             %if enemy b is above enemy a                         if ecdeg > 0 and ecdeg < 180 then                               %for positive slope                             ex (a) += cosd (ecdeg)                             ey (a) += sind (ecdeg)                         elsif ecdeg > 180 and ecdeg < 360 then                          %for negative slope                             ex (a) -= cosd (ecdeg)                             ey (a) -= sind (ecdeg)                         end if                     elsif ey (b) > ey (a) then                         if ecdeg > 0 and ecdeg < 180 then                               %for positive slope                             ex (a) -= cosd (ecdeg)                             ey (a) -= sind (ecdeg)                         elsif ecdeg > 180 and ecdeg < 360 then                          %for negative slope                             ex (a) += cosd (ecdeg)                             ey (a) += sind (ecdeg)                         end if                     end if                 /*elsif ex (a) = ex (b) and ey (a) = ey (b) then                     loop                         exit when ((ex (a) - ex (b)) ** 2) + ((ey (a) - ey (b)) ** 2) > 900                         ex (a) -= cosd (edeg)                         ey (a) -= sind (edeg)                         ex (b) += cosd (ecdeg)                         ey (b) += sind (ecdeg)                     end loop*/                 end if             end if         end for     end for end enemycollide

[tyuo9980]

Here is the whole game if you would want to take a look at it.

[Zren]

Why do you need the angle/slope to detect collision?

Also, skip detection when a = b.

for each thingy
dx := e.x + cos(e.ang) * e.vel
dy := e.y + sin(e.ang) * e.vel

check if calculated coordinates collide with anything

set new coordinates if no collision.

[DemonWasp]

There are a lot of ways to speed your program up. I got it to run relatively smoothly with 100 enemies on a Pentium 4.

One of the easiest is that you're checking each pair of enemies twice, first as (a,b), then as (b,a) later on. The second check does nothing but waste CPU, as far as I can tell. You can set your second for loop so that it goes from a+1 .. b and you'll see a huge speedup immediately.

Secondly, most of your "elsif" conditions are really "else" conditions. You can save yourself a bunch of calculation time this way.

Thirdly, you don't actually need to do very much trig at all. The entire effect CAN be achieved without using any cosines, sines, or arctans. Doing so is a huge speedup. Think about it like this:

code:

7 (B goes this way if they're too close               /              /             B       dist /|           / |          /  |         /   |  dy        A----/       /  dx      /     L  (A goes this way if they're too close)

You can figure out dx, dy and dist pretty easily (you will have to use a sqrt, but don't worry about it -- that's much faster than a cosd or arctan). If the distance is less than double the radius of these craft (about 30 units), then they're too close by some factor, which we'll call "closeness", and they should move away from each other.

However, if you look closely, we now have three similar triangles! In fact, two are congruent. This means that you can calculate the lengths of their sides using ratios. This makes things easy.

First, we determine that A and B will move equal amounts, so each will have to move one-half of the "closeness" factor. Let's just consider A for a moment, then:

code:

B                   /|                  / |           dist  /  |                /   |  dy               /    |              /     |             /      |            /       |           /        |          A---------/  move   /|    dx  dist  / |       /  | moveY      /   |     A'---/      moveX

You should be able to see that the ratio of moveX / moveDist is exactly equal to the ratio dx / dist. If we solve for moveX, we get: moveX = moveDist * dx / dist . You can probably figure out what moveY is on your own. The best bit is, you don't have to recalculate for B: just subtract moveX and moveY instead of adding them (or vice-versa).

My third suggestion gives very subtly different movement from your existing algorithm, but it's much cheaper and faster, and it looks pretty good too.


Final point: Turing is ridiculously slow. Don't be surprised if you can't get Turing to perform anywhere near the original's speed, even with vastly fewer enemies and much less graphics on-screen. Turing can only use one of your CPU's cores, is about 100 times slower than most other languages, and can't leverage your graphics hardware: Geometry Wars probably uses all of the CPUs on its platform quite efficiently, with full graphical acceleration.

[tyuo9980]

Zren @ Thu May 12, 2011 10:54 pm wrote:

Why do you need the angle/slope to detect collision?

Also, skip detection when a = b.

for each thingy
dx := e.x + cos(e.ang) * e.vel
dy := e.y + sin(e.ang) * e.vel

check if calculated coordinates collide with anything

set new coordinates if no collision.

the check of a = b will unfortunately be needed when i implement spawning. because i will be having them spawn at the same point and using this collision to "push" them out.

i am not using slope to detect collision. i am using distance.

here is what i am doing after a collision has been detected. i calculate the slope of the 2 objects its comparing and then moving it up/down according to which direction its facing.

[tyuo9980]

DemonWasp @ Fri May 13, 2011 11:56 am wrote:

There are a lot of ways to speed your program up. I got it to run relatively smoothly with 100 enemies on a Pentium 4.

One of the easiest is that you're checking each pair of enemies twice, first as (a,b), then as (b,a) later on. The second check does nothing but waste CPU, as far as I can tell. You can set your second for loop so that it goes from a+1 .. b and you'll see a huge speedup immediately.

Secondly, most of your "elsif" conditions are really "else" conditions. You can save yourself a bunch of calculation time this way.

Thirdly, you don't actually need to do very much trig at all. The entire effect CAN be achieved without using any cosines, sines, or arctans. Doing so is a huge speedup. Think about it like this:

code:

7 (B goes this way if they're too close               /              /             B       dist /|           / |          /  |         /   |  dy        A----/       /  dx      /     L  (A goes this way if they're too close)

You can figure out dx, dy and dist pretty easily (you will have to use a sqrt, but don't worry about it -- that's much faster than a cosd or arctan). If the distance is less than double the radius of these craft (about 30 units), then they're too close by some factor, which we'll call "closeness", and they should move away from each other.

However, if you look closely, we now have three similar triangles! In fact, two are congruent. This means that you can calculate the lengths of their sides using ratios. This makes things easy.

First, we determine that A and B will move equal amounts, so each will have to move one-half of the "closeness" factor. Let's just consider A for a moment, then:

code:

B                   /|                  / |           dist  /  |                /   |  dy               /    |              /     |             /      |            /       |           /        |          A---------/  move   /|    dx  dist  / |       /  | moveY      /   |     A'---/      moveX

You should be able to see that the ratio of moveX / moveDist is exactly equal to the ratio dx / dist. If we solve for moveX, we get: moveX = moveDist * dx / dist . You can probably figure out what moveY is on your own. The best bit is, you don't have to recalculate for B: just subtract moveX and moveY instead of adding them (or vice-versa).

My third suggestion gives very subtly different movement from your existing algorithm, but it's much cheaper and faster, and it looks pretty good too.


Final point: Turing is ridiculously slow. Don't be surprised if you can't get Turing to perform anywhere near the original's speed, even with vastly fewer enemies and much less graphics on-screen. Turing can only use one of your CPU's cores, is about 100 times slower than most other languages, and can't leverage your graphics hardware: Geometry Wars probably uses all of the CPUs on its platform quite efficiently, with full graphical acceleration.

TYVM! this was very informative. i do know that my elsifs were actually elses but i used the elsif so that my teacher would understand it better when he reads the code. anyways ill just comment it out. I will try your third suggestion when i have time. since this project is due in a few weeks and with my isu's due and my exams coming up i wont have time to really do some time consuming work like this. i would be finishing the actual game first and then work on efficiency later. thanks.

also for when you said, "You can set your second for loop so that it goes from a+1 .. b and you'll see a huge speedup immediately.', what did you mean? i have to check each shape against the other ones to see if they collide, so i dont understand why you would skip checks.

[RandomLetters]

If you check every enemy against each other, you will check twice as many times as you need to.

Why? because first it will compare enemy1 to enemy 2, and later enemy2 to enemy1, which is a waste.

using n = a .. b, will only compare with the following people.

Think of the shaking hands problem, you don't need to shake someone if he has already shaken with you.

[tyuo9980]

RandomLetters @ Fri May 13, 2011 7:36 pm wrote:

If you check every enemy against each other, you will check twice as many times as you need to.

Why? because first it will compare enemy1 to enemy 2, and later enemy2 to enemy1, which is a waste.

using n = a .. b, will only compare with the following people.

Think of the shaking hands problem, you don't need to shake someone if he has already shaken with you.

thanks.

before i would lag when i reach ~80 shapes. now the threshold is ~110

[DemonWasp]

The part from my post that you didn't quite get is exactly what RandomLetters was saying. Your existing code was checking each pair twice, when you only needed to check once. It looks like you've fixed that, though.

[RandomLetters]

Yea, I was explaining what Demonwasp was saying.

[tyuo9980]

is there anything else i can do without changing up the movement algorithm?

[DemonWasp]

Speed-wise, no, not really. It may be helpful to determine exactly how much slower it is without collisions at all -- if you comment out the call to enemycollide, how many enemies can you put on the screen without visible lag?

What I'm saying is that this may not be the slowest function present.

[tyuo9980]

code:

for a : 1 .. enemynum - 1                                                           %enemy self collision         for b : a + 1 .. enemynum             if ((ex (a) - ex (b)) ** 2) + ((ey (a) - ey (b)) ** 2) < 900 then           %calculates distance to check collision. 30x30 = 900 to remove sqrt                 if ex (a) = ex (b) and ey (a) = ey (b) then                             %separate if overlapped                     ex (b) += 1                     ey (b) += 1                 else                     dist := sqrt ((((ex (b) + 14) - (ex (a) + 14)) ** 2) + (((ey (b) + 14) - (ey (a) + 14)) ** 2))                     dx := ex (b) - ex (a)                     dy := ey (b) - ey (a)                     movex := dx / dist                     movey := dy / dist                     ex (b) += movex                     ey (b) += movey                 end if             end if         end for     end for

this is what i have changed using your suggestions. the biggest speed up was the for loop mod, but the actual algorithm change didnt help much at all.

There is a huge difference if i comment out the collision check. ~110 when i have it on, ~350 to feel noticeable lag.

also for the background grid, would it be faster to use a picture than drawing the lines?

[Raknarg]

I think it's better to draw it yourself. I have tried using a lot of sprites and pictures for another game, but it ran really slow when I did. I changes to drawing it myself, and it helped a lot.
It really depends on how detailed the backround it, though.

[tyuo9980]

Raknarg @ Sat May 14, 2011 6:47 pm wrote:

I think it's better to draw it yourself. I have tried using a lot of sprites and pictures for another game, but it ran really slow when I did. I changes to drawing it myself, and it helped a lot.
It really depends on how detailed the backround it, though.

its just a simple grid.