Midpoint Displacement

Up until now all of our programs have been printing grids to console. These were cool to look at but were often only useful for a very specialized purpose. Because of this were are going to do something very different. We are going to write our own Midpoint Displacement algorithm. Midpoint Displacement is a form of the Diamond-Square algorithm ( another algorithm we will be covering later on ). These two algorithms are very similar the main difference being Midpoint-Displacement outputs a line while Diamond-Square outputs a grid. However, to better understand Diamond-Square we later on we are starting simple with Midpoint-Displacement. So let's get started!

Midpoint-Displacement is an extremely simple algorithm ( I wrote a Java version back in high school its so simple ) but it creates unique and interesting outputs every time we run it. The algorithm works as follows. First, two endpoints are created. These will be used as anchors. A midpoint is then found between the two points and it offset by a random number based on a "roughness" value. The algorithm is then run again doing the same thing. Finding the middle between each point and raising or lowering the point based on the "roughness." The idea is simple so let's see what it looks like in code.

Extremely straightforward. The method calls itself each loop around and makes sure that it is only doing the number of points that there should be. We can see there are two methods that we use that are not in the code so we can look at those briefly below.

The "middle" method is just your run of the mill midpoint formula that you learned in elementary school. Then with the "displace" method we can see that we keep the x-value the same and modify the y-value based on it's current value plus a random number in between the negative roughness and positive roughness.

In order to see how what this outputs, I wrote a small method that plots the x and y values on a black image. So when we run the program, we might expect to see something like this.

Or something like this.

We can see that the Midpoint-Displacement algorithm generates ridges and valleys. This has some practical use in real games too! 

Source

I lot of people probably remember playing that game ( or something similar ). It used an algorithm similar to Midpoint-Displacement to create its random and interesting terrains. 

We've got a basic understanding of Midpoint-Displacement now so we can next talk about the Diamond-Square algorithm! This algorithm also has a lot of use in real life games. As usual, hope you learned something and you can see the source code here.