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?

  • \$\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

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.

| improve this answer | |
  • 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

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

| improve this answer | |
  • \$\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 at 15:31

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.