amaze 0.4.1

A maze generator
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

use crate::direction6::Direction6;
use crate::generators::{
    HexGenerationStep, HexGenerationSteps, HexGenerationVisitor, MazeGenerator6D,
    VecHexGenerationVisitor,
};
use crate::hex_coord::HexCoord;
use crate::wall6_grid::Wall6Grid;
use rand::RngExt;
use rand::SeedableRng;
use rand::rngs::StdRng;

pub struct AldousBroder6 {
    rng_seed: u64,
}

impl Default for AldousBroder6 {
    fn default() -> Self {
        Self::new_random()
    }
}

impl AldousBroder6 {
    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 grid = Wall6Grid::new(width, height);
        let mut visitor = VecHexGenerationVisitor::default();

        if width == 0 || height == 0 {
            visitor.on_step(&HexGenerationStep::Complete);
            return (grid, visitor.into_steps());
        }

        let mut visited = vec![false; width * height];
        let mut visited_count = 0usize;
        let total_cells = width * height;

        let mut rng = StdRng::seed_from_u64(self.rng_seed);
        let mut current = HexCoord::new(
            rng.random_range(0..width) as isize,
            rng.random_range(0..height) as isize,
        );

        let idx = (current.r as usize) * width + current.q as usize;
        if !visited[idx] {
            visited[idx] = true;
            visited_count += 1;
            visitor.on_step(&HexGenerationStep::Visit { cell: current });
        }

        while visited_count < total_cells {
            let neighbors = Self::neighbors(current, width, height);
            let next = neighbors[rng.random_range(0..neighbors.len())];
            let next_idx = (next.r as usize) * width + next.q as usize;

            if !visited[next_idx] {
                visited[next_idx] = true;
                visited_count += 1;
                grid.remove_wall_between(current, next);
                visitor.on_step(&HexGenerationStep::Carve {
                    from: current,
                    to: next,
                });
                visitor.on_step(&HexGenerationStep::Visit { cell: next });
            }

            current = next;
        }

        visitor.on_step(&HexGenerationStep::Complete);
        (grid, visitor.into_steps())
    }

    fn neighbors(cell: HexCoord, width: usize, height: usize) -> Vec<HexCoord> {
        let mut result = Vec::with_capacity(6);
        for &dir in &Direction6::CARDINALS {
            if let Some(n) = cell.try_neighbor(dir, width, height) {
                result.push(n);
            }
        }
        result
    }
}

impl MazeGenerator6D for AldousBroder6 {
    fn new_random() -> Self {
        AldousBroder6::new_random()
    }

    fn new_from_seed(rng_seed: u64) -> Self {
        AldousBroder6::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-aldous-broder"
    }

    fn description(&self) -> &'static str {
        "Aldous-Broder algorithm for hexagonal grids producing uniform spanning trees"
    }
}