Computer Science Canada

More efficient 360 degree movement + distance formula?
Author:  tyuo9980 [ Thu May 12, 2011 8:43 pm ]
Post subject:  More efficient 360 degree movement + distance formula?
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
Author:  tyuo9980 [ Thu May 12, 2011 8:48 pm ]
Post subject:  Re: More efficient 360 degree movement + distance formula?
Here is the whole game if you would want to take a look at it.
Author:  Zren [ Thu May 12, 2011 10:54 pm ]
Post subject:  RE:More efficient 360 degree movement + distance formula?
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.
Author:  DemonWasp [ Fri May 13, 2011 11:56 am ]
Post subject:  RE:More efficient 360 degree movement + distance formula?
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.
Author:  tyuo9980 [ Fri May 13, 2011 5:07 pm ]
Post subject:  Re: RE:More efficient 360 degree movement + distance formula?
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.
Author:  tyuo9980 [ Fri May 13, 2011 5:18 pm ]
Post subject:  Re: RE:More efficient 360 degree movement + distance formula?
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.
Author:  RandomLetters [ Fri May 13, 2011 7:36 pm ]
Post subject:  RE:More efficient 360 degree movement + distance formula?
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.
Author:  tyuo9980 [ Fri May 13, 2011 8:20 pm ]
Post subject:  Re: RE:More efficient 360 degree movement + distance formula?
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
Author:  DemonWasp [ Sat May 14, 2011 2:01 pm ]
Post subject:  RE:More efficient 360 degree movement + distance formula?
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.
Author:  RandomLetters [ Sat May 14, 2011 2:58 pm ]
Post subject:  RE:More efficient 360 degree movement + distance formula?
Yea, I was explaining what Demonwasp was saying.
Author:  tyuo9980 [ Sat May 14, 2011 3:13 pm ]
Post subject:  Re: More efficient 360 degree movement + distance formula?
is there anything else i can do without changing up the movement algorithm?
Author:  DemonWasp [ Sat May 14, 2011 5:04 pm ]
Post subject:  RE:More efficient 360 degree movement + distance formula?
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.
Author:  tyuo9980 [ Sat May 14, 2011 5:34 pm ]
Post subject:  Re: More efficient 360 degree movement + distance formula?
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?
Author:  Raknarg [ Sat May 14, 2011 6:47 pm ]
Post subject:  RE:More efficient 360 degree movement + distance formula?
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.
Author:  tyuo9980 [ Sat May 14, 2011 7:16 pm ]
Post subject:  Re: RE:More efficient 360 degree movement + distance formula?
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.
Author:  Raknarg [ Sat May 14, 2011 7:18 pm ]
Post subject:  RE:More efficient 360 degree movement + distance formula?
Then draw statements definitely.
Author:  tyuo9980 [ Sat May 14, 2011 7:23 pm ]
Post subject:  Re: More efficient 360 degree movement + distance formula?
it sucks how u cant edit posts...

anyways i simplified the formula even further without using sqrt.
since it will only detect a collision when the distance is less than 30pixels, the distance of a to b will always be definitely be 29 or 30.
Author:  Raknarg [ Sat May 14, 2011 7:27 pm ]
Post subject:  RE:More efficient 360 degree movement + distance formula?
Btw, you you there's a predefined function for the distance between two points?
Math.Distance (x1, y1, x2, y2)
Just so you know.
Author:  tyuo9980 [ Sat May 14, 2011 7:32 pm ]
Post subject:  Re: RE:More efficient 360 degree movement + distance formula?
Raknarg @ Sat May 14, 2011 7:27 pm wrote:
Btw, you you there's a predefined function for the distance between two points?
Math.Distance (x1, y1, x2, y2)
Just so you know.


yea you mentioned that b4, but i dont want to use sqrt since it can slow down the program by quite a bit.
Author:  Raknarg [ Sat May 14, 2011 7:40 pm ]
Post subject:  RE:More efficient 360 degree movement + distance formula?
Lol, whoops, forgot about that. Razz
Makes sense. So is the collision detection actual circle collosion? Like it changes angle accoding to its direction and where it hits?
Author:  tyuo9980 [ Sat May 14, 2011 8:03 pm ]
Post subject:  Re: RE:More efficient 360 degree movement + distance formula?
Raknarg @ Sat May 14, 2011 7:40 pm wrote:
Lol, whoops, forgot about that. Razz
Makes sense. So is the collision detection actual circle collosion? Like it changes angle accoding to its direction and where it hits?


yep.
Author:  RandomLetters [ Sat May 14, 2011 8:34 pm ]
Post subject:  RE:More efficient 360 degree movement + distance formula?
Usually, x*x is much faster than x^2. Although at this point I don't think the efficiency of your code is the problem.
Author:  tyuo9980 [ Sat May 14, 2011 10:40 pm ]
Post subject:  Re: RE:More efficient 360 degree movement + distance formula?
RandomLetters @ Sat May 14, 2011 8:34 pm wrote:
Usually, x*x is much faster than x^2. Although at this point I don't think the efficiency of your code is the problem.


so do you think that its just turing?
Author:  DemonWasp [ Sat May 14, 2011 10:41 pm ]
Post subject:  RE:More efficient 360 degree movement + distance formula?
Hmm. I'd missed the bonus that, since the speed of these things is 1, the worst-case scenario is that the distance between them is 28 (both going opposite directions, immediately after a collision). You could always just assume that the "closeness" factor I described is 1 (which you do), and it'll be close enough. Very nice.

You should probably also avoid recalculating dx and dy so many times -- you calculate them between 1 and 3 times in your most recent post (once for checking collision, once for calculating distance, and once for calculating the final dx and dy you use.

Aside from that, I think any slowness you're fighting is due to Turing being slow. You could look into using BSPs or other algorithmic improvements, but they're all pretty complex. Try to make do with the performance you have, and see where you can get with that.
Author:  tyuo9980 [ Sat May 14, 2011 11:12 pm ]
Post subject:  Re: More efficient 360 degree movement + distance formula?
thanks guys!

now this is only about 65% of the whole game. i still have to add 'bar' collision and dead/alive filters to the objects. i think the program will good up until ~90 - 100 on my computer after that's added.
the school computers... ehh no so much. i would expect ~40-50

anyways my teacher understands how slow turing can be so i dont think my mark will drop because of this. maybe next yr in gr11 ill b learning another language thats faster, probably pascal. i would really like to learn C++ or C#. only if the schools taught that....
Author:  mirhagk [ Sun May 15, 2011 12:23 am ]
Post subject:  RE:More efficient 360 degree movement + distance formula?
Your school doesn't teach C++ or C#?

I am working on tutorials to upgrade from turing to C#, since it really isn't that difficult, it's still all high level, just now it actually is powerful.

The funny thing is that with something like C# you could use this with thousands and thousands of objects without ever hitting lag lol. Turing is REALLY slow, it actually compiles to C++ (I've been told), so it probably compiles to an old version, with outdated libraries. If I ever take a course on compilers I'm def doing Turing as my final project lol.
Author:  XZNZ [ Sun May 15, 2011 7:52 pm ]
Post subject:  RE:More efficient 360 degree movement + distance formula?
nice
Author:  XZNZ [ Sun May 15, 2011 8:43 pm ]
Post subject:  RE:More efficient 360 degree movement + distance formula?
hey
without using sqrt function multiply by 0.5
and
x * x instead of x^2 will save a lot of time

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy