13483778985

Committed 23 Feb 2025 02:06PM UTC coverage: 91.067% (-0.9%) from 91.92%

Build # 13483778985

Build Type

Pull #13

github

Committed by

web-flow

Commit Message

Merge d260268f4 into 46f49ccb0

Pull Request Pull Request #13: Add Optional Random Seed for Deterministic Maze Generation

Run Details

53 of 53 new or added lines in 11 files covered. (100.0%)

14 existing lines in 8 files now uncovered.

785 of 862 relevant lines covered (91.07%)

1.97 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

85.71

/src/maze/algorithms/recursive_backtracking.rs

use super::Algorithm;
use crate::maze::grid::{Grid, cell::Cell};
use crate::utils::types::Coords;

use rand::prelude::*;

/// The "Recursive Backtracking" algorithm for generating mazes
///
/// This algorithm quite effectively creates narrow passages with multiple dead-ends which makes it
/// easy to get lost, thus eventually making it hard to solve the maze.
///
/// In most cases, this algorithm is fast. However, due to its recursive nature, it requires stack
/// space proportional to the longest acyclic path, which is, in the worst case, the entire maze. So
/// for exceptionally large mazes this algorithm can be fairly inefficient.
pub struct RecursiveBacktracking;

/// An implementation of the "Recursive Backtracking" algorithm for generating mazes
///
/// Here is how it works:
///
/// 1. Chooses a starting point in the field.
///
/// 2. Randomly chooses a wall at that point and carves a passage through to the adjacent cell,
///    but only if the adjacent cell has not been visited yet. This becomes the new current cell.
///
/// 3. If all adjacent cells have been visited, backs up to the last cell that has uncarved walls
///    and repeats.
///
/// 4. The algorithm ends when the process has backed all the way up to the starting
///    point.
impl Algorithm for RecursiveBacktracking {
    fn generate(&mut self, grid: &mut Grid, rng: &mut StdRng) {
        let start_coords = (0, 0);
        carve_passages_from(start_coords, grid, rng);
    }
}

fn carve_passages_from<R: Rng>(coords: Coords, grid: &mut Grid, rng: &mut R) {
    let mut dirs = [Cell::NORTH, Cell::SOUTH, Cell::WEST, Cell::EAST];
    dirs.shuffle(rng);

    for dir in dirs {
        let next = match grid.get_next_cell_coords(coords, dir) {
            Ok(next) => next,
            Err(_) => continue,
        };

        if grid.is_cell_visited(next) {
            continue;
        }

        if let Ok(next) = grid.carve_passage(coords, dir) {
            carve_passages_from(next, grid, rng);
        }
    }
}

1	use super::Algorithm;
2	use crate::maze::grid::{Grid, cell::Cell};
3	use crate::utils::types::Coords;
4
5	use 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.
15	pub 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.
31	impl Algorithm for RecursiveBacktracking {
32	fn generate(&mut self, grid: &mut Grid, rng: &mut StdRng) {	2✔
33	let start_coords = (0, 0);	2✔
34	carve_passages_from(start_coords, grid, rng);	2✔
35	}
36	}
37
38	fn carve_passages_from<R: Rng>(coords: Coords, grid: &mut Grid, rng: &mut R) {	2✔
39	let mut dirs = [Cell::NORTH, Cell::SOUTH, Cell::WEST, Cell::EAST];	2✔
40	dirs.shuffle(rng);	2✔
41
42	for dir in dirs {	6✔
43	let next = match grid.get_next_cell_coords(coords, dir) {	2✔
44	Ok(next) => next,	2✔
UNCOV 45	Err(_) => continue,	×
46	};
47
48	if grid.is_cell_visited(next) {	2✔
UNCOV 49	continue;	×
50	}
51
52	if let Ok(next) = grid.carve_passage(coords, dir) {	2✔
53	carve_passages_from(next, grid, rng);	4✔
54	}
55	}
56	}

unrenamed / knossos / 13483778985

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous