Procedural Generation For Dummies: Galaxy Generation In Which The Heavens Are Built

Written By Martin Evans On 14 January 2016 Filed In Game-Development

Procedural City Generation For Dummies Series

My game, Heist, is a cooperative stealth game set in a procedurally generated city. This series of blog posts is an introduction to my approach for rapidly generating entire cities. This post is a fun diversion away from city generation to explore a weekend project from a few months back: Galaxy Generation!

If you’re interested in following the series as it’s released you can follow me on Twitter, Reddit or Subscribe to my RSS feed

The code related to this article is open source and can be found here and here. It’s a complete C# galaxy generation library which you can use in your own projects.

Galaxy Generation

For my city generator the system is hierarchical - a single generator just knows how to generate one level of the city and then invokes more generators to fill in the gaps. For example a city generator just knows how to place roads, which then calls a city block generator to place buildings, which then invokes a floor generator to place rooms etc.

The galaxy generator works in a similar way; the high level galaxy generator invokes separate generators for different parts of the galaxy such as the core and the arms. However, there is a major difference: when a nested generator creates a star the parent generator has a chance to modify it. This allows me to generate the core and the arms and then apply a swirl effect to all the stars later which vastly simplifies the implementation of the sub-generators.

Let’s look a the basic building blocks one by one…

Sphere

This is the simplest of all of the generators; it simply generates a roughly spherical blob of stars. The blob of stars is denser in the middle and slowly fades to nothing as distance increases. This is achieved through a normal distribution - more commonly known as a bell curve.


Standard Deviation Graph - Wikimedia


A normal distribution is a probability distribution with a higher probability of things being in the center. As you can see from the graph above there is a 68.2% chance of something being within 1 deviation of the center, a 27.2% chance of something being within 2 deviations, a 4.2% chance of being within 3 and so on. The deviation is a parameter which you can pick, so a very large value will get a low density blob of stars spread out a long way and a very small value will get a very high density blob of stars clumped tightly together. My implementation allows you to specify the deviation separately for each axis, so you can actual generate oblate spheroids with this.

In the example above is a sphere with the deviation the same on all axes, so it’s roughly the same in all directions but has no other apparent structure - it has a very natural appearance.

Cluster

The cluster generator is similar to the sphere generator. However, instead of placing individual stars according to a normal distribution it places other generators. In the example above I have generated a clusters of spheres, so we have a loose collection of blobs of stars. This is a perfect example of how a generator calls another, simpler, generator to use as a building block.

This generator is inspired by a vaguely scientific basis of how galaxies work - stars are generated in nebulae which will tend to form a clump of stars. Additionally large masses will pull in nearby stars and form even larger groups. This is used most prominently in the core of the galaxy where a large number of clusters are placed into a relatively tight area to simulate the super high density galactic centre we see in real galaxies (around something of immensely high mass such as a supermassive blackhole).

Spiral

This is the generator which really brings the others together to form something that looks like a real galaxy. Near the start I mentioned how higher level generators in this system have a chance to modify the stars generated at lower levels - this capability is used by the spiral galaxy in two ways.

Firstly all generated stars have a swirl effect applied to them to introduce the appearance of rotation. All the parts of the galaxy are generated as if there were no rotation at all (e.g. the arms are dead straight out from the center) and then the spiral galaxy applies a swirl modifier to bend the arms. The swirl method rotates a star around a given axis based on the distance from the center.

Secondly there is a void right at the center of the galaxy (to simulate the location of a supermassive blackhole). All stars generated within this void are simply deleted.

Let’s have a look at the three parts of the spiral generator:

Background

The background is simply a huge sphere with the standard deviation set to the size of the galaxy. This means that the galactic disk will have some stars above and below and there will be a very low density halo of stars scattered around the galaxy in all directions. The swirl effect is not applied to these stars.

Galactic Core

The galactic core is a very tight cluster, with the standard devitation set to be about 5-10% of the size of the galaxy. The swirl effect is five times stronger on these stars (and is naturally stronger at short distances from the origin) so the center is very strongly rotated around - giving the impression of a chaotic galactic center wrapped around a supermassive blackhole. What started off as spheres distributed around the center ends up many tiny little arms wrapped right around the core.

In the example above you can see the galactic core without swirl (on the left) and with swirl (on the right).

Arms

The arms begin life as a series of spheres generated (roughly) along a line. The swirl effect pulls these straight arms around into a nicer shape which gives the entire galaxy the appearance of rotation.

Other galaxy types could be generated by varying how the arms are created. For example a bar galaxy could not apply the swirl effect within a certain distance of the galactic core - which would cause the arms to remain straight near the core and thus create a solid bar. Alternatively some small arms could be generated between the larger ones with lower density of stars, or perhaps starting away from the core.

In the examples above you can see some arms generated without swirl (on the left) and with swirl (on the right).

Colour

You may noticed that these examples all have colours assigned to the stars. These colours are generated by picking the temperature of the star and then converting that temperature into a colour (assuming the star is a black body radiator). This isn’t a particularly scientifically accurate system for two reasons. Firstly the temperature is picked using a normal distribution; however star temperatures are unlikely to be normally distributed in reality. I couldn’t find any information about the real distribution though, so a normal distribution will do. Secondly stars are not true black body radiators due to various elements in their atmosphere absorbing emitted radiation. However a black body estimate is a close enough estimate.

Names

You can’t see this in the renderings above, but all the stars in these galaxies have names assigned to them. This generates names such as:

  • Superba
  • Gamma-77
  • Alpha Alnati II
  • Ham 44
  • A12
  • Many More

There are several different name generators which are randomly chosen between. Having multiple generators ensure there are entirely different styles of names in the pool - this fixes a common problem with procedural generation where things become boring because the patterns become obvious. Most of the credit for these name generators should go to my friend Pi Lanningham, I developed the most generator (the basic markov model) and then he extended this with all the alternative schemes as well as the system for weighted picking between the themes; thanks Pi!

The most basic is simply a markov chain which was taught with a large set of real star names as well as fictional star names. This generates names such as Superba and Alnati - single nonsense words. The implementation of the markov chains is my own open source library Marvellous Markov Models.

A slightly more complex strategy applies random prefixes and suffixes to markov generated names. There is a slight (1%) chance this could chain further prefixes and suffixes. This could generate names like Alpha Alnati II (greek letter prefix and roman numeral suffix), San Gamma (san prefix), Xendi Kappa (greek letter suffix) or San Gamma Gorgon II 44.7 (2 prefixes, 2 suffixes).

Another strategy simply generates names as if from a scientific index; with a letter and an integer. This generates names such as A-21, C-34 or D-07.

Finally there is a strategy which picks names from a pre-set list. This list doesn’t have many names on it at the moment, but can obviously generate completely unique names (perhaps associated with some special gameplay event at that star). An obvious extension which I have not implemented would be for this name generator to remove unique names from the system once used to ensure that they are truly unique.

Different strategies have weights associated with them so the majority of stars have scientifically indexed name. There’s a lower chance of markov names (with prefixes and suffixes). Finally the very lowest chance is for unique names.