How to generate random terrain

I've been doing some research on terrain generation algorithms, and they are defined here as an algorithm that generates a random "heightmap". A heightmap is an image which is black and white, where the difference between the black and white is the height of the map. You could do these in some random paint-software, but if you need them to be random each time, you have to make an algorithm. For example, the game environment in Minecraft is random each time the game begins.

Random

This is the random version:

Sparks 

Read more: Cartania
This was the first algorithm I tried, I don't believe it has a name, but I named it Sparks. The idea is that you generate several random points and to each point you say that the area surrounding the point should be either land or sea. This was the result:

Hill Algorithm

Read more: Robot frog
The idea behind this algorithm is that you generate many circular hills of random size, and this will give you a terrain similar to:

This algorithm could be modified to speed up the process by first generating the land, then the grass (make sure you have beaches), and so on. This was the result:

Particle Deposition

Read more: Gilles LeBlanc
This algorithm uses the same algorithm as a volcano uses when a volcano generates terrain, but without the volcano. The idea is that you fire the rocks from the volcano on to your map, each time a rock lands on the current ground, you have to check if the rock can continue to roll down, if so roll it down, and if not, don't move the rock. This image explains the process:
Particle Depositon. Source: California State University

The problem with this algorithm is that it's a very slow process since you have to fire each rock and then check if the rock can move, but the result is good:

Value Noise

Read more: Lode Vandevenne
I believe that this is the algorithm used in Minecraft. Markus "Notch" Persson, the creator of Minecraft, has written a shorter post on the terrain generation in Minecraft. According to the blog post, he claims that he used Perlin Noise, but Perlin Noise and Value Noise are similar and are often confused with each other. Anyway, here's the result from Value Noise:

More details and higher resolution. The resolution here is 320x240 and it took about 5 seconds to generate this image (about 1-2 seconds to generate the heightmap itself, the rest of the time is what it took to display the heightmap with Python), so the algorithm is so far the fastest one: 

A heightmap generated with the same algorithm:

Diamond Square

Read more: Paul Boxley
If you would like to see Notch code a random terrain algorithm, you can watch him code one when he is creating the game "Minicraft" here: Twitch (begins at around 3:28:00). I believe that he was coding some kind of modified Diamond Square algorithm and I decided to make a similar algorithm. Here's the result:

And here's the island-version compared with an island from Google Maps, the size is 512x512 and it took about 2.6 seconds to generate the coordinates:

You can easily create a more smoother map by taking the average of the height of the 9 surrounding coordinates at each coordinate. The smooth version with smaller beaches:

Other algorithms

If you are not satisfied with Value Noise, you might want to check out:
  • Perlin Noise (make sure the author of the articles you find has not confused Perlin Noise with Value Noise)
  • Polygonal (Read more: Stanford)

Update!
You can find the python-code here: github.com/Trejdify/Random-Terrain

Comments

  1. Try adapting Schelling's Segregation Model. Makes for nice clean regions.

    ReplyDelete
  2. I've used a midpoint displacement algorithm to do this kind of thing.

    ReplyDelete
  3. Very nice post! In the value noise example, it looks like there are only 6 different pixel values. Does that mean the height map only has a difference of 6 units in height from the lowest point to the highest? Is there some kind of smoothing done before turning a height map (I would assume directly) into a 3d landscape?

    ReplyDelete
  4. Thanks for the link/reference in the particle deposition section! It's appreciated. Also you did a very good writeup with your article. I will definitively look into the value noise algorithm thanks to you.

    ReplyDelete
  5. fractals are an easy and very effective way to generate such terrains.

    ReplyDelete
  6. Fractional Brownian Motion (fBm) is a really good basis function for terrain generation.

    I'd be a little worried about your code - 5 seconds to produce that image is really very slow.

    ReplyDelete

Post a Comment