Midpoint Displacement

Midpoint displacement is a common way to generate terrains in video games. Instead of manually creating a stage you can make an algorithm create one based off randomness. This is faster to calculate than a perlin noise stage which is why it can be found frequently in older video game titles.


Psudo code:


This canvas starts off with two points in an array called points[], one at height/2 and one at math.random(-vertical_displacement, vertical_displacement). The center point is found and a new point is made and added to the array. This new point is offset on the y-axis by an amount however we can't use the same vertical_displacement as we did before as we'd end up with a very jagged terrain.

Instead we have to iterate our variable - vertical_displacement - based on the iteration number of the sketch, in order to generate a smooth stage/terrain.

vertical_displacement = points[0].y + points[1].y / 2;
vertical_displacement *= 2 ** (-roughness);

The top formula is the inital value. The second is applied very iteration of the sketch.

Right now we can add one point to the list, time to add several! This means for loops. But before we can loop through our array how do we know which point should connect to which? We need to sort the array based on x value, so that the points read off from left to right.

I just used a bubble sort for simplicity however it's worth pointing out that the number of points grows exponetially - O(2^n) where n = iterations - so after just 10 iterations points.length = 1024. A merge sort could be used to speed up computation times.

Now we can use a for loop to go through our array and compare the ith item to the (i+1)th item, and then update iterations and vertical_displacement.

var pLength = points.length;

 for (var i = 0; i < pLength - 1; i++){
   var midX = (points[i].x + points[i + 1].x) / 2;
   var midY = (points[i].y + points[i + 1].y) / 2;
   midY += random(-vertical_displacement, vertical_displacement);
   points[pLength + i] = new point(midX, midY);
 }

iterations += 1;
vertical_displacement *= 2 ** (-roughness);
bubbleSort();

NOTE: Do not use points.length to define your for loop as we are increasing the length of the array within the loop