Diamond Square Terrain Generation

[
  {
    "position": 0,
    "color": "#000080"
  },
  {
    "position": 0.15252604166666667,
    "color": "#0066ff"
  },
  {
    "position": 0.350859375,
    "color": "#cc9933"
  },
  {
    "position": 0.5825260416666667,
    "color": "#00cc00"
  },
  {
    "position": 0.7891927083333333,
    "color": "#996600"
  },
  {
    "position": 1,
    "color": "#ffffff"
  }
]

Here's how it works

Initial Setup

• Start with a 2D grid of size (2^n + 1) × (2^n + 1), like 129×129 or 257×257
• Set random height values at the four corners of the grid

The Diamond Step

• Find the center point of each square in the grid
• Set its height to the average of the four corner points plus a random value
• This creates a diamond pattern when you connect these points

    
typescript
    
private diamondStep(x: number, y: number, step: number, scale: number): void {
    const halfStep = step / 2;
    const points = [
        this.heightmap[x - halfStep]?.[y - halfStep],
        this.heightmap[x - halfStep]?.[y + halfStep],
        this.heightmap[x + halfStep]?.[y - halfStep],
        this.heightmap[x + halfStep]?.[y + halfStep]
    ];

    const average = this.getAverage(points);
    this.heightmap[x][y] = average + this.rand.randomRange(-scale, scale);
}

The Square Step

• For each diamond created in the previous step, find the midpoint of each edge
• Set the height to the average of the surrounding four points plus a random value
• This creates new squares for the next iteration

    
typescript
    
private squareStep(x: number, y: number, step: number, scale: number): void {
    const halfStep = step / 2;
    const points = [
        this.heightmap[x - halfStep]?.[y],
        this.heightmap[x + halfStep]?.[y],
        this.heightmap[x]?.[y - halfStep],
        this.heightmap[x]?.[y + halfStep]
    ];

    const average = this.getAverage(points);
    this.heightmap[x][y] = average + this.rand.randomRange(-scale, scale);
}

Recursion

• The grid is now divided into smaller squares
• Reduce the size of the random variation (usually by half) each iteration
• Repeat the Diamond and Square steps on each smaller square
• Continue until the entire grid is filled

The "roughness" or "persistence" parameter controls how quickly the random variations diminish in each iteration. Higher values create rougher terrain, while lower values produce smoother landscapes.

    
typescript
    
generate(size: number, roughness: number, seed?: number): number[][] {
    // Size must be 2^n + 1
    if (size % 2 !== 1) {
        throw new Error("Size must be 2^n + 1");
    }
    this.heightmap = Array(size).fill(0).map(() => Array(size).fill(0));
    this.rand = seed ? new SeededRNG(seed) : new VanillaRNG();

    // Set initial corner values
    this.heightmap[0][0] = this.rand.randomRange(-1, 1);
    this.heightmap[0][size - 1] = this.rand.randomRange(-1, 1);
    this.heightmap[size - 1][0] = this.rand.randomRange(-1, 1);
    this.heightmap[size - 1][size - 1] = this.rand.randomRange(-1, 1);

    let step = size - 1;
    let scale = 1.0;

    while (step > 1) {
        const halfStep = step / 2;

        // Diamond step
        for (let x = halfStep; x < size; x += step) {
            for (let y = halfStep; y < size; y += step) {
                this.diamondStep(x, y, step, scale);
            }
        }

        // Square step
        for (let x = 0; x < size; x += halfStep) {
            for (let y = (x + halfStep) % step; y < size; y += step) {
                this.squareStep(x, y, step, scale);
            }
        }

        step /= 2;
        scale *= Math.pow(2, -roughness);
    }

    return this.heightmap;
}

What makes this algorithm particularly interesting is how it creates natural-looking terrain through a relatively simple process. The fractal-like nature of the algorithm means that the terrain looks similar at different scales - a characteristic often found in real landscapes. However, it can sometimes produce artifacts like visible square patterns, which is why many modern terrain generators use more sophisticated variations of this basic approach.

The algorithm's main limitation is that it requires a grid size of 2^n + 1, but this constraint helps maintain consistent detail levels across the generated terrain. Despite being developed in the 1980s, it remains a fundamental technique in procedural terrain generation, often serving as a building block for more complex algorithms.