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 2ⁿ + 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 = [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()