Gameplay and Artificial Intelligence Programmer

Terrain Generation

Category : Final Year Project Jan 6th, 2014

The Diamond-Square algorithm creates pretty nice looking fractal terrain. It works only on 2D arrays that are 2^n+1 square, which is slightly limiting but the results are good enough that I can live with it.

The four corner values must be set before the algorithm runs or you’re going to end up with a perfectly flat terrain which isn’t pretty realistic anywhere out of the Utah salt flats.  The  algorithm then has two steps every tick, the eponymous diamond and square. During the diamond step the algorithm sets the center point by averaging the four values and adding a random value.  The square step sets the four points halfway between each of the corners by averaging  the two values that on either side of it, then, again, adds a random value.

After these two steps have run there will be nine points set, eight around the edge and one in the middle. This means that we now have four smaller squares that we can call the algorithm on each. The process will then continue until there are no empty points left in the array. It’s a nice quick algorithm that produces nice looking terrain, if terrain that doesn’t really vary very nicely.


Diamond-Square Generated Terrain

To produce something a bit nicer, we can use Voroni sectors to simulate ridges across our terrain. Our Voroni algorithm will select a number of random points spread out across our terrain, then, every point in the array is looped through and given a height value that is a function of how far it is away from the nearest pre-selected point, making this function a binomial you can get nice gentler slopes. We can then take this new map, blend it with our diamond-square terrain to create a nice noisy terrain with ridges, much better than either of the maps on their own.