# Midpoint Displacement in one dimension

## Prerequisites

### Midpoint Displacement in one dimension

#### 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

1. We start with a set of heights initialized to 0. The length of the set must conform to 2n + 1.
2. Then we set the first and last heights to random value. In this case they are 5 and 2: 3. Next we set the midpoint to the average of the two endpoints: 4. And move (or displace) the midpoint up or down by a random amount. In this case we move it down by 1: 5. And repeat the midpoint displacement recursively for the newly created line segments: 6. 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 = *imageWidth

# and then initialize the first and last heights to random values
heights = 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):

# we normalize the heights so that its minimum and maximum values
# fit nicely on the image we are about to draw

# 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()``````