use crate::direction6::Direction6;
use crate::generators::{
HexGenerationStep, HexGenerationSteps, HexGenerationVisitor, MazeGenerator6D,
VecHexGenerationVisitor,
};
use crate::hex_coord::HexCoord;
use crate::wall6_grid::Wall6Grid;
use rand::SeedableRng;
use rand::prelude::IndexedRandom;
use rand::rngs::StdRng;
pub struct RecursiveBacktracker6 {
rng_seed: u64,
}
impl Default for RecursiveBacktracker6 {
fn default() -> Self {
Self::new_random()
}
}
impl RecursiveBacktracker6 {
pub fn new_random() -> Self {
Self {
rng_seed: rand::random(),
}
}
pub fn new_from_seed(rng_seed: u64) -> Self {
if rng_seed == 0 {
Self::new_random()
} else {
Self { rng_seed }
}
}
pub fn generate(&self, width: usize, height: usize) -> Wall6Grid {
self.generate_with_steps(width, height).0
}
pub fn generate_steps(&self, width: usize, height: usize) -> HexGenerationSteps {
HexGenerationSteps::new(self.generate_with_steps(width, height).1)
}
fn generate_with_steps(
&self,
width: usize,
height: usize,
) -> (Wall6Grid, Vec<HexGenerationStep>) {
let mut cells = Wall6Grid::new(width, height);
let mut visitor = VecHexGenerationVisitor::default();
if width == 0 || height == 0 {
visitor.on_step(&HexGenerationStep::Complete);
return (cells, visitor.into_steps());
}
let mut visit_map = vec![false; width * height];
let start = HexCoord::new(0, 0);
let mut backtrace: Vec<HexCoord> = Vec::new();
let mut rng = StdRng::seed_from_u64(self.rng_seed);
let mut current = start;
loop {
let idx = (current.r as usize) * width + current.q as usize;
if !visit_map[idx] {
visitor.on_step(&HexGenerationStep::Visit { cell: current });
}
visit_map[idx] = true;
if let Some(next) =
Self::select_random_unvisited_neighbor(&mut rng, &visit_map, current, width, height)
{
backtrace.push(current);
visitor.on_step(&HexGenerationStep::AddToFrontier { cell: current });
cells.remove_wall_between(current, next);
visitor.on_step(&HexGenerationStep::Carve {
from: current,
to: next,
});
current = next;
continue;
}
if let Some(cell) = backtrace.pop() {
current = cell;
visitor.on_step(&HexGenerationStep::Backtrack { to: cell });
} else {
break;
}
}
visitor.on_step(&HexGenerationStep::Complete);
(cells, visitor.into_steps())
}
fn select_random_unvisited_neighbor(
rng: &mut StdRng,
visit_map: &[bool],
current: HexCoord,
width: usize,
height: usize,
) -> Option<HexCoord> {
let mut candidates = Vec::with_capacity(6);
for &dir in &Direction6::CARDINALS {
if let Some(n) = current.try_neighbor(dir, width, height) {
let idx = (n.r as usize) * width + n.q as usize;
if !visit_map[idx] {
candidates.push(n);
}
}
}
if candidates.is_empty() {
return None;
}
candidates.choose(rng).copied()
}
}
impl MazeGenerator6D for RecursiveBacktracker6 {
fn new_random() -> Self {
RecursiveBacktracker6::new_random()
}
fn new_from_seed(rng_seed: u64) -> Self {
RecursiveBacktracker6::new_from_seed(rng_seed)
}
fn generate(&self, width: usize, height: usize) -> Wall6Grid {
self.generate(width, height)
}
fn generate_steps(&self, width: usize, height: usize) -> HexGenerationSteps {
self.generate_steps(width, height)
}
fn name(&self) -> &'static str {
"hex-recursive-backtracker"
}
fn description(&self) -> &'static str {
"Depth-first backtracking generator for hexagonal grids creating long corridors"
}
}