Created
February 10, 2024 15:50
-
-
Save ericwen229/9ba6c84b75c4f6e8458e64212533cf4f to your computer and use it in GitHub Desktop.
DFS based maze generating algorithm implemented in Rust
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| use rand::rngs::StdRng; | |
| use rand::seq::SliceRandom; | |
| use rand::SeedableRng; | |
| use std::collections::HashSet; | |
| pub fn gen(rows: usize, cols: usize, seed: u64) -> Maze { | |
| MazeGenerator::new(rows, cols, seed).gen() | |
| } | |
| pub struct Maze { | |
| rows: usize, | |
| cols: usize, | |
| edges: HashSet<Edge>, | |
| } | |
| impl Maze { | |
| fn new(rows: usize, cols: usize, edges: HashSet<Edge>) -> Self { | |
| Self { rows, cols, edges } | |
| } | |
| pub fn print(&self) { | |
| // print header line | |
| print!("+"); | |
| for _ in 0..self.cols { | |
| print!("---+"); | |
| } | |
| print!("\n"); | |
| // print rows | |
| for row in 0..self.rows { | |
| print!("|"); | |
| for col in 0..self.cols { | |
| print!(" "); | |
| let edge = Edge::new(Pos::new(row, col), Pos::new(row, col + 1)); | |
| if self.edges.contains(&edge) { | |
| print!(" "); | |
| } else { | |
| print!("|"); | |
| } | |
| } | |
| print!("\n"); | |
| print!("+"); | |
| for col in 0..self.cols { | |
| let edge = Edge::new(Pos::new(row, col), Pos::new(row + 1, col)); | |
| if self.edges.contains(&edge) { | |
| print!(" "); | |
| } else { | |
| print!("---"); | |
| } | |
| print!("+") | |
| } | |
| print!("\n"); | |
| } | |
| } | |
| } | |
| struct MazeGenerator { | |
| rows: usize, | |
| cols: usize, | |
| edges: HashSet<Edge>, | |
| visited: HashSet<Pos>, | |
| rng: StdRng, | |
| } | |
| impl MazeGenerator { | |
| fn new(rows: usize, cols: usize, seed: u64) -> Self { | |
| if rows == 0 || cols == 0 { | |
| panic!() | |
| } | |
| Self { | |
| rows, | |
| cols, | |
| edges: HashSet::new(), | |
| visited: HashSet::new(), | |
| rng: StdRng::seed_from_u64(seed), | |
| } | |
| } | |
| fn gen(mut self) -> Maze { | |
| self.dfs(Pos::new(0, 0)); | |
| Maze::new(self.rows, self.cols, self.edges) | |
| } | |
| fn get_neighbor_list(&self, pos: Pos) -> Vec<Pos> { | |
| let mut list = Vec::with_capacity(4); | |
| if pos.row >= 1 { | |
| list.push(Pos::new(pos.row - 1, pos.col)); | |
| } | |
| if pos.row + 1 < self.rows { | |
| list.push(Pos::new(pos.row + 1, pos.col)); | |
| } | |
| if pos.col >= 1 { | |
| list.push(Pos::new(pos.row, pos.col - 1)); | |
| } | |
| if pos.col + 1 < self.cols { | |
| list.push(Pos::new(pos.row, pos.col + 1)); | |
| } | |
| list | |
| } | |
| fn dfs(&mut self, pos: Pos) { | |
| self.visited.insert(pos); | |
| let mut neighbor_list = self.get_neighbor_list(pos); | |
| neighbor_list.shuffle(&mut self.rng); | |
| for neighbor_pos in neighbor_list { | |
| if self.visited.contains(&neighbor_pos) { | |
| continue; | |
| } | |
| self.edges.insert(Edge::new(pos, neighbor_pos)); | |
| self.dfs(neighbor_pos); | |
| } | |
| } | |
| } | |
| #[derive(Eq, PartialEq, Hash, Debug)] | |
| struct Edge(Pos, Pos); | |
| impl Edge { | |
| fn new(a: Pos, b: Pos) -> Self { | |
| if a < b { | |
| Self(a, b) | |
| } else { | |
| Self(b, a) | |
| } | |
| } | |
| } | |
| #[derive(Copy, Clone, PartialOrd, Eq, PartialEq, Hash, Debug)] | |
| struct Pos { | |
| row: usize, | |
| col: usize, | |
| } | |
| impl Pos { | |
| fn new(row: usize, col: usize) -> Self { | |
| Self { row, col } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment