Generate a random maze
generate_maze.RdCarves a perfect rectangular maze – every cell is reachable and there is exactly one simple path between any two cells – using one of several classic generation algorithms.
Usage
generate_maze(rows = 20L, cols = rows, start = c(1L, 1L),
seed = NULL, verbose = FALSE, open_walls = 0,
algorithm = c("dfs", "prim", "kruskal", "wilson", "eller",
"division", "aldous_broder", "hunt_kill", "binary_tree",
"sidewinder", "growing_tree"),
selection = c("newest", "random", "oldest", "mixed"),
mask = NULL, wrap = c("none", "horizontal", "vertical", "both"),
rooms = NULL)
# S3 method for class 'maze'
print(x, ...)Arguments
- rows
Number of rows in the maze.
- cols
Number of columns in the maze.
- start
Integer vector
c(row, column)giving the starting cell.- seed
Optional integer seed for reproducible generation.
- verbose
Show generation progress in the console.
- open_walls
Probability, in
[0, 1], that any given internal wall between two adjacent cells is removed after the maze is generated. At the default of0, the maze is unchanged (a perfect maze: every cell is reachable and there is exactly one simple path between any two cells). Values above0"braid" the maze by knocking out extra walls, creating loops so that some cells have more than one route between them.- algorithm
The carving algorithm to use, one of
"dfs","prim","kruskal","wilson","eller","division","aldous_broder","hunt_kill","binary_tree","sidewinder"or"growing_tree":"dfs"(the default): randomized depth-first search with backtracking. Produces long, winding corridors with few short dead ends."prim": randomized Prim's algorithm, growing a single tree fromstartby repeatedly carving a random frontier wall. Produces short, bushy dead ends and a more uniformly branching texture than"dfs"."kruskal": randomized Kruskal's algorithm, carving walls in random order via a union-find of connected components. Produces a texture with many short, evenly scattered dead ends and no bias towardstart."wilson": loop-erased random walks generating a uniform spanning tree, so every perfect maze on the grid is equally likely. Slower to converge for large grids but free of any algorithmic bias."eller": a row-by-row, constant-memory algorithm. Produces a texture similar to"kruskal"while only ever holding one row of state."division": recursive division, the only subtractive algorithm here – it starts from a fully open room and recursively splits it with a wall (leaving a single gap) until every chamber is one cell. Produces long straight walls and a distinctly architectural, room-like texture."aldous_broder": a naive random walk that carves into any unvisited cell it stumbles onto, forming a uniform spanning tree (like"wilson", unbiased) but typically slower to finish since it keeps wandering over already-carved territory."hunt_kill": random walks that carve until they get stuck, then "hunt" for the first unvisited cell adjacent to the carved area to start the next walk. Produces winding corridors similar to"dfs"but with fewer very long dead ends."binary_tree": for every cell, randomly carves toward its north or west neighbor only. Extremely fast and simple, but strongly biased: the top row and leftmost column are always open corridors, and every other cell has a diagonal drift toward the top-left corner."sidewinder": like"binary_tree"but row-by-row – carves east along a run of cells, then closes the run out with a single north carve from a random member of it. The top row is always one continuous corridor; every other row still has a (milder) northward bias."growing_tree": keeps a pool of "active" cells and repeatedly carves from one of them (chosen usingselection) to a random unvisited neighbor. A general-purpose algorithm whose texture depends entirely onselection.
mask,wrapandrooms(below) are only supported for"dfs","prim","kruskal","wilson","aldous_broder","hunt_kill"and"growing_tree"– every algorithm that carves by walking the passage graph one neighbor at a time."eller","binary_tree","sidewinder"(row-by-row algorithms) and"division"(which recursively splits a rectangular room) all assume a complete rectangular grid; combining any of them with a non-defaultmask,wraporroomsis an error.- selection
Only used when
algorithm = "growing_tree"; ignored (with a warning if explicitly set) otherwise. Controls which active cell the growing tree carves from next, one of"newest","random","oldest"or"mixed":"newest": always the most recently added cell. This reproduces"dfs"."random": a uniformly random active cell. This approximates"prim"."oldest": always the least recently added cell, carving breadth-first. Produces long, straight corridors radiating fromstart."mixed": flips a coin each step between"newest"and"random", blending the two textures.
- mask
Optional logical matrix of dimension
c(rows, cols)(or coercible to logical) marking which cells are part of the maze.TRUEcells are carvable;FALSEcells are excluded entirely (solid rock), which lets the maze take a non-rectangular shape – a circle, a heart, a logo, text. Ifmaskis supplied androws/colsare left at their defaults, they are inferred fromdim(mask); if both are given explicitly they must agree withdim(mask). The mask must have at least twoTRUEcells, and everyTRUEcell must be reachable from every otherTRUEcell through 4-connectedTRUEneighbors (a maze on a disconnected mask is meaningless and errors).startmust land on aTRUEcell; ifstartis left at its default and it happens to fall on aFALSEcell, it is silently snapped to the firstTRUEcell instead of erroring. Only supported for the neighbor-walking algorithms listed underalgorithm. The mask is stored on the returnedmazeobject.- wrap
Toroidal/cylindrical wrapping of the grid's edges, one of
"none"(the default),"horizontal"(columncolsbecomes adjacent to column 1, in every row),"vertical"(rowrowsbecomes adjacent to row 1, in every column) or"both". The maze is still carved as an ordinary (mask-aware) perfect maze on the flat rectangle first, so it stays fully connected and solvable by plain grid-adjacency tools likesolve_maze();wrapthen randomly opens some bonus passages across the seam(s) on top of that, the same wayopen_wallsadds bonus loops elsewhere. The resulting maze is no longer planar in the usual sense.plot_maze()always draws the maze as a flat rectangle with a solid outer border, so a seam passage is never drawn as an opening or a corridor in the picture – it is simply invisible there, even though it is a real, walkable passage inmaze$passages. This is expected; inspectmaze$passages(edge keys of the form"r1,c1|r2,c2") to see the wrap connections directly. Only supported for the neighbor-walking algorithms listed underalgorithm.- rooms
Optional list of integer vectors
c(row0, col0, row1, col1), each describing a rectangle (inclusive, 1-indexed) that is fully opened – every internal wall inside it removed – before carving begins, so the carving algorithm treats the room as one already-connected region (roguelike-style open chambers linked by carved corridors). Each rectangle must lie inside the maze boundaries and, ifmaskis given, entirely inside theTRUEregion ofmask. Because a room's interior is fully open, a maze withroomsis generally no longer a perfect maze (it can contain loops). Only supported for the neighbor-walking algorithms listed underalgorithm.- x
A
mazeobject.- ...
Additional arguments, currently unused.
Value
An object of class maze containing its dimensions, start and end
cells, algorithm (the algorithm used), carve_order (a
character vector of edge keys in the order the walls were carved –
unique() of which equals the perfect-maze passage set), and
passages (the full set of open walls, including any added by
open_walls). For algorithm = "dfs", "aldous_broder"
and "hunt_kill", traversal and visitation_order
additionally record the generation walk as a list of c(row, column)
positions; for every other algorithm they are NULL. It also
contains open_walls, the probability used, and
walls_removed, the number of internal walls that were actually
opened. When open_walls > 0 the maze is no longer perfect: loops
exist, and there can be more than one route between two cells. The print
method returns the object invisibly.
Examples
maze <- generate_maze(10, 10, seed = 42)
maze
#> <maze> 10 x 10
#> algorithm: dfs
#> start: (1, 1)
#> end: (3, 8)
#> cells: 100
prim_maze <- generate_maze(10, 10, seed = 42, algorithm = "prim")
division_maze <- generate_maze(10, 10, seed = 42, algorithm = "division")
growing_tree_maze <- generate_maze(10, 10, seed = 42,
algorithm = "growing_tree", selection = "mixed")
# A circular maze via a mask built from Euclidean distance to the center.
n <- 21
center <- (n + 1) / 2
dist_from_center <- outer(seq_len(n), seq_len(n), function(r, c) {
sqrt((r - center)^2 + (c - center)^2)
})
circle_mask <- dist_from_center <= n / 2
circular_maze <- generate_maze(mask = circle_mask, algorithm = "prim", seed = 1)
# A wrapped (cylindrical) maze and a maze with two open rooms.
wrapped_maze <- generate_maze(10, 10, seed = 1, wrap = "horizontal")
room_maze <- generate_maze(20, 20, seed = 1,
rooms = list(c(2, 2, 5, 5), c(12, 12, 16, 16)))