X² Math library - fixed point decimal & trig functions

[Reven]

Download
ftp://ftp.excelcia.org/x2/scripts/libma ... d_v101.zip

Introduction

While researching for another tutorial, I was struck by the lack of support in scripting for certain things. Namely, there is no way to really manipulate coordinates.

For example, if you want to calculate a point 5 km away in the direction your ship is pointing. You can't really do this, since there is no floating-point numbers, no trig functions, and no scripting commands that will project courses forward.

There is a way, though - it's just more work. Before computers had nice fancy floating point units built in, back in the ancient days of the Commodore 64 and Apple ][, games that were 3D didn't use floating point. Calculating floating point results without a coprocessor is very time intensive. What programmers back then did as a trick to speed things up, was to use integer numbers and treat them internally as "fixed point" decimals.

Fixed Point

Fixed point is just a different way of thinking of a number, that's all. For example, take the integer 15225 - you look at that and see "fifteen thousand two hundred twenty-five", but that is just a convention. That could also be "fifteen point two two five". Depends on what you want to use it for. After all, the only difference between a fractional number and an integer, is where you put the decimal point.

Let's imagine, then, that integer numbers aren't integers at all. Let's imagine that they are all fractions with a decimal point and three digits after the decimal. An integer that is storing "1", would then be 1/1000, or in common notation 0.001. So, if we consider all integers to be decimals instead, we can use integers for math that normally we would need a floating point for. This is what fixed point is.

There are some changes we need to make in the way we do some mathematical operations, though, when we use integers this way. This is because we're performing fixed point math on a system that doesn't know we are. When you want to multiply two numbers that are integers, but that you want to think of as fixed point, then after each integer multiplication, you need to shift the decimal point over. The reason for this can be shown with an example. Let's say we have two fractional numbers we want to multiply:

1.125 Χ 8.000 = 9.000

In our method of using integers as fixed point decimals, though, we are representing the numbers like this:

1125 Χ 8000 = 9000

When we actually perform the math to multiply 1125 Χ 8000, the result we get is (of course) 9000000, and not 9000. This is because the computer doesn't know that we want to think of them as decimal numbers instead of integers. So, each time we multiply, we have to manually "move" the decimal place back over to where it shoult be...

1125 Χ 8000 ÷ 1000 = 9000

The added division by 1000 shifts the result's decimal place over where it should be, and we are happy.

Addition and subtraction won't require any special consideration. As long as both numbers are "fixed point" with the same number of digits after the decimal, we can add and subtract away like normal.

Trigonometry

But, being able to add/subtract/multiply/divide fixed-point decimals doesn't do anything for being able to, say, project a course forward. We need trigonometry, and there aren't any trig functions in X²'s scripting commands.

So, I dredged up my math. Wow - there really is a reason why I might want to calculate a cosine by hand. I mean, who really believes a math teacher or professor when he says "you might need this some day".

The explanation of the trig functions is a little technical - feel free to skip ahead to the section on the library scripting commands if you're not interested.

Calculating sines and cosines manually can be done with the following formulae:

• Sin θ = θ - θ^3/3! + θ^5/5! ±…
  Cos θ = 1 - θ^2/2! + θ^4/4! ±…

These formulae assume that the angle, θ, is in radians. Also, it assumes that 0 ≤ θ≤ ½Π. This isn't bad, because standard trig identities will allow us to use this formula anywhere on a circle.

We could use this formula ad infinitum, but since we are dealing with a fixed number of digits after the decimal, it doesn't make sense to go hog wild. Going as far as actually shown in the formulae above is good enough, though it will be a little off when an angle is close to a multiple of 90 degrees. The more "in the middle" the angle is, the more accurate we'll be.

LIBMATH

After I'd dredged up all my old math lectures, I decided to write a library that would handle this stuff. After all, spending my time dredging up memories of math isn't my idea of something to do all the time. Happily, the X² scripting language is eminently set up to handle repetitive tasks. Each script can return a value to its calling script, thus, we can write functions.

All we need are multiplication, division, and whatever trig functions we want to use. Remember, addition and subtraction in fixed point don't need any special handling.

There are some things we need to remember, though:

X² and Angles

In normal math, angles are usually either in degrees (0-360), gradians (0-400), or radians (0-2Π). In order to be different, X² returns all angles as a number between 0 and 65535 (16 bit angles). Since this is the case, it makes sense to have all the trig functions handle angles of this type. If that's what we have, then that's what our functions should expect.

How Big

What we are doing when we use integers as fixed point decimals, is trading range for precision. That is, every integer number in a computer has a maximum and minimum value. Since X² uses 32-bit integers, that gives us 2³², or 4,294,967,296 combinations. Since one bit is used to specify whether the number is negative or not, we are left with 2³¹ values above zero, and the same below. Or in other words, a range of between -2147483648 and 2147483647. When you are using these as fixed point numbers with three digits after the decimal, this means that 2147483.647 is the largest number you can have. We have reduced the maximum value we can store by a factor of 1000, but we hace also increased the precision by a factor of 1000 too. We can't get something for nothing.

Additionally, when you perform several operations with fixed-point numbers, you get rounding errors. Because you never have more than three decimal places of precision, each operation rounds to the nearest thousandth. If you perform several operations in a row, like you would need to in a formula, then each subsequent operation makes the result more inacurate. So, when writing math functions that handle fixed point, it's good to internally use more precision than you need at the end. This ensures that you don't compound rounding errors at each step.

However, as we've discussed, in fixed point more precision means less range. If our library functions use 4 decimal places internally, this reduces our range to ±214748. No operation can exceed that at any point, or else we'll overflow the 32-bit integers we're using, and our result will be garbage. Since ±214748 is enough range for most purposes, this is a tradeoff we accept in this library in order to make it more accurate.

Additionally, in order to make the calculating of formulae as accurate as possible, it's good to provide functions that multiply not just two values, but more than that. This is because we can shift the precision up to 4 decimal places internally for the entire series of operations, not just for each 2-number multiplication. Then at the end, shift back and give the result. So, our library should supply functions which allow multi-number multiplications, and when we use it, we should try and write our scripts to calculate formulae using as many multiplications at once as possible, and try and avoid the rounding errors that occur when you perform single operations many times.

The Functions

We'll go through two sample functions for the library - one multiplcation and one trig. If you're impatient, feel free to skip to the end where we actually do something with all this.

libmath.fixed.mult4

Code: Select all

Arguments:
    * 1: Mult1 , Var/Number , 'First value'
    * 2: Mult2 , Var/Number , 'Second value'
    * 3: Mult3 , Var/Number , 'Third value'
    * 4: Mult4 , Var/Number , 'Fourth value'

$Product = ( $Mult1 * $Mult2 / 100 * $Mult3 / 1000 * $Mult4 + 5000 ) / 10000
return $Product

A simple function to multiple four numbers together. We talked about using an extra decimal place of precision, remember, to aid overall accuracy. This is done after the first multiplication. Remember, we need to divide to shift the decimal place after each multiplication. In this case, the first time we divide to shift the decimal place, we only divide by 100 instead of 1000. This steps the result up to an extra decimal point of precision. At the end, we divide by 10000 to shift back. Before the last division, though, we add 5000 in order to round the result.

libmath.fixed.sin

Code: Select all

Arguments:
    * 1: Theta , Var/Number , 'Theta'

001   * Convert to fixed point and invoke wrapping function
002   $Theta = $Theta mod 65536 * 1000
003   * Formula only works on first 90 degrees, so we find out what quadrand we are in
004   if $Theta >= 49152000
005    $Theta = 65536000 - $Theta
006    $Sign = -1
007   else if $Theta >= 32768000
008    $Sign = -1
009   else if $Theta >= 16384000
010    $Theta = 32768000 - $Theta
011    $Sign = 1
012   else
013    $Sign = 1
014   end
015   
016   * Convert Theta to radians and increase precison to 4 decimal places
017   $Radians = ( $Theta / 65536 * 62832 + 50 ) / 1000
018   * Sin Theta equals Theta minus Theta cubed over 6 plus Theta to the fifth over 120
019   * If Theta is in Radians and between zero and half Pi
020   * Not exact, but good enough for the 4 decimal place fixed point we are using
021   $Sin = ( $Radians - $Radians * $Radians / 10000 * $Radians / 60000 + $Radians * $Radians / 10000
          * $Radians / 10000 * $Radians / 10000 * $Radians / 1200000 + 5 ) / 10
022   $Sin = $Sin * $Sign
023   *$Message = sprintf: fmt='Theta %s Radians %s Sine %s', $Theta, $Radians, $Sin, null, null
024   *send incoming message $Message to player: display it=[TRUE]
025   return $Sin

A little more complicated function here to approximate the sine of a number (theta).

The first part of the function converts the angle we get (0 to 65535) to fixed point and wraps it in case it's larger than 65535. The formula only works on the first ½Π radians (first 90 degrees). So, after we wrap the angle, we need figure out which part of the circle we are in, so we can adjust our result. The rest of a sine wave is identical to the first 90 degrees. The second 90 degrees is the same as the first, flipped horizontally so that it's decreasing again. The next 180 degrees are the same as the first, just below zero instead of above. We adjust our incoming angle so that it's between 0 and 90 degrees, then we set a sign variable that lets us know whether we should have a positive or negative result.

Line 16 is where we convert our input angle into radians and then step up to 4 decimal place fixed point. It's hard to see how we step uo to 4 decimal places - it's done when we multiply by 2Π. We use 62832 to add a nother decimal point of precision during that multiplication, instead of 6283. Then, even though we are dividing by 1000 again, we are shifting the decimal left 3 places when the previous multiplication shifted it right by four. This gives us the extra precision.

Line 21 executes the formula, rounds the result, and steps back down to 3 decimal places at the end.

What can we Do with it?

All right, so 10 out of 10 for geekness factor, but can you dance to it? This is the question.

Here is a sample of what can actually be done with fixed-point math and trig:

AsteroidFront

This function will ask for a range from the user. It then will look at the current location and heading of the player's ship, and create an asteroid in front of the ship at the range you specify.

Code: Select all

Arguments:
    * 1: Range , Var/Number , 'Range in metres'

001   * 
002   * Example of libmath - create an asteroid in front of the player ship
003   * 
004   * Written by Kurt Fitzner a.k.a. Reven
005   * 
006   
007   * Get the location and heading of the player ship
008   $X = [PLAYERSHIP] -> get x position
009   $Y = [PLAYERSHIP] -> get y position
010   $Z = [PLAYERSHIP] -> get z position
011   $Alpha = [PLAYERSHIP] -> get rot alpha
012   $Beta = [PLAYERSHIP] -> get rot beta
013   
014   * We need the sine and cosine of both angles, so we do it all at once
015 @ $sinAlpha = [THIS] -> call script 'libmath.fixed.sin' :  Theta=$Alpha
016 @ $cosAlpha = [THIS] -> call script 'libmath.fixed.cos' :  Theta=$Alpha
017 @ $sinBeta = [THIS] -> call script 'libmath.fixed.sin' :  Theta=$Beta
018 @ $cosBeta = [THIS] -> call script 'libmath.fixed.cos' :  Theta=$Beta
019   
020   * Calculate the offset of the asteroid
021 @ $Offset.X = [THIS] -> call script 'libmath.fixed.mult4' :  First value=$Range 
        Second value=$cosBeta  Third value=-1000  Fourth value=$sinAlpha
022 @ $Offset.Y = [THIS] -> call script 'libmath.fixed.mult' :  Multiplier=$Range  Multiplicand=$sinBeta
023 @ $Offset.Z = [THIS] -> call script 'libmath.fixed.mult3' :  First value=$Range
        Second value=$cosBeta Third value=$cosAlpha
024   
025   * Add the offset to the ship coordinates to get the position of the asteroid
026   $X = $X + $Offset.X
027   $Y = $Y + $Offset.Y
028   $Z = $Z + $Offset.Z
029   
030   * Create the asteroid
031   $Sector = [PLAYERSHIP] -> get sector
032   $Asteroid =  create asteroid: type=1 addto=$Sector resource=0 yield=10 x=$X y=$Y z=$Z
033   return null

We'll pay more attention to the example than we did to the math functions, as there are several "gotchas" in X² when it comes to angles, coordinates, and trig.

• Argument: Range
  The range is the argument for this script. The nice thing about ranges in X² is that they are all calculated internally in meters. So, if we simply think of any range or any coordinate as being in kilometers instead, then we don't need to adjust them for our fixed point method. We use 3 digits of fixed point, so an integer representing meters is the same as a fixed point number with 3 digits after the decimal that represents kilometers (1000 meters to the kilometer, after all). This is the major reason why I decided to use 3 digit fixed point for the library.
• Lines 8-12
  Here we simply get the current location of the ship, and also the heading. There are three angles for the heading, Alpha, Beta, and Gamma. Alpha is the bearing of the ship. Beta is the elevation. Gamma we don't need, since it's the rotation of the ship, and that isn't needed to figure out where "in front" of the ship is.
• Lines 15-18
  We end up using the sine and cosine of both angles, so we just go ahead and calculate them here.
• Line 21 - X offset
  We calculate the X offset of the asteroid here. The standard formula (X = r∙cos β∙sin α) has to be adjusted. One, there is some weirdness in X² with the Alpha angle. In a standard coordinate system, the angle will increase as you turn clockwise. In X², it increases as you turn counter-clockwise. This means any formula you use to calculate a position on the X axis using trig and angles will need to be reversed. This is why we multiply by -1000 (-1.000) - so the formula we end up using is X = r∙cos β∙-1∙sin α
• Line 22 - Y offset
  The Y axis in X² is the up/down axis. If you are looking at a "top" view of a sector (the normal sector map), then Y is going down into the monitor, or coming up out of it. In a normal coordinate system, you would think of Z as doing this, so we use the Z axis formula on X²'s Y axis. The formula we use here is Y = r∙sin β
• Line 23 - Z offset
  As mentioned above, the Y and Z axes in X² are sort of reversed from what one might think of as normal (actually, most 3D games work this way). So, the formula we use for this offset is Z = r∙cos β∙cos α
• The rest
  The rest should be self explanatory. We add the offset to the ship's coordinates, and plot an asteroid down at that location.

The program actually works. Honestly, at the end of my research into this, I was actually quite surpised it worked. Screwing around with fixed point, approximating trig functions... I half thought by the time I got around to getting a coordinate, that I'd be lucky to drop an asteroid into the same sector. But, here is what happened when I placed one 500 meters in front of my ship:

[ external image ]
Asteroid 500 metres off my bow

If you look carefully, it seems to be very slightly off to one side. It might be the shape of the asteroid, but more likely it's some of the inaccuracies in the whole method. But, it at least shows fixed point math is practical in X².

[moggy2]

Thank you god

I've been putting off certain projects because the script editor was missing this, and my Maths stinks . I was beginging to think I was going to have to go and work all this out again for myself. Thankyou very much.

[Reven]

I half wondered if anyone would even find this useful. I'm just thrilled that someone will get some use out of it.

[Nemesi$]

Don't forget to link it in your Sticky-Thread ;]

[The_Rock]

Don't forget to link it in your Sticky-Thread ;]

Indeed. :)

Great work as usual Raven.

[The_Abyss]

Great work Reven!

[Reven]

I've already linked it in to the sticky-thread tutorial list, it's just at the end of the list, since it doesn't fit with the series as originally proposed. Though, I'm not really sure if I have authority to do this or not. Can a moderator let me know if that's allowed? Simply because I write a tutorial doesn't mean it automatically deserves mention in a sticky thread, so should I leave the tutorial list alone?

Anyways, I also went over this tutorial and added to it a little. When I read it over again today, it seemed a little abrupt in places. This is because it was originally written as a README file for the library, and then expanded into a tutorial. I've tried to fill it out with some more explanation in places where it was weak.

If you would like to write scripts that can calculate positions in a similar way to the example, and if the explanations in the tutorial are confusing, post what you're confused about and I'll try and clear it up in the tutorial.

Thanks to all for the comments!

[ZeligtheLiar]

So this is what you've been doing the last few days.
Awesome work Reven! This will almost certainly revolutionalize many scripts.

[Shadowfax2]

OMG Reven

I'm not going to pretend I understand it or will be able to use it.

I don't know what you do for a living but yikes! Great work as always!

[Troj]

Domo Arigato , Mr Reveno

[Troj]

Don't forget to link it in your Sticky-Thread ;]

Lol, good signature

[Reven]

I don't know what you do for a living but yikes! Great work as always!

Software project management and programming... but, I'm hoping to get a job with Egosoft. Think I've got a chance?

[Shadowfax2]

Reven, you impressed the hell out of me, you got my vote...

Unfortunately I don't work for the HR dept of Egosoft...or any other dept of Egosoft for that matter although I wish I did.

I would have loved to have been able to beta test for them.

I did beta testing for a couple of the Star Fleet Command games and it was really fulfilling hunting/killing bugs on a software title that brought to the screen my favourite paper/pencil game.

Ah well, we can all have dreams. I just got to live mine for a little while.

[Reven]

I've posted a new version (1.0.1) of libmath. Anyone who has downloaded the library should upgrade to the new version. It fixes a bug in the sin & cos functions where angles between 32768 and 49152 (180 and 270 degrees) would return incorrect answers. Also, it increases the sin & cos accuracy somewhat.

You can download it at ftp://ftp.excelcia.org/x2/scripts/libma ... d_v101.zip

[OnlineKenji]

Too bad I didn't see this until after I had made my own MATH functions. I modeled them after the MATH objects in Javascript. Great work anyway, thanks for your contributions to this fine community

[IvanT]

Incredible post Reven.. many thanks for all of this. I think we're going to see some fantastic mods with the kind of background work that you've provided.
Much appreciated.!
IvanT

[JustHere4Coffee]

months after this work was created, months after the last comment, I've had an idea that I hope I can implement using these mathlibs...

thank you so much for making them!

[Kailric]

Is there a working link to this somewhere?

[JustHere4Coffee]

Is there a working link to this somewhere?

send me a pm to remind me, and I'll see about uploading it somewhere - it's at home, I'm at work... alternatively, keep trying the original link, it worked only a couple of weeks ago, maybe it's an intermittent fault at the server

[theojk]

I tried to use your libmath and your AsteroidFront, but is doesnt work in all directions. So I wrote a script to test all angles between 0 and 360 degrees (actually 0 to 65536).
I have found 2 sign-errors in the cosinus-funktion:
- for angles between 16384 and 32767 (source line 006 must be Sign = 1)
- for angles over 49152 (source line 012 must be Sign = -1)