Blog 3.0 I make games.
City Generation For Dummies Series
- Procedural Generation For Dummies: Galaxy Generation
- Procedural Generation For Dummies: Lot Subdivision
- Procedural Generation For Dummies: Road Generation
- Procedural Generation For Dummies
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!
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…
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.
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).
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:
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.
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).
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).
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.
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:
- Alpha Alnati II
- Ham 44
- 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.
- Procedural Generation For Dummies: Galaxy Generation 14 Jan 2016
- 2015 Retrospective 04 Jan 2016
- Procedural Generation For Dummies: Lot Subdivision 27 Dec 2015
- Procedural Generation For Dummies: Road Generation 11 Dec 2015
- Procedural Generation For Dummies 11 Dec 2015
- Deferred Transparency 09 Oct 2015
- Xna In 2015 24 Aug 2015
- Node Machine 26 Jun 2015
- Procedural Generation Of Facades And Other Miscellania 29 May 2015
- This Path Was Made For Walking 23 Apr 2015
- Cross Chunk Navmeshes 27 Mar 2015
- Changelog 27 06 Mar 2015
- Drawing Stuff On Other Stuff With Deferred Screenspace Decals 27 Feb 2015
- Random Gibberish 22 Feb 2015
- This Wall Is Sticky 17 Feb 2015
- Changelog 25 08 Feb 2015
- 2014 Retrospective 13 Jan 2015
- Super Sonic Sound 08 Jan 2015
- Sandboxing Is Dead Long Live Sandboxing 22 Dec 2014
- Changelog 22 B 14 Dec 2014
- Changelog 22 07 Dec 2014
- Possible Interruption To Service 06 Dec 2014
- The Game Programmer Awakens (changelog 21b) 30 Nov 2014
- The Return Of The Programmer (changelog 21) 16 Nov 2014
- The Return Of The Vending Machines 26 Oct 2014
- There Are Vending Machines Everywhere 16 Oct 2014
- Changelog 20 12 Oct 2014
- Ragdolls Are Hard 05 Oct 2014
- Changelog 19 28 Sep 2014
- The Return Of The Game Programmer 21 Sep 2014
- The Ball Is Picked Back Up 17 Aug 2014
- It's Good To Be Back 03 Aug 2014
- Serious Injury 21 Jul 2014
- We Marveled At Our Own Magnificence As We Gave Birth To Ai 14 Jul 2014
- Changelog 17 06 Jul 2014
- Changelog 16 29 Jun 2014
- Happy Birthday 22 Jun 2014
- Changelog 14 15 Jun 2014
- Losing My Way 08 Jun 2014
- Wildcard 02 Jun 2014
- Changelog 13 25 May 2014
- Changelog 12 16 May 2014
- WAI NO VIDEO (Again) 11 May 2014
- Changelog 10 04 May 2014
- Changelog 9 27 Apr 2014
- Changelog 8 20 Apr 2014
- Long Overdue Style Upgrade 18 Apr 2014
- WAI NO VIDEO 13 Apr 2014
- Changelog 7 07 Apr 2014
- Changelog 6 30 Mar 2014
- Changelog 5 23 Mar 2014
- Changelog 4 16 Mar 2014
- This Is Madness! 11 Mar 2014
- Changelog 3 09 Mar 2014
- Changelog 2 02 Mar 2014
- Changelog 1 23 Feb 2014
- Changelog 0 15 Feb 2014
- Payday The Heist 2 13 Jan 2014
- 730 Days Later 01 Jan 2014
- I Just Needed A Rest 12 Nov 2013
- Splinter Cell Blacklist 27 Aug 2013
- Gruelling Homework Assignment 26 Aug 2013
- Scripting Is Dead Long Live Scripting 14 Aug 2013
- The Reports Of My Death Are Greatly Exaggerated 05 Aug 2013
- 27 Gigawatts Of Cake 11 Jun 2013
- Trees Are Well Behaved 22 May 2013
- A Brief Project Update 14 May 2013
- Finite State Machines (are Boring) 16 Apr 2013
- Pathfinding 10 Apr 2013
- Artificial Stupidity Series 08 Apr 2013
- Valve Need To Stop Reading My Mind (and Other Miscellanea) 20 Mar 2013
- Elements Of Style 26 Feb 2013
- Moving To Axmingholmesbury 23 Feb 2013
- The Future Is Steamy 08 Feb 2013
- Mathematical Trickery 22 Jan 2013
- Thinking Aloud About Release 09 Jan 2013
- Game Developers Don't Make Timetables 03 Jan 2013
- What Is Heist? 20 Dec 2012
- How Does Procedural Generation Work? 14 Dec 2012
- Why Does Heist Keep Crashing? 07 Dec 2012
- What Isn't Procedural Generation? 23 Nov 2012
- What Is Procedural Generation? 18 Nov 2012
- Procedural Generation Series 15 Nov 2012
- Packet Encoding(3) 12 Nov 2012
- Packet Encoding(2) 08 Nov 2012
- Packet Encoding 07 Nov 2012
- Deployment Hax 28 Oct 2012
- Wibbly Wobbly Pipey Wipey 24 Oct 2012
- New Release(2) 24 Oct 2012
- New Release 20 Oct 2012
- Say What? 17 Oct 2012
- Get Up And Initiate That Session 15 Oct 2012
- Topological My Dear Watson 14 Oct 2012
- Omg Wtf Multiplayer 13 Oct 2012
- Full Steam Ahead 24 Sep 2012
- You Should Check Out Greenlight 01 Sep 2012
- It's Full Of Entities 20 Aug 2012
- Persistence 06 Aug 2012
- I'll Be Back 01 Aug 2012
- Artificial Stupidity 24 Jul 2012
- Overindulgence 16 Jul 2012
- Not My Cup Of Tea 09 Jul 2012
- Artsy Stuff 02 Jul 2012
- This Was A Triumph 25 Jun 2012
- Multiplayer Release 18 Jun 2012
- Fortnightly Fun 10 Jun 2012
- New Blog 31 May 2012