14673949004

Committed 25 Apr 2025 09:38PM UTC coverage: 89.164% (-0.06%) from 89.22%

Build # 14673949004

Build Type

push

github

Committed by

web-flow

Commit Message

Update bevy 016 and Edition 2024 (#9)

Chore: Update to bevy 0.16 and to Edition 2024.

- adds pedantic linting

Run Details

54 of 68 new or added lines in 18 files covered. (79.41%)

1 existing line in 1 file now uncovered.

864 of 969 relevant lines covered (89.16%)

1.97 hits per line

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

97.37

/src/maze/algorithms/recursive_division.rs

use super::{Algorithm, BOOL_TRUE_PROBABILITY};
use crate::{
    maze::grid::{cell::Cell, Grid},
    utils::types::Coords,
};
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(grid: &mut Grid, x: usize, y: usize, ax: usize, ay: usize, rng: &mut impl Rng) {
        // 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.
/// Does not support start position.
///
/// 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.
///  
/// # Warn
///
/// The `generate` function will warn in case a [`start_coords`] is passed.
impl Algorithm for RecursiveDivision {
    fn generate(&mut self, grid: &mut Grid, c: Option<Coords>, rng: &mut StdRng) {
        if c.is_some() {
            eprintln!("Algorithm `{}` doesn't suppoer `start_coords`", self.name());
        }
        let width = grid.width();
        let height = grid.height();
        RecursiveDivision::divide(grid, 0, 0, width - 1, height - 1, rng);
    }

    fn has_start_coords(&self) -> bool {
        false
    }

    fn name(&self) -> &'static str {
        "RecursiveDivision"
    }
}

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

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

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

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

naomijub / bevy_knossos / 14673949004

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