#### Introduction

- Midpoint Displacement is a simple algorithm for generating realistic looking height ranges.
- It is a recursive algorithm that subdivides a line into segments, adding a decreasing amount of randomness at each round.

#### Algorithm

- We start with a set of heights initialized to 0. The length of the set must conform to 2
^{n}+ 1. - Then we set the first and last heights to random value. In this case they are 5 and 2:
- Next we set the midpoint to the average of the two endpoints:
- And move (or displace) the midpoint up or down by a random amount. In this case we move it down by 1:
- And repeat the midpoint displacement recursively for the newly created line segments:
- Each time we subdivide the line segments, the amount we displace the midpoint should also decrease:

#### code (Python)

```
from PIL import Image
import PIL.ImageDraw as ImageDraw
import random
import numpy as np
from math import floor
from collections import deque
def main():
imageWidth = 513
imageHeight = 256
roughness = 200
# we initialize all the heights to 0
heights = [0]*imageWidth
# and then initialize the first and last heights to random values
heights[0] = random.randint(0, 256)
heights[imageWidth - 1] = random.randint(0, 256)
# we create a queue of the line segments we need to subdivide
q = deque()
# and add the first segment to it
q.append((0, imageWidth - 1, roughness))
# now we go through and subdivide each segment
while len(q) != 0:
left, right, randomness = q.popleft()
center = (left + right + 1) // 2
# set the midpoint to the average of the two ends
heights[center] = (heights[left] + heights[right]) // 2
# and then add some randomness
heights[center] = heights[center] + random.randint(-randomness, randomness)
# if the width of the segment is greater than 2 then it can be subdivided
if right - left > 2:
# when we add the new line segments to the queue, we reduce the amount of randomness
q.append((left, center, floor(randomness // 2)))
q.append((center, right, floor(randomness // 2)))
# finally we render these heights
im = renderHeights(heights, imageWidth, imageHeight)
im.save("test.png", "PNG")
im.show()
# draws the given heights on the image
# the heights should be normalized to be between 0 and image.height
def renderHeights(heights, imageWidth, imageHeight):
imagePadding = 32
# we normalize the heights so that its minimum and maximum values
# fit nicely on the image we are about to draw
heights = normalize(heights, imagePadding, imageHeight - imagePadding)
# we need to convert the heights to a series of points to be plotted
points = [(i, heights[i]) for i in range(0, imageWidth)]
# and add the corners so that tha polygon is nice and closes properly
points.insert(0, (0, 0))
points.append((imageWidth - 1, 0))
im = Image.new("L", (imageWidth, imageHeight))
draw = ImageDraw.Draw(im)
draw.polygon(points, fill=200)
return im
# normalizes an array of numbers such that the smallest number will be
# the newLowerBound and the largest number will be the newUpperBound
# every other number will be scaled to be between those points
def normalize(data, newLowerBound, newUpperBound):
min = np.min(data)
max = np.max(data)
range = max - min
newRange = newUpperBound - newLowerBound
return [(a - min) * newRange / range + newLowerBound for a in data]
main()
```