Let’s code it: A-Maze-ing

In our work sometimes is nice to experiment and today we will try to build a maze. This will be the partial animated result!

Note there are small graphical problems with the current implementation but we are interested in the maze algorithm code.

Building blocks

The cell

Firstly let’s define the smallest piece that composes a maze: a single cell. The cell needs to have the following properties:

1. Whether walls (top, right, bottom, left) are present or not in this cell;
2. Whether the cell is already visited.

#[derive(Clone, Debug)]
pub struct Cell {
    t: bool,
    r: bool,
    b: bool,
    l: bool,
    visited: bool,
}

impl Default for Cell {
    fn default() -> Self {
        Cell {
            t: true,
            r: true,
            b: true,
            l: true,
            visited: false,
        }
    }
}

The grid

Next, we need to define the base data structure we will use for the maze generation. Considering that in Rust there is not matrix built inside the language and the fact that a Vec of Vecs is not a very cache friendly idea (remember that inside the first Vec we could store only the reference to the inside Vecs) we want to build everything using a single array. From the image below you can see the logical and the memory representation that we will use:

To calculate the index of a single cell, some math can be applied. To move to the correct position, we need to multiply the y of our coordinates by the width of the grid (to get the row position) and add the x that represents the offset on the row.

Following the code for all the methods that we will use for the maze generation:

pub struct Grid<T: Clone> {
    data: Vec<T>,
    width: usize,
    height: usize,
}

impl<T> Grid<T>
where
    T: Clone,
{
    pub fn new(data: T, width: usize, height: usize) -> Self {
        Self {
            // Duplicates the defalt data value
            data: vec![data; width * height],
            width,
            height,
        }
    }

    /// Returns the value using the coordinates
    #[inline]
    pub fn get_value(&self, x: usize, y: usize) -> &T {
        &self.data[(x + y * self.width) as usize]
    }

    /// Returns the mutable value using the coordinates
    #[inline]
    pub fn get_value_with_index_mut(&mut self, index: usize) -> &mut T {
        &mut self.data[index as usize]
    }

    /// Returns the value of the cell above the current index
    #[inline]
    pub fn get_top_index(&self, index: usize) -> Option<(&T, usize)> {
        // The above cell is at the same column in the row above.
        // Subtracting the width will move the index to the correct value
        let top: i32 = index as i32 - self.width as i32;
        // Checks if the new calculated index is outside the grid, in case the original index is on the first row
        if top >= 0 {
            Some((&self.data[top as usize], top as usize))
        } else {
            None
        }
    }

    /// Returns the value of the cell on the right of the current index
    #[inline]
    pub fn get_right_index(&self, index: usize) -> Option<(&T, usize)> {
        // To calculate the right cell add one to the current index
        let right_index = index + 1;
        // Checks if the new index is outside of the grid
        // Checks if the new index is on the same row of the input index otherwise the new index is not present
        if right_index < self.data.len() as usize
            && self.are_indices_on_same_row(index as i32, right_index as i32)
        {
            Some((&self.data[right_index], right_index))
        } else {
            None
        }
    }

    /// Returns the value of the cell above the current index
    #[inline]
    pub fn get_bottom_index(&self, index: usize) -> Option<(&T, usize)> {
        // The bottom cell is at the same column in the row above.
        // Adding the width will move the index to the correct value
        let bottom = index + self.width;
        // Checks if the new calculated index is outside the grid, in case the original index is on the last row
        if bottom < self.data.len() {
            Some((&self.data[bottom], bottom))
        } else {
            None
        }
    }

    /// Returns the value of the cell on the right of the current index
    #[inline]
    pub fn get_left_index(&self, index: usize) -> Option<(&T, usize)> {
        // To calculate the left cell remove one to the current index
        let left_index = index as i32 - 1;
        // Checks if the new index is outside of the grid
        // Checks if the new index is on the same row of the input index otherwise the new index is not present
        if left_index >= 0 && self.are_indices_on_same_row(index as i32, left_index) {
            Some((&self.data[left_index as usize], left_index as usize))
        } else {
            None
        }
    }

    /// Checks if the indices are on the same row, this is used to check if the left and right are present or not
    #[inline]
    fn are_indices_on_same_row(&self, index_a: i32, index_b: i32) -> bool {
        let converted_width = self.width as i32;
        // Calculates the start index for the current row
        let index_a_row = index_a / converted_width * converted_width;
        // Calculates the start index of the next row
        let next_row = index_a_row + converted_width;
        index_b >= index_a_row && index_b < next_row
    }

    /// Returns the size of the entire maze
    #[inline]
    pub fn cell_count(&self) -> usize {
        self.data.len()
    }
}

Note that T needs to be Clone because of this line data: vec![data; width * height], the value is cloned multiple times at this point. This is to initialize the entire grid with a single default (in this case) value.

The maze

The next step is to the define the struct that will maintain the entire maze in memory. This is defined by the following fields:

• data: it’s the grid that will contain all the cells;
• current: the index of the cell currently working on;
• stack: this will collect the cells in the exploration phase, is needed only because we allow the maze not only to be pre-rendered but even to be calculated step by step;
• completed: this is to check if the maze is completed or not, will be used in the exploration phase to see if there is remaining work to perform;
• config: a struct that manages our random value.

struct Maze {
    data: Grid<Cell>,
    current: usize,
    stack: Vec<usize>,
    completed: bool,
    config: Config,
}

impl Maze {
    pub fn new(width: usize, height: usize, pre_render: bool, config: Config) -> Self {
        let mut maze = Self {
            data: Grid::new(Cell::default(), width as usize, height as usize),
            width,
            height,
            current: 0,
            stack: Vec::<usize>::new(),
            completed: false,
            config,
        };

        while pre_render && !maze.completed {
            maze.update();
        }

        maze
    }

    /// Returns the cell at coordinates
    pub fn get_cell(&self, x: usize, y: usize) -> &Cell {
        &self.data.get_value(x, y)
    }

    /// Checks if the cell at coordinates is the current for the exploration
    pub fn is_current(&self, x: usize, y: usize) -> bool {
        self.current == (x + y * self.data.width)
    }
}

struct Config {
    pub random: Xoshiro256Plus,
}

impl Config {
    pub fn create_config(seed: Option<u64>) -> Self {
        let random = if let Some(s) = seed {
            Xoshiro256Plus::seed_from_u64(s)
        } else {
            Xoshiro256Plus::seed_from_u64(thread_rng().next_u64())
        };
        Self { random }
    }
}

The algorithm

The central piece is very simple, these are the steps executed:

1. Mark the current cell al visited, the first time will be (0, 0);
2. Search for a new cell to visit, this could be a neighbour of the current cell or a cell in the stack:
   1. If there a neighbour push that into the stack, remove the wall between this cell and the current using a direction, and make the neighbour the current cell;
   2. If there isn’t a neighbour extract a cell from the stack.
3. When there are no cell into the stack and no neighbours of the current cell the exploration is finished.

impl Maze {
    /// Move the maze into the next step of the exploration
    pub fn update(&mut self) {
        // Gets the current cell for the exploration
        let mut current = &mut self.data.get_value_with_index_mut(self.current);
        // Sets the current cell to be visited
        current.visited = true;
        // Gets a neighbour for the current cell
        let neighbours = self.get_next_neighbour();
        // Checks if the stack is not empty or there are other neighbours to visit
        if !self.stack.is_empty() || neighbours.is_some() {
            // If the are neighbour cells to explore
            if let Some((n, direction)) = neighbours {
                // Puts the neighbour in the stack of cell to visit
                self.stack.push(n);
                // Removes the wall in the chosen direction
                self.remove_walls(n, direction);
                // Moves the current cell index to the new neighbour to continue the exploration
                self.current = n;
            } else {
                // Otherwise takes a cell from the stack because there are no neighbours available
                // Unwrap can be safely called here because there is already a check for the empty stack (there are not neighbours)
                self.current = self.stack.pop().unwrap();
            }
        } else {
            // There are no more cell to explore
            self.completed = true;
        }
    }

    /// Gets a neighbour around the current cell
    fn get_next_neighbour(&mut self) -> Option<(usize, Direction)> {
        // Collect all the possible neighbours
        let mut result = Vec::new();
        // Top
        if let Some((top_cell, index)) = self.data.get_top_index(self.current) {
            if !top_cell.visited {
                result.push((index as usize, Direction::Top));
            }
        }
        // Right
        if let Some((right_cell, index)) = self.data.get_right_index(self.current) {
            if !right_cell.visited {
                result.push(((index) as usize, Direction::Right));
            }
        }
        // Bottom
        if let Some((bottom_cell, index)) = self.data.get_bottom_index(self.current) {
            if !bottom_cell.visited {
                result.push(((index) as usize, Direction::Bottom));
            }
        }
        // Left
        if let Some((left_cell, index)) = self.data.get_left_index(self.current) {
            if !left_cell.visited {
                result.push(((index) as usize, Direction::Left));
            }
        }

        // Checks if there are neighbour
        if result.is_empty() {
            None
        } else {
            // Chooses a random direction
            Some(result[self.config.random.gen_range(0..result.len())])
        }
    }

    fn remove_walls(&mut self, next: usize, direction: Direction) {
        // Depending on the direction remove the walls from the current cell and the "next"
        // To remove a wall we can just mark the walls of the adjacent cells as false
        match direction {
            Direction::Top => {
                self.data.get_value_with_index_mut(self.current).t = false;
                self.data.get_value_with_index_mut(next).b = false;
            }
            Direction::Right => {
                self.data.get_value_with_index_mut(self.current).r = false;
                self.data.get_value_with_index_mut(next).l = false;
            }
            Direction::Bottom => {
                self.data.get_value_with_index_mut(self.current).b = false;
                self.data.get_value_with_index_mut(next).t = false;
            }
            Direction::Left => {
                self.data.get_value_with_index_mut(self.current).l = false;
                self.data.get_value_with_index_mut(next).r = false;
            }
        }
    }
}

/// Used to identify the wall that will be removed
#[derive(Clone, Copy, Debug)]
enum Direction {
    Top,
    Right,
    Bottom,
    Left,
}

Drawing it

To draw the generated maze we will use SDL2 because is pretty simple to setup and use. The algorithm used to draw the maze is the following:

1. Setup SDL2;
2. Create the maze;
3. For each frame update the maze exploring a new cell if not completed;
4. Draw all the cell of the maze (blue for those visited, light blue for those not touched).

To draw each cell we are going to draw the cell itself (a rect) and four lines: top, right, bottom, left. If the wall is not present the line will not be drawn.

fn main() {
    // Initialises sdl2
    let sdl = sdl2::init().expect("Impossible to load sdl");

    // Hides the mouse in the window
    sdl.mouse().show_cursor(false);
    sdl.mouse().capture(true);

    // Creates the video system used to draw
    let video_system = sdl.video().expect("No video subsystem available");

    // Disables antialiasing, this is because lines are straight and precise, enabling this could cause strange effects
    let gl_attr = video_system.gl_attr();
    gl_attr.set_multisample_buffers(0);
    gl_attr.set_multisample_samples(0);
    gl_attr.set_accelerated_visual(true);

    // A pixel more is needed because how the cell are drawn
    let width = 1601;
    let height = 901;
    // Creates the window where the draw will be display
    let window = video_system
        .window("Game", width as u32, height as u32)
        .build()
        .expect("A window cannot be created");

    // Creates the canvas that will be used to draw
    let mut canvas = window
        .into_canvas()
        .build()
        .expect("A canvas cannot be created");

    // Needed to capture input from keyboard
    let mut event_pump = sdl.event_pump().expect("No event pump");

    // Timer is used to cap the number of frames per second
    let mut timer = sdl.timer().expect("No timer");

    // Used to check if the application should continue to run or not
    let mut running = true;

    // Used to calculate the frame cap in milliseconds
    let fps_cap = (1.0 / 60.0) * 1000.0;

    // The size of the single cell inside the maze
    let side = 20;
    let mut maze = Maze::new(
        width as usize / side,
        height as usize / side,
        false,
        Config::create_config(Some(1234)),
    );
    while running {
        // Gets the performance counter to calculate at the end if a pause is needed (frame-cap)
        let start = timer.performance_counter();

        // Gets input from keyboard
        for event in event_pump.poll_iter() {
            match event {
                // Do we need to quit?
                Event::Quit { .. }
                | Event::KeyDown {
                    keycode: Some(Keycode::Escape),
                    ..
                } => running = false,
                _ => {}
            }
        }

        // Updates the maze step by step if not completed
        if !maze.completed {
            maze.update();
        }

        // Clears the screen
        canvas.set_draw_color(Color::RGB(92, 137, 179));
        canvas.clear();
        // Render the current state of the maze
        render(&mut canvas, &mut maze, side as i32);

        // Draws everything on the screen
        canvas.present();

        // Gets the performance counter, calculate the elapsed
        let end = timer.performance_counter();
        let elapsed = (end - start) as f32 / timer.performance_frequency() as f32 * 1000.0;

        // If needed delay the next frame
        if (fps_cap - elapsed) > 0.0 {
            timer.delay((fps_cap - elapsed).floor() as u32);
        }
    }
}

// Renders the current state of the maze on the canvas
fn render(canvas: &mut Canvas<Window>, maze: &mut Maze, side: i32) {
    let rows = maze.data.height;
    let columns = maze.data.width;
    // Loops over the grid
    for y in 0..rows {
        for x in 0..columns {
            // Gets the cell that needs to be drawn
            let cell = maze.get_cell(x, y);
            // Draws the cell
            draw_cell(
                canvas,
                cell,
                // Calculates the x and y position using the width of the cell
                // This is needed to calculate the real offset on the screen
                x as i32 * side,
                y as i32 * side,
                side,
                // If the cell in the current one and the maze is not completed, draw it
                if maze.is_current(x, y) && !maze.completed {
                    (255, 150, 50, 50)
                } else {
                    (255, 16, 32, 87)
                },
            );
        }
    }
}

fn draw_cell(
    canvas: &mut Canvas<Window>,
    cell: &Cell,
    x: i32,
    y: i32,
    side: i32,
    colour: (u8, u8, u8, u8),
) {
    let scale = 1.0;
    let line_colour = (255, 255, 255, 255);
    // If the cell is visited draw it, otherwise will be empty to see the background
    if cell.visited {
        draw_rect(canvas, x, y, side as u32, side as u32, colour);
    }
    // If present draw top wall
    if cell.t {
        draw_line(canvas, (x, y), (x + side, y), scale, line_colour);
    }
    // If present draw bottom wall
    if cell.b {
        draw_line(
            canvas,
            (x, y + side),
            (x + side, y + side),
            scale,
            line_colour,
        );
    }
    // If present draw right wall
    if cell.r {
        draw_line(
            canvas,
            (x + side, y),
            (x + side, y + side),
            scale,
            line_colour,
        );
    }
    // If present draw left wall
    if cell.l {
        draw_line(canvas, (x, y), (x, y + side), scale, line_colour);
    }
}

fn draw_rect(canvas: &mut Canvas<Window>, x: i32, y: i32, w: u32, h: u32, color: (u8, u8, u8, u8)) {
    // Sets the colour
    canvas.set_draw_color(Color::RGBA(color.1, color.2, color.3, color.0));
    // Draws a single rect using the previous colour
    canvas.fill_rect(Rect::new(x, y, w, h)).unwrap();
}

fn draw_line(
    canvas: &mut Canvas<Window>,
    start: (i32, i32),
    end: (i32, i32),
    scale: f32,
    color: (u8, u8, u8, u8),
) {
    // Sets the colour
    canvas.set_draw_color(Color::RGBA(color.1, color.2, color.3, color.0));
    // Sets the width of the line
    canvas.set_scale(scale, scale).unwrap();
    // Draws a line using the colour and the width
    canvas
        .draw_line(Point::new(start.0, start.1), Point::new(end.0, end.1))
        .unwrap();
}

Note the framerate is capped at 60 fps (16 ms per frame) otherwise, the application is going to use too many resources, and we would like to see the maze appearing in front of us a little at a time instead of all at once.

See you next time!