Apologies if this is in the wrong forum, but its both a math AND a C++ related matter, so if I am in error, please accept my apologies. I am currently working on something that fits into neither of my previous areas of exploration (high-precision positioning OR large area positioning). I would be interested in hearing from other people what their experiences are with the following task: Environment: 1) "Static" (non-expanding) Universe, measuring n x n x n Light years, where n is almost the absolute limit of the long long datatype. 2) Numerous celestial bodies Data: 1) There are 1000m in a kilometre. 2) There are 9 trillion km in a light year Requirements: 1) While travelling in space, an "intergalactic coordinate system" should be used, with the "root" (0,0,0) of the universe coordinate system being at the centre of the universe. For the purposes of this discussion, lets make the universe cube-shaped (in game this is somewhat different, but not majorly so). 2) The universe remain as large as possible (not scale down just to make life easy) to allow for high tech level ships that are faster than light capable (i.e prioritise maximum playing area over development simplicity). 3) Position accuracy whilst in space need only be 1m. However it may be necessary to provide higher resolution, which would mean either making the Metres portion of the coordinates a float, accurate to 2 dp, or adding a "very fine" component to the coordinate system, measuring centimetres. 4) Due to the extreme distances involved, the game clients need to see space coordinates in the form: GLY-MLY-LY-AU(or MKM)-KM-M, even if the underlying data is held in a different format (such as LY-KM-M for example). 5) Objects and their positions will be distibuted across a number of server nodes. The requirements of comparing position of object A with the position of object B are as standard (collision detection for example) 6) The "parsec" is not appropriate for this environment, as it is derived from observational data and is not trivial for players to understand. Problems: Ignoring the DISPLAY of the coordinates on the client-side for a moment (JUST dealing with how the information is actually stored in various objects on the server-side).... 1) Providing sufficient scope, whilst providing sufficient accuracy. 2) The balances between functionality, simplicity and accuracy are a bit of a bugger to be frank. 3) providing the simplest way to accurately compare objects positions based on their coordinates 4) For any component in the coordinate system, automatically "rounding up" the various components to their next highest neighbour. (e.g. 10 trillion KM rounds up to 1 and a bit light-years). My initial thoughts about how to address this centred around 3 main approaches. 1) Using a master "position" struct, comprising of 4 structs relating to Coarse, medium and fine (Light years, kilometres and metres) 2) a position class 3) simply using separate variables for the light-year, km and m values Using structs is ok. however, maintaining the data is not so straightforward. Modifying an objects position requires an external mechanism to feed in the correct order of data, for example, adding 3 LY and 900,000,000 KM to a position that is currently 4 LY and 9.9 trillion KM SHOULD yield 8 LY 1,000,000 KM, but without intervention (rounding) will yield 7 LY and 10 point something trillion KM. Using classes seems to be the most compact method, in that all the methods for dealing with the coordinate system can be contained all in the one class. Moreover it would support / assist in the distributed nature of the system as object serialisation methodologies are quite common. however this does seem to increase overhead and has a slightly "clunky" feel, something like using a sledgehammer to crack a nut. Simply using separate variables to hold the positional data would seem to offer all the problems with methods 1 and 2, with none of the rewards. However it is very simple, would add little in the way of overhead and traffic. It does not lend itself to tidy coding though and would be horrendous to fix should the coordinate system ever need to change. I have given a lot of thought to how to address the problems and requirements stated above. Currently I am in two minds as to whether I should go with a struct or a class and a third mind as to whether there is something more suited to this problem or even a solution that encompasses both and yields a more simple, flexible solution. To that end, I am hoping that someone else who has looked at this problem could perhaps give me "food for thought" or perhaps some anecdotal evidence from someone more experienced who has tried this and has definite ideas on what "works" and what doesnt. Sorry for the long post by the way, I was attempting to be thorough and provide all the information in one go, rather than wasting peoples time by making them ask me questions I can provide the answers to straight off the bat. Regards Richard

A long long is 64 bits. Your cube is then 2^64 light years on a side (that was the requirement you expressed, no?). A light year is just under 10^16 = 2^{16/log_10(2)} ~= 2^53 meters. Hence your cube is a little under 2^(64+53) = 2^117 meters on a side. Let's round 117 up to 128 and represent all your coordinates by 128-bit integers (which can be implemented as a class containing two long longs and having some overloaded operators). Then your possible positions will be a lattice with spacing between points of under half a millimeter.

Emergent,

thanks for replying. Originally, I did want to use 128 bit integers to represent the information as it is quite straightforward. I'll add that to the pool of things Im going to try and see which of the methods works out the best.

Thanks again for taking the time to reply.

Re. your PM...

1.) Re.: 'not entirely clear on how you came to the conclusion that I would have "half milimetre" resolution':

I worked out above that your cube is roughly 2^117 meters on a side. So, it could be represented to a meter resolution with 117 bits per coordinate. If we instead use 128 bits, we have an extra 11 bits. This further subdivides each meter interval into 2^(-11)--meter intervals. 2^(-11) = 0.00048828125, which is just under 0.5*10^(-3) meters -- half a millimeter.

(EDIT: This is after a lot of rounding on my part, but I was always conservative with my rounding, so really treat the 0.5mm as an upper bound on the distance between grid points; you'll in fact do even better than this.)

2.) Re.: 'Roll my own [128-bit datatype]'

Basically you'd just implement the "gradeschool algorithms" for arithmetic. For instance, for addition, you'd add the lower ("least significant") bits, and carry any overflow to the upper bits, which you subsequently add... I'm not sure what reference to refer you to (I guess I learned this as a side effect of electronics courses?); maybe someone else can recommend something simple and to-the-point... I bet you that this is something you can figure out with a pencil and paper on your own though... (I may also have some example code kicking around I can post that you can learn from, though it's not specialized to the 128-bit case...)

[Edited by - Emergent on March 22, 2010 3:01:08 PM]

Another option would be to use integer coordinates (32 or 64 bit) for "grid cell location" plus 32 bit floats for a local coordinate system. This might be faster than using large integer classes and would provide reasonable precision if you keep your grid cell size relatively small (~1km). It would require some logic overhead to keep track of the grid cell coordinates. Basically, if an object exceeds some distance from the origin along an axis, either add or subtract from the local coordinate position and subtract or add to the grid coordinate position.

Another advantage of this system is that you can keep your rendering data as 32 bit floats, though you would have to split objects into chunks smaller than the grid size or risk losing precision. Doing small-scale physics simulation is also made easier; most physics libraries use 32 bit floats internally.

If you used doubles instead for the local frame, your grid cells could be much larger, reducing the need for complex object splitting.

If you're looking to model the galaxy, you could use 64 bit grid coordinates and 64 bit floats for a total of 117 bits of precision (64 + 53 bit mantissa).

However, it might just be simpler in the long run to use a fixed point arithmetic scheme like Emergent described.

A quick google turns up the MUNTL library, which looks like it probably does what you want. I haven't used it myself, but I get the impression that to use it you define integer sizes at compile time with template arguments, and that seems like a good fit for your case.

Quote:Original post by Emergent
Re. your PM...

1.) Re.: 'not entirely clear on how you came to the conclusion that I would have "half milimetre" resolution':

I worked out above that your cube is roughly 2^117 meters on a side. So, it could be represented to a meter resolution with 117 bits per coordinate. If we instead use 128 bits, we have an extra 11 bits. This further subdivides each meter interval into 2^(-11)--meter intervals. 2^(-11) = 0.00048828125, which is just under 0.5*10^(-3) meters -- half a millimeter.

(EDIT: This is after a lot of rounding on my part, but I was always conservative with my rounding, so really treat the 0.5mm as an upper bound on the distance between grid points; you'll in fact do even better than this.)

Yep, thats pretty much what I thought you were implying, but I didnt want to assume. Thanks for clarifying and yes, thats the ideal. I had (again) intended to include a short integer to provide the sub=metre accuracy, but your way is more elegant.

Quote:
2.) Re.: 'Roll my own [128-bit datatype]'

Basically you'd just implement the "gradeschool algorithms" for arithmetic. For instance, for addition, you'd add the lower ("least significant") bits, and carry any overflow to the upper bits, which you subsequently add... I'm not sure what reference to refer you to (I guess I learned this as a side effect of electronics courses?); maybe someone else can recommend something simple and to-the-point... I bet you that this is something you can figure out with a pencil and paper on your own though... (I may also have some example code kicking around I can post that you can learn from, though it's not specialized to the 128-bit case...)

Yup, I get where you're going. Its referred to in a lot of the papers Ive studied over the last few days as "gradeschool math" or "school math". Basically, the simple algorithms go:

1234
+5678
------

and then most of them split numbers up into either chunks like:

12 34
56 78

or reverse one of them (Im typing this from memory so that might not be right, Id have to check my notes - of which Im accumulating quite a pile) and then do some bit rotation.

A lot of them (especially the arbitrary math libs) have x number of elements in an array or linked list to represent the actual components of the type and then some other temporaries. Thats fine for arbitrary precision math, because of course the designer has no idea of the complexity of what the end user is going to do.
However, I know that 128 bit integers are as high as I need (for now - Im not completely stupid, Im going to use 2 system wide constants through the internals of the code, WORD_SIZE and MAX_INT for future portability) so it is quite frustrating that the solution I need is les complex than most of the math libs provide, but just out of reach of my current compilers >..<

I get how the basic algorithms go. The more difficult ones, well, I guess thats down to elbow-grease and patience. I'll get there :)

Ive done a fair amount of research over the weekend (long weekend for me, happy days!) and Ive covered the following topics:


1- Knuth (read relevant chapters from TAOCP and other books)

2- Examined a number of "BigInt" libraries and tools from various people

3- Looked at code from OpenSSL

4 - Looked at code from tomcrypt

5 - Examined "Bernstein" (using inline assembler for optimisation) - ** side note as I have control over the hardware, assembly optimisations might not be a bad idea, as an add+carry can be performed directly on two 64 bit integers)

6 - Karatsuba algorithm

7 - Using the __int128_t type in gcc (as they are all 64 bit boxes) - i can declare them, assign them (using hex only for some reason) but not display them or anything, so Im in some doubt as to how far along the __int128 implementation is in gcc, other than to say it appears to be only a "built-in" type in the compiler itself.

8 - GMP (far too much other stuff in there that I dont need and would pose a portability issue if I comitted to it.

9 - NTL - nice, but is too transparent. - again, would pose a portability issue.

At some point, 128 bit integers will make it into mainstream use and until then, I need to roll my own I guess. With that in mind, Im hoping to abstract it out enough that what is presented to the coder is a datatype. No aunties drawers or "write this as a string" nonsense.

That way - hopefully - I will be able to simply remove my custom type, leaving access to a native one.

Or not. and I'll lose my remaining hair (all 3 strands of it!)

RP

Quote:Original post by Aressera
Another option would be to use integer coordinates (32 or 64 bit) for "grid cell location" plus 32 bit floats for a local coordinate system. This might be faster than using large integer classes and would provide reasonable precision if you keep your grid cell size relatively small (~1km). It would require some logic overhead to keep track of the grid cell coordinates. Basically, if an object exceeds some distance from the origin along an axis, either add or subtract from the local coordinate position and subtract or add to the grid coordinate position.

Another advantage of this system is that you can keep your rendering data as 32 bit floats, though you would have to split objects into chunks smaller than the grid size or risk losing precision. Doing small-scale physics simulation is also made easier; most physics libraries use 32 bit floats internally.

If you used doubles instead for the local frame, your grid cells could be much larger, reducing the need for complex object splitting.

If you're looking to model the galaxy, you could use 64 bit grid coordinates and 64 bit floats for a total of 117 bits of precision (64 + 53 bit mantissa).

However, it might just be simpler in the long run to use a fixed point arithmetic scheme like Emergent described.

Thanks for taking the time to reply.

If Im reading right then what you're suggesting is splitting up the universe into zones (grid cells). I have designed the server-side so that the client handlers already use a dynamic resolution system: their scope (the area of the universe they cover) and - ultimately - the number of clients they handle is adjusted according to feedback from the load controllers. As this happens at the server-side management level I dont think it would cause any problems with another zoning scheme in place, but you are right when you say it would add some logic overhead, even if only at the management layer.

The rendering system is local to the game clients. Clients will not recieve absolute coordinates in the form we're discussing here unless they are within terrestrial bounds (which is another story altogether). They do get coordinates, but they are for display purposes only and presented in a watered-down user friendly way (GLY-MLY-LY-KM-M whilst in space and xxx,yyy,zzz whilst within 15,000m of a celestial body) used primarily for their own navigation and mapping tools. Galaxy names and numbers are also used for this purpose but not for internal positioning.

Whilst in space, the game clients are only fed updates on positions of objects that are within visible range (in the case of celestial bodies - this is a significant distance). But the coordinate system used by the game client is "local" interpretation of a _sector_ produced server-side specifically relevant to that client (a simple case of a bounding box defined only as short integers of the form x,y and z).

Quote:
1) "Static" (non-expanding) Universe, measuring n x n x n Light years, where n is almost

the absolute limit of the long long datatype.

2) Numerous celestial bodies



Data:

1) There are 1000m in a kilometre.

2) There are 9 trillion km in a light year

Better would be to create elementary cube as double*double*dounle where 1.0 equals to a meter to relate to your space.

I think that manualy writing constants, 9tril*1000m, will vaste precision or scale of scalar datatypes you already use for elementary cube vectors.


The nxnxn global vector should be double*double*double too, where 0.5 equals
half a elementary cube edge, thats max double.

So vector (10.5,10.5,10.5) is a toprightfront corner of 10*10*10 cube. The mantis part adresses the cube edge. So the global uniferse position of the vector is

(10.5,10.5,10.5)*2*halfcubeedge.

This should equal to vector (0.5,0.5,0.5)*doublemax always (linear algebra axiom).
Your actual transform logic can happen only in double*double*double space anyway. Thus (10.0,10.0,10.0)*halfcubeedge vector maps to (0,0,0) of your local cube vector, what is what you want.

You get global presision (lowestabsolutedoublevalue)*doublemax of a meter.
I would make the cubes a float edge to have better precision, yes cube is smaller then but you have maxdouble of them .

Vector I have mentioned,(10.5,10.5,10.5) is a corner of tenth cube, but how do you transform (10.6,10.6,10.6) vector to local space of tenth cube(the one the player is in)? Solution is to make 0.5 eaual to maxdouble/2, this way you can transform any reasonable neighbouring vector from different cube to local space of neighbour the player is in.

(10.5,10.5,10.5) maps to local vector (0.5,0.5,0.5)*cubedge
(10.6,10.6,10.6) maps to local vector (0.6,0.6,0.6)*cubedge
correct scene around player anywhere (considering his volume of scene is smaller than doublemax/2*doublemax/2*doublemax/2).