Can you make a world so enormous that you'd never be able to see all of it? That might sound nonsensical, but by utilising the power of computers, a whole universe can be yours.

## Size is everything

I have a family, a mortgage and a lawn that won’t mow itself. I’m a crotchety old man with no time to play video games any more. Whatever happens in the gaming world these days tends to pass me by.

Video games create whole imaginary worlds and allow you to experience them in ways no other medium can. Right now, I usually imagine worlds where babies change their own nappies, grass cuts itself and the kitchen tap dispenses cool, refreshing beer.

Thankfully, many video game creators are more imaginative than I. They’ve given us endless examples of worlds that came purely from their imaginations: haunted mansions, fantasy islands, ancient lands that cover virtual square miles. The best examples are rich in detail and finely crafted.

Consider something like Grand Theft Auto, which features a complete, living city filled with cars, buildings, pedestrians, maniacs with automatic weapons and all the other things you’d find in any large conurbation. Now, while building a digital copy New York takes a lot less work than the actual place took to build, creating a virtual world nevertheless takes a lot of time and effort. Software needs writing, layouts need planning, objects need drawing and animating, characters need bringing to life. Video game production today resembles movie making, with dozens of people from different departments working together.

Which is why the recently-released game No Man’s Sky intrigues me so much. So widely discussed is this game, it has managed to penetrate the defenses that my own world puts up to protect me against enjoyable things. No Man’s Sky is a science fiction game where you play an interstellar explorer who travels across the universe from planet to planet, collecting resources, fighting creatures and flying spacecraft. What makes this game stand out from all the others is the size of the universe the explorer inhabits.

It contains 18 quintillion planets1.

Quintillion.

Quintillion.

I didn’t make that word up, it’s genuine. A quintillion is a 1 followed by 18 zeroes.

So this game has 18,000,000,000,000,000,000 planets to explore.

And make no mistake, each planet is a sizable, detailed world, filled with animals, fauna, and varied terrain.

The universe in No Man’s Sky is so colossal that it’s impossible to visit every planet in it, or anywhere near all of them. Think about it. If you live to eighty years of age, you’ll have lived for about 42 million minutes. If you played this game non-stop your entire life, taking only one minute to explore each planet, you’d have seen less than 1% of the available universe.

In fact, you’d have seen roughly 0.0000000000001% of it.

To really blow your mind, think about this: the universe in No Man’s Sky is far too large to fit into the disc it is sold on. At the time of writing, a high-capacity Blu-Ray disc can store about 100 gigabytes (GB) of information2 - that’s roughly 100 billion (100,000,000,000) bytes3. Trying to cram information about 18 quintillion planets into a Blu-Ray disc would therefore allow you only a tiny fraction of a single byte to describe a whole planet.

Compare that to OpenStreetMap, which maps only the planet Earth and requires about 50 GB of compressed data4.

And, just to show off, the developers of No Man’s Sky have revealed that most of the disc is empty anyway. The whole game is about 6 GB is size - and much of that is used to store music.

So what gives? A game like Grand Theft Auto takes a team of dozens to produce a world the size of one city. How can the developers of No Man’s Sky create a functioning universe so unimaginably bigger and manage to get a Blu-Ray disc to behave like Doctor Who’s TARDIS?

## Let the camera do the work

To begin answering this, we need to understand how computers create visual worlds. One of the first people to tackle this problem was John Warnock, co-founder of Adobe5, the company that brought you Acrobat and the joys of updating programs every freaking day. The story goes that a colleague of his was trying to work out a way for a computer to display an image of New York harbour as seen by a passing ship. The image had to play out in real time, which meant that the view changed slowly as the ship moved. Warnock’s colleague was stumped by how to make the computer achieve parallax – that is, make objects closer to the ship appear to pass in front of objects farther away.

One way to achieve this would be to actually get on a ship, take lots of photographs of New York harbour from lots of different angles and then put those digital images into a database. When you want the computer to simulate sailing past New York, you simply instruct the computer to playback those images in the right order, just like an animation.

I say ‘simply’, but there really is nothing simple about this. Glossing over the difficult logistics of actually taking the photographs, this approach poses myriad technical problems. First of all comes the problem of storage. To simulate both moving along the whole harbour as well as being able to look in several different directions, you’d need to devise a route with a series of points spaced several metres apart and then at each point take several photographs from different directions. But New York harbour is a hundred square miles, so there would be many thousands of points and therefore many thousands of pictures to take. If we conservatively say that each photograph would take up one megabyte of space, that would still necessitate gigabytes of storage. But John Warnock tackled this problem in the late 1960s, when even the largest disks were unable to store anywhere near this amount of data.

Still, technology marches on. We have much bigger hard disks today, so could we use this approach now?

We may indeed have the space, but that still wouldn’t solve the most fundamental problem with this approach, namely how limited it is. For example, how could you look back at the ship while ‘standing’ on the shore? How could you show the view from the top of the Statue of Liberty? The answer is: you can’t. If you didn’t take a picture of it, you can’t make the computer show it.

Warnock took a much different approach, one that had the twin advantages of being both terrifically cheaper in terms of storage, as well as endlessly more flexible. He described New York Harbour to the computer and told the computer draw the image for him. To do this, Warnock broke the view down into component elements (basically water, buildings, boats etc.) and taught the computer how to draw them. Take the water for example: it’s blue, flat and stretches off into the distance in every direction. Buildings are essentially cuboids, some brown, some grey, some short, some tall. Defining an element is simply describing it in simple terms that the computer understands, like size, shape, and colour.

Descriptions like these took up the merest fraction of space compared with the equivalent image data. He simply had to put all of them together in their correct positions and tell the computer to draw them from a specific angle. The result was a depiction of New York Harbour from sea level, or from the shore or from the Statue of Liberty’s nose or wherever the hell you wanted.

The moral of this story is: if you want to create your own virtual world in a computer, it’s far better to describe your world in terms of models and then make the computer draw them for you. You can then explore your world by moving a virtual camera around this generated environment; the computer takes care of adjusting the scenery as you do so. This process of computers taking model elements and drawing them onto a screen is called rendering. Rendering is important in this article because video games use this approach when creating their virtual worlds.

To render things, the programmer needs to provide two things:

• The instructions that define the environment, called the game engine. This takes care of things like how light behaves in this universe, how gravity works, whether there is friction and so on.
• The specific elements that live in the environment (water, buildings, giant mushrooms, flying fire-breathing llamas), sometimes called the content.

The content usually determines a game’s size, whereas the engine could actually be fairly small in comparison. In fact, the content can grow and grow while the engine can stay the same size.

All this is how the makers of Grand Theft Auto create their city. Much of the disc is crammed with content: model descriptions of cars, buildings, guns, prostitutes, flattened pedestrians and everything else you else you see in an afternoon’s rampage.

And that’s all very well for the makers of Grand Theft Auto, but it’s still not a sufficient solution for No Man’s Sky. Don’t forget, its universe is made up 18 quintillion planets, each with its own population of animals, plants and artefacts. There just isn’t enough space on a disc to describe all this content.

So how can you make a video game while providing little or no content?

Welcome to the world of procedural generation.

If you take the usual approach to creating a planet in a video game world, you build up a description something like this:

* Place a green weed at position 432:221
* Place a first-aid box at position 434:210
* Place a snarling bugblatter beast at position 435:213
* Place a spare pair of pants at position 436:218
... and so on.


You can imagine that using this method to describe a whole planet filled with weeds, beasts and soiled underwear takes up a lot of disc space.

But with procedural generation, your instruction to the computer is more like this:

* Make a planet


That’s it. Instead of the game designer using their own imagination to design a planet, they essentially delegate the imaginative work to the computer. “Go wild,” they say to their digital counterpart. “Make me a planet a million square miles in area. Populate it with trees and rivers and snarling beasts and place them wherever you like.”

This may sound to you (especially if you’ve ever programmed a computer before) like a recipe for disaster and chaos. How on earth – or on any planet for that matter – can you get a computer to create a virtual world for you without giving it specific instructions for laying that world out?

This is where procedural generation comes in. It’s a tricky subject to explain, so let me begin with a simple idea: fractals.

## Love fractally

Even if you have no idea what a fractal actually is, there’s a good chance you’ve already seen one in the form of an elaborate and psychedelic-looking pattern. When shown on screen, they’re often animated, with the camera endlessly ‘zooming’ into a particular area of the fractal, thus revealing new detail. And no matter how far the camera zooms in, it always reveals a new fractal that looks the same. A fractal is made up of many fractals, each of which is made up of many fractals, each of which is made up many fractals, each of which is… It’s like zooming in on a fern leaf to find it’s made up of lots of little fern leaves, each of which is made up of lots of little fern leaves, and so on.

Understanding how to make a fractal can help you understand procedural generation. A very simple one is a T-square6. Here’s how you make it:

2. At each convex corner (i.e. each corner that points outwards) place another new square that’s half the width of the original square. Each new square should be centred on the corner.
3. Go back to step 2.

The image above shows, from left to right, the results of the first few iterations of that procedure.

That’s one example of how to make a fractal. And, in case you hadn’t worked it out yet, fractals are an example of procedural generation. When you create a T-square, you’re creating a complex shape procedurally, that is to say, you’re building up a shape by following instructions.

Just to labour the point, I’ll show you another fractal called the Koch snowflake7. Here’s how to make it.

2. Consider each side in the shape separately.
3. Take one side of the shape and divide the line into three equal parts.
4. Remove the middle part.
5. Add two new lines (same length as the part you removed) and use them to make a point sticking out of the side.
6. Repeat steps 3-5 for all other sides of the shape.
7. Go back to step 2.

Again, this is procedural generation: following instructions to build a visual.

An alternative way to model the snowflake (one similar to the way most video games work) would be to store the visual layout as data and interpret that data when rendering it. For example, the data required to render a Koch snowflake could be a series of straight lines that make up each side of the shape; rendering it would simply mean drawing each line. In this case, for the initial stage of the equilateral triangle we would need to store six sets of coordinates (because each line is defined as a pair of points). To render a snowflake after one repetition, 24 sets of coordinates would need storing (because it has twelve lines). For a two-repetition snowflake, 96 coordinates (48 lines). After three repetitions, 384 coordinates (192 lines), and so on. As you can see, using this method means the larger and more complex your shape is, the more storage space you need to describe it.

But with procedural generation, you no longer have instructions and data – you just have instructions. You can build up as much complexity as you want and it will cost you no additional storage. The amount of space needed to store “repeat this 3 times” compared with “repeat this 3 thousand times” is exactly the same to a computer.

Now, we can finally begin to marry procedural generation with video games. Imagine you’re creating a video game which depicts the game world using an overhead view, as though your character is running around a map. You build up an environment by describing the lines to the game engine, which then takes those lines and renders them as walls. In this way, you can create a 2D, top-down video game.8

Using a T-square, we could generate the lines of a map without using any data. If you wanted a simple square room in your game world, you would perform one repetition of the T-square steps above. If you performed a second repetition, you would get a modest castle with four turrets. Three repetitions would yield a super fortress whose four main turrets had mini-turrets of their own. And so on. You could add more and more complexity to your world simply by performing more repetitions of the steps.

You could also make the game world as large as you wanted without using more storage space. You want a small room? Tell the engine that each pixel of the map corresponds to one metre in the game world. For a much bigger room, tell it that each pixel maps to 100 metres. For a stupidly big room, make each pixel equal one mile!

But no matter its size, a game with one empty room wouldn’t make for an awfully interesting game. However, you can probably imagine taking a more complex variety of this approach to create a world more more varied and interesting. Perhaps you could adapt the steps above to generate three rooms. Or maybe three castles. You could even mix them up, generating one castle that contains 16 rooms. It shouldn’t be too much effort to also adapt those instructions further, so that rooms are connected via a tunnel (two parallel lines).

The little example here generates four castle connected by tunnels. The size and complexity of each castle are chosen randomly during generation. Try it… you’ll generate a different layout every time.

In fact, a whole genre of early computer games worked just like this. They were called ‘roguelikes’ after one of earliest examples Rogue. In a roguelike, you played an adventurer delving into maze-like dungeons filled with dangerous creatures and fabulous treasures. These games emerged in the late 1970s and early 1980s when computer graphics were still crude. The game world was presented to you using a top-down view, with lines representing walls and simple symbols standing in for the hideous enemies (for instance, a vicious, venomous viper poised to sink its fangs into your fragile flesh… was rendered using the letter ‘S’).

Such a game was novel enough in itself back in those days, but roguelikes typically had an additional selling point. The game’s creator didn’t manually design the layout of the game world. It was procedurally generated. The rooms, the connecting tunnels, the enemies and the treasures were all created and positioned by the computer at the start of a new game.

Critically, the layout was different every time they played, ensuring players kept coming back for more.

## The power of randomness

There are many varied ways to generate a dungeon and each roguelike used its own procedure, although at a basic level there are usually two approaches: 1) place the rooms first, then attempt to connect them via tunnels, or 2) place the tunnels using a maze generation algorithm, then unify sections of the maze to form rooms9.

One example generates its game world along the following lines10:

1. Generate a room at the centre of the map.
2. Choose a random wall of the room and then choose a random spot on that wall (a tunnel will be dug from this spot).
3. Verify that there’s enough space to dig a tunnel (you don’t want to dig through a feature that’s already there). If there’s not enough space, go back to step 2.
4. Generate the tunnel.
5. At the end of this tunnel, generate a new room connected to it.
6. If the dungeon is still incomplete at this point, go back to step 2.
7. Otherwise, generate some monsters and treasures at random points around the dungeon.
8. Finished. Play!

This description admittedly presents a very simplified view. At a few points it uses the word ‘generate’ and that hides a lot of detail. But generating a room or a tunnel is very much like creating a fractal, which we looked at earlier. For example, generating a room is simply a case of drawing a shape and you can write a set of instructions for that. To add some variety into your dungeon, you could give the walls of each room a random length, or make every tunnel a random size and shape.

Randomness is important in a procedurally generated game because it ensures the environment is different every time you play. If the computer follows the same set of instructions to create every room, then all the rooms will end up looking the same. However, if you inject a bit of randomness into the process, so that the instructions for generating a room look like this…

1. Let X equal a random number between 1 and 10.
2. Let Y equal a random number between 1 and 10.
3. Draw a rectangle with sides X and Y.


… then all your rooms will end up different shapes and sizes, some big, some small, some square, and some long and skinny. It makes the environment interesting and organic.

You can approach randomness a couple of different ways in a procedurally generated game environment. The authors of the roguelike games wanted players to keep coming back for more – even after they had successfully completed the game – so those authors wrote procedures that created a different world every time. This never-ending sense of challenge and discovery ensured players never suffered the inconvenience of a social life.

But other games took a different approach. Their authors wanted the game world to be the same for each player every time they played. They randomly generated an environment so that it appeared varied and interesting, but did so in such a way that the generation procedure always created exactly the same environment.

The idea of randomly generating the exact same thing each time seems odd and self-contradictory, but it’s perfectly possible thanks to the computational concept of determinism. The key is in the detail of generating a random number. Algorithms for random number generation are usually very sophisticated (which can make them difficult to understand), so I’ll use a very simple one for the purposes of explanation. This generates a random number between one and ten.

1. Input seed
2. Let SUM = seed multiplied by 5
3. Let result = remainder when SUM is divided by 11


The ‘seed’ is a starting number, a beginning point for the mathematical acrobatics that follow. Different seeds give different results. Try it yourself. If you use 1 as the seed, you should get 5 as the result; using 2 as the seed gives you 10; 3 yields 4 and so on.

Now let’s go back to the previous room generation algorithm for a roguelike. The writer wants a continuous series of random numbers for their room dimensions. Ideally, they need a source of chaos that spits out endless, unpredictable random numbers to act as seeds. A favoured source is the computer’s clock. It sits there literally counting the minutes (or more accurately the milliseconds), updating the clock’s state hundreds of times per second. The algorithm can think of the clock as a seed generator that throws out an endless stream of numbers.

Let’s say that the first instruction (Let X equal a random number between 1 and 10.) is executed when the clock reads 10:31:04.10111. The number generator snips off the last digit (1) and uses it as the seed for the random number generator, yielding a result of 512. By the time the computer comes to the second instruction (Let Y equal a random number between 1 and 10), time has advanced - let’s say by 3 milliseconds to 10:31:04.104. The seed this time around is 4; plugging 4 into the random number generator yields 9. So, when the computer gets to the third instruction, it will draw a 5x9 rectangle. Keep doing this, and they’ll end up with rooms all manner of unpredictable shapes and sizes.

## Elite generation

That works fine if they want a different environment every time. But what if the author wanted to generate an environment that was always the same? In this case, they could plug the output of the random number generator back into the beginning, so that the output of one run then becomes the seed for the next run. This way, the process is unguided but it always yields the same results whenever your run it. If, in the case of our random number generator, it starts off with 1 as the seed, it gives 5 as the result; plugging 5 back in as the seed gives 3; 3 yields 4 and so on. If you repeated this process, the result would be the same. To get the process started, the game author would have to provide the initial seed of 1 (this number would be stored on the game disc), but then they could sit back and watch as the computer churned the numbers and built up the game world. They could even experiment with different seeds before settling on the initial seed that gives their favourite results. What’s important in the end is that when the player starts the game, the game world generator takes that initial seed stored on disc and creates the same world.

Generating a world that’s the same every time is not as pointless as it might seem. When a game features one consistent world (generated or not) all the players can share their experiences or compete with each other in a common frame of reference. It’s also essential when the player might need to revisit areas they’ve already been, in which case the generation procedure must rebuild that portion of the world in precisely the same way as before.

One early computer game in particular relied on this ability. It was called Elite and allowed the player to take control of an interstellar space craft going from world to world, trading exotic resources, fighting space pirates and avoiding the galactic police. The goal was to get rich by buying low, selling high and carrying out an odd bit of ‘no questions asked’ work on the side. It is also an example of how procedural generation is not just limited to drawing shapes.

Elite was launched in 1984 for the BBC Micro on a floppy disc that could store just a few hundred thousand bytes. Yet the game is capable of generating a universe of 282 trillion galaxies, each with 256 named star systems. That’s right: every star system had a name, a pronounceable (albeit science-fictiony) name. Examples included Lave, Diso or Leesti. Clearly all these trillions of names couldn’t be stored on a flimsy floppy, so, just like the layout of the galaxy, the names were procedurally generated as well.

This was done by referring to a long string of letters which was stored on the disc:

“LEXEGEZACEBISOUSESARMAINDIREAERATENBERALAVETIEDORQUANTEISRION”

To generate the name of a star system, a few random numbers are chosen (whose values don’t exceed the length of this string). Each number would correspond to a letter in the string, and for each one the game engine would take both the corresponding letter and its immediate successor. When all letters were put together, they spelled out the name. For example, the numbers 1, 5 and 11 might be generated. As a result, the algorithm would pick out “LE”, “GE” and “BE”, giving a star system called “Legebi”13.

Try it yourself!

An interesting fact… Although the original 1984 edition of Elite could create a universe of 282 trillion galaxies – creating the feeling of being an insignificant speck on an insignificant speck – this ability was vastly curtailed on orders of the game’s publisher14. Their view was that such a colossal universe would make the player suspect mathematical trickery was behind everything and leave a strong feeling of artificiality. In the end, the game included only eight galaxies.

Conversely, the authors of No Man’s Sky have not felt bound by such a fear. Was that a smart move? I’m sure the gamers will be debating it for some time.

In the meantime, I’ll be mowing my lawn.

## In summary

In this article I’ve shown you how it’s possible to draw shapes of endless size and complexity, generate maps populated with creatures and treasures, and even produce an impossibly huge list of original names in just a few milliseconds. The examples I used may have come from the early days of video games, but modern games using procedural generation – more sophisticated and better-looking as they are – still follow the basic ideas written here.

I certainly hope that I’ve demystified the magic behind a procedurally generated game like No Man’s Sky. The monumental size of its game world is created by some programming trickery. Travelling through its universe is akin to travelling through a fractal. As you keep going, the computer dutifully continues to create the world around you out of nothing more than a list of algorithmic instructions. When you land on the next planet, the game doesn’t load that planet’s data from the game disc. It puts the new world together in real time in the blink of an eye by taking a few basic object types and coming up with endless varieties. After all, every object has properties to manipulate, just as in a roguelike a room has dimensions. Plants have properties like type, size, colour. This plant here is a weed, a short red one. That plant there is a tree, tall, skinny and purple. Oh, there’s a yellow dinosaur-type creature with six legs that’s covered in feathers. Keep repeating this long enough, and you end up with a fully-populated planet to explore.

Once you’ve explored that one, then where to next? Well, there’s a quintillion choices and chances are your next destination will be very different from the last.

## Notes and references

1. http://www.polygon.com/2014/8/19/6045933/its-impossible-to-visit-every-planet-in-no-mans-sky

2. http://www.blu-ray.com/faq/

3. A byte is the smallest amount of storage your computer can address, and is the amount of space takes to store one character.

4. http://wiki.openstreetmap.org/wiki/Planet.osm

5. Robert X. Cringely. Accidental Empires. Addison-Wesley, 1996.

6. http://mathtician.weebly.com/t-square-fractal.html

7. http://math.rice.edu/~lanius/frac/koch.html

8. Just for your interest, you could also make a pseudo-3D game this way. Again, the lines would tell the computer where the walls are, but it would render the world from the player’s point of view by putting a virtual camera onto the map. If the camera points at a line, the computer renders a wall in front of the player. This is how games like Doom work.

9. http://pcg.wikidot.com/pcg-algorithm:dungeon-generation

10. http://www.roguebasin.com/index.php?title=Dungeon-Building_Algorithm

11. That’s 10 hours 31 minutes 4 seconds and 101 milliseconds.

12. 5 = 5 x 1, 5 = remainder when 5 is divided by 11

13. http://wiki.alioth.net/index.php/Oolite_planet_list#Where_do_these_crazy_names_come_from.3F

14. https://www.theguardian.com/books/2003/oct/18/features.weekend