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

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 (Python)

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