Skip to contents

Scans a maze object for dead ends – cells of degree 1 in the passage graph, i.e. cells reachable through exactly one open wall – and, with probability p, knocks out one more wall from each, creating a loop. When a dead end has a neighbor that is itself a dead end, that wall is preferred, since carving it removes two dead ends for the price of one wall; otherwise a random closed wall out of the cell is chosen instead.

Usage

braid(maze, p = 1)

Arguments

maze

A maze object, as returned by generate_maze().

p

Probability, in [0, 1], that any given dead end has a wall knocked out. At the default of 1, every dead end that has an available wall to open is braided away. At 0, braid() is a no-op.

Value

A modified maze object of class maze, with passages, carve_order, and walls_removed updated to reflect the newly opened walls. All other fields (rows, cols, start, end, algorithm, etc.) are unchanged.

Details

This is deliberately different from – and complements – the open_walls argument of generate_maze(). open_walls blindly removes any internal wall of the maze at random, with no regard for where dead ends are. braid() is targeted: it only ever opens walls that eliminate (or shorten) dead ends, which is the classic "braiding" operation used to turn a perfect maze into a braided one with fewer, shorter dead ends and more loops. You can use both: generate with open_walls for random loops and then call braid() to specifically clear out remaining dead ends, or vice versa.

The newly opened walls are appended to carve_order (so animations and replays of maze construction remain sensible) and counted in walls_removed, on top of any walls already removed by open_walls at generation time.

See also

generate_maze for the open_walls argument, which removes walls at random rather than targeting dead ends; sparsify for the opposite operation of carving more dead ends out of a maze.

Examples

maze <- generate_maze(10, 10, seed = 42)
braided <- braid(maze)
braided$walls_removed
#> [1] 9
plot_maze(braided)