ExtendedSource checked

Drunkard's Walk

Generates paths or caves by moving a random walker through a grid.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Procedural Generation
Difficulty: Beginner
Family: Random Walk Generation
Tier: Extended
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 0
Relationships: 4
Code example: Not ready
Visualization: Ready
Aliases: Random Walk Cave Generation

Overview

Drunkard's Walk carves or marks cells as a random walker steps around, creating winding organic shapes.

Core Concepts

generated structurerandom drawroom layoutrandom walk generationseeded variationrule expansionspatial structure

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(s)

Average

O(s)

Worst

O(s)

Space

O(n)

When to Use

Use Drunkard's Walk when you need to move randomly from cell to cell.
Use it for cave generation with inputs like grid.
Use it when repeatable content can be produced from compact rules, parameters, and seeds.
Use it when the Random Walk Generation 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 carved grid or path.

What It Does

Moves randomly from cell to cell
Carves or marks visited cells

Use Cases

Cave generation
Organic paths
Simple random maps

Inputs

Grid
Start position
Step count

Outputs

Carved grid or path

Pseudocode

1.Choose a starting cell
2.Mark or carve the current cell
3.Choose a random neighboring direction
4.Move the walker
5.Repeat until enough cells are carved

Canonical Example

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

Implementation Notes

Keep the input contract explicit: Grid; Start position; Step count.
Use this step as the implementation spine: Choose a starting cell.
Then preserve the next state change: Mark or carve the current cell.
Expose seed and parameters so results can be reproduced and tuned.

Common Pitfalls

Multiple walkers or bias rules can make results less stringy.
Letting random choices create disconnected, invalid, or impossible-to-use output.
Returning carved grid or path without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

2D Grid Wavefront & Trajectory

Show a wandering path carving open cells.

Step 1 of 5: Choose a starting cell

random-walk-grid

Notes

Drunkard's Walk operates in O(s) time and O(n) space within the Random Walk Generation family. Often compared with Cellular Automata Cave Generation and Binary Space Partitioning Dungeon Generation.

Sources (1)

What each reference supports for this entry.

Procedural Content Generation in Games

Book

Procedural-generation reference supporting Drunkard's Walk constraint solving, constructive generation, terrain, dungeon, or stochastic content workflow.

Open source