# `Yog.Generator.Maze`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.96.0/lib/yog/generator/maze.ex#L1)

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
    maze = Yog.Generator.Maze.recursive_backtracker(20, 20, seed: 42)
    IO.puts(Yog.Render.ASCII.grid_to_string(maze))

## Algorithms

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

## Output Format

All algorithms return a `Yog.Builder.GridGraph` struct that can be:
- Rendered with `Yog.Render.ASCII`
- Converted to a plain graph with `Yog.Builder.GridGraph.to_graph/1`
- Used with pathfinding algorithms

## Examples

    # Generate and render a binary tree maze
    iex> maze = Yog.Generator.Maze.binary_tree(10, 10, seed: 42)
    iex> is_struct(maze, Yog.Builder.GridGraph)
    true
    iex> maze.rows
    10

    # Get the underlying graph for pathfinding
    iex> maze = Yog.Generator.Maze.recursive_backtracker(5, 5)
    iex> graph = Yog.Builder.GridGraph.to_graph(maze)

## References

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

# `maze_opts`

```elixir
@type maze_opts() :: [seed: integer(), topology: :plane]
```

Maze generation options

# `add_passage`

```elixir
@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.

# `aldous_broder`

```elixir
@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

# `binary_tree`

```elixir
@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

# `create_empty_grid`

```elixir
@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.

# `ellers`

```elixir
@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

# `growing_tree`

```elixir
@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.

# `hunt_and_kill`

```elixir
@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

# `kruskal`

```elixir
@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

# `prim_simplified`

```elixir
@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.

# `prim_true`

```elixir
@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.

# `recursive_backtracker`

```elixir
@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

# `recursive_division`

```elixir
@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

# `sidewinder`

```elixir
@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)

# `wilson`

```elixir
@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)

---

*Consult [api-reference.md](api-reference.md) for complete listing*