Maze Generation & Solving

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

Introduction

A perfect maze is a spanning tree on a grid. Every cell is reachable from every other cell by exactly one path. This means there are no loops and no isolated sections.

Yog provides a rich suite of maze generation algorithms, ranging from the extremely fast but biased (Binary Tree) to the perfectly uniform but slower (Wilson’s).

Comparing Textures

Different algorithms produce mazes with different “textures.” Some prefer long straight corridors, while others create twisty, winding passages.

rows = 15
cols = 15

# 1. Binary Tree - Very fast, strong diagonal bias
binary_tree = Yog.Generator.Maze.binary_tree(rows, cols)

# 2. Sidewinder - Efficient, strong vertical/horizontal corridors
sidewinder = Yog.Generator.Maze.sidewinder(rows, cols)

# 3. Recursive Backtracker - Most popular for games, very twisty
backtracker = Yog.Generator.Maze.recursive_backtracker(rows, cols)

# 4. Wilson's - Perfectly uniform, but slower
wilson = Yog.Generator.Maze.wilson(rows, cols)

IO.puts "--- Binary Tree ---"
IO.puts Yog.Render.ASCII.grid_to_string_unicode(binary_tree)

IO.puts "\n--- Sidewinder ---"
IO.puts Yog.Render.ASCII.grid_to_string_unicode(sidewinder)

IO.puts "\n--- Recursive Backtracker ---"
IO.puts Yog.Render.ASCII.grid_to_string_unicode(backtracker)

IO.puts "\n--- Wilson's ---"
IO.puts Yog.Render.ASCII.grid_to_string_unicode(wilson)

Solving the Maze

Because a maze is just a graph, we can use Yog‘s pathfinding algorithms to find the exit.

Let’s generate a complex maze and solve it from the top-left to the bottom-right.

maze = Yog.Generator.Maze.recursive_backtracker(20, 20)
graph = Yog.Builder.GridGraph.to_graph(maze)

start_node = Yog.Builder.GridGraph.coord_to_id(maze, 0, 0)
end_node = Yog.Builder.GridGraph.coord_to_id(maze, 19, 19)

# Solve using Dijkstra
case Yog.Pathfinding.Dijkstra.shortest_path(graph, from: start_node, to: end_node) do
  {:ok, path} ->
    # Create "occupants" to mark the path in ASCII
    occupants = 
      path.nodes 
      |> Map.new(fn id -> {id, "•"} end)
      |> Map.put(start_node, "S")
      |> Map.put(end_node, "E")

    IO.puts Yog.Render.ASCII.grid_to_string_unicode(maze, occupants)
    IO.puts "\nPath length: #{path.weight} steps"

  :error ->
    IO.puts "No path found! (Wait, perfect mazes always have a path... check implementation)"
end

Visualizing with DOT

If you want a more “premium” look, you can render the maze using Graphviz.

# We'll use a smaller maze for visualization
small_maze = Yog.Generator.Maze.recursive_backtracker(10, 10)
dot = Yog.Render.DOT.to_dot(Yog.Builder.GridGraph.to_graph(small_maze))

Kino.VizJS.render(dot)

Randomness and Seeds

All generators accept a :seed option for reproducibility.

maze1 = Yog.Generator.Maze.recursive_backtracker(10, 10, seed: 123)
maze2 = Yog.Generator.Maze.recursive_backtracker(10, 10, seed: 123)

# These will be identical
Yog.Render.ASCII.grid_to_string(maze1) == Yog.Render.ASCII.grid_to_string(maze2) |> IO.inspect(label: "Identical?")

Algorithm Properties

Different algorithms have different characteristics:

# Compare the "twistiness" by looking at average path length
mazes = [
  {"Binary Tree", Yog.Generator.Maze.binary_tree(20, 20)},
  {"Sidewinder", Yog.Generator.Maze.sidewinder(20, 20)},
  {"Backtracker", Yog.Generator.Maze.recursive_backtracker(20, 20)},
  {"Wilson's", Yog.Generator.Maze.wilson(20, 20)}
]

for {name, maze} <- mazes do
  graph = Yog.Builder.GridGraph.to_graph(maze)
  start = Yog.Builder.GridGraph.coord_to_id(maze, 0, 0)
  finish = Yog.Builder.GridGraph.coord_to_id(maze, 19, 19)
  {:ok, path} = Yog.Pathfinding.shortest_path(in: graph, from: start, to: finish)
  IO.puts("#{name}: shortest path = #{path.weight} steps")
end

Summary

Yog makes it easy to:

1. Generate mazes using 10+ different algorithms.
2. Render them to ASCII for debugging or DOT for presentation.
3. Solve them by treating them as standard graphs.

Try changing the algorithm in the “Solving” section to aldous_broder/3 or wilson/3 to see how the path changes!