Struct RecursiveDivision

pub struct RecursiveDivision;

The “Recursive Division” algorithm for generating mazes

According to Wikipedia and James Buck’s maze generation blogs this algorithm should be implemented as a wall adder, as opposed to the rest of the algorithms in this library which are designated as “passage carvers”. In a nutshell, the idea is to recursively divide the original grid with no walls — call this a “chamber” — into smaller subchambers with randomly positioned walls and single passages within them. This fractal nature makes this algorithm novel. You could theoretically continue the process indefinitely at progressively finer and finer levels of detail on demand. This may be useful when developing a game where a player wanders from one section of the maze to another without a need to store the entire maze in the memory.

My implementation of this algorithm is a bit different from the above. The design of this library supports only the passage-carving technique (mixing both techniques would lead to an uglier API and less efficient generation mechanism, which I tested using benchmarks). Given that I’ve slightly modified the algorithm to be rather a “passage carver”. The method and its fractal nature remain though. Of course, the generation process would be less fancy this way, but this library has nothing to do with visualizing the generation progress step-by-step. If you’re interested in this side of the maze generation world, feel free to check my other program for the terminal called Daedalus.

It’s also worth mentioning that the algorithm’s fractal nature leads to some visual artifacts and bottlenecks like a single passage between two sections that effectively divide the entire maze into two distinct regions, thus making it easy to spot the passage and work backward to a solution.

Trait Implementations

impl Algorithm for RecursiveDivision

An implementation of the “Recursive Division” algorithm for generating mazes

It works like this:

1. Begins with an original grid as a working field.

2. Bisects the field either horizontally or vertically by carving a passage through the wall from a random cell.

3. Repeats step #2 with the areas on either side of the wall where the passage was carved.

4. Continues, recursively, until the maze reaches the desired resolution.

fn generate(&mut self, grid: &mut Grid, rng: &mut StdRng)

Runs algorithm through the given Grid object, thus mutating the grid and generating a new maze