# Midpoint Displacement in two dimensions

## Prerequisites

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