ExtendedSource checked

Diamond-Square Algorithm

Generates fractal height maps by alternating square and diamond averaging steps.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Procedural Generation
Difficulty: Intermediate
Family: Fractal Terrain
Tier: Extended
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 0
Relationships: 4
Code example: Not ready
Visualization: Ready

Overview

The Diamond-Square Algorithm starts with corner heights and recursively fills midpoints with averaged values plus random displacement.

Core Concepts

generated structureheight fieldmulti-scale detailrandom drawfractal terrainseeded variationrule expansionspatial structure

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(n)

When to Use

Use Diamond-Square Algorithm when you need to subdivide a height grid.
Use it for terrain generation with inputs like grid size.
Use it when repeatable content can be produced from compact rules, parameters, and seeds.
Use it when the Fractal Terrain tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when authored control matters more than variation or replayability.
Avoid it when the required output is not generated height map.

What It Does

Subdivides a height grid
Adds decreasing random displacement at each scale

Use Cases

Terrain generation
Fractal landscapes
Height map prototyping

Inputs

Grid size
Corner heights
Randomness scale

Outputs

Generated height map

Pseudocode

1.Initialize corner heights
2.Run a square step to fill centers
3.Run a diamond step to fill edge midpoints
4.Reduce the random displacement
5.Repeat until the grid is filled

Canonical Example

Input: seed = 42, size = 8x8
Output: generated map, pattern, or noise field
Explanation: Diamond-Square Algorithm: The algorithm expands a small set of rules and random choices into structured content.

Implementation Notes

Keep the input contract explicit: Grid size; Corner heights; Randomness scale.
Use this step as the implementation spine: Initialize corner heights.
Then preserve the next state change: Run a square step to fill centers.
Expose seed and parameters so results can be reproduced and tuned.

Common Pitfalls

Grid sizes are usually one more than a power of two.
Letting random choices create disconnected, invalid, or impossible-to-use output.
Returning generated height map without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Spatial Primitive & Sweep-Line Canvas

Show a coarse grid gaining finer terrain detail each pass.

Step 1 of 5: Initialize corner heights

fractal-heightmap

Notes

Diamond-Square Algorithm operates in O(n) time and O(n) space within the Fractal Terrain family. Often compared with Perlin Noise and Fractal Brownian Motion.