Skip to contents

Summarizes the structural character of a maze: how many dead ends it has, how long its corridors are, how branchy it is, how "wide" it is from corner to corner, how much of the grid its shortest solution covers, and how straight its corridors tend to run. Useful for comparing mazes produced by different generate_maze() algorithms or open_walls settings.

Usage

maze_stats(maze)

# S3 method for class 'maze_stats'
print(x, ...)

# S3 method for class 'maze_stats'
as.data.frame(x, row.names = NULL, optional = FALSE, ...)

Arguments

maze

A maze object returned by generate_maze().

x

A maze_stats object, as returned by maze_stats().

...

Additional arguments, currently unused.

row.names, optional

Passed on for compatibility with as.data.frame(); not otherwise used.

Value

An object of class maze_stats (a list, printed with its own print method, and convertible to a one-row data frame with as.data.frame()) containing:

rows, cols

The maze's dimensions.

algorithm

The generation algorithm recorded on maze.

open_walls

The open_walls probability recorded on maze.

dead_ends, dead_end_pct

The number of degree-1 cells, and that count as a fraction of all cells.

corridor_mean, corridor_max

The mean and maximum corridor length (in edges), across every corridor as defined above. NA for a 1x1 maze, which has no corridors.

degree1, degree2, degree3, degree4

The number of cells with exactly 1, 2, 3, or 4 open passages. These four counts sum to rows * cols (every generated maze keeps every cell connected, so degree 0 does not occur except in a degenerate 1x1 maze).

diameter

The length, in steps, of the longest shortest path between any two cells in the maze – its graph diameter. Computed by a double-sweep BFS: farthest cell from an arbitrary corner, then farthest cell from that cell, then the shortest-path length between those two. This is exact for a perfect maze (a tree) but only an approximation, typically a slight underestimate, for a braided maze with loops.

solution_length, solution_pct

The number of cells on the shortest path from maze$start to maze$end (via solve_maze(maze, algorithm = "bfs")), and that count as a fraction of all cells.

river

A straightness measure in [0, 1], NA if the maze has no corridor with at least two edges. Within a corridor, each step after the first either continues in the same direction as the step before it or turns; river is the fraction of those steps that continue straight, averaged over every corridor with at least two edges (each corridor contributes one fraction, regardless of its length). A river near 1 means the maze is dominated by long, straight corridors; a river near 0 means corridors turn at nearly every cell.

The print method returns x invisibly; as.data.frame() returns a one-row data.frame with one column per element above.

Details

A corridor here is a maximal run of cells between two "special" cells (a dead end, a branch, or an intersection – any cell whose number of open passages, its degree, is not exactly 2), following the unique route through the intervening degree-2 cells. In a perfect maze every corridor has exactly two such endpoints. A braided maze (see open_walls in generate_maze()) can additionally contain a loop of degree-2 cells with no special cell on it at all; each such loop is counted as one more corridor whose length is its own edge count.

Examples

maze <- generate_maze(15, 15, seed = 42)
maze_stats(maze)
#> <maze_stats> 15 x 15 (dfs)
#>   dead ends:   25 (11.1%)
#>   degree 1/2/3/4: 25 / 177 / 23 / 0
#>   corridors:   mean 4.77, max 28
#>   diameter:    167
#>   solution:    30 cells (13.3% of maze)
#>   river:       0.358

# Braiding a maze (adding loops) tends to shorten its corridors and
# increase its branching.
braided <- generate_maze(15, 15, seed = 42, open_walls = 0.3)
as.data.frame(maze_stats(braided))
#>   rows cols algorithm open_walls dead_ends dead_end_pct corridor_mean
#> 1   15   15       dfs        0.3        11   0.04888889      1.557377
#>   corridor_max degree1 degree2 degree3 degree4 diameter solution_length
#> 1            7      11     102      93      19       29              12
#>   solution_pct     river
#> 1   0.05333333 0.4180791