How-To: Maze Generation & Solving

Mix.install([
  {:yog_ex, "~> 0.98"},
  {:kino_vizjs, "~> 0.8.0"}
])

Introduction

A perfect maze is mathematically defined as a spanning tree over a grid graph. In a perfect maze:

1. Every cell is reachable from every other cell.
2. There is exactly one unique path between any two cells (no loops/cycles, and no isolated cells).

Yog provides generators for producing perfect mazes using various algorithms, along with builder utilities to convert these mazes into standard graphs that can be searched and solved using standard pathfinding algorithms.

This guide walks step-by-step through generating a maze, representing it as a graph, and solving it programmatically.

Step 1: Generate the Maze

First, we generate a maze. We'll use the Recursive Backtracker algorithm, which generates winding, complex passages with relatively long corridors.

rows = 12
cols = 12

# Generate a maze structure
maze = Yog.Generator.Maze.recursive_backtracker(rows, cols, seed: 42)

# Print a basic ASCII representation of the wall layouts
IO.puts(Yog.Render.ASCII.grid_to_string_unicode(maze))

Step 2: Convert the Grid to a Graph

Although the maze is structured as a grid, we need to convert it into a standard Yog.Graph to use Yog's graph traversal and pathfinding algorithms.

The Yog.Builder.GridGraph module handles this. It creates a node for each cell and adds undirected edges between adjacent cells if there is no wall between them.

# Convert the maze structure into a standard graph
graph = Yog.Builder.GridGraph.to_graph(maze)

# Inspect the graph properties
IO.inspect(Yog.node_count(graph), label: "Graph Node Count")
IO.inspect(Yog.edge_count(graph), label: "Graph Edge Count (Passages)")

Step 3: Define the Start, Exit, and Solve

In a grid graph, each node is indexed by a flat integer ID. We can translate 2D grid coordinates (row, col) into their corresponding node IDs using Yog.Builder.GridGraph.coord_to_id/3.

For our example:

• Start: Top-Left corner (0, 0)
• Exit: Bottom-Right corner (rows - 1, cols - 1)

Once we have the node IDs, we can use Yog.Pathfinding.shortest_path/1 to find the unique path from start to exit.

start_node = Yog.Builder.GridGraph.coord_to_id(maze, 0, 0)
exit_node = Yog.Builder.GridGraph.coord_to_id(maze, rows - 1, cols - 1)

# Find the path using Dijkstra's algorithm
case Yog.Pathfinding.shortest_path(in: graph, from: start_node, to: exit_node) do
  {:ok, path} ->
    IO.inspect(path.nodes, label: "Path Node IDs")
    IO.inspect(path.weight, label: "Path Length (Steps)")

  :error ->
    IO.puts("No path exists!")
end

Step 4: Annotate and Render the Solution

We can display the solved path by passing an "occupants" map to the ASCII renderer. The renderer will place our custom symbols inside the maze cells corresponding to the solved path.

{:ok, path} = Yog.Pathfinding.shortest_path(in: graph, from: start_node, to: exit_node)

# Create a map of cell IDs to unicode indicators
occupants =
  path.nodes
  # Mark path nodes with a bullet
  |> Map.new(fn id -> {id, "•"} end)
  # Mark starting point
  |> Map.put(start_node, "S")
  # Mark exit point
  |> Map.put(exit_node, "E")

# Render the final layout
IO.puts(Yog.Render.ASCII.grid_to_string_unicode(maze, occupants))

Step 5: Visualizing the Underlying Spanning Tree

To see how the graph looks visually, we can render it to DOT format and display it using Kino.VizJS. This clearly exposes the spanning tree structure.

# We'll use a small 6x6 maze to keep the diagram readable
small_maze = Yog.Generator.Maze.recursive_backtracker(6, 6, seed: 100)
small_graph = Yog.Builder.GridGraph.to_graph(small_maze)

# Render graph network using Graphviz
dot = Yog.Render.DOT.to_dot(small_graph)
Kino.VizJS.render(dot, height: "800px")

Step 6: Comparing Corridor "Textures"

Different maze generation algorithms create different structural patterns or "textures". For example, a Binary Tree algorithm has a strong diagonal bias with long corridors running east/south, while Wilson's algorithm generates completely uniform and organic corridor patterns.

Let's generate the same size grid using different algorithms, solve them, and compare their solved path lengths to see how layout textures impact navigation:

size = 20

algorithms = [
  {"Binary Tree", &Yog.Generator.Maze.binary_tree/3},
  {"Sidewinder", &Yog.Generator.Maze.sidewinder/3},
  {"Recursive Backtracker", &Yog.Generator.Maze.recursive_backtracker/3},
  {"Wilson's", &Yog.Generator.Maze.wilson/3}
]

for {name, generator} <- algorithms do
  # Generate with same dimensions and seed
  maze = generator.(size, size, seed: 42)
  g = Yog.Builder.GridGraph.to_graph(maze)
  
  start = Yog.Builder.GridGraph.coord_to_id(maze, 0, 0)
  exit = Yog.Builder.GridGraph.coord_to_id(maze, size - 1, size - 1)
  
  {:ok, path} = Yog.Pathfinding.shortest_path(in: g, from: start, to: exit)
  
  IO.puts("#{String.pad_trailing(name, 22)}: Shortest path = #{path.weight} steps")
end