mazer/algorithms/
binary_tree.rs

1use crate::behaviors::maze::MazeGeneration;
2use crate::algorithms::MazeAlgorithm;
3use crate::grid::Grid;
4use crate::cell::{Coordinates, MazeType};
5use crate::error::Error;
6
7use std::collections::HashSet;
8
9pub struct BinaryTree;
10
11impl MazeGeneration for BinaryTree {
12    fn generate(&self, grid: &mut Grid) -> Result<(), Error> {
13        match grid.maze_type {
14            MazeType::Orthogonal => {} // proceed with maze generation for allowed Orthogonal (square) grid type
15            maze_type => {
16                return Err(Error::AlgorithmUnavailableForMazeType {
17                    algorithm: MazeAlgorithm::BinaryTree,
18                    maze_type: maze_type,
19                });
20            }
21        }
22        let rows = grid.height;
23        let cols = grid.width;
24
25        // Capture initial state if capture_steps is true
26        if grid.capture_steps {
27            let changed_cells = HashSet::new(); // Empty set for initial state
28            self.capture_step(grid, &changed_cells);
29        }
30
31        for row in 0..rows {
32            for col in 0..cols {
33                let current_coords = Coordinates { x: col, y: row };
34                let right_exists = col + 1 < cols;
35                let down_exists = row + 1 < rows;
36                let carve_down = if right_exists && down_exists {
37                    grid.random_bool() // Randomly decide between down and right
38                } else {
39                    !right_exists
40                };
41                if carve_down {
42                    if down_exists {
43                        let down_coords = Coordinates { x: col, y: row + 1 };
44                        grid.link(current_coords, down_coords)?;
45                        if grid.capture_steps {
46                            let mut changed_cells = HashSet::new();
47                            changed_cells.insert(current_coords);
48                            changed_cells.insert(down_coords);
49                            self.capture_step(grid, &changed_cells);
50                        }
51                    }
52                } else {
53                    if right_exists {
54                        let right_coords = Coordinates { x: col + 1, y: row };
55                        grid.link(current_coords, right_coords)?;
56                        if grid.capture_steps {
57                            let mut changed_cells = HashSet::new();
58                            changed_cells.insert(current_coords);
59                            changed_cells.insert(right_coords);
60                            self.capture_step(grid, &changed_cells);
61                        }
62                    }
63                }
64            }
65        }
66        Ok(())
67    }
68}
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73    use crate::cell::{MazeType, Coordinates};
74
75    #[test]
76    fn print_5_x_5_orthogonal_maze() {
77        match Grid::new(
78            MazeType::Orthogonal,
79            4,
80            4,
81            Coordinates { x: 0, y: 0 },
82            Coordinates { x: 3, y: 3 },
83            false,
84        ) {
85            Ok(mut grid) => {
86                assert!(!grid.is_perfect_maze().unwrap());
87                BinaryTree
88                    .generate(&mut grid)
89                    .expect("BinaryTree maze generation failed");
90                println!("\n\nBinary Tree\n\n{}\n\n", grid.to_asci());
91                assert!(grid.is_perfect_maze().unwrap());
92            }
93            Err(e) => panic!("Unexpected error generating grid: {:?}", e),
94        }
95    }
96
97    #[test]
98    fn print_12_x_24_orthogonal_maze() {
99        match Grid::new(
100            MazeType::Orthogonal,
101            12,
102            24,
103            Coordinates { x: 0, y: 0 },
104            Coordinates { x: 11, y: 23 },
105            false,
106        ) {
107            Ok(mut grid) => {
108                assert!(!grid.is_perfect_maze().unwrap());
109                BinaryTree
110                    .generate(&mut grid)
111                    .expect("BinaryTree maze generation failed");
112                println!("\n\nBinary Tree\n\n{}\n\n", grid.to_asci());
113                assert!(grid.is_perfect_maze().unwrap());
114            }
115            Err(e) => panic!("Unexpected error generating grid: {:?}", e),
116        }
117    }
118
119    #[test]
120    fn reject_5_x_5_delta_binary_tree_maze() {
121        match Grid::new(
122            MazeType::Delta,
123            4,
124            4,
125            Coordinates { x: 0, y: 0 },
126            Coordinates { x: 3, y: 3 },
127            false,
128        ) {
129            Ok(mut grid) => {
130                assert!(!grid.is_perfect_maze().unwrap());
131                match BinaryTree.generate(&mut grid) {
132                    Ok(()) => {
133                        panic!("Successfully generated a BinaryTree maze for a Delta grid, which should have been rejected!");
134                    }
135                    Err(e) => {
136                        println!(
137                            "As expected, Delta grid is rejected for BinaryTree maze generation: {:?}",
138                            e
139                        );
140                    }
141                }
142            }
143            Err(e) => panic!("Unexpected error generating grid: {:?}", e),
144        }
145    }
146
147    #[test]
148    fn reject_5_x_5_sigma_binary_tree_maze() {
149        match Grid::new(
150            MazeType::Sigma,
151            4,
152            4,
153            Coordinates { x: 0, y: 0 },
154            Coordinates { x: 3, y: 3 },
155            false,
156        ) {
157            Ok(mut grid) => {
158                assert!(!grid.is_perfect_maze().unwrap());
159                match BinaryTree.generate(&mut grid) {
160                    Ok(()) => {
161                        panic!("Successfully generated a BinaryTree maze for a Sigma grid, which should have been rejected!");
162                    }
163                    Err(e) => {
164                        println!(
165                            "As expected, Sigma grid is rejected for BinaryTree maze generation: {:?}",
166                            e
167                        );
168                    }
169                }
170            }
171            Err(e) => panic!("Unexpected error generating grid: {:?}", e),
172        }
173    }
174
175    #[test]
176    fn test_binary_tree_with_capture_steps() {
177        let start = Coordinates { x: 0, y: 0 };
178        let goal = Coordinates { x: 19, y: 19 };
179        match Grid::new(MazeType::Orthogonal, 20, 20, start, goal, true) {
180            Ok(mut grid) => {
181                assert!(!grid.is_perfect_maze().unwrap());
182                BinaryTree.generate(&mut grid).expect("Maze generation failed");
183                assert!(grid.is_perfect_maze().unwrap());
184                assert!(grid.generation_steps.is_some());
185                let steps = grid.generation_steps.as_ref().unwrap();
186                assert!(!steps.is_empty());
187                // Check if any cells become linked across all generation steps
188                let has_linked_cells = steps.iter().any(|step| {
189                    step.cells.iter().filter_map(|opt| opt.as_ref()).any(|cell| !cell.linked.is_empty())
190                });
191                assert!(has_linked_cells, "No cells were linked during maze generation");
192                let has_open_walls = steps.iter().any(|step| {
193                    step.cells.iter().filter_map(|opt| opt.as_ref()).any(|cell| !cell.open_walls.is_empty())
194                });
195                assert!(has_open_walls, "No cells have open walls in generation steps");
196            }
197            Err(e) => panic!("Unexpected error generating grid: {:?}", e),
198        }
199    }
200}
mazer/algorithms/binary_tree.rs

mazer/algorithms/
binary_tree.rs
