Random Walk Map Generation

I experimented a little with generating world maps. A common approach it to use Perlin noise, which can result in astonishing landscapes. I wanted to see if it is possible to create a world map with a much simpler approach: slightly modified random walks.

My algorithm can be described in five trivial steps:

1. Place N (e.g. 10) arbitrary start points with elevation 'height' (e.g. 500)
2. For each point P in the map, choose a random neighbor P'.
3. Calculate their difference in elevation minus one: diff = P.height - P'.height - 1
4. If diff > 0, move that amount of elevation to the neighbour P'. (i.e. P.height -= diff; P'.height += diff;).
5. Go back to step 2.

The most notable difference to the classical random walk is that due to the condition in step 4, the algorithm does not like to revisit nodes it has visited before. Note that step 2 can be optimized by focusing on the known hot spots.

Doing this on a 640x480 map with 10 start points looks as follows.

Starting with 10 islands

Islands are growing

Some of the islands connected

First larger landmasses emerge

Final map

What are the advantages of the random walk approach?

• It is trivial to implement.
• The two parameters (number of start locations and their height) allow to intuitively tune the number of islands as well as their size.
• The algorithm can be applied to any graph or topology. Unlike with the Perlin approach, no coordinate system is required. All that's needed is a set of connected nodes.

The main disadvantage of this approach is that it is computationally expensive when generating large landmasses as the same nodes are revisited often.