Sparsify a maze by carving out dead ends
sparsify.RdThe opposite of braid(): repeatedly erases dead-end cells by
removing their single connecting passage, turning them into isolated
cells. Erasing a dead end can turn its former neighbor into a new dead
end, so the process repeats in passes until either no dead ends remain, a
pass erases nothing, or a safety cap on the number of passes is reached.
Arguments
- maze
A
mazeobject, as returned bygenerate_maze().- p
Probability, in
[0, 1], that any given dead end is erased in a pass. Higher values cull more of the maze;0is a no-op.
Value
A modified maze object of class maze, with passages
and walls_removed updated. carve_order and all other fields
are unchanged (see Details).
Details
The resulting maze is generally not a perfect maze anymore: some
cells become fully isolated (unreachable from every other cell), so
solve_maze() may fail to find a path between an isolated cell and
anything else. Choosing start/end cells that remain
connected (for example with set_endpoints(), or by checking
solve_maze() succeeds) is the caller's responsibility.
carve_order is left untouched: it still records how the
original maze was carved, but since sparsify() removes some
of those passages, carve_order (or unique() of it) no longer
reproduces the final set of open walls, and replaying it (e.g. via
animate_maze()) would show walls that sparsify() has since
closed back up. walls_removed is adjusted down when an erased
passage happened to be one of the "extra" loop walls counted in it, so it
keeps tracking the number of walls open beyond a spanning tree of the
maze.
See also
braid for the opposite operation.
Examples
maze <- generate_maze(10, 10, seed = 42)
sparse <- sparsify(maze, p = 0.5)
sparse$passages
#> [1] "4,1|5,1" "5,1|5,2" "5,2|6,2" "6,1|6,2" "6,1|7,1" "7,1|7,2"
#> [7] "7,2|8,2" "8,2|8,3" "7,3|8,3" "6,3|7,3" "6,3|6,4" "6,4|7,4"
#> [13] "7,4|7,5" "7,5|7,6" "7,6|7,7" "6,7|7,7" "5,7|6,7" "5,7|5,8"
#> [19] "4,8|5,8" "4,8|4,9" "3,9|4,9" "2,9|3,9" "2,8|2,9" "2,7|2,8"
#> [25] "2,7|3,7" "3,7|4,7" "4,6|4,7" "4,6|5,6" "5,6|6,6" "6,5|6,6"
#> [31] "5,5|6,5" "5,4|5,5" "5,3|5,4" "4,3|5,3" "4,2|4,3" "3,2|4,2"
#> [37] "2,2|3,2" "2,2|2,3" "1,3|2,3" "1,3|1,4" "1,4|1,5" "1,5|1,6"
#> [43] "1,6|1,7" "1,7|1,8" "1,8|1,9" "1,10|1,9" "1,10|2,10" "2,10|3,10"
#> [49] "3,10|4,10" "4,10|5,10" "5,10|5,9" "5,9|6,9" "6,8|6,9" "6,8|7,8"
#> [55] "7,8|8,8" "8,7|8,8" "8,7|9,7" "9,6|9,7" "9,5|9,6" "10,5|9,5"
#> [61] "10,5|10,6" "10,6|10,7" "10,7|10,8" "10,8|9,8" "9,8|9,9" "8,9|9,9"
#> [67] "7,9|8,9" "7,10|7,9" "7,10|8,10" "10,4|10,5" "10,4|9,4" "9,3|9,4"
#> [73] "10,3|9,3" "10,2|10,3" "1,6|2,6" "2,5|2,6" "2,4|2,5" "2,4|3,4"
#> [79] "3,4|4,4"