maze

Maze generation algorithms for creating perfect mazes.

Perfect mazes are spanning trees on a grid where every cell connects to every other cell via exactly one path (no loops, no isolated areas).

Based on “Mazes for Programmers” by Jamis Buck.

Quick Start

// Generate a maze using the Recursive Backtracker algorithm
let maze = maze.recursive_backtracker(20, 20, seed: Some(42))
// Use ascii renderer
grid_to_string(maze) |> io.println

Algorithms

Algorithm	Speed	Bias	Best For
`binary_tree`	O(N)	Diagonal	Simplest, fastest
`sidewinder`	O(N)	Vertical	Memory constrained
`recursive_backtracker`	O(N)	Corridors	Games, roguelikes
`hunt_and_kill`	O(V²)	Winding	Few dead ends
`aldous_broder`	O(V²)	None	Uniform randomness
`wilson`	O(V) avg	None	Efficient uniform
`kruskal`	O(N log N)	None	Balanced corridors
`prim_simplified`	O(N log N)	Radial	Many dead ends
`prim_true`	O(N log N)	Jigsaw	Dense texture
`ellers`	O(N)	Horizontal	Infinite height mazes
`growing_tree`	O(N)	Varies	Versatility
`recursive_division`	O(N log N)	Rectangular	Rooms, fractal feel

Output Format

All algorithms return a yog/builder/grid.Grid that can be:

Rendered with yog/render/ascii
Converted to a plain graph with grid.to_graph/1
Used with pathfinding algorithms

References

Mazes for Programmers by Jamis Buck (Pragmatic Bookshelf, 2015)

Types

BinaryTreeBias

</>

Direction bias for the Binary Tree algorithm.

pub type BinaryTreeBias {
  NorthEast
  NorthWest
  SouthEast
  SouthWest
}

Constructors

```
NorthEast
```
```
NorthWest
```
```
SouthEast
```
```
SouthWest
```

GrowingTreeSelector

</>

Selector strategy for the Growing Tree algorithm.

pub type GrowingTreeSelector {
  Last
  First
  Random
  Middle
  Mix(GrowingTreeSelector, Float)
}

Constructors

```
Last
```
```
First
```
```
Random
```
```
Middle
```
```
Mix(GrowingTreeSelector, Float)
```

HuntScanMode

</>

Scan mode for the Hunt-and-Kill algorithm.

pub type HuntScanMode {
  ScanSequential
  ScanRandom
}

Constructors

```
ScanSequential
```
```
ScanRandom
```

SidewinderDirection

</>

Direction for the Sidewinder algorithm to carve.

pub type SidewinderDirection {
  North
  South
  East
  West
}

Constructors

```
North
```
```
South
```
```
East
```
```
West
```

Values

aldous_broder

</>

pub fn aldous_broder(
  rows: Int,
  cols: Int,
  seed seed: option.Option(Int),
) -> grid.Grid(Nil, Int)

Generates a maze using the Aldous-Broder algorithm.

Produces a truly uniform spanning tree using a random walk.

Characteristics

Time: O(N²) worst case
Space: O(1) auxiliary
Bias: None
Texture: Completely unbiased, uniform corridors

When to Use

When mathematical lack of bias is required
Small grids

When NOT to Use

Large grids (highly inefficient)

binary_tree

</>

pub fn binary_tree(
  rows: Int,
  cols: Int,
  seed seed: option.Option(Int),
) -> grid.Grid(Nil, Int)

Generates a maze using the Binary Tree algorithm.

The simplest maze algorithm. For each cell, randomly carves a passage to either the north or east neighbor (or other chosen bias). Creates an unbroken corridor along two boundaries.

Characteristics

Time: O(N) where N = rows × cols
Space: O(1) auxiliary
Bias: Strong diagonal (NE by default)
Texture: Distinctive diagonal corridors

When to Use

When speed is critical
For educational demonstrations
When predictable texture is acceptable

When NOT to Use

When uniform randomness is required
When aesthetic variety matters

Examples

let m = maze.binary_tree(5, 5, seed: Some(42))
// m.rows == 5

binary_tree_with_options

</>

pub fn binary_tree_with_options(
  rows: Int,
  cols: Int,
  bias: BinaryTreeBias,
  seed seed: option.Option(Int),
) -> grid.Grid(Nil, Int)

Generates a maze using the Binary Tree algorithm with custom bias.

ellers

</>

pub fn ellers(
  rows: Int,
  cols: Int,
  seed seed: option.Option(Int),
) -> grid.Grid(Nil, Int)

Generates a maze using Eller’s algorithm.

A row-by-row algorithm that uses constant memory relative to width.

Characteristics

Time: O(N)
Space: O(cols)
Bias: Horizontal
Texture: Balanced, consistent corridors

When to Use

Generating mazes of infinite/very large height
Memory-critical environments

growing_tree

</>

pub fn growing_tree(
  rows: Int,
  cols: Int,
  selector: GrowingTreeSelector,
  seed seed: option.Option(Int),
) -> grid.Grid(Nil, Int)

Generates a maze using the Growing Tree algorithm.

A versatile algorithm that can simulate others depending on selection strategy.

Characteristics

Time: O(N)
Space: O(N) for active list
Bias: Varies by strategy
Texture: Varies by strategy
Last: Simulates Recursive Backtracker
First: Simulates very long, straight corridors
Random: Simulates Simplified Prim’s
Middle: Unique hybrid texture

hunt_and_kill

</>

pub fn hunt_and_kill(
  rows: Int,
  cols: Int,
  seed seed: option.Option(Int),
) -> grid.Grid(Nil, Int)

Generates a maze using the Hunt-and-Kill algorithm.

Performs a random walk until stuck, then hunts for an unvisited cell adjacent to the visited region.

Characteristics

Time: O(N²) worst case
Space: O(1) auxiliary
Bias: High winding, dense
Texture: Uniform but with fewer dead ends than others

When to Use

When you want a maze with few dead ends
When space is critical but time is less so

When NOT to Use

Very large grids (O(N²) can be slow)

hunt_and_kill_with_options

</>

pub fn hunt_and_kill_with_options(
  rows: Int,
  cols: Int,
  scan_mode: HuntScanMode,
  seed seed: option.Option(Int),
) -> grid.Grid(Nil, Int)

Generates a maze using the Hunt-and-Kill algorithm with custom options.

kruskal

</>

pub fn kruskal(
  rows: Int,
  cols: Int,
  seed seed: option.Option(Int),
) -> grid.Grid(Nil, Int)

Generates a maze using randomized Kruskal’s algorithm.

Produces a uniform spanning tree by randomly merging disjoint sets.

Characteristics

Time: O(N log N)
Space: O(N) for set tracking
Bias: None
Texture: Balanced corridors, uniform distribution

When to Use

When you want unbiased mazes on non-grid topologies
For a balanced roguelike feel

prim_simplified

</>

pub fn prim_simplified(
  rows: Int,
  cols: Int,
  seed seed: option.Option(Int),
) -> grid.Grid(Nil, Int)

Generates a maze using the Simplified Prim’s algorithm.

Creates mazes with strong radial texture and many dead ends.

Characteristics

Time: O(N log N)
Space: O(N) for frontier list
Bias: Radial (spreads from start)
Texture: Jigsaw-like, very dense with short corridors

When to Use

When you want a dense maze with many branches
To create paths that feel “grown” from a source

prim_true

</>

pub fn prim_true(
  rows: Int,
  cols: Int,
  seed seed: option.Option(Int),
) -> grid.Grid(Nil, Int)

Generates a maze using True Prim’s algorithm.

Uses random weights for each cell to produce a jigsaw-like texture.

Characteristics

Time: O(N log N)
Space: O(N) for weights and frontier
Bias: None
Texture: Jigsaw texture, balanced but dense

recursive_backtracker

</>

pub fn recursive_backtracker(
  rows: Int,
  cols: Int,
  seed seed: option.Option(Int),
) -> grid.Grid(Nil, Int)

Generates a maze using the Recursive Backtracker algorithm (DFS).

Performs a random walk avoiding visited cells, backtracking when stuck. Creates twisty mazes with long corridors - the most popular algorithm for games.

Characteristics

Time: O(N) where N = rows × cols
Space: O(N) for the explicit stack
Bias: Twisty passages, long corridors
Texture: Classic “roguelike” maze aesthetic

When to Use

Games and roguelikes (most popular choice)
When you want twisty, exploratory mazes
Longest path puzzles

When NOT to Use

If memory is extremely limited (N can be large)

Examples

let m = maze.recursive_backtracker(20, 20, seed: Some(123))
// Produces twisty corridors

recursive_division

</>

pub fn recursive_division(
  rows: Int,
  cols: Int,
  seed seed: option.Option(Int),
) -> grid.Grid(Nil, Int)

Generates a maze using the Recursive Division algorithm.

Starts with a full grid and adds walls.

Characteristics

Time: O(N log N)
Space: O(log N) for recursion stack
Bias: Rectangular
Texture: Room-like, fractal aesthetic

When to Use

When you want a maze that feels “built”
Creating architectural layouts

sidewinder

</>

pub fn sidewinder(
  rows: Int,
  cols: Int,
  seed seed: option.Option(Int),
) -> grid.Grid(Nil, Int)

Generates a maze using the Sidewinder algorithm.

Row-based algorithm that creates vertical corridors.

Characteristics

Time: O(N) where N = rows × cols
Space: O(cols) - only tracks current run
Bias: Vertical corridors (north-south)
Texture: Long vertical passages with horizontal “rungs”

When to Use

When you want vertical maze progression
Memory-constrained environments
Creating “floor” separation in games

When NOT to Use

When you need horizontal bias

sidewinder_with_options

</>

pub fn sidewinder_with_options(
  rows: Int,
  cols: Int,
  direction: SidewinderDirection,
  seed seed: option.Option(Int),
) -> grid.Grid(Nil, Int)

Generates a maze using the Sidewinder algorithm with custom direction.

wilson

</>

pub fn wilson(
  rows: Int,
  cols: Int,
  seed seed: option.Option(Int),
) -> grid.Grid(Nil, Int)

Generates a maze using Wilson’s algorithm.

Produces a uniform spanning tree using loop-erased random walks.

Characteristics

Time: O(N) average
Space: O(N) for current walk
Bias: None
Texture: Completely unbiased, elegant aesthetic

When to Use

When you want a truly unbiased maze efficiently
Generating perfect test data

When NOT to Use

When you want specific hallway or corridor textures