knossos/maze/algorithms/
prim.rs

1use super::Algorithm;
2use crate::utils::types::Coords;
3use crate::maze::grid::{Grid, cell::Cell};
4
5use rand::prelude::*;
6use std::vec;
7
8/// The Prim's algorithm for generating mazes
9///
10/// The original version of the algorithm generates a minimal spanning tree in a graph.
11/// With one little change, it becomes a suitable method for generating mazes.
12///
13/// Mazes generated by Prim’s algorithm share many of the characteristics of those created
14/// via Kruskal’s algorithm, such as having an abundance of short cul-de-sacs which makes
15/// the maze harder to puzzle out at a glance
16pub struct Prim {
17    frontiers: Vec<Coords>,
18}
19
20impl Prim {
21    /// Create a new instance of the algorithm with an empty set of the frontier cells
22    pub const fn new() -> Prim {
23        Prim { frontiers: vec![] }
24    }
25
26    fn mark(&mut self, coords: Coords, grid: &mut Grid) {
27        grid.mark_cell(coords);
28
29        let (x, y) = coords;
30        self.add_frontier((x + 1, y), grid);
31        self.add_frontier((x, y + 1), grid);
32        if x > 0 {
33            self.add_frontier((x - 1, y), grid);
34        }
35        if y > 0 {
36            self.add_frontier((x, y - 1), grid);
37        }
38    }
39
40    fn add_frontier(&mut self, (x, y): Coords, grid: &mut Grid) {
41        if x < grid.width()
42            && y < grid.height()
43            && !grid.is_cell_marked((x, y))
44            && !self.frontiers.iter().any(|f| *f == (x, y))
45        {
46            self.frontiers.push((x, y));
47        }
48    }
49
50    fn neighbours(&self, (x, y): Coords, grid: &mut Grid) -> Vec<Coords> {
51        let mut neighbours = vec![];
52
53        if x > 0 && grid.is_cell_marked((x - 1, y)) {
54            neighbours.push((x - 1, y))
55        }
56
57        if x + 1 < grid.width() && grid.is_cell_marked((x + 1, y)) {
58            neighbours.push((x + 1, y))
59        }
60
61        if y > 0 && grid.is_cell_marked((x, y - 1)) {
62            neighbours.push((x, y - 1))
63        }
64
65        if y + 1 < grid.height() && grid.is_cell_marked((x, y + 1)) {
66            neighbours.push((x, y + 1))
67        }
68
69        neighbours
70    }
71}
72
73impl Default for Prim {
74    fn default() -> Self {
75        Self::new()
76    }
77}
78
79/// An implementation of the Prim's algorithm for generating mazes
80///
81/// For efficiency, let’s define a legend for the following algorithm steps:
82/// - "F" or "frontier”: the set of all cells that are not yet in the maze, but are adjacent to a
83///   cell that is in the maze.
84///
85/// The standard version of the algorithm generates a minimal spanning tree in a graph. With a
86/// slight change of adding some random, it works something like this:
87///
88/// 1. Chooses an arbitrary cell and adds it to the maze.
89///
90/// 2. Adds all neighbor cells that are not in the F yet to F.
91///
92/// 3. Removes one of the F cells at random and carves a passage from that to whichever adjacent
93///    cell is already part of the maze.
94///
95/// 4. Adds the neighbours of the formerly frontier cell to the F.
96///
97/// 5. Repeats steps 3 and 4 until the F is empty.
98impl Algorithm for Prim {
99    fn generate(&mut self, grid: &mut Grid, rng: &mut StdRng) {
100        self.mark(get_rand_coords(grid, rng), grid);
101
102        while !self.frontiers.is_empty() {
103            let index = rng.random_range(0..self.frontiers.len());
104            let coords = self.frontiers.remove(index);
105
106            let neighbours = self.neighbours(coords, grid);
107
108            let index = rng.random_range(0..neighbours.len());
109            let (nx, ny) = neighbours[index];
110
111            let (x, y) = coords;
112
113            if let Some(dir) = direction(x, y, nx, ny) {
114                grid.carve_passage(coords, dir).unwrap();
115                self.mark(coords, grid);
116            }
117        }
118    }
119}
120
121fn get_rand_coords<R: Rng>(grid: &Grid, rng: &mut R) -> Coords {
122    let x = rng.random_range(0..grid.width());
123    let y = rng.random_range(0..grid.height());
124    (x, y)
125}
126
127fn direction(x: usize, y: usize, nx: usize, ny: usize) -> Option<Cell> {
128    if x < nx {
129        return Some(Cell::EAST);
130    }
131    if x > nx {
132        return Some(Cell::WEST);
133    }
134    if y < ny {
135        return Some(Cell::SOUTH);
136    }
137    if y > ny {
138        return Some(Cell::NORTH);
139    }
140
141    unreachable!("The x and y coordinates are never equal to nx and ny")
142}
143
144#[cfg(test)]
145mod tests {
146    use super::*;
147
148    #[test]
149    fn default_call() {
150        let algo = Prim::default();
151        let v: Vec<Coords> = vec![];
152        assert_eq!(v, algo.frontiers);
153    }
154}
knossos/maze/algorithms/prim.rs

knossos/maze/algorithms/
prim.rs
