Weeabeu Banner
Anime
Personal
Reviews
Tech
All

Terrain Generation with the Diamond-Square Algorithm

 

Here’s an interesting little algorithm I coded up before an interview – Terrain generation with the Diamond-Square Algorithm.

The algorithm itself is quite simple, but makes some nice graphs.

diamond-square-algorithm

  1. Initialize the corners of your N*N area randomly.
  2. Square Section – Get the center point of your corners and set it to be the average of those 4 corners ± a random amount
  3. Diamond Section – Get the center of each edge and set itto be the average of the surrounding diamond shape ± a random amount
    1. In the example image, the left red point would be the average of the black points above, below and to the right of it – but you should include a fourth point if it exists.
  4. Repeat until your grid is populated.

Here’s what this looks like with a simple heat map in 2D:

687474703a2f2f692e696d6775722e636f6d2f6533436476336e2e706e67

 

And in 3D:

687474703a2f2f692e696d6775722e636f6d2f57345035386c542e706e67

687474703a2f2f692e696d6775722e636f6d2f545a7741434d4e2e706e67

 

This is a very simple algorithm to implement, but quite effective for what it does. You can change the random variant to increase the choppiness/smoothness of the resultant graph. The more points in the grid, the better this looks. Take this high-N example from playful.js for example:

download

 

Setting the sea level in your render is a matter of picking a Y-level and wherever there isn’t any rock below this point, fill the area with water. This is a pretty nice way to get both lakes and hills in one step.

There’s also an added benefit of exporting the co-ordinates so you only have to ever compute the terrain once.

You can browse the source of my implementation (In Python 2.7) on Github

Print Friendly
Labels: Tech

Anything to add?