

 This page uses content from Wikipedia. The original article was at Maze generation algorithm. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)




Task

Generate and show a maze, using the simple Depth-first search algorithm.

Start at a random cell.
Mark the current cell as visited, and get a list of its neighbors. For each neighbor, starting with a randomly selected neighbor:
If that neighbor hasn't been visited, remove the wall between this cell and that neighbor, and then recurse with that neighbor as the current cell.


 Related tasks
 Maze solving.


use rand::{thread_rng, Rng, rngs::ThreadRng};
 
const WIDTH: usize = 16;
const HEIGHT: usize = 16;
 
#[derive(Clone, Copy)]
struct Cell {
    col: usize,
    row: usize,
}
 
impl Cell {
    fn from(col: usize, row: usize) -> Cell {
        Cell {col, row}
    }
}
 
struct Maze {
    cells: [[bool; HEIGHT]; WIDTH],         //cell visited/non visited
    walls_h: [[bool; WIDTH]; HEIGHT + 1],   //horizontal walls existing/removed
    walls_v: [[bool; WIDTH + 1]; HEIGHT],   //vertical walls existing/removed
    thread_rng: ThreadRng,                  //Random numbers generator
}
 
impl Maze {
 
    ///Inits the maze, with all the cells unvisited and all the walls active
    fn new() -> Maze {
        Maze { 
            cells: [[true; HEIGHT]; WIDTH], 
            walls_h: [[true; WIDTH]; HEIGHT + 1],
            walls_v: [[true; WIDTH + 1]; HEIGHT],
            thread_rng: thread_rng(),
        }
    }
 
    ///Randomly chooses the starting cell
    fn first(&mut self) -> Cell {
        Cell::from(self.thread_rng.gen_range(0, WIDTH), self.thread_rng.gen_range(0, HEIGHT))
    }
 
    ///Opens the enter and exit doors
    fn open_doors(&mut self) {
        let from_top: bool = self.thread_rng.gen();
        let limit = if from_top { WIDTH } else { HEIGHT };
        let door = self.thread_rng.gen_range(0, limit);
        let exit = self.thread_rng.gen_range(0, limit);
        if from_top { 
            self.walls_h[0][door] = false;
            self.walls_h[HEIGHT][exit] = false;
        } else {
            self.walls_v[door][0] = false;
            self.walls_v[exit][WIDTH] = false;
        }
    }
 
    ///Removes a wall between the two Cell arguments
    fn remove_wall(&mut self, cell1: &Cell, cell2: &Cell) {
        if cell1.row == cell2.row {
            self.walls_v[cell1.row][if cell1.col > cell2.col { cell1.col } else { cell2.col }] = false;
        } else { 
            self.walls_h[if cell1.row > cell2.row { cell1.row } else { cell2.row }][cell1.col] = false;
        };
    }
 
    ///Returns a random non-visited neighbor of the Cell passed as argument
    fn neighbor(&mut self, cell: &Cell) -> Option<Cell> {
        self.cells[cell.col][cell.row] = false;
        let mut neighbors = Vec::new();
        if cell.col > 0 && self.cells[cell.col - 1][cell.row] { neighbors.push(Cell::from(cell.col - 1, cell.row)); }
        if cell.row > 0 && self.cells[cell.col][cell.row - 1] { neighbors.push(Cell::from(cell.col, cell.row - 1)); }
        if cell.col < WIDTH - 1 && self.cells[cell.col + 1][cell.row] { neighbors.push(Cell::from(cell.col + 1, cell.row)); }
        if cell.row < HEIGHT - 1 && self.cells[cell.col][cell.row + 1] { neighbors.push(Cell::from(cell.col, cell.row + 1)); }
        if neighbors.is_empty() {
            None
        } else {
            let next = neighbors.get(self.thread_rng.gen_range(0, neighbors.len())).unwrap();
            self.remove_wall(cell, next);
            Some(*next)
        }
    }
 
    ///Builds the maze (runs the Depth-first search algorithm)
    fn build(&mut self) {
        let mut cell_stack: Vec<Cell> = Vec::new();
        let mut next = self.first();
        loop {
            while let Some(cell) = self.neighbor(&next) {
                cell_stack.push(cell);
                next = cell;
            }
            match cell_stack.pop() {
                Some(cell) => next = cell,
                None => break,
            }
        }
    }
 
    ///Displays a wall
    fn paint_wall(h_wall: bool, active: bool) {
        if h_wall {
            print!("{}", if active { "+---" } else { "+   " });
        } else {
            print!("{}", if active { "|   " } else { "    " });
        }
    }
 
    ///Displays a final wall for a row
    fn paint_close_wall(h_wall: bool) {
        if h_wall { println!("+") } else { println!() }
    }
 
    ///Displays a whole row of walls
    fn paint_row(&self, h_walls: bool, index: usize) {
        let iter = if h_walls { self.walls_h[index].iter() } else { self.walls_v[index].iter() };
        for &wall in iter {
            Maze::paint_wall(h_walls, wall);
        }
        Maze::paint_close_wall(h_walls);
    } 
 
    ///Paints the maze
    fn paint(&self) {
        for i in 0 .. HEIGHT {
            self.paint_row(true, i);
            self.paint_row(false, i);
        }
        self.paint_row(true, HEIGHT);
    }
}
 
fn main() {
    let mut maze = Maze::new();
    maze.build();
    maze.open_doors();
    maze.paint();
}