Skip to contents

The 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.

Usage

sparsify(maze, p = 0.5)

Arguments

maze

A maze object, as returned by generate_maze().

p

Probability, in [0, 1], that any given dead end is erased in a pass. Higher values cull more of the maze; 0 is 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"