// Copyright Marcus Del Favero 2025
// Licensed under the GNU AGPLv3 with an exception, see `README.md` for details
use glam::UVec2;
use rand::Rng;

use super::Maze;

/** Generates a maze using randomised depth-first search. */
pub fn generate(maze: &mut Maze, rng: &mut impl Rng) {
	// Using https://en.wikipedia.org/w/index.php?title=Maze_generation_algorithm&oldid=1232975151#Iterative_implementation_(with_stack)
	let init_pos = UVec2::new(rng.next_u32(), rng.next_u32()) % maze.get_size();

	maze.visit_cell(init_pos);

	let mut stack = Vec::new();
	stack.push(init_pos);

	while let Some(pos) = stack.pop() {
		if let Some(edge) = maze.random_unvisited_neighbour(pos, rng) {
			stack.push(pos);
			maze.open_cell(pos, edge);
			let neighbour = pos + edge;
			maze.visit_cell(neighbour);
			stack.push(pos + edge);
		}
	}
}
