knossos/maze/algorithms/
recursive_backtracking.rs

1use super::Algorithm;
2use crate::maze::grid::{Grid, cell::Cell};
3use crate::utils::types::Coords;
4
5use rand::prelude::*;
6
7/// The "Recursive Backtracking" algorithm for generating mazes
8///
9/// This algorithm quite effectively creates narrow passages with multiple dead-ends which makes it
10/// easy to get lost, thus eventually making it hard to solve the maze.
11///
12/// In most cases, this algorithm is fast. However, due to its recursive nature, it requires stack
13/// space proportional to the longest acyclic path, which is, in the worst case, the entire maze. So
14/// for exceptionally large mazes this algorithm can be fairly inefficient.
15pub struct RecursiveBacktracking;
16
17/// An implementation of the "Recursive Backtracking" algorithm for generating mazes
18///
19/// Here is how it works:
20///
21/// 1. Chooses a starting point in the field.
22///
23/// 2. Randomly chooses a wall at that point and carves a passage through to the adjacent cell,
24///    but only if the adjacent cell has not been visited yet. This becomes the new current cell.
25///
26/// 3. If all adjacent cells have been visited, backs up to the last cell that has uncarved walls
27///    and repeats.
28///
29/// 4. The algorithm ends when the process has backed all the way up to the starting
30///    point.
31impl Algorithm for RecursiveBacktracking {
32    fn generate(&mut self, grid: &mut Grid, rng: &mut StdRng) {
33        let start_coords = (0, 0);
34        carve_passages_from(start_coords, grid, rng);
35    }
36}
37
38fn carve_passages_from<R: Rng>(coords: Coords, grid: &mut Grid, rng: &mut R) {
39    let mut dirs = [Cell::NORTH, Cell::SOUTH, Cell::WEST, Cell::EAST];
40    dirs.shuffle(rng);
41
42    for dir in dirs {
43        let next = match grid.get_next_cell_coords(coords, dir) {
44            Ok(next) => next,
45            Err(_) => continue,
46        };
47
48        if grid.is_cell_visited(next) {
49            continue;
50        }
51
52        if let Ok(next) = grid.carve_passage(coords, dir) {
53            carve_passages_from(next, grid, rng);
54        }
55    }
56}
knossos/maze/algorithms/recursive_backtracking.rs

knossos/maze/algorithms/
recursive_backtracking.rs
