knossos 1.2.0

use super::Algorithm;
use crate::utils::types::Coords;
use crate::maze::grid::{Grid, cell::Cell};

use rand::prelude::*;
use std::vec;

/// The Prim's algorithm for generating mazes
///
/// The original version of the algorithm generates a minimal spanning tree in a graph.
/// With one little change, it becomes a suitable method for generating mazes.
///
/// Mazes generated by Prim’s algorithm share many of the characteristics of those created
/// via Kruskal’s algorithm, such as having an abundance of short cul-de-sacs which makes
/// the maze harder to puzzle out at a glance
pub struct Prim {
    frontiers: Vec<Coords>,
}

impl Prim {
    /// Create a new instance of the algorithm with an empty set of the frontier cells
    pub const fn new() -> Prim {
        Prim { frontiers: vec![] }
    }

    fn mark(&mut self, coords: Coords, grid: &mut Grid) {
        grid.mark_cell(coords);

        let (x, y) = coords;
        self.add_frontier((x + 1, y), grid);
        self.add_frontier((x, y + 1), grid);
        if x > 0 {
            self.add_frontier((x - 1, y), grid);
        }
        if y > 0 {
            self.add_frontier((x, y - 1), grid);
        }
    }

    fn add_frontier(&mut self, (x, y): Coords, grid: &mut Grid) {
        if x < grid.width()
            && y < grid.height()
            && !grid.is_cell_marked((x, y))
            && !self.frontiers.iter().any(|f| *f == (x, y))
        {
            self.frontiers.push((x, y));
        }
    }

    fn neighbours(&self, (x, y): Coords, grid: &mut Grid) -> Vec<Coords> {
        let mut neighbours = vec![];

        if x > 0 && grid.is_cell_marked((x - 1, y)) {
            neighbours.push((x - 1, y))
        }

        if x + 1 < grid.width() && grid.is_cell_marked((x + 1, y)) {
            neighbours.push((x + 1, y))
        }

        if y > 0 && grid.is_cell_marked((x, y - 1)) {
            neighbours.push((x, y - 1))
        }

        if y + 1 < grid.height() && grid.is_cell_marked((x, y + 1)) {
            neighbours.push((x, y + 1))
        }

        neighbours
    }
}

impl Default for Prim {
    fn default() -> Self {
        Self::new()
    }
}

/// An implementation of the Prim's algorithm for generating mazes
///
/// For efficiency, let’s define a legend for the following algorithm steps:
/// - "F" or "frontier”: the set of all cells that are not yet in the maze, but are adjacent to a
///   cell that is in the maze.
///
/// The standard version of the algorithm generates a minimal spanning tree in a graph. With a
/// slight change of adding some random, it works something like this:
///
/// 1. Chooses an arbitrary cell and adds it to the maze.
///
/// 2. Adds all neighbor cells that are not in the F yet to F.
///
/// 3. Removes one of the F cells at random and carves a passage from that to whichever adjacent
///    cell is already part of the maze.
///
/// 4. Adds the neighbours of the formerly frontier cell to the F.
///
/// 5. Repeats steps 3 and 4 until the F is empty.
impl Algorithm for Prim {
    fn generate(&mut self, grid: &mut Grid, rng: &mut StdRng) {
        self.mark(get_rand_coords(grid, rng), grid);

        while !self.frontiers.is_empty() {
            let index = rng.random_range(0..self.frontiers.len());
            let coords = self.frontiers.remove(index);

            let neighbours = self.neighbours(coords, grid);

            let index = rng.random_range(0..neighbours.len());
            let (nx, ny) = neighbours[index];

            let (x, y) = coords;

            if let Some(dir) = direction(x, y, nx, ny) {
                grid.carve_passage(coords, dir).unwrap();
                self.mark(coords, grid);
            }
        }
    }
}

fn get_rand_coords<R: Rng>(grid: &Grid, rng: &mut R) -> Coords {
    let x = rng.random_range(0..grid.width());
    let y = rng.random_range(0..grid.height());
    (x, y)
}

fn direction(x: usize, y: usize, nx: usize, ny: usize) -> Option<Cell> {
    if x < nx {
        return Some(Cell::EAST);
    }
    if x > nx {
        return Some(Cell::WEST);
    }
    if y < ny {
        return Some(Cell::SOUTH);
    }
    if y > ny {
        return Some(Cell::NORTH);
    }

    unreachable!("The x and y coordinates are never equal to nx and ny")
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn default_call() {
        let algo = Prim::default();
        let v: Vec<Coords> = vec![];
        assert_eq!(v, algo.frontiers);
    }
}