Saturday, 30 April 2011

Simple procedural heightmap generation

There are already several methods for procedural terrain generation (perlin noise, fractals, diamond-square algorithm, etc.). All of them has it's advantages, disadvantages, I do not want to judge or compare them, I just want to describe yet another method I came up with. I think it's main advantage is it's simplicity, it is very easy to implement, yet produces interesting terrains.

The algorithm starts with a flat heightmap, i.e. every cell of the map has a height of 0. Then in a number of iterations it modifies the heightmap, creating the final terrain. In every iteration step a line is generated which crosses the map region, this is achieved by randomly choosing two defining points in the map area. Then the height of every cell of the map on one side of the line is increased by a given value (practically by 1). That is, we repeatedly cut the map into two halves randomly, and raise the level of one of them.

After several iterations the heightmap has enough variation. The height values are between 0 and the number of iterations. After finding the minimum and maximum values we can interpolate the height values into any range we want. The number of iterations required to get a good looking terrain depends on the size of the map, larger maps usually require more iterations.

Advantages of this algorithm:
  • simplicity
  • works for any map size
  • scalable (the quality of the terrain can be controlled with the number of iterations)
  • high computational cost ( for an W*H sized map and N lines it is O(W*H*N) )
  • not "infinite" like perlin noise
An online demo is available here, it is implemented in processing.js. It generates a 100*100 map with 256 iterations. Since it runs in the browser the calculation speed is quite slow, so be patient.
The source code is also available: download.

A 256x256 map generated with 1024 lines

1 comment: