Coordinates & Compressed Space
The Milky Way is 120kly (ish) according to Wikipedia. That's kilo-light years. That sounds big! Ok lets say I want to positiom things with millimetre accuracy. A light year is 9.4605284 × 10^18 millimetres (thanks Google!) So the milky way is approx 1.13526341 × 10^24 millimetres across. 1135263410000000000000000 mm. How many bytes are needed to store a number that big? My calculations put this at 10 bytes. That's a nice chunky number. If we want multiple galaxies or more accuracy we need more bytes too. I'd probably round this up to a lovely 12 bytes.
So I have a super number which can store galaxies to mm precision, except its too big to fit in CPU registers and so all math is horribly complicated and slow. No thanks!
For a game to have a chance of managing this I need to keep the coordinates in a useful form.
There are a few solutions to this problem and I'll outline the one I'm going to try first. I'm going to keep rendering and physics working in lovely floating point numbers. The main reason is that everything is simple when using these, though they lose accuracy pretty quickly. To deal with this I'm going to have reference points evenly distributed across the universe, creating a classic nested coordinate system. All floating point numbers will be local to one of these reference points.
These reference points will have a volume of space defined around them so they overlap the next reference point by 50%. When you move far enough from your ref point the game will switch which point you're anchored too. I need to be careful that these switches dont introduce too much error or performance penalty.
An objects coordinates will be split into a local space floating point position and a reference point ID. The reference points may also need to be put within a nested coordinate space to get extra space, and that can be repeated as many times as necessary.
I'm considering only allowing interactions between objects living in the same reference point, as it will simplify things. We'll see how that plays out.
Finally from a gameplay point of view I'm planning to allow the scale of the generated universe be controllable. I doubt very much that a real size scale for most things will be the default setting. I don't want people dying of old age travelling. I'll aim to reduce how much boring space there is between interesting things without breaking the illusion. This applies to many things, not just the distance between planets. The distance between cities or continents or any feature of interest. Sure people can have 1:1 if they want though! I suspect that space travel will still need FTL drives, stasis pods or wormholes to get around and not die of boredom!