Overview
Midpoint displacement subdivides segments or grids and offsets new midpoint values by decreasing random amounts.
CoreSource checked
Midpoint Displacement
Generates rough terrain or curves by recursively displacing midpoints.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Procedural Generation
- Difficulty
- Beginner
- Family
- Fractal Terrain
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
recursive subdivisionrandom offsetroughness decayfractal detail
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 when generating terrain needs recursive subdivision.
- Use when the input matches the assumptions behind fractal Terrain.
When Not to Use
- Avoid when the design needs strict authored control over every generated detail.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Generates rough terrain or curves by recursively displacing midpoints
- Uses recursive subdivision and random offset to guide the work.
- Produces generated map, texture, layout, or pattern.
Use Cases
- Generating terrain
- Creating textures
- Building levels or natural patterns
Inputs
- Seed
- Generation parameters
- Constraint rules
Outputs
- Generated map, texture, layout, or pattern
Key Formulas (1)
Displaced midpoint
mid = (left + right) / 2 + random(−scale, scale)
mid = (left + right) / 2 + random(-scale, scale)Adds controlled random variation at each subdivision level.
Pseudocode
- 1.Initialize the seed, grid, rule set, or generator state
- 2.Choose the next cell, feature, or parameter to update
- 3.Apply constraints, noise, or stochastic choices
- 4.Repeat until the generated structure satisfies the stopping rule
Canonical Example
- Input
- seed = 7 with a small tile set, rule set, terrain grid, or generation parameter
- Output
- Generated map, texture, layout, or pattern
- Explanation
- Midpoint Displacement applies recursive subdivision to produce generated map, texture, layout, or pattern.
Implementation Notes
- Keep the seed and parameters stored with generated output for reproducibility.
- Keep the recursive subdivision step separate enough to test independently.
- Store seed, parameters, and validation results with generated output so artifacts can be reproduced.
Common Pitfalls
- Small parameter changes can create large visual or structural differences.
- Test edge cases, not only clean examples.
- Changing a seed or constraint weight can create artifacts that are hard to reproduce without recorded parameters.
Interactive Mechanism Walkthrough
Spatial Primitive & Sweep-Line CanvasShow the generation state evolving from seed values to the final artifact.
Step 1 of 4: Initialize the seed, grid, rule set, or generator state
procedural-generation-mechanismNotes
Midpoint Displacement should be used with the assumptions and tradeoffs of fractal Terrain in mind.
Sources (1)
What each reference supports for this entry.
Texturing and Modeling: A Procedural Approach
BookProcedural-generation reference for Midpoint Displacement's noise, texture synthesis, and terrain/shape generation use cases.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toDiamond-Square Algorithm
Midpoint displacement is a simpler recursive fractal terrain method.
Conceptual neighborFault Formation Terrain
Both are heightfield terrain generation methods.
Related Algorithms
Tags
Procedural GenerationTerrainFractalNoise