Generation Algorithms (Part I) from "Mazes for Programmers"

main.rs

use rand_0_9_2::{prelude::*, rng};
use std::collections::{HashMap, HashSet};
use std::hash::Hash;

const WIDTH: usize = 40;
const HEIGHT: usize = 15;
const SCALE: usize = 2;

const ISOLATED_COLUMN: char = '■';
const VERTICAL_WALL: char = '│';
const HORIZONTAL_WALL: char = '─';
const WALL_CORNER_SE: char = '┌';
const WALL_CORNER_NE: char = '└';
const WALL_CORNER_SW: char = '┐';
const WALL_CORNER_NW: char = '┘';
const WALL_JUNCTION_E: char = '├';
const WALL_JUNCTION_W: char = '┤';
const WALL_JUNCTION_N: char = '┴';
const WALL_JUNCTION_S: char = '┬';
const WALL_CROSS: char = '┼';

fn main() {
    showcase("Binary Tree", binary_tree);
    showcase("Sidewinder", sidewinder);
    showcase("Aldous-Broder", aldous_broder);
    showcase("Wilson's", wilsons);
    showcase("Hunt & Kill", hunt_and_kill);
    showcase(
        "Recursive Backtracker (explicit stack)",
        recursive_backtracker,
    );
    showcase(
        "Recursive Backtracker (implicit stack)",
        recursive_backtracker2,
    );
}

pub fn binary_tree(grid: &mut Grid<Pos>) {
    let rng = &mut rng();

    for p in grid.each_cell() {
        let mut neighbors = vec![];
        if grid.contains(p.north()) {
            neighbors.push(p.north())
        }
        if grid.contains(p.east()) {
            neighbors.push(p.east())
        }

        if let Some(neighbor) = neighbors.choose(rng) {
            grid.link(p, *neighbor);
        }
    }
}

pub fn sidewinder(grid: &mut Grid<Pos>) {
    let rng = &mut rng();

    let mut run = vec![];
    for row in grid.each_row() {
        run.clear();

        for p in row {
            run.push(p);

            let at_eastern_boundary = !grid.contains(p.east());
            let at_northern_boundary = !grid.contains(p.north());

            let should_close_out =
                at_eastern_boundary || (!at_northern_boundary && rng.random_bool(0.5));

            if should_close_out {
                let member = *run.choose(rng).unwrap();
                if grid.contains(member.north()) {
                    grid.link(member, member.north());
                }
                run.clear();
            } else {
                grid.link(p, p.east());
            }
        }
    }
}

pub fn aldous_broder(grid: &mut Grid<Pos>) {
    let mut rng = rng();

    let mut cell = grid.random_cell(&mut rng);
    let mut unvisited = grid.size() - 1;

    while unvisited > 0 {
        let neighbor = grid.neighbors(cell).choose(&mut rng).unwrap();

        if grid.links(neighbor).is_empty() {
            grid.link(cell, neighbor);
            unvisited -= 1;
        }

        cell = neighbor;
    }
}

pub fn wilsons(grid: &mut Grid<Pos>) {
    let mut rng = rng();

    let mut unvisited: Vec<_> = grid.each_cell().collect();

    let idx = rng.random_range(0..unvisited.len());
    let first = unvisited.swap_remove(idx);

    while !unvisited.is_empty() {
        let mut cell = *unvisited.choose(&mut rng).unwrap();
        let mut path = vec![cell];

        while unvisited.contains(&cell) {
            cell = grid.neighbors(cell).choose(&mut rng).unwrap();
            if let Some(pos) = path.iter().position(|&p| p == cell) {
                path.truncate(pos);
            } else {
                path.push(cell);
            }
        }

        for i in 1..path.len() {
            grid.link(path[i], path[i - 1]);
            let idx = unvisited.iter().position(|&p| p == path[i - 1]).unwrap();
            unvisited.swap_remove(idx);
        }
    }
}

pub fn hunt_and_kill(grid: &mut Grid<Pos>) {
    let mut rng = rng();

    let mut current = Some(grid.random_cell(&mut rng));

    while let Some(cur) = current {
        if let Some(neighbor) = grid.unlinked_neighbors(cur).choose(&mut rng) {
            grid.link(cur, neighbor);
            current = Some(neighbor);
        } else {
            current = None;

            for cell in grid.each_cell() {
                if grid.unlinked(cell) {
                    if let Some(neighbor) = grid
                        .neighbors(cell)
                        .filter(|&n| !grid.unlinked(n))
                        .choose(&mut rng)
                    {
                        current = Some(cell);
                        grid.link(cell, neighbor);
                        break;
                    }
                }
            }
        }
    }
}

pub fn recursive_backtracker(grid: &mut Grid<Pos>) {
    let mut rng = rng();

    let start = grid.random_cell(&mut rng);
    let mut stack = vec![start];

    while !stack.is_empty() {
        let current = *stack.last().unwrap();
        if let Some(neighbor) = grid.unlinked_neighbors(current).choose(&mut rng) {
            grid.link(current, neighbor);
            stack.push(neighbor);
        } else {
            stack.pop();
        }
    }
}

pub fn recursive_backtracker2(grid: &mut Grid<Pos>) {
    let mut rng = rng();
    let start = grid.random_cell(&mut rng);
    recursive_backtracker2_recur(start, grid, &mut rng);
}

fn recursive_backtracker2_recur(current: Pos, grid: &mut Grid<Pos>, rng: &mut impl Rng) {
    let mut neighbors: Vec<_> = grid.unlinked_neighbors(current).collect();
    neighbors.shuffle(rng);

    for neighbor in neighbors {
        if grid.unlinked(neighbor) {
            grid.link(current, neighbor);
            recursive_backtracker2_recur(neighbor, grid, rng);
        }
    }
}

fn showcase<P: Copy + Eq + GridPos + Hash + Neighbors>(
    title: &str,
    make_maze: impl Fn(&mut Grid<P>),
) {
    let mut grid = Grid::<P>::new(HEIGHT, WIDTH);

    make_maze(&mut grid);

    let mut walls = Vec::new();
    let mut tiles = Vec::new();

    let n_cols = grid.draw(SCALE as u8, &mut walls);

    beautify(&walls, &mut tiles, n_cols);

    println!("{}", title);
    println!("Dead ends: {}", grid.deadends().count());
    render(&tiles, n_cols);
    println!();
}

fn beautify(walls: &[bool], tiles: &mut Vec<char>, columns: usize) {
    tiles.clear();
    for (i, w) in walls.iter().enumerate() {
        let x = i % columns;

        let ch = if *w {
            let lt = x > 0 && walls[i - 1];
            let rt = x < columns - 1 && walls[i + 1];
            let up = i >= columns && walls[i - columns];
            let dn = walls.get(i + columns).copied().unwrap_or(false);

            match (lt, rt, up, dn) {
                (false, false, false, false) => ISOLATED_COLUMN,
                (false, false, false, true) => VERTICAL_WALL,
                (false, false, true, false) => VERTICAL_WALL,
                (false, false, true, true) => VERTICAL_WALL,
                (false, true, false, false) => HORIZONTAL_WALL,
                (false, true, false, true) => WALL_CORNER_SE,
                (false, true, true, false) => WALL_CORNER_NE,
                (false, true, true, true) => WALL_JUNCTION_E,
                (true, false, false, false) => HORIZONTAL_WALL,
                (true, false, false, true) => WALL_CORNER_SW,
                (true, false, true, false) => WALL_CORNER_NW,
                (true, false, true, true) => WALL_JUNCTION_W,
                (true, true, false, false) => HORIZONTAL_WALL,
                (true, true, false, true) => WALL_JUNCTION_S,
                (true, true, true, false) => WALL_JUNCTION_N,
                (true, true, true, true) => WALL_CROSS,
            }
        } else {
            ' '
        };

        tiles.push(ch);
    }
}

fn render(tiles: &[char], columns: usize) {
    for (i, ch) in tiles.iter().enumerate() {
        print!("{}", ch);
        if (i + 1) % columns == 0 {
            println!()
        }
    }
}

type Pos = (isize, isize);

pub struct Grid<P> {
    rows: isize,
    columns: isize,
    links: HashMap<P, HashSet<P>>,
}

impl<P: Copy + Eq + GridPos + Hash + Neighbors> Grid<P> {
    pub fn new(rows: usize, columns: usize) -> Self {
        Grid {
            rows: rows as isize,
            columns: columns as isize,
            links: Default::default(),
        }
    }

    pub fn size(&self) -> usize {
        (self.rows * self.columns) as usize
    }

    pub fn contains(&self, p: P) -> bool {
        let (row, col) = p.to_tuple();
        row >= 0 && col >= 0 && row < self.rows && col < self.columns
    }

    pub fn each_cell(&self) -> impl Iterator<Item = P> + 'static {
        self.each_row().flatten()
    }

    pub fn each_row(&self) -> impl Iterator<Item = impl Iterator<Item = P>> + 'static {
        let rows = self.rows;
        let cols = self.columns;
        (0..rows).map(move |row| (0..cols).map(move |col| P::new2d(row, col)))
    }

    pub fn random_cell(&self, mut rng: impl Rng) -> P {
        let row = rng.random_range(0..self.rows as usize) as isize;
        let col = rng.random_range(0..self.columns as usize) as isize;
        P::new2d(row, col)
    }

    pub fn neighbors(&self, p: P) -> impl Iterator<Item = P> {
        [p.north(), p.south(), p.east(), p.west()]
            .into_iter()
            .filter(|nb| self.contains(*nb))
    }

    pub fn unlinked_neighbors(&self, p: P) -> impl Iterator<Item = P> {
        self.neighbors(p).filter(|&n| self.unlinked(n))
    }

    pub fn link(&mut self, a: P, b: P) {
        self.links.entry(a).or_insert(Default::default()).insert(b);
        self.links.entry(b).or_insert(Default::default()).insert(a);
    }

    pub fn unlink(&mut self, a: P, b: P) {
        if let Some(l) = self.links.get_mut(&a) {
            l.remove(&b);
        };
        if let Some(l) = self.links.get_mut(&b) {
            l.remove(&a);
        };
    }

    pub fn linked(&self, a: P, b: P) -> bool {
        self.links.get(&a).map(|l| l.contains(&b)).unwrap_or(false)
    }

    pub fn unlinked(&self, p: P) -> bool {
        self.n_links(p) == 0
    }

    pub fn n_links(&self, p: P) -> usize {
        self.links.get(&p).map(|l| l.len()).unwrap_or(0)
    }

    pub fn links(&mut self, p: P) -> &HashSet<P> {
        self.links.entry(p).or_insert(Default::default())
    }

    pub fn deadends(&self) -> impl Iterator<Item = P> {
        self.each_cell().filter(|&p| self.n_links(p) == 1)
    }

    pub fn draw(&self, scale: u8, buf: &mut Vec<bool>) -> usize {
        buf.clear();

        let n_columns = 1 + self.columns * scale as isize;

        for r in 0..1 + self.rows * scale as isize {
            let row = r / scale as isize;
            let y = r % scale as isize;
            for c in 0..n_columns {
                let col = c / scale as isize;
                let x = c % scale as isize;

                let p = P::new2d(row, col);

                if y == 0 {
                    if !self.linked(p, p.north()) {
                        buf.push(true);
                        continue;
                    }
                }

                if x == 0 {
                    if !self.linked(p, p.west()) {
                        buf.push(true);
                        continue;
                    }
                }

                if x == 0 && y == 0 {
                    buf.push(true);
                    continue;
                }

                buf.push(false);
            }
        }

        n_columns as usize
    }
}

pub trait GridPos {
    fn new2d(row: isize, col: isize) -> Self;
    fn to_tuple(self) -> (isize, isize);
}

impl GridPos for Pos {
    fn new2d(row: isize, col: isize) -> Self {
        (row, col)
    }

    fn to_tuple(self) -> (isize, isize) {
        self
    }
}

pub trait Neighbors {
    fn north(&self) -> Self;
    fn south(&self) -> Self;
    fn west(&self) -> Self;
    fn east(&self) -> Self;
}

impl Neighbors for Pos {
    fn north(&self) -> Self {
        (self.0 - 1, self.1)
    }

    fn south(&self) -> Self {
        (self.0 + 1, self.1)
    }

    fn west(&self) -> Self {
        (self.0, self.1 - 1)
    }

    fn east(&self) -> Self {
        (self.0, self.1 + 1)
    }
}