18 replies to this topic

[YOK-dfa]

Does anyone have any good pointers to algorithms used to calculate trajectories of objects that move on the screen without using floating point operations? Basically i want an object to start at a specific screen coordinate and then move in a certain direction. This direction is specified in degrees (0 - 360 degrees).

I was thinking of actually using a table for this ( 0 - 45 degrees) and reusing this for the other values of the angle. The value in the table would specify how much pixels the vertical movement (m) should be for (n) pixels horizontally.

Or are there better ways to implement this?


Second question:
See picture. The idea is that the object is moving across the screen in a straight line until it enters the gravity-field of a planet. The course of the object get's changed (the close to the planet, the bigger the course deviation ofcourse). Multiple planets with interfering gravity fields could be on the screen at once.

I could ofcourse use the real mathematical formula's the realistically compute the trajectory of the object, but the target machine does not have the computing power for that (to further complicate matters, the only math. instructions it has are add and negate )

Anyone have an idea about how to implement this? The trajectory doesn't have to be 100% correct, as long as it looks convincing. I don't need complete instructions, but just some pointers to info or something would be appreciated too...

[Thomas Jentzsch]

I suppose you are looking for fractional math.

For movement, add small values (X/Y speeds) to the lower bits/bytes of X and Y position each frame. The direction itself doesn't matter here, only the speed in the two directions.

For gravity fields, I suggest using tables, which convert distances into gravity force and direction and add the result to the X/Y speeds.

[Cybergoth]

Thomas Jentzsch, on Tue Mar 7, 2006 2:19 PM, said:

I suppose you are looking for fractional math.

Isn't that just another name for floating point math?

[YOK-dfa]

Thomas Jentzsch, on Tue Mar 7, 2006 3:19 PM, said:

I suppose you are looking for fractional math.

For movement, add small values (X/Y speeds) to the lower bits/bytes of X and Y position each frame. The direction itself doesn't matter here, only the speed in the two directions.

So, how would that work? Let's say the path of the object can be described by the function X = 5/9 * Y. You suggest adding 9 to Y and 5 to X every frame? That would make the object move very fast across the screen ?? I could ofcourse take 2 (or more) bytes for the X and Y value and divide the result by a factor 2^n (i think the processor has a ROR equivalent instruction). This would lower the moving speed, but it would cost more RAM (which i don't really have available)...

If you only do it every z-th frame than the object would appear to teleport to positions on the line. In that case, how do i easily calculate the in-between positions?

Edited by YOK-dfa, Tue Mar 7, 2006 8:49 AM.

[Thomas Jentzsch]

Cybergoth, on Tue Mar 7, 2006 3:41 PM, said:

Isn't that just another name for floating point math?

But the point is not floating.

[Thomas Jentzsch]

YOK-dfa, on Tue Mar 7, 2006 3:48 PM, said:

I could ofcourse take 2 (or more) bytes for the X and Y value and divide the result by a factor 2^n (i think the processor has a ROR equivalent instruction). This would lower the moving speed, but it would cost more RAM (which i don't really have available)...

But you will need at least two bytes each for X/Y position (7..8 bits for screen position, the remaining bits for inter-pixel positions). Else your movement speed will not be fine enough. For speed, you most likely can get away with one byte each (maybe you have to shift before adding to position).

BTW: You divisor doesn't have to be a factor of 2^n. E.g. you could add 15 and 27 or 75 and 135... So when the factor changes, e.g. due to gravity you can pretty simple adjust the speeds here.

Quote

If you only do it every z-th frame than the object would appear to teleport to positions on the line. In that case, how do i easily calculate the in-between positions?

I haven't thought about that (I suppose it's not really simple), but for really variable speed, you must be able to move the object e.g. every 4.25th frame then. So you would need at least two bytes here too.

Edited by Thomas Jentzsch, Tue Mar 7, 2006 10:01 AM.

[Robert M]

I think what Thomas is referring to is better described as fixed-point math. For fixed point math you do all math as integer math and then slap a decimal point in at a fixed bit position every thing to the right of the decimal magically becomes a fraction, and the left side is the integer you use to draw the object on the screen.

Let's keep things simple and assume you are using a 16-bit X-position value. The decimal point will be conveniently placed between the 2 bytes.

Xwhole = [Xpos]:[Xfraction]

Now you need to declare an X velocity as a single byte holding a signed byte value.
Each time you are going to add the velocity to the you must do this:

Xadjust = 0
If Xvelocity is negative THEN // The MSB is set.
Xadjust = $FF // for a negative velocity you must extend the sign to 16-bits.
ENDIF

Xfraction = Xfraction + Xvelocity
Xpos = Xpos + Xadjust + carry from previous addition.

Then use the XPos byte to position the object on screen.
NOTE: it will take at least 2 updates to change Xpos by 1 pixel. To get a higher velocity for the object you need to either add Xvelocity multiple times each display frame, or extend it to 16 bits just like Xwhole.

Repeat this technique for the Y axis.

Doing gravity is another problem entirely, and I will have to think about it and propose a solution later. Basically you need to find a quick way to calculate the distance from the gravity source to the object = SQRT(Xdiff^2 +Ydiff ^2) = nasty , and then mulitply that times some gravitational factor for the object yielding an acceleration that you must proportionally divide between Xvelocity and Yvelocity based on the angle of the object to the source.

The real question is, how realistic does this need to be? Are you willing to go with an approximation of gravity or do you need a NASA grade simulation?

Cheers!

Edited by Robert M, Tue Mar 7, 2006 10:03 AM.

[Cybergoth]

Thomas Jentzsch, on Tue Mar 7, 2006 3:49 PM, said:

Cybergoth, on Tue Mar 7, 2006 3:41 PM, said:

Isn't that just another name for floating point math?

But the point is not floating.

Good point

But still you're pretty flexible as to where you put the point

Greetings,
Manuel

[Thomas Jentzsch]

Robert M, on Tue Mar 7, 2006 5:00 PM, said:

I think what Thomas is referring to is better described as fixed-point math.

Yup!

Quote

If Xvelocity is negative THEN  // The MSB is set.
     Xadjust = $FF      // for a negative velocity you must extend the sign to 16-bits.
ENDIF

I don't get this part. Negative velocity works exactly like positive one.

Quote

Xfraction = Xfraction + Xadjust 
Xpos = Xpos + Xadjust + carry from previous addition.

Shouldn't that be:
Xpos = Xpos + carry from previous addition?

Quote

NOTE: it will take at least 2 updates to change Xpos by 1 pixel.   To get a higher velocity for the object you need to either add Xvelocity multiple times each display frame, or extend it to 16 bits just like Xwhole.

Or use 8 bits and shift before adding.

Quote

Doing gravity is another problem entirely, and I will have to think about it and propose a solution later.   Basically you need to find a quick way to  calculate the distance from the gravity source to the object = SQRT(Xdiff^2 +Ydiff ^2) = nasty , and then mulitply that times some gravitational factor for the object yielding an acceleration that you must proportionally divide between Xvelocity and Yvelocity based on the angle of the object to the source. 

Space War has some pretty realistic looking gravity in there. The whole physics are done really well. Unfortunately the orginally choosen parameters make the physic almost unrecognizable. I discovered this when doing the PDP hack.

Quote

The real question is, how realistic does this need to be?  Are you willing to go with an approximation of gravity or do you need a NASA grade simulation?

Yup, that's the question. Do you want the physics exact or just convincing?

Edited by Thomas Jentzsch, Tue Mar 7, 2006 10:18 AM.

[Robert M]

Thomas Jentzsch, on Tue Mar 7, 2006 10:11 AM, said:

Quote

If Xvelocity is negative THEN  // The MSB is set.
     Xadjust = $FF      // for a negative velocity you must extend the sign to 16-bits.
ENDIF

I don't get this part. Negative velocity works exactly like positive one.

I was skimping in my example, probably a bad idea to teach the concept, but my urge to save a byte of RAM won out. In the example, I am using only 8 bits to hold the velocity rather than 16. Since the velocity is a signed value I need to extend the sign bit of the 8-bit velocity make a 16-bit value before I can add it to the 16-bit position.

EDIT: A better name than Xadjust would have been Xsignextend

Cheers!

Edited by Robert M, Tue Mar 7, 2006 10:33 AM.

[YOK-dfa]

Thomas Jentzsch, on Tue Mar 7, 2006 5:11 PM, said:

Quote

The real question is, how realistic does this need to be?  Are you willing to go with an approximation of gravity or do you need a NASA grade simulation?

Yup, that's the question. Do you want the physics exact or just convincing?

YOK-dfa, on Tue Mar 7, 2006 2:30 PM, said:

The trajectory doesn't have to be 100% correct, as long as it looks convincing.  I don't need complete instructions, but just some pointers to info or something would be appreciated too...

The algorithm i figured of using was that you take the object trajectory is a vector and when you get close to a planet you calculate the vector from the object to the planet. Then you take the weighted average of those vectors to get the new movement vector for the object. The closer the object is to the planet the higher the weight of the vector that points to it's center.

Something like this:

Vector(new) = ( Vector(pointing from object to center of planet) x Weight + Vector(old) x (Weight - 1) ) / 2

where Weight is bigger as the object is closer to the planet. Problem here is ofcourse calculating the value of the vector that points from the object to the planet. I could use tables for this, but again, i have very strict memory restrictions...

[Robert M]

Thomas Jentzsch, on Tue Mar 7, 2006 10:11 AM, said:

Quote

Xfraction = Xfraction + Xadjust 
Xpos = Xpos + Xadjust + carry from previous addition.

Shouldn't that be:
Xpos = Xpos + carry from previous addition?

Sorry Thomas, I edited that mistake. It should be:

Xfraction = Xfraction + Xvelocity
Xpos = Xpos + Xadjust + Carry from previous addition.

Sorry for the confusion.

[Thomas Jentzsch]

YOK-dfa, on Tue Mar 7, 2006 5:44 PM, said:

YOK-dfa, on Tue Mar 7, 2006 2:30 PM, said:

The trajectory doesn't have to be 100% correct, as long as it looks convincing.  I don't need complete instructions, but just some pointers to info or something would be appreciated too...

Got you now.

Quote

The algorithm i figured of using was that you take the object trajectory is a vector and when you get close to a planet you calculate the vector from the object to the planet. Then you take the weighted average of those vectors to get the new movement vector for the object. The closer the object is to the planet the higher the weight of the vector that points to it's center.

IMO the position and the speed define the vector very well. The center of the gravity and the strengh of it would define the other vector. Then you just have to add the gravity vector strength to the speed to get the new, resulting speed. And finally the speed to the position to get the new position.

The "only" remaining problem is calculating the gravity strength (or weight).

[YOK-dfa]

Thomas Jentzsch, on Tue Mar 7, 2006 6:52 PM, said:

The "only" remaining problem is calculating the gravity strength (or weight).

I think i just have to experiment with some random values until i find some convincing values. The 'pull' of the planet is constant i guess, and the weight is probably some quadratic function of the distance.

weight = constant * (distance ^ 2)

I just hope i have enough space left for the actual gamecode after implementing all this math stuff It's supposed to all fit in 2K...

[batari]

Thomas Jentzsch, on Tue Mar 7, 2006 11:11 AM, said:

Robert M, on Tue Mar 7, 2006 5:00 PM, said:

If Xvelocity is negative THEN  // The MSB is set.
    Xadjust = $FF      // for a negative velocity you must extend the sign to 16-bits.
ENDIF

I don't get this part. Negative velocity works exactly like positive one.

The integer portion doesn't need special consideration. But when negative, the fractional bits are inverted (if this makes any sense.) So to perform proper arithmetic you need to check the sign bit of the integer portion to see what you need to do with the fractional part.

[djmips]

batari, on Tue Mar 7, 2006 6:08 PM, said:

Thomas Jentzsch, on Tue Mar 7, 2006 11:11 AM, said:

Robert M, on Tue Mar 7, 2006 5:00 PM, said:

If Xvelocity is negative THEN  // The MSB is set.
     Xadjust = $FF      // for a negative velocity you must extend the sign to 16-bits.
ENDIF

I don't get this part. Negative velocity works exactly like positive one.

The integer portion doesn't need special consideration. But when negative, the fractional bits are inverted (if this makes any sense.) So to perform proper arithmetic you need to check the sign bit of the integer portion to see what you need to do with the fractional part.

You can treat fixed point addition and subtraction as you would regular two's complement addition and subtraction. Just use an extra byte and have a 16 bit (s8. velocity and add that to the a 16 bit position. Then there is no need to check the sign and create a temp Xadjust variable. This is a little more clear and flexible ( allows you to have velocities that are greater than 1 per update)

[Thomas Jentzsch]

djmips, on Thu Mar 9, 2006 12:04 AM, said:

You can treat fixed point addition and subtraction as you would regular two's complement addition and subtraction.  Just use an extra byte and have a 16 bit (s8. velocity and add that to the a 16 bit position. Then there is no need to check the sign and create a temp Xadjust variable. This is a little more clear and flexible ( allows you to have velocities that are greater than 1 per update)

Yup, and that's what did in my minigames. The resulting code is pretty compact and elegant, using a small subroutine for all 16 bit math.

But he is short of RAM and probably has more than one object moving around. So saving two bytes for speed for each object is probably a good compromise.

[batari]

djmips, on Thu Mar 9, 2006 12:04 AM, said:

You can treat fixed point addition and subtraction as you would regular two's complement addition and subtraction.  Just use an extra byte and have a 16 bit (s8. velocity and add that to the a 16 bit position. Then there is no need to check the sign and create a temp Xadjust variable. This is a little more clear and flexible ( allows you to have velocities that are greater than 1 per update)

Easier but at the expense of RAM. Plus, acceleration in s8.8 would need four more bytes... Maybe even 6 (gravity is 1-D, and thrust is 2-D.) For a Lunar Lander game using only s8.8 you might need 14 bytes per object.

In my game Superbug, I'm doing things a little differently. Position is s8.8 but I have a velocity in polar coordinates (magnitude and direction) which takes two bytes total. (Four bytes would be needed for X and Y components in s8.8.). Acceleration is usually small anyway, so I don't even store it and just add immediates to the velocity, as it always occurs in the same direction the car is pointing anyway (just like a Lunar Lander's thrust would.) But in doing so I need to check the sign bit of velocity to see if I need to add or subtract immediates.

That's what I was talking about, but was too tired to explain better at the moment

Although the math starts to get tricky, there is opportunity to save RAM here.

[Bruce Tomlin]

Basically, the difference between fixed point and floating point is that floating point has an exponent.

Fixed point is like if you were trying to multiply 2.2 by 3.3. If there is always going to be one digit after the decimal point, then it's "fixed". So you can store them as 22 and 33. When you multiply, you have to remember that you now have more digits after the decimal point. 22 * 33 = 726, but your result now has two decimal places, so it's 7.26. Then you can round or truncate the result, or you can use it as a fixed point number with two decimal places.

In binary, you can do this in lots of ways. Usually in 16 bits, it's done in nibbles. So you can have a 4.12 number, an 8.8 number, or a 12.4 number. The former has a small range but more precision. The latter has a large range but less precision. You just do regular math on them, and shift the result as necessary when multiplying.