Yep

Maze making in Rust (part 3)

Intro

Last time I posted, I had just finished the first iteration of the maze Celltype. The code has taken a big leap forward since then. We now have:

This is in a large part due to various wonderful recursers sharing their thoughts and time with me. (Particular shout out to Kevan Hollbach, Enric Calabuig for stellar pairing sessions on these parts of the code).

Contents

So, how did we get from there to here?

On writing this up, I found the different iterations roughly aligned with the 'make it work, make it right, make it fast' aphorism:

There (make it work, sort of) :

To (make it right, or at least better) :

Here (make it fast, or at least faster) :

If you’re interested in seeing what the code looks like now then do jump straight to the end!

Otherwise, we’ll start at the first stage with a quick re-cap of Cell’s first iteration and then move on through all the other changes step-by-step.

There (make it work, sort of)

Previously, I had sketched a building block of the maze, called Cell.

Cell had fields for:

Here’s the code as it was:

pub struct Cell {
    row: u8,
    column: u8,
    north: Option<Box<Cell>>,
    east: Option<Box<Cell>>,
    south: Option<Box<Cell>>,
    west: Option<Box<Cell>>,
    links: HashMap<Box<Cell>, bool>
}

This allowed me to add a Cell to another’s links fields. You can see from my previous post here that it took me a little while to implement because I wasn't used to handling recursive data types.

Shortcomings of this design

This design worked for a toy-test with one cell being linked to others (and therefore ‘owning’ them) and no bi-directional links (i.e. two cells with one other in their links fields). However, as soon as I needed a grid full of cells bi-directionally linked to one another, this structure was no longer fit for purpose.

In Ruby, the language used in Jamis Buick’s Mazes for Programmers examples, this data structure would have been fine, as Ruby is more permissive than Rust.

However, Rust’s ownership requirements mean that this sort of design makes it difficult (impossible?) for multiple cells holding Box<Cell> of each other in their links field. This is because you can’t have multiple owners with read-write access to variables without using something like the interior mutability pattern of Rc<RefCell<T>>. (Or at least that’s my understanding).

So, I needed a different way of letting cells know that they were linked to one another. But, I wasn’t ready for the interior mutability pattern just yet…

To (make it right, or at least better)

Instead of implementing interior mutability I went for updating the datatype for the links field to hold a linked cell’s location, rather than a reference to the cell itself. So links has gone from HashMap<Box<Cell>, bool> to a vector of locations, Vec<Location>. This solved the circular ownership problem, allowing multiple cells to have bi-directional links to other cells, because it was easy make copies or references of Location instances.

Code for updated Cell and new Location types:

#[derive(Eq, PartialEq, Debug, Default)]
pub struct Cell {
    row: usize,
    column: usize,
    north: Option<Location>,
    east: Option<Location>,
    south: Option<Location>,
    west: Option<Location>,
    links: Vec<Location>, //<- this used to be HashMap<Box<Cell>, bool>
}
//instead we store locations of linked cells, rather than a reference to the cell itself
#[derive(Debug, Eq, PartialEq)]
pub struct Location {
    row: usize,
    column: usize,
}

A grid to contain all cells

With the updated Cell came a brand new container for the maze cells, called Grid . This had the below behaviour and properties:

Grid properties:

struct Grid {
    rows: usize,
    columns: usize,
    cells: Vec<Vec<Cell>>,
}

Grid behaviour:

impl Grid {
    pub fn prepare_grid(&mut self) -> Vec<Vec<Cell>> {
        let mut cells: Vec<Vec<Cell>> = Vec::new();

        for r in 0..self.rows {
            let mut row: Vec<Cell> = Vec::new();

            for c in 0..self.columns {
                row.push(Cell::empty(r, c));
            }

            cells.push(row)
        }
        cells
    }

    pub fn get_neighbour(
        rows: &i32,
        columns: &i32,
        current_location: &Location,
        direction: &str,
    ) -> Option<Location> {
        let row_range = 0..*rows;
        let col_range = 0..*columns;
        let current_row = current_location.row as i32;
        let current_column = current_location.column as i32;

        match direction {
            "north" => {
                if row_range.contains(&(current_row - 1)) {
                    Some(Location {
                        row: current_location.row - 1,
                        column: current_location.column,
                    })
                } else {
                    None
                }
            }
            "east" => {
                if col_range.contains(&(current_column + 1)) {
                    Some(Location {
                        row: current_location.row,
                        column: current_location.column + 1,
                    })
                } else {
                    None
                }
            }
            "south" => {
                if row_range.contains(&(current_row + 1)) {
                    Some(Location {
                        row: current_location.row + 1,
                        column: current_location.column,
                    })
                } else {
                    None
                }
            }
            "west" => {
                if row_range.contains(&(current_column - 1)) {
                    Some(Location {
                        row: current_location.row,
                        column: current_location.column - 1,
                    })
                } else {
                    None
                }
            }

            _ => None,
        }
    }

    pub fn configure_cells(&mut self) {
        for row in self.cells.iter_mut() {
            for cell in row.iter_mut() {
                let location = Location {
                    row: cell.row,
                    column: cell.column,
                };
                let rows = *&self.rows as i32;
                let columns = *&self.columns as i32;

                cell.north = Grid::get_neighbour(&rows, &columns, &location, "north");
                cell.east = Grid::get_neighbour(&rows, &columns, &location, "east");
                cell.south = Grid::get_neighbour(&rows, &columns, &location, "south");
                cell.west = Grid::get_neighbour(&rows, &columns, &location, "west");
            }
        }
    }
}

(I’m aware that I’m probably not using impl correctly, looking into the proper pattern for this on my to-do )

Now we’ve seen the updated Cell and the new Grid type, let’s look at the first maze making algorithm I implemented, binary tree.

Binary Tree algorithm to create a maze (two loops)

For anyone not familiar with the binary tree algorithm, the steps it takes are as follows:

  1. Visit each cell in the grid once
  2. Update each cell’s links field by applying the below rules in sequence:
    1. For the cell on the north-eastern corner, don’t link north or east
    2. For cells on the northern (zeroth) row, always link to the east
    3. For cells on the eastern column, always link to the north
    4. For every other cell, randomly choose whether to link to the north or east

When links are ‘bi-directional’, if cell a is visited and it’s linked to cell b, then cell b is aware of the link as well. But, just because cell b has had a link declared to it, does not mean it’s been ‘visited’. Cell b will still need to be visited later on if it hasn't been visited already. At this point, cell b’s links field will be extended, so it has the original link to cell a, and also the new one declared when visiting itself. (Unless it’s the north eastern corner, in which case it only receives links from other cells, when we visit the north eastern corner we do not add anything to its links field.)

Implementing Binary Tree

Onto the implementation, and why the current version of Cell meant implementing the algorithm required two loops.

What I wanted to do when implementing the binary tree algorithm was this:

  1. Visit each cell one-by-one
  2. Randomly choose to carve north or east according to the algorithm
  3. Update the currently visited cell’s links field (we’ll call this the source cell) with the newly linked cell’s Location (we’ll call this the target cell)
  4. Then, update the target cell’s links field to contain the source cell’s Location

Buuuuut, I couldn’t do step 4. Instead I had to use a two step process. One step where I set all of the source cell’s links, and a second step where I update the target cell’s links:

  1. Visit each cell one-by-one
  2. Randomly choose to carve north or east according to the algorithm
  3. Update the visited (source) cell’s links field with the newly linked (target) cell’s Location
  4. Instead of updating target cell’s links field now, I instead collect this link in the all_links vector using a new Link datatype (see definition below). all_links collects source and target Locations for all the cells’ links that were created during the initial loop, so we can inform the target cells of who they've been linked to.
  5. After iterating over every cell:
    1. Iterate over the vector of Links
    2. Get cells at the Location from the target field
    3. Update these target cells’ links field to contain the Location from the source field

Link datatype:

pub struct Link {
    pub source: Location,
    pub target: Location,
}

Why did it take two loops when one is preferable? This was because I could only mutate the current (source) cell’s links field (via iter_mut() ). But I couldn’t mutate the target cell in the same block because I had no way of owning it. I’m still a bit fuzzy on why this was the case, is it because anything outside of what iter_mut() is currently providing is still owned by Grid? Not sure.

Binary Tree implementation

Here’s what the (rough and ready) Binary Tree implementation looked like with the two loop process:

fn binary_tree(mut grid: Grid) -> Grid {
    let mut all_links: Vec<Link> = vec![]; //collects all links generated during loop over over all cells

    for row in grid.cells.iter_mut() {
        for cell in row.iter_mut() {
            let is_northmost_cell = cell.north.is_none();
            let is_eastmost_cell = cell.east.is_none();
            let is_north_eastern_cell = is_northmost_cell & is_eastmost_cell;

            if is_north_eastern_cell {
                break;
            } else if is_northmost_cell {
                let eastern_location = cell.east.unwrap();
                cell.links.push(eastern_location);
                all_links.push(Link { source: cell.location, target: eastern_location });

            } else if is_eastmost_cell {
                let northern_location = cell.north.unwrap();
                cell.links.push(northern_location);
                all_links.push(Link {source: cell.location, target: northern_location});
            } else {
                let linked_neighbour =
                    binary_tree_random_neighbour(cell.east.unwrap(), cell.north.unwrap());

                cell.links.push(linked_neighbour);
                all_links.push(Link {source: cell.location, target: linked_neighbour});

            }
        }
    }
    for link in all_links.iter() { // second loop, now going over all links
        let Link {source, target} = link;

        let target_cell = grid.cells.index_mut(target.row).index_mut(target.column);
        target_cell.links.push(*source); //updating every target cell so they know what source cell they've been linked to
    }
    grid
}

We'll go over how this was improved in the final section.

Display function to display a maze

It’s all very well having mazes, cells and maze making algorithms. But without the ability to see a maze, it’s a bit theoretical. Enter: display_maze() This was relatively straightforward to implement using the example in Mazes for Programmers, so I don’t have much to say here compared to the previous sections.

The only outstanding question I can see is whether I’m concatenating and formatting strings in a sensible way. There was a lot of hack-and-hoping involved…

display_maze() Code

impl Grid {
...
pub fn display_maze(self) {
        let start = String::from("+");
        let middle = String::from("---+".repeat(self.columns));
        let end = String::from("\n");
        let mut output = format!("{}{}{}", start, middle, end);

        for row in self.cells.iter() {
            let mut top = String::from("|");
            let mut bottom =  String::from("+");

            for cell in row.iter() {
                let body = "   ";
                let east_boundary = if Cell::is_linked(&cell, "east") {
                    " "
                } else {
                    "|"
                };
                top.push_str((body.to_owned() + east_boundary).as_str());

                let south_boundary = if Cell::is_linked(&cell, "south") {
                    "   "
                } else {
                    "---"
                };
                let corner = "+";
                bottom.push_str((south_boundary.to_owned() + corner).as_str());
            }
            output.push_str((top.to_owned() + "\n").as_str());
            output.push_str((bottom.to_owned() + "\n").as_str());
        }

        println!("{}", output);
    }
...
}

This gives us ASCII mazes in the terminal, like the Binary Tree maze below: A big binary tree maze on the terminal

Here (make it fast, or at least faster)

And now, finally, we’re in the here and now! The current code brings the below improvements and features:

A smart grid to contain all cells

When first pairing with Kevan on the earlier version of Grid, he mentioned that we may want to explore the Rc<RefCell<T>> interior mutability pattern. But I kicked this can down the road because two loops for Binary Tree wasn’t too bad and also (mostly) I was scared of Rc and RefCell.

However when I came to implement the sidewinder algorithm, the all_links vector looked like it was going to bring even more implementation complications. What I really needed was to be able to update multiple cells in a single iteration of a loop. So I admitted that it was time to pick up that particular can-that-had-been-kicked and dig into the interior mutability pattern…

Here's what the new implementation looks like:

SmartGrid properties

#[derive(Debug)]
pub struct SmartGrid {
    pub rows: usize,
    pub columns: usize,
    pub cells: Vec<Vec<Rc<RefCell<MazeCell>>>>, // this used to be Vec<Vec<Cell>>
}

SmartGrid behaviours

impl SmartGrid {
    pub fn prepare_grid(&mut self) -> Vec<Vec<Rc<RefCell<MazeCell>>>> {
        let mut cells = Vec::new();

        for r in 0..self.rows {
            let mut row: Vec<Rc<RefCell<MazeCell>>> = Vec::new();

            for c in 0..self.columns {
                row.push(Rc::new(RefCell::new(MazeCell::empty(r, c))));
            }

            cells.push(row)
        }
        cells
    }

    pub fn get_neighbour(
        rows: &i32,
        columns: &i32,
        current_location: &Location,
        direction: Direction,
    ) -> Option<Location> {
        let row_range = 0..*rows;
        let col_range = 0..*columns;
        let current_row = current_location.row as i32;
        let current_column = current_location.column as i32;

        match direction {
            Direction::North => {
                if row_range.contains(&(current_row - 1)) {
                    Some(Location {
                        row: current_location.row - 1,
                        column: current_location.column,
                    })
                } else {
                    None
                }
            }
            Direction::East => {
                if col_range.contains(&(current_column + 1)) {
                    Some(Location {
                        row: current_location.row,
                        column: current_location.column + 1,
                    })
                } else {
                    None
                }
            }
            Direction::South => {
                if row_range.contains(&(current_row + 1)) {
                    Some(Location {
                        row: current_location.row + 1,
                        column: current_location.column,
                    })
                } else {
                    None
                }
            }
            Direction::West => {
                if row_range.contains(&(current_column - 1)) {
                    Some(Location {
                        row: current_location.row,
                        column: current_location.column - 1,
                    })
                } else {
                    None
                }
            }
        }
    }
    pub fn link_cells(
        &self,
        mut source: RefMut<MazeCell>,
        target: Location,
        is_bidirectional: bool,
    ) {
        if is_bidirectional {
            source.links.push(target);
            let mut target_cell = self.cells[target.row][target.column].borrow_mut();
            target_cell.links.push(source.location);
        } else {
            source.links.push(target);
        }
    }

    pub fn configure_cells(&self) {
        for row in self.cells.iter() {
            for cell in row.iter() {
                let rows = *&self.rows as i32;
                let columns = *&self.columns as i32;
                let mut cell = cell.borrow_mut();
                cell.north =
                    SmartGrid::get_neighbour(&rows, &columns, &cell.location, Direction::North);
                cell.east =
                    SmartGrid::get_neighbour(&rows, &columns, &cell.location, Direction::East);
                cell.south =
                    SmartGrid::get_neighbour(&rows, &columns, &cell.location, Direction::South);
                cell.west =
                    SmartGrid::get_neighbour(&rows, &columns, &cell.location, Direction::West);
            }
        }
    }
}

To expand on these in specific relation to their use in SmartGrid, (with my shaky understanding) :

Binary tree algorithm refactored to one loop

With the interior mutability pattern we can now refactor the binary tree algorithm to use one less loop:

pub fn binary_tree(grid: SmartGrid) -> SmartGrid {
	 // no more collecting all links up here..
    for row in &grid.cells {
        for cell in row {
            let cell = cell.borrow_mut();
            let is_northmost_cell = cell.north.is_none();
            let is_eastmost_cell = cell.east.is_none();
            let is_north_eastern_cell = is_northmost_cell & is_eastmost_cell;


            if is_north_eastern_cell {
                break;
            } else if is_northmost_cell {
                let eastern_location = cell.east.unwrap();
                SmartGrid::link_cells(&grid, cell, eastern_location, BIDI);
            } else if is_eastmost_cell {
            //... because we can update both source and target cells with link_cells()
                let northern_location = cell.north.unwrap();
                SmartGrid::link_cells(&grid, cell, northern_location, BIDI);
            } else {
                let linked_neighbour =
                    binary_tree_random_neighbour(cell.east.unwrap(), cell.north.unwrap());
                SmartGrid::link_cells(&grid, cell, linked_neighbour, BIDI);
            }
        }
    }
	  //... so no need to have to iterate over collected links down here anymore
    grid
}

We no longer need to collect the outbound links and iterate over them later, instead we call link_cells (which has been moved into SmartGrid as it made more sense for the ‘parent’ of maze cells to update cells’ internal state rather than cells updating other cells’ internal state) once and that updates both the source and target cells’ links field with the relevant locations. Great!

Sidewinder algorithm

Now onto the Sidewinder Algorithm, which should be made simpler by the new SmartGrid.

While Sidewinder is still simple, it's a lot, probably too much, to hold in your head. It’s much easier to understand when you can see the maze evolving step-by-step, so I recommend heading over to Jamis Buck’s article on the Sidewinder algorithm where you can see just that.

For completeness, I'll put the steps below anyway:

  1. Visit each cell in the grid once
  2. Update each cell’s links field by applying the below rules in sequence:
    1. For the cell on the north-eastern corner, don’t link north or east
    2. For cells on the northern (zeroth) row, link to the east
    3. For every other cell, add it to a ‘run’ and follow the below steps:
      1. Randomly choose whether to be linked to north or east
      2. If east, continue visiting other cells
      3. If north, look back on visited cells from this run (inclusive of the current cell) and randomly pick a cell that should link north
        1. NB: If the run contains only one cell, and that cell is on the eastern border, always link that cell to the north
      4. Empty the collected run, move onto the next cell and add that to a new run

Sidewinder algorithm code implementation

const BIDI: bool = true;

pub fn side_winder(grid: SmartGrid) -> SmartGrid {
    for row in &grid.cells {
        let mut run: Vec<Location> = Vec::new();

        for cell in row {
            let cell = cell.borrow_mut();
            let is_northmost_cell = cell.north.is_none();
            let is_eastmost_cell = cell.east.is_none();
            let zero_or_one = rand::thread_rng().gen_range(0..=1);
            let should_close_run = is_eastmost_cell || (!is_northmost_cell & (zero_or_one == 0));

            run.push(cell.location.clone());

            if should_close_run {
                let member_location = run.choose(&mut rand::thread_rng()).unwrap();
                let member_cell;
                if member_location == &cell.location {
                    member_cell = cell;
                } else {
                    member_cell =
                        grid.cells[member_location.row][member_location.column].borrow_mut();
                }

                if !is_northmost_cell {
                    let northern_location = member_cell.north.unwrap();
                    SmartGrid::link_cells(&grid, member_cell, northern_location, BIDI);
                    run.clear();
                }
            } else {
                let eastern_location = cell.east.unwrap();
                SmartGrid::link_cells(&grid, cell, eastern_location, BIDI);
            }
        }
    }
    grid
}

And that's it for the mammoth update! Since this post there have been a few new developments, namely implementing Dijkstra's solver and the ability to display the Mazes in a rust creative programming framework called Nannou. But I'll leave this for future posts as this one is way too long already 🙈