Module maze_generator::growing_tree

source · [−]
Expand description

Growing tree implementation

  1. Let C be a list of cells, initially empty. Add one cell to C, at random.
  2. Choose a cell from C, and carve a passage to any unvisited neighbor of that cell, adding that neighbor to C as well. If there are no unvisited neighbors, remove the cell from C.
  3. Repeat #2 until C is empty

Pretty straight-forward, really. But the fun lies in how you choose the cells from C, in step #2. If you always choose the newest cell (the one most recently added), you’ll get the recursive backtracker. If you always choose a cell at random, you get Prim’s. It’s remarkably fun to experiment with other ways to choose cells from C.

Explanation and credits to Jamis Buck’s Buckblog

Structs

GrowingTreeGenerator

Generator implementation which uses the recursive-backtracking algorithm.

Enums

GrowingTreeSelectionMethod

Different ways in which the next root cell is selected from the stack of possibilities