If you like the technical nitty-gritty details about game development, then you're in for a treat!
Posted by Spacew00t on Jul 26th, 2013
I knew going into SubLight that space was big, and I wanted to show people just how big it is. Little did I realize how much I myself would learn about the scale of the universe! For starters, we can say that the universe is about 15 billion light years in radius ( give or take a few billion). Okay, well that's big, but it's still pronounceable, not too intimidating, right? I mean, some people probably have that much money!
This is the deception that light years lull us into, because we assume a light year is a reasonably sized unit. In fact, it's unbelievably MASSIVE! It's so astonishingly large, that it's almost meaningless outside of scientific measurements. The problem I ran into while simulating universes in SubLight is the huge disparity between interplanetary distances, interstellar distances, and intergalactic distances.
When programming a game, you have to decide what your smallest measuring units represent, and in doing so, determine the max distance you can go from the origin of your Universe (since your computer often handles data in predefined ranges). Floats are often used, because they conveniently store decimal numbers, but they are inaccurate at large values. Because of the special way they store information, they allow a large range, but only at a certain accuracy. Once you get above a certain number, their inaccuracy is greater than 1. That means statements like this will return true:
Basically, the computer will think that ten quadrillion minus one equals ten quadrillion!
Still though, ten quadrillion, who needs a number that large? Unfortunately, SubLight does. If we wanted to simulate our universe, each of those units would have to equal more than 14,000,000 kilometers! That means the smallest distance our ship could ever travel is 36 times the distance the Earth is from our Moon! You’d be leaping all over the place, unable to orbit planets, dock with space stations, or even keep the camera smoothly tracking the ship! We’re looking for at least centimeter or millimeter accuracy here, the smallest amount someone could reasonably notice in game.
Okay, so if 10 quadrillion units isn’t enough, what is?
If you want real accuracy, you need to use a type of data that has rigidly defined limits. Although this means your units won’t be able to be as large, at least they’ll never be inaccurate! First, we have int, with a max value of 2,147,483,647, but as we’ve already established, 10 quadrillion isn’t enough, so 2 billion definitely won’t be enough!
The next option is the long, and with a max value of 9,223,372,036,854,775,807, or more than 9 quintillion. This sounds good! I had to look up what the name of it was, so surely that must be long enough to reliably simulate the universe. Well... unfortunately no, even that massive number only gives us accuracy down to 15,000 kilometers. Better... but nowhere near the millimeter accuracy we’re aiming for. What now? There aren’t many bigger datatypes, and since long got us most of the way there, why not two longs?
Assuming the first long represents everything to the left of the decimal point, and the second long is everything to the right of the decimal point... that could work!If the first long represents light years, and the second long a fraction of a light year, that gives us accuracy almost down to the millimeter, finally!
The actual value is closer to 1.02571254 mm per 0.0000000000000000001 units of our system, but damn, at least we can get accuracy out to 9,223,372,036,854,775,807 light years! Oh, wait... that’s a lot of light years... we were only shooting for about 15 billion! No problem, by changing 1 of our units to represent a gigameter (1 million kilometers) instead of a light year, we get 0.1 nanometers of accuracy out to 100 billion light years! Hot damn, we’ve got accuracies way smaller than we need at distances more than 5 times what we wanted!
What’s the cost of all this to your computer? At the end of the day, not much. Since floats take up about 32 bits, and our new two long data type is 128, it’s only a 4x increase in storage space for more than 900x the maximum distance. Since the universe in SubLight is procedurally generated, we can do trickery that requires us to only store the systems we’ve visited and interacted with. That means we can store the positions of a million systems in less than 16 megabytes (and I very much challenge you to visit a million systems!).
As for its cost on the CPU, I can only venture the vaguest guess that it probably won’t affect performance much, since there’s only a couple thousand of these two long units being messed around with every frame.
I know this was a rather dry and technical post, but hopefully it can shine some light on the issues of simulating distances on such an intergalactic scale! And remember, if you'd like to help fund development, you can buy the alpha here (or just download it for free in the downloads section!)
Special thanks to this article, which inspired this post, and helped me solve some of the problems I was having.