Struct Prim

pub struct Prim { /* private fields */ }

The Prim’s algorithm for generating mazes

The original version of the algorithm generates a minimal spanning tree in a graph. With one little change, it becomes a suitable method for generating mazes.

Mazes generated by Prim’s algorithm share many of the characteristics of those created via Kruskal’s algorithm, such as having an abundance of short cul-de-sacs which makes the maze harder to puzzle out at a glance

Implementations

impl Prim

pub const fn new() -> Prim

Create a new instance of the algorithm with an empty set of the frontier cells

Trait Implementations

impl Algorithm for Prim

An implementation of the Prim’s algorithm for generating mazes

For efficiency, let’s define a legend for the following algorithm steps:

• “F” or “frontier”: the set of all cells that are not yet in the maze, but are adjacent to a cell that is in the maze.

The standard version of the algorithm generates a minimal spanning tree in a graph. With a slight change of adding some random, it works something like this:

1. Chooses an arbitrary cell and adds it to the maze.

2. Adds all neighbor cells that are not in the F yet to F.

3. Removes one of the F cells at random and carves a passage from that to whichever adjacent cell is already part of the maze.

4. Adds the neighbours of the formerly frontier cell to the F.

5. Repeats steps 3 and 4 until the F is empty.

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

impl Default for Prim

fn default() -> Self

Returns the “default value” for a type.