@spec add_passage(
  Yog.Builder.GridGraph.t(),
  non_neg_integer(),
  non_neg_integer(),
  non_neg_integer(),
  non_neg_integer()
) :: Yog.Builder.GridGraph.t()

Adds a bidirectional passage between two adjacent cells.

The cells are identified by their {row, col} coordinates.

@spec aldous_broder(non_neg_integer(), non_neg_integer(), keyword()) ::
  Yog.Builder.GridGraph.t()

Generates a maze using the Aldous-Broder algorithm.

A random-walk algorithm that produces a uniform spanning tree (all possible perfect mazes are equally likely). Extremely inefficient but mathematically unbiased.

Characteristics

• Time: O(N log N) to O(N²) depending on luck
• Space: O(N) to track visited cells
• Bias: None (Uniform Randomness)
• Texture: Well-distributed passages, no corridors bias

Algorithm

1. Start at a random cell, mark as visited.
2. While there are unvisited cells: a. Pick a random neighbor of the current cell. b. If the neighbor has not been visited:
   • Carve a passage between the current cell and neighbor.
   • Mark the neighbor as visited. c. Move to the neighbor.

Options

• :seed - Random seed for reproducibility

Examples

iex> maze = Yog.Generator.Maze.aldous_broder(10, 10, seed: 42)
iex> maze.rows
10

When to Use

• When you need a truly uniform random maze without any geometric bias
• When performance is secondary to mathematical purity
• For small to medium grids

When NOT to Use

• Very large grids (can take a long time to finish)
• When speed is a priority

@spec binary_tree(non_neg_integer(), non_neg_integer(), keyword()) ::
  Yog.Builder.GridGraph.t()

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

Options

• :seed - Random seed for reproducibility
• :bias - Direction bias: :ne (default), :nw, :se, :sw

Examples

iex> maze = Yog.Generator.Maze.binary_tree(5, 5, seed: 42)
iex> maze.rows
5
iex> maze.cols
5

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

@spec create_empty_grid(non_neg_integer(), non_neg_integer()) ::
  Yog.Builder.GridGraph.t()

Creates an empty grid graph with nodes but no edges.

Each cell becomes a node with ID = row * cols + col.

@spec ellers(non_neg_integer(), non_neg_integer(), keyword()) ::
  Yog.Builder.GridGraph.t()

Generates a maze using Eller's algorithm.

A row-based algorithm that creates mazes of theoretically infinite height using constant memory (proportional only to grid width).

Characteristics

• Time: O(N) where N = rows × cols
• Space: O(cols) auxiliary space for set tracking
• Bias: None significant, though row-layering can be visible
• Texture: Balanced, consistent corridors

Algorithm (Row-by-Row)

1. Assign unique sets to each cell in the first row.
2. Randomly connect adjacent cells that are in different sets.
3. For each unique set, randomly choose at least one cell and carve down.
4. In the next row, cells with downward passages inherit their sets; others get new sets.
5. Repeat for all rows. In the last row, connect all remaining disjoint sets.

Options

• :seed - Random seed for reproducibility

Examples

iex> maze = Yog.Generator.Maze.ellers(10, 10, seed: 42)
iex> maze.rows
10

@spec growing_tree(non_neg_integer(), non_neg_integer(), keyword()) ::
  Yog.Builder.GridGraph.t()

Generates a maze using the Growing Tree algorithm.

A versatile algorithm that can simulate other algorithms (Recursive Backtracker, Prim's) depending on how the next cell is selected from the active list.

Strategies

• :last (Default): Selects the most recently added cell (simulates Recursive Backtracker).
• :random: Selects a random cell (simulates Simplified Prim's).
• :middle: Selects the median cell from the active list.
• :first: Selects the oldest cell (creates a very long, straight corridor).

Options

• :strategy: One of :last, :random, :middle, :first.
• :mix: A tuple {strategy, probability} to switch behaviors (e.g., {:last, 0.5}).
• :seed: Random seed for reproducibility.

@spec hunt_and_kill(non_neg_integer(), non_neg_integer(), keyword()) ::
  Yog.Builder.GridGraph.t()

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

Similar to Recursive Backtracker but without explicit stack. Performs a random walk until stuck, then "hunts" for an unvisited cell adjacent to the visited region, connects it, and continues.

Characteristics

• Time: O(N²) worst case (due to hunt phase)
• Space: O(1) auxiliary (no stack!)
• Bias: Long, winding passages; fewer dead ends
• Texture: Similar to Recursive Backtracker but more organic

Algorithm

1. Start at random cell, mark as visited
2. Perform random walk to unvisited neighbors until stuck
3. When stuck, scan grid for unvisited cell adjacent to visited region
4. Connect that cell to the visited region
5. Resume random walk from that cell
6. Repeat until all cells visited

Options

• :seed - Random seed for reproducibility
• :scan_mode - How to hunt: :sequential (default) or :random

Examples

iex> maze = Yog.Generator.Maze.hunt_and_kill(10, 10, seed: 42)
iex> maze.rows
10

When to Use

• When you want Recursive Backtracker texture without the stack
• Memory-constrained environments
• Longest path puzzles
• Fewer dead ends than Recursive Backtracker

Comparison

vs Recursive Backtracker: Similar texture, no stack needed, hunt phase slower vs Binary Tree: Much less bias, more interesting

@spec kruskal(non_neg_integer(), non_neg_integer(), keyword()) ::
  Yog.Builder.GridGraph.t()

Generates a maze using Kruskal's algorithm.

A randomized version of the Minimum Spanning Tree algorithm. It treats every cell as a separate set and randomly merges sets by carving passages until all cells are connected in a single set.

Characteristics

• Time: O(N log N) or O(N α(N)) depending on shuffling and DSU operations
• Space: O(N) to store edges and the Disjoint Set structure
• Bias: None (Uniform Randomness)
• Texture: No obvious corridors or diagonal bias, very "balanced"

Algorithm

1. Create a set for each cell.
2. Create a list of all potential edges between adjacent cells.
3. Shuffle the list of edges.
4. For each edge, if the two cells it connects are in different sets: a. Carve a passage between them. b. Merge the two sets.

Options

• :seed - Random seed for reproducibility

Examples

iex> maze = Yog.Generator.Maze.kruskal(10, 10, seed: 42)
iex> maze.rows
10

When to Use

• When you want a uniform maze with a different structural feel than Wilson's
• For randomized grid maps where you want an efficient "merge-based" generation

When NOT to Use

• Extremely large grids if memory for the edge list is constrained

@spec prim_simplified(non_neg_integer(), non_neg_integer(), keyword()) ::
  Yog.Builder.GridGraph.t()

Generates a maze using Simplified Prim's algorithm.

Similar to Growing Tree with random selection. Creates mazes with strong radial texture and many dead ends.

@spec prim_true(non_neg_integer(), non_neg_integer(), keyword()) ::
  Yog.Builder.GridGraph.t()

Generates a maze using True Prim's algorithm.

Each cell has a random weight. Always selects the lowest-weight cell from the frontier. Creates many short dead ends, jigsaw puzzle texture.

@spec recursive_backtracker(non_neg_integer(), non_neg_integer(), keyword()) ::
  Yog.Builder.GridGraph.t()

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

Algorithm

1. Start at a random cell, mark as visited
2. While there are unvisited neighbors, pick one randomly and move there
3. Carve passage and push current cell to stack
4. When stuck (no unvisited neighbors), pop from stack and continue
5. Repeat until stack is empty

Options

• :seed - Random seed for reproducibility

Examples

iex> maze = Yog.Generator.Maze.recursive_backtracker(10, 10, seed: 42)
iex> maze.rows
10

When to Use

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

Comparison

vs Binary Tree: Much less bias, more interesting texture vs Sidewinder: More twisty, less predictable vs Hunt-and-Kill: Similar output but uses explicit stack

@spec recursive_division(non_neg_integer(), non_neg_integer(), keyword()) ::
  Yog.Builder.GridGraph.t()

Generates a maze using the Recursive Division algorithm.

Unlike most other algorithms which start with an empty grid and add passages, this starts with a full grid and adds walls by removing passages.

Characteristics

• Time: O(N log N)
• Space: O(log N) recursion depth
• Bias: Large rectangles (the chambers formed during division)
• Texture: Fractal-like, clearly organized into rectangular regions

Options

• :seed - Random seed for reproducibility

@spec sidewinder(non_neg_integer(), non_neg_integer(), keyword()) ::
  Yog.Builder.GridGraph.t()

Generates a maze using the Sidewinder algorithm.

Row-based algorithm that creates vertical corridors. For each row:

1. Start a "run" of cells
2. Randomly decide to end the run (carve north) or continue east
3. At row end, carve north from a random cell in the run

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"

Options

• :seed - Random seed for reproducibility

Examples

iex> maze = Yog.Generator.Maze.sidewinder(5, 5, seed: 42)
iex> maze.rows
5
iex> maze.cols
5

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 (use Binary Tree with :ne/:nw bias)

@spec wilson(non_neg_integer(), non_neg_integer(), keyword()) ::
  Yog.Builder.GridGraph.t()

Generates a maze using Wilson's algorithm.

Produces a perfectly uniform spanning tree (like Aldous-Broder) but using loop-erased random walks. Much more efficient than Aldous-Broder while maintaining the same unbiased quality.

Characteristics

• Time: Faster than Aldous-Broder (O(N) to O(N log N) typical)
• Space: O(N) for visited set and walk tracking
• Bias: None (Uniform Randomness)
• Texture: Well-distributed, no corridor bias

Algorithm

1. Pick a random cell and add to visited set.
2. While there are unvisited cells: a. Pick a random unvisited cell. b. Perform random walk until hitting a visited cell. c. If walk crosses itself, the older path is overwritten (loop erasure). d. Add the final path to the visited set and carve passages.

Options

• :seed - Random seed for reproducibility

Examples

iex> maze = Yog.Generator.Maze.wilson(10, 10, seed: 42)
iex> maze.rows
10

When to Use

• When you need a truly uniform random maze without any geometric bias
• When performance is more important than in Aldous-Broder
• For medium to large grids

When NOT to Use

• When speed is the absolute absolute priority (Binary Tree/Recursive Backtracker are faster)