Finding lowest common denominator

[Insectoid]

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

[gitoxa]

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.

[Insectoid]

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

[PaulButler]

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.

[Insectoid]

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!

[gitoxa]

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 ?

[Insectoid]

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.

[Tony]

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.

[Insectoid]

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.

[Saad]

Read this for 2 methods to achieve what you want to do.

[Insectoid]

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.

[Saad]

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.

[Insectoid]

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!

[Tony]

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

[SNIPERDUDE]

True say, without math it's just syntax.