Faster maze generator

maze_generator.rs

//! A faster rewrite of `maze_generator.py` in Rust.
//!
//! The Python version generated a 100x200 maze in about thirty seconds.
//! This version generated a 1000x1000 maze in about five seconds.

extern crate rand;
extern crate itertools;
extern crate integer_sqrt;

use rand::Rng;
use itertools::Itertools;
use integer_sqrt::IntegerSquareRoot;
use std::ops::Add;
use std::fmt;

#[derive(Copy, Clone, PartialEq, Eq)]
enum Tile {
    Wall,
    Gap,
}

#[derive(Copy, Clone, PartialEq, Eq)]
enum Direction {
    Up,
    Right,
    Down,
    Left,
}

const DIRECTIONS: [Direction; 4] = [
    Direction::Up,
    Direction::Right,
    Direction::Down,
    Direction::Left,
];

#[derive(Copy, Clone, PartialEq, Eq)]
enum Moore {
    Up,
    UpRight,
    Right,
    DownRight,
    Down,
    DownLeft,
    Left,
    UpLeft
}

const MOORE: [Moore; 8] = [
    Moore::Up,
    Moore::UpRight,
    Moore::Right,
    Moore::DownRight,
    Moore::Down,
    Moore::DownLeft,
    Moore::Left,
    Moore::UpLeft,
];

#[derive(Copy, Clone, PartialEq, Eq, Debug)]
struct Point(isize, isize);

struct Maze {
    width: usize,
    height: usize,
    data: Vec<Tile>,
}

/// Return a random point with `x` between 0 and `width` and `y` between 0 and
/// `height`.
fn random_point<R: Rng>(rand: &mut R, width: usize, height: usize) -> Point {
    Point(rand.gen_range(0, width) as isize,
          rand.gen_range(0, height) as isize)
}

/// Return a random number between 0 and `r`, with a bias towards `r`.
fn favored_random<R: Rng>(rand: &mut R, r: usize) -> usize {
    //rand.gen_range(0, r * r).integer_sqrt()
    rand.gen_range(0, r)
}

impl fmt::Display for Tile {
    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
        write!(fmt, "{}", match self {
            Tile::Wall => '.',
            Tile::Gap => '@',
        })
    }
}

impl Direction {
    /// Return the opposite direction.
    fn reverse(self) -> Direction {
        use Direction::*;
        match self {
            Up    => Down,
            Right => Left,
            Down  => Up,
            Left  => Right
        }
    }
    /// Return Moore directions near this.
    fn region(self) -> [Moore; 3] {
        use Moore::*;
        use Direction as D;
        match self {
            D::Up    => [UpLeft, Up, UpRight],
            D::Right => [UpRight, Right, DownRight],
            D::Down  => [DownRight, Down, DownLeft],
            D::Left  => [DownLeft, Left, UpLeft],
        }
    }
    /// Convert this direction to a point offset.
    fn to_point(self) -> Point {
        use Direction::*;
        match self {
            Up    => Point(0, 1),
            Right => Point(1, 0),
            Down  => Point(0, -1),
            Left  => Point(-1, 0),
        }
    }
}

impl Moore {
    fn to_point(self) -> Point {
        use Moore::*;
        match self {
            Up        => Point(0, 1),
            UpRight   => Point(1, 1),
            Right     => Point(1, 0),
            DownRight => Point(1, -1),
            Down      => Point(0, -1),
            DownLeft  => Point(-1, -1),
            Left      => Point(-1, 0),
            UpLeft    => Point(-1, 1),
        }
    }
}

impl Add for Point {
    type Output = Self;
    fn add(self, other: Self) -> Self {
        Point(self.0 + other.0, self.1 + other.1)
    }
}

impl Add<Direction> for Point {
    type Output = Self;
    fn add(self, other: Direction) -> Self {
        self + other.to_point()
    }
}

impl Add<Moore> for Point {
    type Output = Self;
    fn add(self, other: Moore) -> Self {
        self + other.to_point()
    }
}

impl Maze {
    /// Create a maze full of `Wall`s with the given dimensions.
    fn blank(width: usize, height: usize) -> Self {
        Maze {
            width,
            height,
            data: vec![Tile::Wall; width * height]
        }
    }
    fn valid_index(&self, x: isize, y: isize) -> bool {
           0 <= x && x < (self.width as isize)
        && 0 <= y && y < (self.height as isize)
    }
    /// Turn a point index into an index in the flat tile vector. Return `None`
    /// if the index is out of bounds.
    fn translate_index(&self, index: Point) -> Option<usize> {
        let Point(x, y) = index;
        if self.valid_index(x, y) {
            Some((x as usize) + (y as usize) * self.width)
        } else {
            None
        }
    }
    /// Return the tile at a given point.
    fn get(&self, index: Point) -> Option<Tile> {
        self.translate_index(index)
            .map(|idx| self.data[idx])
    }
    /// Return a mutable reference to the tile at a given point.
    fn get_mut(&mut self, index: Point) -> Option<&mut Tile> {
        self.translate_index(index)
            .map(move |idx| &mut self.data[idx])
    }
    /// Count how many Moore neighbors of `point` are gaps, excluding those in
    /// the excluded `Direction`.
    fn count_gap_neighbors(&self, point: Point, exclude: Direction) -> Option<usize> {
        let excluded = exclude.region();
        if self.valid_index(point.0, point.1) {
            Some(MOORE.iter()
                .filter(|d| !excluded.contains(d))
                .filter_map(|d| self.get(point + *d)
                .filter(|d| *d == Tile::Gap))
                .count())
        } else {
            None
        }
    }
    fn random<R: Rng>(rng: &mut R, width: usize, height: usize) -> Self {
        let mut maze = Maze::blank(width, height);
        let mut points = {
            let start_point = random_point(rng, width, height);
            *maze.get_mut(start_point).unwrap() = Tile::Gap;
            vec![start_point]
        };
        while !points.is_empty() {
            let point_index = favored_random(rng, points.len());
            let point = points[point_index];
            let mut any_valid_directions = false;
            // Shuffle the list of directions before iterating over them
            // to make sure there isn't any bias to the order they are
            // added.
            let mut directions = DIRECTIONS;
            rng.shuffle(&mut directions);
            for dir in directions.iter() {
                let neighbor = point + *dir;
                if points.contains(&neighbor) { continue; }
                if let Some(0) = maze.count_gap_neighbors(neighbor, dir.reverse()) {}
                else { continue; }
                any_valid_directions = true;
                *maze.get_mut(neighbor).unwrap() = Tile::Gap;
                points.push(neighbor);
            }
            if !any_valid_directions {
                points.remove(point_index);
            }
        }
        maze
    }
}

impl fmt::Display for Maze {
    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
        for line in self.data.iter().chunks(self.width).into_iter() {
            for tile in line {
                write!(fmt, "{}", tile)?;
            }
            write!(fmt, "\n")?;
        }
        Ok(())
    }
}

fn main() {
    let mut args = std::env::args();
    let _name = args.next();
    let width = args.next().unwrap().parse().unwrap();
    let height = args.next().unwrap().parse().unwrap();
    println!("{}", Maze::random(&mut rand::thread_rng(), width, height));
}