5
\$\begingroup\$

I've been thinking about No Man's Sky a lot recently and all the technical challenges they must face. For example, how on earth do you store a players location in a world that is so enormous?

I assume x,y,z isn't feasible. I notice the advertised number of planets (18 quintillion) is exactly double the maximum integer you can store on 64-bits, if that is relevant.

From watching tech videos of him (Sean Murray) describing the architecture, he seems to say everything is generated by formula where the inputs are x and y. Obviously he's simplifying, but how might one accomplish this?

\$\endgroup\$
3
  • \$\begingroup\$ Good Question, i was wondering about this myself. Would someone be able to answer a somewhat related Question: How does the drawing work with those huge values, like in 'EvE Online' where even the furthest planets are drawn? \$\endgroup\$ – tkausl Jul 18 '15 at 0:14
  • \$\begingroup\$ You should ask another question about that, but I worked on an open world game once where as you got to thinking edges of the map, floating point precision issues cropped up. Our solution was to divide the world into sectors and have everything in a sector happen as an offset from the center of the sector (physics, animation, etc). This kept the player near the origin mathematically no matter where they traveled to. \$\endgroup\$ – Alan Wolfe Jul 18 '15 at 1:49
  • \$\begingroup\$ You might be interested in this presentation on Kerbal Space Program, where they talk about a LOT of these issues. They use a floating origin point, double-precision types, and a number of other techniques: youtu.be/mXTxQko-JH0 \$\endgroup\$ – adsilcott Sep 23 '15 at 20:29
8
\$\begingroup\$

Two possible options might be:

  • "big number" classes, such as this one, which represent arbitrarily large numbers through mathematics on arrays of integers used to simulate an appropriate storage space.
  • hierarchy; that is, using a tiered coordinate system possibly represented by two integers per component; the first integer represents the position of (say) a planetary system within a galaxy, and the second represents position within that system (et cetera)

Fundamentally these are very similar approaches, differing mainly in the interface they present over the multiple-integer abstraction.

A given game may choose one over the other depending on it's needs. For example, in a space game like No Man's Sky, you might only be able to "warp" between star systems. In this case there is a distinct transition phase that the game can use to smoothly transition from one coordinate space to another.

However, you might be able to smoothly and arbitrarily fly from space on to a planet surface, in which case you might have a harder time masking the coordinate system transition (it's doable but might be annoying depending on the rest of your game's implementation and how you deal with straddling cells or something). In that case you might prefer to represent coordinates using a "big number" class that simply let's you pretend you have a larger coordinate space to work in, at the minor cost of some performance now and then.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I think the second option is more appropriate for the game since big numbers isn't good choice for fast calculations. \$\endgroup\$ – Ocelot Jul 18 '15 at 13:24
2
\$\begingroup\$

An int64 is pretty huge (really!), but one way to deal with this sort of a problem is to have one coordinate set define what grid cell you are in (gridx, gridy) then another coordinate set to define the offset within that cell (offsetx, offsety).

Note though that if you used 32 bit ints for the grid cell x and y, and 32 bit ints for the offset x and y, you could combine them into one 64 bit number for each full coordinate component.

In this way, a 64 bit int for positions can be thought of as being equivalent to a 32 bit grid cell with a 32 bit offset within that cell :p

\$\endgroup\$
1
  • \$\begingroup\$ +1 for this. Keep the "actual" x,y,z capped at something low-ish like 32 or 256 so that local floating point math stuff can take your numbers "as is" with at most double the stride amount in the integer part, which keeps precision usable, and then the second set of X,Y,Z - 64 bit ints that specify grid position. Most "hard" math happens on the floats which both the GPU as well as the CPU's ALU are already optimised for. \$\endgroup\$ – htmlcoderexe Feb 26 '20 at 15:31
0
\$\begingroup\$

The simplest solution to storing any position is to use floating point numbers (specifically, 3 of them can store a 3D position in a Vector3).

Floating point numbers have different levels of precision. Most programs and games use 32-bit single-precision floats, which are not super accurate, they work well for for most games but not ones that take place on huge scales. Single-precision floats have a limited amount of precision, which is unsuitable for games that use large scales. Single-precision floats have 23 significant binary digits (they are 32-bit, 8 of the bits are used for the exponent and 1 bit is used for positive/negative). First-person games depend on the world having better than about half a millimeter of precision. The formula 0.0005 * (2^23) shows us that errors big enough to notice appear approximately a few kilometers away from the world origin. This is fine for most games, as most games take place on scales smaller than a few kilometers.

The solution, simply put, requires us to add more significant digits. Double-precision floats are 64-bit, with 52 of those bits being significant binary digits. This is 29 more significant binary digits than single-precision floats, which increases the maximum usable area by a factor of about half a billion, to about 2 Tm (2 billion km). We go from a fifth the length of Manhattan to an area greater than the orbital radius of Saturn.

A fair question to ask is how other games handle large scales. Some games that use 64-bit doubles for large scales include Star Citizen, Arma 3, Space Engineers, and Minecraft. There's also Unigine, which is focused on being an engine for simulations, and Unigine can use doubles. For games that need somewhat large scales, sometimes maps are designed around the constraint of 32-bit floats, to be square and approximately 4 kilometers in radius, such as PlanetSide 2's Indar map. Kerbal Space Program had to implement their own 64-bit math types, doing a huge amount of calculations in user code. Even with all their effort, KSP struggled with floating-point issues for many years since the engine they are using (Unity) uses 32-bit single-precision floats, and these issues came to be known as The Kraken.

A commonly cited technique is origin shifting. This involves moving the world around the player such that the player is always near the world origin. This technique can work, but it comes with many of its own limitations. For example, it doesn't always work for multiplayer, where the server needs to have precision for all players at once. There are many tricks to make this work better, but this heavily complicates things to the point that it's both easier and more efficient to use doubles.

When this question was asked in 2015, hardware supported acceleration for 64-bit doubles was not as good as it is now, so other techniques such as origin shifting and manually calculating positions with grids and offsets (like Alan Wolfe said) were considered a better idea for AAA games that need as much performance as possible. The modern solution is to simply use doubles, since they are more precise numbers, and they are well supported on modern hardware with things like AVX2 on Intel CPUs from 2013 or newer and AMD CPUs from 2015 or newer (this is especially true if you want to make a AAA game like No Man's Sky where you want to target high-end hardware new enough to have these features).

We don't know what No Man's Sky uses, but I'm going to guess that it uses 64-bit doubles somewhere in its code, and it probably uses shifting and/or grids since it's an older game made when relying on doubles wasn't as efficient of an option.

TL;DR: If you have the choice, use doubles. They are the easiest and most reliable solution, and on modern hardware they are still a performant and efficient solution. Read more here.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.