Braid a maze by removing dead ends
braid.RdScans 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.
Arguments
- maze
A
mazeobject, as returned bygenerate_maze().- p
Probability, in
[0, 1], that any given dead end has a wall knocked out. At the default of1, every dead end that has an available wall to open is braided away. At0,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)