Computer Science Canada

Finding lowest common denominator
Author:  Insectoid [ Mon Sep 08, 2008 5:06 pm ]
Post subject:  Finding lowest common denominator
For a game I'm working on, a koopa (yes, from mario) has to move randomly around the screen. I want him to pick a point, randomly, on the screen, then move there. I figured I can do this with slope, but the problem is, the slope has to be in its lowest form. How can I do this?

My procedure:
Turing:

proc move_koopa
    var count := 200

    %checks if the location of the koopa is the same as it's destination, if returns true then chooses a new destination   
    if koopa_X = koopa_dest_X and koopa_Y = koopa_dest_Y then
        koopa_dest_X := Rand.Int (1, maxx)
        koopa_dest_Y := Rand.Int (1, maxy)
    end if

    %the slope calculation
     koopa_ver := koopa_dest_Y - koopa_Y
     koopa_hor := koopa_dest_X - koopa_X

    %my attempt at finding the lowest common denominator
    loop
        exit when koopa_ver mod count = 0 and koopa_hor mod count = 0
        count -= 1
        exit when count = 0   
    end loop

    koopa_Y += koopa_ver
    koopa_X += koopa_hor
end move_koopa
Author:  gitoxa [ Mon Sep 08, 2008 8:08 pm ]
Post subject:  Re: Finding lowest common denominator
I'd start at 2, and find the lowest common number (incrementing by 1) that divides into both with a remainder of 0. First number found would be the lowest, if none are found by the time the number is half the denominator, then it's already in lowest form.

That said, I'm not quite sure I understand your reasoning behind needing it in lowest form.
Author:  Insectoid [ Mon Sep 08, 2008 8:32 pm ]
Post subject:  RE:Finding lowest common denominator
I need the slope in lowest terms because otherwise I might get something like 20/10, which would cause my koopa to move 20 pixels up and 10 pixels right. I would want it moving at 2/1.

Anyways, I got it working...sort of...It is inconsistent...

Turing:

proc move_koopa
    var koopa_pic : int
    var count := 10000
    if koopa_X = koopa_dest_X and koopa_Y = koopa_dest_Y then
        koopa_dest_X := Rand.Int (1, maxx)
        koopa_dest_Y := Rand.Int (1, maxy)
    end if

    koopa_hor := (koopa_dest_X - koopa_X)
    koopa_ver := (koopa_dest_Y - koopa_Y)

    loop
        exit when koopa_ver mod count = 0 and koopa_hor mod count = 0
        count -= 1
        exit when count = 0
    end loop

    koopa_ver div= count
    koopa_hor div= count

    if koopa_hor > 0 then
        koopa_pic := koopa_left
    else
        koopa_pic := koopa_right
    end if

    koopa_Y += koopa_ver
    koopa_X += koopa_hor
    Pic.Draw (koopa_pic, koopa_X, koopa_Y, picMerge)
end move_koopa
Author:  PaulButler [ Mon Sep 08, 2008 8:39 pm ]
Post subject:  RE:Finding lowest common denominator
Euclid's got your back: http://en.wikipedia.org/wiki/Euclidean_algorithm

I don't know turing but hopefully the example code in the article will be easy enough to understand.
Author:  Insectoid [ Mon Sep 08, 2008 9:17 pm ]
Post subject:  RE:Finding lowest common denominator
Thanks, I have implemented that, but now have the error 'overflow in integer expression'. I completely forget what this means. So, I'm posting my new, revised code!

Turing:

function gcd (a, b : int) : int
    if b = 0 then
        result a
    else
        result gcd (b, a mod b)
    end if
end gcd

proc move_koopa
    var koopa_pic : int
    var count := 10000
    if koopa_X = koopa_dest_X and koopa_Y = koopa_dest_Y then
        koopa_dest_X := Rand.Int (1, maxx)
        koopa_dest_Y := Rand.Int (1, maxy)
    end if

    koopa_hor := (koopa_dest_X - koopa_X)
    koopa_ver := (koopa_dest_Y - koopa_Y)

   
    koopa_hor div= gcd (koopa_hor, koopa_ver)
    koopa_ver div= gcd (koopa_hor, koopa_ver)
   

    if koopa_hor > 0 then
        koopa_pic := koopa_left
    else
        koopa_pic := koopa_right
    end if

    koopa_Y += koopa_ver
    koopa_X += koopa_hor
    Pic.Draw (koopa_pic, koopa_X, koopa_Y, picMerge)
end move_koopa


Hurray for ancient math geeks!
Author:  gitoxa [ Mon Sep 08, 2008 9:50 pm ]
Post subject:  Re: RE:Finding lowest common denominator
insectoid @ Mon Sep 08, 2008 8:32 pm wrote:
I need the slope in lowest terms because otherwise I might get something like 20/10, which would cause my koopa to move 20 pixels up and 10 pixels right. I would want it moving at 2/1.


I figured that much, but what happens when you get a slope of something like 23/7 ?
Author:  Insectoid [ Tue Sep 09, 2008 11:39 am ]
Post subject:  RE:Finding lowest common denominator
Then I would divide it by 2 and round, and the target would be represented by a box perhaps 8X8 pixels, that would account for any error caused by rounding. I'd just have to find the greatest possible error and make my box that big.
Author:  Tony [ Tue Sep 09, 2008 11:48 am ]
Post subject:  Re: RE:Finding lowest common denominator
insectoid @ Mon Sep 08, 2008 8:32 pm wrote:
I might get something like 20/10, which would cause my koopa to move 20 pixels up and 10 pixels right. I would want it moving at 2/1.

Ugghhh... no. You are making your koopa travel at different speeds, depending on the slope.

Keep your vector as direction (angle) and magnitude (float point value). Keep the position of the koopa in real values as well, and round to integers only to draw the frame.
Author:  Insectoid [ Tue Sep 09, 2008 12:12 pm ]
Post subject:  RE:Finding lowest common denominator
Could you provide an example? I've never used Math beyond basic operators in programming before. I figure I'd better learn sooner than later.
Author:  Saad [ Tue Sep 09, 2008 1:40 pm ]
Post subject:  RE:Finding lowest common denominator
Read this for 2 methods to achieve what you want to do.
Author:  Insectoid [ Tue Sep 09, 2008 3:38 pm ]
Post subject:  RE:Finding lowest common denominator
Thank you! I couldn't make heads or tails of the tutorial (I only just started Gr. 11 functions this month, all we've done is linear and quadratic review), but I managed to rip off his code (I know, I know...) and have it work in my game. (I did give The_Bean credit in the code). I understand what everything does, just not how the cod does it.
Author:  Saad [ Tue Sep 09, 2008 3:51 pm ]
Post subject:  Re: RE:Finding lowest common denominator
insectoid @ Tue Sep 09, 2008 3:38 pm wrote:
Thank you! I couldn't make heads or tails of the tutorial (I only just started Gr. 11 functions this month, all we've done is linear and quadratic review), but I managed to rip off his code (I know, I know...) and have it work in my game. (I did give The_Bean credit in the code). I understand what everything does, just not how the cod does it.


There is another one at the bottom which you might find easy to understand.
Author:  Insectoid [ Tue Sep 09, 2008 4:11 pm ]
Post subject:  RE:Finding lowest common denominator
Well, that is a lot simpler, but what the heck, it's working now, I don't want to fiddle around with the koopa any more. I'd rather look at the complicated trig later on after learning advanced trig in school.

P.S. This week we (my class) start learning java and I start learning Python!
Author:  Tony [ Tue Sep 09, 2008 5:33 pm ]
Post subject:  Re: RE:Finding lowest common denominator
insectoid @ Tue Sep 09, 2008 4:11 pm wrote:
P.S. This week we (my class) start learning java and I start learning Python!

That doesn't at all matter, since your problem is with Math Wink
Author:  SNIPERDUDE [ Tue Sep 09, 2008 8:53 pm ]
Post subject:  RE:Finding lowest common denominator
True say, without math it's just syntax.
Author:  isaiahk9 [ Thu Sep 11, 2008 4:16 pm ]
Post subject:  RE:Finding lowest common denominator
Call me stupid, but why couldn't you just lose the fractions? For instance :

loop

var RandomKoopaLocationx - random
integer
var RandomKoopaLocationy - random
integer

if RandomKoopaLocationx = currentx and RandomKoopaLocationy = currenty then

else
loop
var distancebetweenx : int := RandomKoopaLocationx - currentx
var distancebetweeny : int := RandomKoopaLocationy - currentx
var slope : int := distancebetweenx / distancebetweeny
%get Turing to round the variable "slope" for you
currentx += slope
if currenty > RandomKoopaLocationy then
currenty -= 1
else
currenty += 1
end if
end loop
end if
end loop

Sweet thing about my code is changing the RandomKoopax to the player's coordinates, makes the enemy home in. My code is probably inneffective, but why so? It gets rid of all these LCDs.
Author:  Insectoid [ Thu Sep 11, 2008 4:33 pm ]
Post subject:  RE:Finding lowest common denominator
Dude, you missed the point. did you read the whole thread? I'm using trigonometry now, man! I have no idea how it works, but w/e. You can see the finished product in ' mario-themed wall avoider thing' in the turing submissions.
Author:  isaiahk9 [ Thu Sep 11, 2008 4:58 pm ]
Post subject:  RE:Finding lowest common denominator
Oh well. I thought my code would've been simpler/more versatile for enemy homing in on you. Guess not. Sorry for my pointless post then.

:


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

Terms of Use | Privacy Policy