9 Comments

Building an Infinite Procedurally-Generated World

I had a lot of fun writing my last blog post: All Work & No Play – Taking Time to Code for Fun. In it I talked about writing fun code that keeps you interested in programming and keeps you creative. I used the example of writing a 2D procedurally-generated, infinite world. In this post, I am going to explain details of how that example works.

proc_terrain_small

Bring the Noise

To build our terrain, we need something better than just randomly selecting a tile for each set of coordinates. Since we want the world to be infinite, we can’t design it by hand: that’s where Perlin noise comes in. Perlin noise is an algorithm for generating organic looking, multidimensional noise quickly (at least for 2D). You’ll want to know a few terms when playing with Perlin noise:

Octaves
The number of subsequent generations to run, usually double the frequency and half the amplitude.
Persistence
How to weight the additional octaves when adding them.

These can be fun to play with when generating terrain; they will make it smooth and flat or bumpy and spiky.

Homework assignment: try merging two noise datasets that have been generated with different octave / persistence values.

From Noise to Tiles

Once you have access to random 2D data, it’s pretty straight forward to convert that noise into usable data. Simply set up thresholds for each tile type you want to support, eg:

  • water if < 0.3
  • grass if >= 0.3 and <= 0.6
  • mountain if > 0.6

I recommend leaving the upper and lower cases open. If they are not left open, you may end up with holes in your map for unexpectedly high or low values. An alternative is to clamp or scale the noise values when you generate them.

Going Beyond Tiles

An infinite world of terrain isn’t all that interesting for very long without something in it. We want to add things like trees, caves, and towns to our game. We can simply use the same random number generator (RNG) that we used to generate our noise to determine when to place and how to build objects. We have to be careful though. If we use a single RNG for the whole world, the order in which we discover things will change the how they are generated.

chunks_small

The trick to deterministically creating the world based on a seed is to break it up into chunks (see screenshot above). A chunk is simply a range of tiles in the world. We keep 9 chunks loaded at a time. Each chunk is 50×50 grid of tiles. When the player enters a place with no chunk, we generate a new one. The first thing we do is seed a new RNG for that chunk with the global seed and the coordinates for that chunk. This allows us to throw away the chunk when the player leaves it, but know that it will be recreated the same when the player comes back. Just make sure your code is deterministic and that it only pulls random values from the chunk’s RNG and things should work out well.

The source for this project can be found on github. Please leave a comment if you are doing something similar and want an excuse to show off.

UPDATE:
Example uses tileset from Oryx Design Lab. Thanks!