February 10, 2013

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.


This is the random version:


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)

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