BUILDING A GALAXY

INTRODUCTION

We wanted the galaxy to be a real physical place where you have complete freedom of movement. For example, you could be in orbit around Earth, and then by simply engaging the FTL engines at say 25% you can fly over to Mars in a dozen seconds, but when you get there you change your mind and throttle up to 100%, propelling the ship straight out of the Sol system and into deep space. Then, you catch a glimpse of a bright star and steer the ship towards it, throttling down on approach so that you can arrive in orbit around a distant exoplanet. You could even change your mind half way and point the ship at a different star instead.

You can explore every square centimeter of the entire galaxy, even the space between stars, and below is how we did it.

THE QUESTION OF SCALE

Seed-driven procedural generation is naturally the secret sauce that makes this all possible, but we’re still faced with the challenge of managing all of that data, and generating it in real-time so that it’s available to the game engine without a huge amount of CPU overhead.

We’re making Starship Simulator in Unreal Engine 5, but despite its native support for 64 bit doubles (really, really big numbers), it still only allows us to use a relatively limited INT32 value as a seed for the random number generator. This presents us with a challenge, because even with negative numbers taken into account, there are still only about 4 billion unique INT32 values available. When you then consider that our galaxy has a base volume of roughly 8 trillion cubic lightyears, there’s just not enough unique seeds available for each cubic lightyear to have its own seed.

To overcome this particular problem we’ve split the galaxy into 100ly cubes that we’re calling “Sectors”, and this reduces the minimum number of unique seeds required to a much more reasonable 10 million. In fact, we now have enough seeds available to include the galactic halo region as well, giving us a total playable area of 4 quadrillion cubic lightyears.  There isn’t actually a hard limit on how far from the galaxy you can fly, but stars will eventually stop generating.

THE STRUCTURE OF THE GALAXY

Splitting the galaxy into multiple 100ly³ sectors actually helps us in numerous ways, beyond simply reducing the number of unique seeds required. It also means each sector can have a galactic region type associated with it (core, arm, inter-arm, etc), and we can also customise any individual sector any way we want. For example, to use real-world star data instead of procedural generation, where such data exists. Some sectors can also be specialty regions, such as open or globular clusters, or perhaps even something weird and unknown.

Despite taking a bit of sci-fi license here and there for the sake of interesting gameplay, we’re endeavouring to be scientifically accurate wherever possible, and the physical structure of the galaxy is certainly no exception. As mentioned above, each sector knows which region of the galaxy it’s located in, and that directly controls the age and class of stars that are generated within it. For example, you’ll likely never find young O-Class stars in the inter-arm regions, so you’ll need to look for local clusters in the galactic arms if you want to find those types of stars. This also has a bearing on the development level of any alien species generated in that sector, but we’ll dig deeper into that subject later.

The current sector types at the time of writing are:

GALACTIC CORE

CENTRAL BULGE

THIN DISC – ARM & INTER-ARM REGIONS

THICK DISC

GALACTIC HALO

GLOBULAR CLUSTERS

INTERGALACTIC SPACE

Because each sector has a volume of 100³ lightyears, that means there are exactly 1 million unique coordinate points within each and every sector where a “Location” can exist. A location can be a star system, a black hole, a rogue planet, or anything in-between. Each location has a volume of 1 cubic lightyear, and this is where we spawn all of the interesting stuff such as planets, aliens, and other interesting things to interact with. This does of course mean that no star system can exceed 1 lightyear in diameter, but for 99.999% of cases that’s more than enough space.

Next we’ll look at how the sectors are actually generated.

GENERATING THE GALAXY

Every time your ship crosses the border into a new sector, the game will run the sector generation algorithm. In fact, at any given moment there are 27 sectors being generated, which represents a 3x3x3 grid of sectors surrounding the ship’s location. Typically that’s an average of 100,000 stars worth of data to filter and sort!

Each sector has a globally unique seed, which is derived mathematically from the sector’s XYZ coordinates. This seed is used to randomly distribute star systems and any other interesting locations within a sector, in addition to randomly determining extra location data such as a star’s temperature and spectral class.

The percentage chance for each type of star class or other location to be generated depends on the type of sector we’re looking at, in addition to the overall density of locations as determined by a galactic density map. Each pixel on the map represents a single individual sector, whereby the pixel’s 0-1 value translates to 0-8000 stars, plus or minus a bit of randomness. The greyscale image on the right represents the actual density map used by the game right now, but there are plans to refine this further to achieve a better overall galactic structure.

To maintain performance it’s critical that we never generate more than the absolute barest minimum amount of data required, and also that we never generate fresh data unless we absolutely need to. To that end, the galaxy system has already gone through numerous optimisation passes to achieve what we have today.

The system adheres to the principle of “generate once, use many”, which means once we’ve gone through the effort of generating all the sector data, we store it in a central location for all other game systems to access. There is however one additional task to perform, which is to sort the list of stars by distance to the current ship location, and this takes place every time the ship passes the border of the next whole lightyear. We’ll come back to that point later though.

Now that we have our sectors generated, and we know what locations exists within those sectors, how do we generate the contents of each location? This is where careful data management is critical, because we can’t generate every planet in every one of the sector’s locations all at once. Instead, when you scan a star system using the ship’s sensors it will generate some data on the fly, but again it’s no more data than is actually needed for the sensors display. The full data for a star system will only be generated when you pass within its 1ly cube, and high-cost data such as 8k surface textures will only be generated when you are in range of a planet.

Speaking of planets, let’s take a look at how the star systems themselves are generated.

BUILDING STAR SYSTEMS

Just as with the galaxy itself, we were keen from the outset for our star systems to be built using real world astrophysics. When exploring distant exoplanets we want to feel that they are in every way plausible, and given the same environmental conditions a similar planet might actually exist out there for real somewhere.

The process begins by taking the Temperature, Radius and Spectral Class of the central star that was generated by the galaxy system. We use this to derive the mass of the star, and then randomly add a little extra to ascertain the total mass of our proto-planetary disk. We also define the age of the star system at this stage, driven  by both the star’s spectral class and its location in the galaxy. For example, you won’t find young star systems outside of the thin-disc region.

Next, we perform a number of calculations to define the various temperature regions within the system. We do this by working out how far from the star you need to be to achieve a specific Equilibrium Temperature using a given Bond Albedo, and this tells us where regions such as the Habitable Zone and Frost Line are located.

Now comes the fun part. Armed with our total mass pool (the proto-planetary disk) and our temperature regions, we randomly pick the location for the first planet. This will typically be no closer to the star than where the Equilibrium Temperature exceeds 2000 Kelvin. Once we know where the planet is, we work out what its basic type is (Silicate, Metallic, Gas, etc), and then work out its Equilibrium Temperature using its Bond Albedo. As a general rule, planets closer to the star have a higher quantity of heavier elements (metals) than those further out, because the lower mass volatiles (ices) are more easily blown outward by the stellar wind.

We then use the planet’s basic type to randomly decide its overall mass, and deduct that amount of mass from our mass pool.

For silicate and metallic planets we then work out what percentage of the planet is made up of its Core, Mantle, and Crust, along with defining the densities of those regions. This is then used to derive the overall radius of the planet. For example, if a planet’s core makes up a high percentage of its overall mass, it’s going to have a smaller radius because most of its mass consists of high density material.

Now that we know the planet’s mass and radius, we can calculate its surface gravity using Newton’s law of universal gravitation.

Next, we decide whether or not the planet has an atmosphere, and if so how thick it is. This is then used to work out any additional greenhouse effects, which when combined with the planet’s Equilibrium Temperature, gives us our final average surface temperature.

Using all of the above we can now define the planet’s final type. Silicate planets with surface temperatures hot enough to melt rock become lava planets. Gaseous worlds in the outer reaches of the system become Ice Giants, and if we’re really lucky an atmospheric planet in the habitable zone will become an Earth Analogue.

When placing the next planet we don’t just randomly choose a location, we instead employ the Blagg Formulation of the Titius-Bode law. The jury is still out on the validity of the Titius-Bode law, but for our purposes it does a good enough job of making sure planets are appropriately spaced apart. In a nutshell, each planet is approximately 1.5 to 1.9 times further away from the star than the one before it.

We repeat this process until there’s no more mass left from our proto-planetary disk, and then we sprinkle the outermost edge of the system with icy dwarf planets and other rocky bodies to create a Kuiper Belt type region. We also plan to add comets and other transitional objects in the future.

So, now we have a galaxy filled with billions of interesting star systems, how do we navigate and explore them? I’m glad you asked, because that’s the next section.

NAVIGATING AND EXPLORING THE GALAXY

To successfully navigate any space you really need to know two key pieces of information:- where you are, and where you’re going. Let’s start by taking a look at our galactic coordinate system so we can answer those questions.

As a quick reminder, the galactic space is subdivided into 100ly³ “Sectors”, which are in turn subdivided into 1ly³ “Locations”. This is important because this forms the basis of the “Galactic Coordinates”.

The image on the right is the nav-entry panel as it appears in the game currently, and you’ll notice it’s displaying two different coordinate systems. This is because we don’t just need to know where the ship is relative to the galaxy, we also need to know where it is within the 1ly cube of its current location.

We just happen to be in orbit around Earth, so let’s break down our galactic coordinates of  X: -25850 Y: 50 Z: 50

The coordinates for the exact centre of our galaxy (Sag A*) are 50,50,50, which is the middle of Sector 0,0,0. This sounds odd at first, but it’s because each sector is 100ly³, so 50,50,50 is the exact middle of the 100ly cube.

That means Sol is -25800 lightyears away from Sag A* on the X axis, 0ly above (Z), and 0ly to the side (Y). Or in other words, Sol is in the exact centre of Sector -258,0,0.  Confused yet? Don’t worry, it takes a while to get the hang of it, and you only really need to know this if you’re going to be piloting the ship!

But what about the “Local Coordinates”? Well, as above, each “Location” within a sector consists of a 1ly cube, so the local coordinates represent where in that cube your ship (or target) currently is. Every star, planet, or alien space station will have their own set of local coordinates, so you’ll need to use both the Galactic and Local coordinates to pinpoint the exact location of an object within the galaxy. Behind the scenes this works with sub-millimetre accuracy, but for the navigation system we deal in kilometres in an effort to keep the number of digits from becoming too crazy.

It’s also worth mentioning that 0,0,0 in the local coordinate system is also the true world origin point of the game engine, and this will generally always represent either the central star for single-star systems, or the barycentre for multi-star systems. So, if we look at the local coordinates for our current position around Earth in kilometres (X: 46m Y: 64m Z: 128m), using vector math that translates to 150m km away from the local 0,0,0. Which is of course 1 Astronomical Unit.

(If you’re wondering why the Earth is in a strange position, it’s because the Sol system has an inclination of 60.2 degrees to the galactic plane)

So now that we know exactly where we are, and also where our target is located (a planet orbiting Sirius in the case of our example), it’s a relatively simple matter of  just pointing the ship in the right direction and firing up the FTL engines.

As your ship accelerates to the speeds needed to traverse the space between stars (570ly/h, or 5,000,000C), your Local Coordinates will increase until you reach the edge of your current Location’s 1ly cube. At that point your Galactic Coordinates will increment by 1 in that direction, and your Local Coordinates will wrap around to reflect the fact you have just entered a new Location cube. (As far as the game engine is concerned, you never fly further than 0.5ly from the world origin point)

If anything exists within that Location it will be loaded in at that point, otherwise you’re just flying through cold, empty space. What this means of course, and what we intended from the outset, is you don’t actually need to target anything or have a route planned to explore the galaxy. You can literally just pick whichever direction tickles your fancy and fly around until you stumble across something worth investigating. 100% real-time, 100% seamless.

In our final section, let’s take a look at what we’ve got planned to keep exploration fresh and engaging.