138 lines
4.4 KiB
Plaintext
138 lines
4.4 KiB
Plaintext
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();
|
|
}
|