HOME Mathematics Computer Science
Midpoint Displacement in two dimensions
Midpoint Displacement in two dimensions

Introduction
  • The Midpoint Displacement algorithm can be extended into two dimensions
  • This allows us to generate 2D heightmaps that can be used for terrain generation
Image rendered in SketchUp
Algorithm
  1. We start by setting the corners to random values:
  2. Then we displace the midpoint of each edge:
  3. And set the center to be the average of the 4 midpoints + a random displacement:
  4. Finally, we apply the above two steps recursively:
Code
import random
from math import floor
from collections import deque

def main():
    size = 129
    heightmap = [[0]*size for i in range(size)]

    heightmap[0][0] = random.randint(0, 256)
    heightmap[size - 1][0] = random.randint(0, 256)
    heightmap[0][size - 1] = random.randint(0, 256)
    heightmap[size - 1][size - 1] = random.randint(0, 256)

    q = deque()
    q.append((0, 0, size - 1, size - 1, 200))

    while len(q) != 0:
        top, left, bottom, right, randomness = q.popleft()

        centerX = (left + right) // 2
        centerY = (top + bottom) // 2

        heightmap[centerX][top] = (heightmap[left][top] + heightmap[right][top]) // 2 + random.randint(-randomness, randomness)
        heightmap[centerX][bottom] = (heightmap[left][bottom] + heightmap[right][bottom]) // 2 + random.randint(-randomness, randomness)
        heightmap[left][centerY] = (heightmap[left][top] + heightmap[left][bottom]) // 2 + random.randint(-randomness, randomness)
        heightmap[right][centerY] = (heightmap[right][top] + heightmap[right][bottom]) // 2 + random.randint(-randomness, randomness)

        heightmap[centerX][centerY] = (heightmap[left][top] +
                                       heightmap[right][top] +
                                       heightmap[left][bottom] +
                                       heightmap[right][bottom]) // 4 + \
                                      random.randint(-randomness, randomness)

        if right - left > 2:
            q.append((top, left, centerY, centerX, randomness // 2))
            q.append((top, centerX, centerY, right, randomness // 2))
            q.append((centerY, left, bottom, centerX, randomness // 2))
            q.append((centerY, centerX, bottom, right, randomness // 2))

main()