Skip to contents

All mazes below are 25 x 25, generated with seed = 42 and with start and end pinned to opposite corners (set_endpoints(strategy = "corners")). Each card shows the generation algorithm carving the maze and then A-star finding the shortest path.

All algorithms at once

Animated collage of every generation algorithm

One algorithm at a time

Depth-first search
algorithm = “dfs”
Depth-first search: generationGeneration
Depth-first search: solved with A-starA* solve
Prim
algorithm = “prim”
Prim: generationGeneration
Prim: solved with A-starA* solve
Kruskal
algorithm = “kruskal”
Kruskal: generationGeneration
Kruskal: solved with A-starA* solve
Wilson
algorithm = “wilson”
Wilson: generationGeneration
Wilson: solved with A-starA* solve
Eller
algorithm = “eller”
Eller: generationGeneration
Eller: solved with A-starA* solve
Recursive division
algorithm = “division”
Recursive division: generationGeneration
Recursive division: solved with A-starA* solve
Aldous-Broder
algorithm = “aldous_broder”
Aldous-Broder: generationGeneration
Aldous-Broder: solved with A-starA* solve
Hunt-and-kill
algorithm = “hunt_kill”
Hunt-and-kill: generationGeneration
Hunt-and-kill: solved with A-starA* solve
Binary tree
algorithm = “binary_tree”
Binary tree: generationGeneration
Binary tree: solved with A-starA* solve
Sidewinder
algorithm = “sidewinder”
Sidewinder: generationGeneration
Sidewinder: solved with A-starA* solve
Growing tree (newest)
algorithm = “growing_tree”, selection = “newest”
Growing tree (newest): generationGeneration
Growing tree (newest): solved with A-starA* solve
Growing tree (random)
algorithm = “growing_tree”, selection = “random”
Growing tree (random): generationGeneration
Growing tree (random): solved with A-starA* solve
Growing tree (oldest)
algorithm = “growing_tree”, selection = “oldest”
Growing tree (oldest): generationGeneration
Growing tree (oldest): solved with A-starA* solve
Growing tree (mixed)
algorithm = “growing_tree”, selection = “mixed”
Growing tree (mixed): generationGeneration
Growing tree (mixed): solved with A-starA* solve

Reproduce it

The images come from scripts/generate_mazes2.R in the GitHub repository. A single maze and its animations take a few lines:

library(mazegenerator)

maze <- generate_maze(25, 25, algorithm = "wilson", seed = 42)
maze <- set_endpoints(maze, strategy = "corners")

animate_maze(maze, output_file = "generation.gif")

path <- solve_maze(maze, algorithm = "astar", trace = TRUE)
animate_solution(maze, solution = path, output_file = "solve.gif")