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.

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.

 

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!

Conversation
  • Is it possible to make the edges of the world merge together? For example, can the world be 32 chunks wide and seamlessly mesh together at the edges, allowing a player to travel continually eastward and end up where they started?

    • Shawn Anderson Shawn Anderson says:

      Thanks for the question.

      The shape you’re defining is a torus. I’ve never thought about connecting some arbitrary edges together. An easy cop-out would be to make your world an island with all water edges. That could be achieved by scaling the height down based on the distance from the center of the map. You could also do some digging on this subreddit or ask for some ideas there.

  • Jacob says:

    you could use 3D simplex noise

    I just made a quick example of this in swift…
    https://github.com/j-j-m/SceneKit-Experiments

    • Shawn Anderson Shawn Anderson says:

      Thanks for responding, Jacob.
      You are definitely right, 3D simplex could be used.
      I’ll have to check out your examples.

  • Cave Johnson says:

    How do you make sure that the sides of adjacent chunks merge?

    • Shawn Anderson Shawn Anderson says:

      Hey Cave,

      The chunk edges all line up thanks to Perlin noise. It can produce an infinite plane of heights that I use for the tiles. The chunks just let me control how much I load into memory at a time. Hope that helps.

      • Cave Johnson says:

        Thank you, I’ll look into the Perlin noise some more.

  • Chris Perver says:

    This is great. I was thinking about doing something like this in C, but I didn’t know how to make the edges of the chunks line up. Will look at the code to see how it is done. Would be interesting to add a height map to this to make it 3d.

    • Shawn Anderson Shawn Anderson says:

      Thanks Chris. Using Perlin noise is what gives you the smooth edges that line up. This does build a height map, but my code slices that down into various tiles based on that height-map. Using that to build a height-map should be pretty straight forward. Feel free to contact me if you’d like any help going through the code.

      • Carl Smith says:

        Do you need to generate the height map for the whole world, then chop it into tiles? If so, it cannot be infinite?? I don’t understand how to render the individual tiles incrementally, but still have them join up at the edges.

        • Shawn Anderson Shawn Anderson says:

          Carl,
          That’s the beauty of the Perlin noise: it gives us a known set of data that all fits together. We can generate height maps for an area using the Perlin noise data knowing that if/when we need to generate the next chunk the Perlin noise will line up smoothly. Hopefully that makes sense. If not, this blog does a great job explaining it: https://www.redblobgames.com/maps/terrain-from-noise/

          Thanks for “stopping by”

  • Comments are closed.