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

91.89

/src/maze/algorithms/recursive_division.rs

use super::{Algorithm, BOOL_TRUE_PROBABILITY};
use crate::maze::grid::{cell::Cell, Grid};

use rand::prelude::*;

enum Orientation {
    Horizontal,
    Vertical,
}

/// The "Recursive Division" algorithm for generating mazes
///
/// According to [Wikipedia](https://en.wikipedia.org/wiki/Maze_generation_algorithm#Recursive_division_method)
/// and [James Buck's maze generation blogs](https://weblog.jamisbuck.org/2011/1/12/maze-generation-recursive-division-algorithm)
/// this algorithm should be implemented as a wall adder, as opposed to the rest of the algorithms
/// in this library which are designated as "passage carvers". In a nutshell, the idea is to
/// recursively divide the original grid with no walls — call this a "chamber" — into smaller
/// subchambers with randomly positioned walls and single passages within them. This fractal nature
/// makes this algorithm novel. You could theoretically continue the process indefinitely at
/// progressively finer and finer levels of detail on demand. This may be useful when developing a
/// game where a player wanders from one section of the maze to another without a need to store the
/// entire maze in the memory.
///
/// My implementation of this algorithm is a bit different from the above. The design of this
/// library supports only the passage-carving technique (mixing both techniques would lead to an
/// uglier API and less efficient generation mechanism, which I tested using benchmarks). Given that
/// I've slightly modified the algorithm to be rather a "passage carver". The method and its fractal
/// nature remain though. Of course, the generation process would be less fancy this way, but this
/// library has nothing to do with visualizing the generation progress step-by-step. If you're
/// interested in this side of the maze generation world, feel free to check my other program for
/// the terminal called [Daedalus](https://github.com/unrenamed/daedalus).
///
/// It's also worth mentioning that the algorithm's fractal nature leads to some visual artifacts
/// and bottlenecks like a single passage between two sections that effectively divide the entire
/// maze into two distinct regions, thus making it easy to spot the passage and work backward to a
/// solution.
pub struct RecursiveDivision;

impl RecursiveDivision {
    fn divide<R: Rng>(grid: &mut Grid, x: usize, y: usize, ax: usize, ay: usize, rng: &mut R) {
        // Calculate subfield width
        let w = ax - x + 1;
        // Calculate subfield height
        let h = ay - y + 1;

        if w < 2 || h < 2 {
            if w > 1 {
                // Carve passages till the horizontal end of the subfield
                for cx in x..ax {
                    grid.carve_passage((cx, y), Cell::EAST).unwrap();
                }
            } else if h > 1 {
                // Carve passages till the vertical end of the subfield
                for cy in y..ay {
                    grid.carve_passage((x, cy), Cell::SOUTH).unwrap();
                }
            }
            return;
        }

        // Which way a subfield with the given dimensions ought to be bisected
        let orientation = choose_orientation(w, h, rng);

        // Get X and Y coordinates of a cell where a passage will be carved
        let px = rng.random_range(x..ax);
        let py = rng.random_range(y..ay);

        // Define what direction is corresponding to the wall orientation
        let dir = match orientation {
            Orientation::Horizontal => Cell::SOUTH,
            Orientation::Vertical => Cell::EAST,
        };

        // Carve passage
        let (nx, ny) = grid.carve_passage((px, py), dir).unwrap();

        // Determine the bounds of the subfields and get them split
        match orientation {
            Orientation::Horizontal => {
                // Top subfield
                RecursiveDivision::divide(grid, x, y, ax, py, rng);
                // Bottom subfield
                RecursiveDivision::divide(grid, x, ny, ax, ay, rng);
            }
            Orientation::Vertical => {
                // Left subfield
                RecursiveDivision::divide(grid, x, y, px, ay, rng);
                // Right subfield
                RecursiveDivision::divide(grid, nx, y, ax, ay, rng);
            }
        }
    }
}

/// An implementation of the "Recursive Division" algorithm for generating mazes
///
/// It works like this:
///
/// 1. Begins with an original grid as a working field.
///
/// 2. Bisects the field either horizontally or vertically by carving a passage
///    through the wall from a random cell.
///
/// 3. Repeats step #2 with the areas on either side of the wall where the passage
///    was carved.
///
/// 4. Continues, recursively, until the maze reaches the desired resolution.
impl Algorithm for RecursiveDivision {
    fn generate(&mut self, grid: &mut Grid, rng: &mut StdRng) {
        let width = grid.width();
        let height = grid.height();
        RecursiveDivision::divide(grid, 0, 0, width - 1, height - 1, rng);
    }
}

fn choose_orientation<R: Rng>(width: usize, height: usize, rng: &mut R) -> Orientation {
    if width < height {
        return Orientation::Horizontal;
    }

    if height < width {
        return Orientation::Vertical;
    }

    if !rng.random_bool(BOOL_TRUE_PROBABILITY) {
        Orientation::Horizontal
    } else {
        Orientation::Vertical
    }
}

1	use super::{Algorithm, BOOL_TRUE_PROBABILITY};
2	use crate::maze::grid::{cell::Cell, Grid};
3
4	use rand::prelude::*;
5
6	enum Orientation {
7	Horizontal,
8	Vertical,
9	}
10
11	/// The "Recursive Division" algorithm for generating mazes
12	///
13	/// According to [Wikipedia](https://en.wikipedia.org/wiki/Maze_generation_algorithm#Recursive_division_method)
14	/// and [James Buck's maze generation blogs](https://weblog.jamisbuck.org/2011/1/12/maze-generation-recursive-division-algorithm)
15	/// this algorithm should be implemented as a wall adder, as opposed to the rest of the algorithms
16	/// in this library which are designated as "passage carvers". In a nutshell, the idea is to
17	/// recursively divide the original grid with no walls — call this a "chamber" — into smaller
18	/// subchambers with randomly positioned walls and single passages within them. This fractal nature
19	/// makes this algorithm novel. You could theoretically continue the process indefinitely at
20	/// progressively finer and finer levels of detail on demand. This may be useful when developing a
21	/// game where a player wanders from one section of the maze to another without a need to store the
22	/// entire maze in the memory.
23	///
24	/// My implementation of this algorithm is a bit different from the above. The design of this
25	/// library supports only the passage-carving technique (mixing both techniques would lead to an
26	/// uglier API and less efficient generation mechanism, which I tested using benchmarks). Given that
27	/// I've slightly modified the algorithm to be rather a "passage carver". The method and its fractal
28	/// nature remain though. Of course, the generation process would be less fancy this way, but this
29	/// library has nothing to do with visualizing the generation progress step-by-step. If you're
30	/// interested in this side of the maze generation world, feel free to check my other program for
31	/// the terminal called [Daedalus](https://github.com/unrenamed/daedalus).
32	///
33	/// It's also worth mentioning that the algorithm's fractal nature leads to some visual artifacts
34	/// and bottlenecks like a single passage between two sections that effectively divide the entire
35	/// maze into two distinct regions, thus making it easy to spot the passage and work backward to a
36	/// solution.
37	pub struct RecursiveDivision;
38
39	impl RecursiveDivision {
40	fn divide<R: Rng>(grid: &mut Grid, x: usize, y: usize, ax: usize, ay: usize, rng: &mut R) {	1✔
41	// Calculate subfield width
42	let w = ax - x + 1;	1✔
43	// Calculate subfield height
44	let h = ay - y + 1;	2✔
45
46	if w < 2 \|\| h < 2 {	2✔
47	if w > 1 {	1✔
48	// Carve passages till the horizontal end of the subfield
49	for cx in x..ax {	2✔
50	grid.carve_passage((cx, y), Cell::EAST).unwrap();	1✔
51	}
52	} else if h > 1 {	1✔
53	// Carve passages till the vertical end of the subfield
54	for cy in y..ay {	2✔
55	grid.carve_passage((x, cy), Cell::SOUTH).unwrap();	1✔
56	}
57	}
UNCOV 58	return;	×
59	}
60
61	// Which way a subfield with the given dimensions ought to be bisected
62	let orientation = choose_orientation(w, h, rng);	1✔
63
64	// Get X and Y coordinates of a cell where a passage will be carved
65	let px = rng.random_range(x..ax);	1✔
66	let py = rng.random_range(y..ay);	1✔
67
68	// Define what direction is corresponding to the wall orientation
69	let dir = match orientation {	1✔
70	Orientation::Horizontal => Cell::SOUTH,	1✔
71	Orientation::Vertical => Cell::EAST,	1✔
72	};
73
74	// Carve passage
75	let (nx, ny) = grid.carve_passage((px, py), dir).unwrap();	1✔
76
77	// Determine the bounds of the subfields and get them split
78	match orientation {	1✔
UNCOV 79	Orientation::Horizontal => {	×
80	// Top subfield
81	RecursiveDivision::divide(grid, x, y, ax, py, rng);	1✔
82	// Bottom subfield
83	RecursiveDivision::divide(grid, x, ny, ax, ay, rng);	1✔
84	}
UNCOV 85	Orientation::Vertical => {	×
86	// Left subfield
87	RecursiveDivision::divide(grid, x, y, px, ay, rng);	1✔
88	// Right subfield
89	RecursiveDivision::divide(grid, nx, y, ax, ay, rng);	1✔
90	}
91	}
92	}
93	}
94
95	/// An implementation of the "Recursive Division" algorithm for generating mazes
96	///
97	/// It works like this:
98	///
99	/// 1. Begins with an original grid as a working field.
100	///
101	/// 2. Bisects the field either horizontally or vertically by carving a passage
102	/// through the wall from a random cell.
103	///
104	/// 3. Repeats step #2 with the areas on either side of the wall where the passage
105	/// was carved.
106	///
107	/// 4. Continues, recursively, until the maze reaches the desired resolution.
108	impl Algorithm for RecursiveDivision {
109	fn generate(&mut self, grid: &mut Grid, rng: &mut StdRng) {	1✔
110	let width = grid.width();	1✔
111	let height = grid.height();	1✔
112	RecursiveDivision::divide(grid, 0, 0, width - 1, height - 1, rng);	1✔
113	}
114	}
115
116	fn choose_orientation<R: Rng>(width: usize, height: usize, rng: &mut R) -> Orientation {	1✔
117	if width < height {	1✔
118	return Orientation::Horizontal;	1✔
119	}
120
121	if height < width {	1✔
122	return Orientation::Vertical;	1✔
123	}
124
125	if !rng.random_bool(BOOL_TRUE_PROBABILITY) {	2✔
126	Orientation::Horizontal	1✔
127	} else {
128	Orientation::Vertical	1✔
129	}
130	}

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