Skip to contents

Carves 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 of 0, the maze is unchanged (a perfect maze: every cell is reachable and there is exactly one simple path between any two cells). Values above 0 "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 from start by 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 toward start.

  • "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 using selection) to a random unvisited neighbor. A general-purpose algorithm whose texture depends entirely on selection.

mask, wrap and rooms (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-default mask, wrap or rooms is 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 from start.

  • "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. TRUE cells are carvable; FALSE cells are excluded entirely (solid rock), which lets the maze take a non-rectangular shape – a circle, a heart, a logo, text. If mask is supplied and rows/cols are left at their defaults, they are inferred from dim(mask); if both are given explicitly they must agree with dim(mask). The mask must have at least two TRUE cells, and every TRUE cell must be reachable from every other TRUE cell through 4-connected TRUE neighbors (a maze on a disconnected mask is meaningless and errors). start must land on a TRUE cell; if start is left at its default and it happens to fall on a FALSE cell, it is silently snapped to the first TRUE cell instead of erroring. Only supported for the neighbor-walking algorithms listed under algorithm. The mask is stored on the returned maze object.

wrap

Toroidal/cylindrical wrapping of the grid's edges, one of "none" (the default), "horizontal" (column cols becomes adjacent to column 1, in every row), "vertical" (row rows becomes 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 like solve_maze(); wrap then randomly opens some bonus passages across the seam(s) on top of that, the same way open_walls adds 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 in maze$passages. This is expected; inspect maze$passages (edge keys of the form "r1,c1|r2,c2") to see the wrap connections directly. Only supported for the neighbor-walking algorithms listed under algorithm.

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, if mask is given, entirely inside the TRUE region of mask. Because a room's interior is fully open, a maze with rooms is generally no longer a perfect maze (it can contain loops). Only supported for the neighbor-walking algorithms listed under algorithm.

x

A maze object.

...

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)))