13474961313

Committed 22 Feb 2025 05:12PM UTC coverage: 90.545% (-1.4%) from 91.92%

Build # 13474961313

Build Type

Pull #13

github

Committed by

web-flow

Commit Message

Merge 77cc77c7b into 46f49ccb0

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

Run Details

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

58 existing lines in 13 files now uncovered.

814 of 899 relevant lines covered (90.55%)

217654.5 hits per line

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

89.29

/src/maze/algorithms/binary_tree.rs

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

use clap::ValueEnum;
use rand::prelude::*;

/// An enumeration over supported biases for the "Binary Tree" algorithm
///
/// Each bias represents the two of four sides of the maze that will be spanned
/// by a single corridor.
#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, ValueEnum)]
pub enum Bias {
    /// Produces two long corridors on the Northern and Western sides of the maze
    NorthWest,

    /// Produces two long corridors on the Northern and Eastern sides of the maze
    NorthEast,

    /// Produces two long corridors on the Southern and Western sides of the maze
    SouthWest,

    /// Produces two long corridors on the Southern and Eastern sides of the maze
    SouthEast,
}

/// The "Binary Tree" algorithm for generating mazes
///
/// This is an almost-trivially simple one, but you pay for that simplicity with a few side effects:
/// a notable bias (routes tend to run diagonally) and long corridors spanning two sides. Still,
/// this is quite a performant algorithm since it operates without any state at all looking at the
/// current cell only, without regard for the rest of the cells and rows in the maze.
pub struct BinaryTree {
    bias: Bias,
}

impl BinaryTree {
    /// Create a new instance of the algorithm with a given bias
    ///
    /// # Example
    /// ```
    /// use knossos::maze::{BinaryTree, Bias};
    ///
    /// let algorithm = BinaryTree::new(Bias::NorthWest);
    /// ```
    pub const fn new(bias: Bias) -> BinaryTree {
        BinaryTree { bias }
    }

    fn populate_dirs(&self, coords: Coords, grid: &Grid) -> Vec<Cell> {
        let mut dirs = vec![];
        let (x, y) = coords;

        match self.bias {
            Bias::NorthWest => {
                if y > 0 {
                    dirs.push(Cell::NORTH)
                }
                if x > 0 {
                    dirs.push(Cell::WEST)
                }
            }
            Bias::NorthEast => {
                if y > 0 {
                    dirs.push(Cell::NORTH)
                }
                if x + 1 < grid.width() {
                    dirs.push(Cell::EAST)
                }
            }
            Bias::SouthWest => {
                if y + 1 < grid.height() {
                    dirs.push(Cell::SOUTH)
                }
                if x > 0 {
                    dirs.push(Cell::WEST)
                }
            }
            Bias::SouthEast => {
                if y + 1 < grid.height() {
                    dirs.push(Cell::SOUTH)
                }
                if x + 1 < grid.width() {
                    dirs.push(Cell::EAST)
                }
            }
        }

        dirs
    }
}

/// An implementation of the "Binary Tree" algorithm for generating mazes
///
/// The algorithm is pretty simple: for every cell in the grid, randomly carve a passage either
/// north, or west.
impl Algorithm for BinaryTree {
    fn generate(&mut self, grid: &mut Grid, rng: &mut StdRng) {
        for y in 0..grid.height() {
            for x in 0..grid.width() {
                let dirs = self.populate_dirs((x, y), grid);
                if let Some(dir) = dirs.choose(rng) {
                    grid.carve_passage((x, y), *dir).ok();
                }
            }
        }
    }
}

1	use super::Algorithm;
2	use crate::maze::grid::cell::Cell;
3	use crate::maze::grid::Grid;
4	use crate::utils::types::Coords;
5
6	use clap::ValueEnum;
7	use rand::prelude::*;
8
9	/// An enumeration over supported biases for the "Binary Tree" algorithm
10	///
11	/// Each bias represents the two of four sides of the maze that will be spanned
12	/// by a single corridor.
13	#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, ValueEnum)]
14	pub enum Bias {
15	/// Produces two long corridors on the Northern and Western sides of the maze
16	NorthWest,
17
18	/// Produces two long corridors on the Northern and Eastern sides of the maze
19	NorthEast,
20
21	/// Produces two long corridors on the Southern and Western sides of the maze
22	SouthWest,
23
24	/// Produces two long corridors on the Southern and Eastern sides of the maze
25	SouthEast,
26	}
27
28	/// The "Binary Tree" algorithm for generating mazes
29	///
30	/// This is an almost-trivially simple one, but you pay for that simplicity with a few side effects:
31	/// a notable bias (routes tend to run diagonally) and long corridors spanning two sides. Still,
32	/// this is quite a performant algorithm since it operates without any state at all looking at the
33	/// current cell only, without regard for the rest of the cells and rows in the maze.
34	pub struct BinaryTree {
35	bias: Bias,
36	}
37
38	impl BinaryTree {
39	/// Create a new instance of the algorithm with a given bias
40	///
41	/// # Example
42	/// ```
43	/// use knossos::maze::{BinaryTree, Bias};
44	///
45	/// let algorithm = BinaryTree::new(Bias::NorthWest);
46	/// ```
47	pub const fn new(bias: Bias) -> BinaryTree {	8✔
48	BinaryTree { bias }
49	}
50
51	fn populate_dirs(&self, coords: Coords, grid: &Grid) -> Vec<Cell> {	800✔
52	let mut dirs = vec![];	800✔
53	let (x, y) = coords;	800✔
54
55	match self.bias {	800✔
56	Bias::NorthWest => {
57	if y > 0 {	200✔
58	dirs.push(Cell::NORTH)	180✔
59	}
UNCOV 60	if x > 0 {	×
61	dirs.push(Cell::WEST)	180✔
62	}
63	}
64	Bias::NorthEast => {
65	if y > 0 {	200✔
66	dirs.push(Cell::NORTH)	180✔
67	}
68	if x + 1 < grid.width() {	200✔
69	dirs.push(Cell::EAST)	180✔
70	}
71	}
72	Bias::SouthWest => {
73	if y + 1 < grid.height() {	200✔
74	dirs.push(Cell::SOUTH)	180✔
75	}
76	if x > 0 {	200✔
77	dirs.push(Cell::WEST)	180✔
78	}
79	}
80	Bias::SouthEast => {
81	if y + 1 < grid.height() {	200✔
82	dirs.push(Cell::SOUTH)	180✔
83	}
84	if x + 1 < grid.width() {	200✔
85	dirs.push(Cell::EAST)	180✔
86	}
87	}
88	}
89
90	dirs	800✔
91	}
92	}
93
94	/// An implementation of the "Binary Tree" algorithm for generating mazes
95	///
96	/// The algorithm is pretty simple: for every cell in the grid, randomly carve a passage either
97	/// north, or west.
98	impl Algorithm for BinaryTree {
99	fn generate(&mut self, grid: &mut Grid, rng: &mut StdRng) {	8✔
100	for y in 0..grid.height() {	88✔
101	for x in 0..grid.width() {	800✔
UNCOV 102	let dirs = self.populate_dirs((x, y), grid);	×
103	if let Some(dir) = dirs.choose(rng) {	792✔
UNCOV 104	grid.carve_passage((x, y), *dir).ok();	×
105	}
106	}
107	}
108	}
109	}

unrenamed / knossos / 13474961313

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