Diamond Square algorithm

For my class Procedural content generation my team and I are working on creating a procedural vulcano island. We created our project with Unity. Each of us uses their own approach to creating this vulcano island.

Play demo 0.1
You can try the first version here:
Play here

Approach
The vulcano island that I want to generate has to do this with the help of 'Eveolutionairy AI'. Before I can address this however, I need to generate some terrain that looks a bit like actual terrain. The end result will be judged by the user instead of the code (which is normally the case with Evolutionary AI). All terrains that pass the test are then compared by the user to see which random value yield the best result. But first: the algorithm to generate the base terrain. We use 5 different colors to identify the terrain:
- red: lava
- blue: water
- green: vegetation
- brown: dirt
- grey: rock


Midpoint algoritm
Right after my search for terrain generation I came accross an algorithm which is used in 2d games: the midpoint algorithm. This deceivingly simple algorithm uses a simple step in combination with recursion to generate lovely 2d mountains.The algorithm also allows for 'tweaking'of the terrain generation. If I can somehow manage to have a good control on those random values, I might be able to get the results I want.
The following steps and image explain the way the midpoint algorithm works:
- Find the midpoint of 2 points
- Apply random height to the midpoint.
- repeat process x number of times for every 2 new points.


One of the random values we can influence is the 'roughness' value. The image below (source) demonstrates how the roughness value can influence the fractals of the terrain.


Diamond Square
Now that we have a 2d terrain generator, we move on to the 3d stuff. The Diamond square algorithm utilizes the midpoint algorithm and allows us to create 3d terrain. The algorithm works as follow:

1. Generate a tile map or a 2d vertex array in the shape of a square. The dimension should be a power of two, plus 1. For my scene I use a 2d vertex array of 129x129.
2. The diamond step
- Take a square of 4 points from your terrain
- Average the heights of the corners
- Add a random value to the average
- Apply average to center of the square
3. Square step
- Apply midpoint algorithm for every 2 points in the square.
4. Repeat steps 2 and 3 till all tiles/vertices have been used in the algorithm.



Results and optimization
The first resulst are in! The folloing 2 images show a representation of the terrain roughly is going to look like. Note that the terrain uses vertex coloring which can result in odd color combo's (for instance: lava that goes up and down).



For a first test, I am quite happy. However, the test results can vary enormous, even if the same range of random values is used. The image below shows a generated terrain with the same range values as the image above. Obviously, I need to do somehting about that. In the next blog I will discuss how I address this and how the research for the perfect Vulcano island develops.