# Implementing Midpoint Displacement Algorithm

**URL:** <https://discourse.processing.org/t/implementing-midpoint-displacement-algorithm/20441>\
**Category:** Coding Questions\
**Created:** [May 3, 2020, 4:58pm UTC](https://discourse.processing.org/t/implementing-midpoint-displacement-algorithm/20441 "2020-05-03T16:58:53Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![Dangeroustuber](https://avatars.discourse-cdn.com/v4/letter/d/dec6dc/32.png) [@Dangeroustuber](https://discourse.processing.org/u/Dangeroustuber)\
**Post date:** [May 3, 2020, 4:58pm UTC](https://discourse.processing.org/t/implementing-midpoint-displacement-algorithm/20441/1 "2020-05-03T16:58:53Z")

</div>

Hi, i want to implement the Midpoint displacement algorithm. Please help!

I can’t find a good source to follow in 1D and i dont understand it fully that i can implement it myself alone. I’m not interested in 2d case before i manage to make something like the image below.

This is the code i have so far. The loop does the calculation necessary from a math perspective.

Things i think im missing:  
random numbers and assigning all the info to a straight line on screen

```auto
float[] v = new float[1025];

void setup() {
 size(600,600); 
}

void draw() {
  for(int i = 2*2*2*2*2*2*2*2*2*2; i > 1; i /= 2) {
    for(int j = i / 2; j < 2*2*2*2*2*2*2*2*2*2; j = j + i ) {
    /*   
    give value to v[j] = + number * rnd function
    */
    }
  }
}

```

I’m simply looking to create something like this:

![0fd97fc7ab7ac5a7670935f1695d2a0c614e5252 (1)](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/a/a966ebe35b226e7ad06b1b1ec20111b7e93b121b.png)

Example found on google.

---

<div class="post-metadata">

**Author:** ![quark](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/quark/32/26_2.png) [@quark](https://discourse.processing.org/u/quark)\
**Post date:** [May 3, 2020, 5:55pm UTC](https://discourse.processing.org/t/implementing-midpoint-displacement-algorithm/20441/2 "2020-05-03T17:55:09Z")

</div>

The MPD algorithm is best done using a recursive method, the code you show uses an iterative approach which will not work well or if at all.

So the algorithm works like this. Lets keep it simple and assume that we have just 9 points rather than the 1025 in your code. In fact we can have any number of points np provided np = 2^n + 1 where n is any positive integer.

Lets call these points p\_0, p\_1 … to p\_8 and we start with knowing the values for the first and last point.

So step one is to calculate the mid point  
p\_4 = (p\_0 + p\_8)/2 + displacement.

Now we have three points we can calculate two more mid points  
p\_2 = (p\_0 + p\_4)/2 + displacement.  
p\_6 = (p\_4 + p\_8)/2 + displacement.

Now we repeat the process  
p\_1 = (p\_0 + p\_2)/2 + displacement.  
p\_3 = (p\_2 + p\_4)/2 + displacement.  
p\_5 = (p\_4 + p\_6)/2 + displacement.  
p\_7 = (p\_6 + p\_8)/2 + displacement.

Where displacement is some random value and we now have all 9 points.

You can see we are repeating the same process but with smaller and smaller segments, this is typically done recursively.

---

<div class="post-metadata">

**Author:** ![Dangeroustuber](https://avatars.discourse-cdn.com/v4/letter/d/dec6dc/32.png) [@Dangeroustuber](https://discourse.processing.org/u/Dangeroustuber)\
**Post date:** [May 3, 2020, 8:22pm UTC](https://discourse.processing.org/t/implementing-midpoint-displacement-algorithm/20441/3 "2020-05-03T20:22:49Z")

</div>

Thank you i really appreciate your answer. Sadly i’m not skilled enough to fully understand the connection between what you have written and how it would look like in code. I do understand what you have written though, that makes sense to me.

Could you give me steps to solving with _recusive method_? or could you explain how i would do the recursion and then how i would apply the implemented function.

---

<div class="post-metadata">

**Author:** ![quark](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/quark/32/26_2.png) [@quark](https://discourse.processing.org/u/quark)\
**Post date:** [May 4, 2020, 6:54am UTC](https://discourse.processing.org/t/implementing-midpoint-displacement-algorithm/20441/4 "2020-05-04T06:54:53Z")

</div>

I can provide simple code to do the 1D case and that will demonstrate the recursive method do you want me to post it?

---

<div class="post-metadata">

**Author:** ![Dangeroustuber](https://avatars.discourse-cdn.com/v4/letter/d/dec6dc/32.png) [@Dangeroustuber](https://discourse.processing.org/u/Dangeroustuber)\
**Post date:** [May 4, 2020, 7:44am UTC](https://discourse.processing.org/t/implementing-midpoint-displacement-algorithm/20441/5 "2020-05-04T07:44:20Z")

</div>

I would like that very much thank you. That would be very helpful.

---

<div class="post-metadata">

**Author:** ![quark](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/quark/32/26_2.png) [@quark](https://discourse.processing.org/u/quark)\
**Post date:** [May 4, 2020, 8:16am UTC](https://discourse.processing.org/t/implementing-midpoint-displacement-algorithm/20441/6 "2020-05-04T08:16:26Z")

</div>

This is only a guide for you to experiment with there are several improvements for instance using noise() instead of random() and use bezier curves to get a smoother contour.

```auto
// Number of points must be 2^n + 1 where n is any
// positive integer
int np = 65;

float[] p = new float[np];
float stepSize; // horizontal distance between points
float displacement; // the maximum vertical displacement 
                    // at the mid point (may be + or -)

void setup(){
  size(1025, 400);
  stepSize = float(width) / (np- 1);
  displacement = 2 * stepSize;
  // Initialise the values 
  p[0] = random(0.2, 0.45) * height;
  p[np - 1] = random(0.55, 0.8) * height;
  mpd(p, 0, p.length -1);
}

void draw(){
  background(255);
  stroke(255,0,0);
  strokeWeight(1.1);
  for(int i = 1; i < p.length; i++){
    line( (i-1) * stepSize, p[i-1], i * stepSize, p[i]);
  }
}

// This is a recursive function because it calls itself!
void mpd(float[] array, int ps, int pe){
  // find the index for the centre array position
  int pmid = (pe + ps)/ 2;
  // if it is the same as the start then recursion is finished
  // We must have some condition to halt recursion otherwise we 
  // crash the sketch
  if(pmid == ps) return; // finished
  // Calculate the midpoint position and add a displacement
  array[pmid] = 0.5 *( array[ps] + array[pe]) + random(-displacement, displacement);
  // Now recurse the function with the two 'sub arrays'
  mpd(array, ps, pmid);
  mpd(array, pmid, pe);
}

```