Recursive Backtracking - Rust

recursive-backtracking.rs

/*
 * recursive backtracking translated from the ruby at
 * http://weblog.jamisbuck.org/2010/12/27/maze-generation-recursive-backtracking
 */

use std::io::stdio::print;
use std::io::stdio::println;

// Height and width, change these for a different maze size
// (sorry, it's not a command line argument, as that would
//  greatly increase complexity)
static width: uint = 20; 
static height: uint = 20;

enum Direction {
    N = 1,
    S = 2,
    E = 4,
    W = 8,
}

impl Direction {
    fn opposite(self) -> Direction {
        match self {
            N => S,
            S => N,
            E => W,
            W => E,
        }
    }
}


struct Grid([[uint, ..width], ..height]);

impl Grid {
    // Create a new grid filled with zeros
    fn new() -> Grid {
        Grid([[0, ..width], ..height])
    }

    // Gets a mutable reference to a sepcific value in the grid
    fn get_mut<'a>(&'a mut self, loc: (uint, uint)) -> &'a mut uint {
        let &Grid(ref mut inner) = self;
        &mut inner[loc.y()][loc.x()]
    }

    // Show the bit field grid
    #[allow(dead_code)]
    fn show(&self) {
        let &Grid(ref inner) = self;
        for row in inner.iter() {
            for col in row.iter() {
                print!("{:3u}", *col);
            }
            print("\n");
        }
    }

    // Show the maze itself
    fn show_fancy(&self) {
        // Render top
        let mut top = String::from_char(1, ' ');
        top.grow(width * 2 - 1, '_');
        println(top.as_slice());

        // Render inside
        for y in range(0u, height) {
            print("|");
            for x in range(0u, width) {
                print(if self[(x, y)] & (S as uint) != 0 { " " } else { "_" });
                if self[(x, y)] & (E as uint) != 0 {
                    print(if (self[(x, y)] | self[(x + 1, y)]) & (S as uint) != 0 { " " } else { "_" })
                } else {
                    print("|");
                }
            }
            println("");
        }
    }
}

impl Index<(uint, uint), uint> for Grid {
    // Easy indexing of grid, so we don't have to extract the inner during access
    fn index(&self, loc: &(uint, uint)) -> uint {
        let &Grid(inner) = self;
        inner[(*loc).y()][(*loc).x()]
    }
}


trait Location {
    fn x(&self) -> uint;
    fn y(&self) -> uint;

    // Checks whether the location is actually in the grid
    fn in_grid(&self) -> bool {
        self.x() < width && self.y() < height
    }
}

impl Location for (uint, uint) {
    #[inline]
    fn x(&self) -> uint {
        let (x, _) = *self;
        x
    }

    #[inline]
    fn y(&self) -> uint {
        let (_, y) = *self;
        y
    }
}

// Get coordinates for the new location
fn movdir(cloc: (uint, uint), dir: Direction) -> (uint, uint) {
    let nx = match dir {
        E => 1,
        W => -1,
        _ => 0,
    } + cloc.x();
    let ny = match dir {
        N => -1,
        S => 1,
        _ => 0,
    } + cloc.y();

    (nx, ny)
}

// See article - http://weblog.jamisbuck.org/2010/12/27/maze-generation-recursive-backtracking
fn carve_passages_from(cloc: (uint, uint), grid: &mut Grid) {
    use std::rand::{task_rng, Rng};

    let mut rng = task_rng();
    let mut dirs = [N, S, E, W];
    rng.shuffle(dirs);

    for direction in dirs.iter() {
        let nloc = movdir(cloc, *direction);
        if nloc.in_grid() && grid[nloc] == 0 {
            *grid.get_mut(cloc) |= *direction as uint;
            *grid.get_mut(nloc) |= direction.opposite() as uint;
            carve_passages_from(nloc, grid);
        }
    }
}

fn main() {
    println!("Generating Maze: {} x {}", width, height);
    let mut grid = Grid::new();
    carve_passages_from((0, 0), &mut grid);
    grid.show_fancy();
    // grid.show();
}