Since I need to run Quinti-Maze in a Rust no_std environment, none of the existing maze generation crates can be used directly. I derived my version from the Knossos crate and its version of the Growing Tree generation algorithm, adapting it to no_std and generating the maze in three dimensions.

Here is the definition of a maze in Quinti-Maze 2022.

type Doors = [bool; 6];

#[derive(Debug, Default, Clone, Copy)]
pub struct Cell {
    pub doors: Doors,
    pub visited: bool,
}

#[derive(Debug)]
pub struct Maze<const X: usize, const Y: usize, const Z: usize> {
    cells: [[[Cell; X]; Y]; Z],
}

I somewhat unnecessarily made the maze generic in its dimensions.

pub type QuintiMaze = Maze<5, 5, 5>;
pub const CELL_COUNT: usize = QuintiMaze::cell_count();

#[derive(Default)]
pub struct MazeGenerator {
    maze: QuintiMaze,
    cells: Vec<Coord, CELL_COUNT>,
}

pub fn generate(&mut self, seed: Option<u64>) {
    let mut rng = ChaChaRng::seed_from_u64(seed.unwrap_or(12));
    let (max_x, max_y, max_z) = QuintiMaze::dimensions();
    let x = rng.gen_range(0..max_x) as isize;
    let y = rng.gen_range(0..max_y) as isize;
    let z = rng.gen_range(0..max_z) as isize;

    let mut directions: Vec<Direction, 6> = Default::default();
    directions.extend([
        Direction::North,
        Direction::South,
        Direction::West,
        Direction::East,
        Direction::Up,
        Direction::Down,
    ]);

    self.cells.push(Coord { x, y, z }).expect("push");

    while !self.cells.is_empty() {
        let mut index = Some(rng.gen_range(0..self.cells.len()));
        let coords = self.cells[index.unwrap_or(0)];

        directions.shuffle(&mut rng);
        for dir in &directions {
            let next = match self.get_next_cell_coords(coords, dir) {
                Some(next) => next,
                None => continue,
            };

            if self.is_cell_visited(next) {
                continue;
            }

            if let Some(next) = self.carve_passage(coords, dir) {
                self.cells.push(next).expect("push");
                index = None;
                break;
            }
        }

        if let Some(index) = index {
            self.cells.remove(index);
        }
    }
    self.maze.cells[max_x - 1][max_z - 1][max_z - 1].remove_wall(&Direction::Up);
}

In order to stay more true to the std implementation, I used the heapless crate. This crate provides a vector type that works much like the std vector, but requires you to pre-allocate all the space it can use.

Randomness is provided by the rand_chacha crate, which is usable in no_std.

One thing I found in using this algorithm is that the mazes it generates are more difficult to solve than my “remove a lot of random walls” algorithm from 1982. That, or I have much less patience. Either way, I needed a way to quickly win. Enter, a maze solver.

pub type SolutionPath = Deque<Coord, CELL_COUNT>;

fn find_exit(
    maze: &QuintiMaze,
    prior_location: Option<Coord>,
    location: Coord,
    result: &mut SolutionPath,
) -> bool {
    for direction in [
        Direction::Up,
        Direction::Down,
        Direction::West,
        Direction::East,
        Direction::South,
        Direction::North,
    ] {
        let cell = maze.get_cell(&location);
        if cell.has_door(direction) {
            let new_location = location.move_in_direction(direction);
            if maze.is_win(&new_location) {
                result.push_back(new_location).expect("push");
                result.push_back(location).expect("push");
                return true;
            }
            if Some(new_location) != prior_location
                && find_exit(maze, Some(location), new_location, result)
            {
                result.push_back(location).expect("push");
                return true;
            }
        }
    }
    false
}

pub fn find_path_to_exit(maze: &QuintiMaze, starting_position: Coord) -> (bool, SolutionPath) {
    let mut vec = SolutionPath::new();

    let result = find_exit(maze, None, starting_position, &mut vec);

    (result, vec)
}

I added a key to run this finder and show the next direction to move to reach the exit. I was concerned that this recursive implementation might overflow the stack, but so far that’s not occurred. The solution path is clearly oversized, but that also has not been a problem.

In general I’m being more wasteful of memory in this implementation than is necessary. The Cell struct is 7 bytes, when one could represent it in a single byte. The Feather M4, though, is fairly beefy for a microcontroller, with 160KB of RAM, so more size optimization isn’t necessary.