Diamond Square

Last time we talked about the Midpoint Displacement algorithm in preparation for the Diamond Square algorithm. Dimond Square is basically a 2D version of Midpoint Displacement. It has lots of use in modern video games due to its speed and ease of implementation. So let's get started to see how it actually works.

Source

Wikipedia has a helpful image to help easily understand the algorithm. First four corners are selected and their height values are remembered. Those values are averaged and given a random offset value. The center of those four is now the new corner. This is the diamond step. The square step is next. The middle is used as a reference and each point out from it is set to a random value and the average of the four corners. This is repeated multiple times. 

In the code below we can see the implementation of the "generate" method. This method is where the bulk of the work for Diamond Square is done. It loops over the grid a certain number of times, each time doing a "diamond' step and a "square" step as discussed above.

Then below we can see the implementation of the actual diamond_step and square_step methods. These do as discussed in the description above.

The last bit we have to talk about is the sample method. This is a clever method that uses bit operations to get locations on the map. Because of how it works it allows the map to wrap around itself and generate maps that have borders that will be seamless. We can see the actual implementation below.

Now that we see how it works, we can see the result!

This is an example output. We can see the high areas are lighter than low areas. This has a fault though which is discussed below.

While this algorithm has advantages, it also comes with some downfalls. One of the notable downfalls that affects many when using this algorithm is that it has a tendency to generate ridges in lines. So many times there will be a set of ridge peaks or valleys at very similar locations. There are ways around this but those are out of the scope of this post. Another downfall is that the map has to be a size of 2^n + 1. This is rarely a problem but can be if you need a certain sized map. The simplicity of this algorithm is what makes it so powerful and why these downfalls are rarely an actual problem.

Thats the basics with Diamond Square. It's a simple implementation and generates random results. As usual hope you learned something and heres the full code.