terrain_forge/algorithms/
maze.rs

1use crate::{Algorithm, Grid, Rng, Tile};
2
3#[derive(Debug, Clone)]
4pub struct MazeConfig {
5    pub corridor_width: usize,
6}
7
8impl Default for MazeConfig {
9    fn default() -> Self {
10        Self { corridor_width: 1 }
11    }
12}
13
14pub struct Maze {
15    config: MazeConfig,
16}
17
18impl Maze {
19    pub fn new(config: MazeConfig) -> Self {
20        Self { config }
21    }
22}
23
24impl Default for Maze {
25    fn default() -> Self {
26        Self::new(MazeConfig::default())
27    }
28}
29
30impl Algorithm<Tile> for Maze {
31    fn generate(&self, grid: &mut Grid<Tile>, seed: u64) {
32        let mut rng = Rng::new(seed);
33        let step = self.config.corridor_width + 1;
34        let (w, h) = (grid.width(), grid.height());
35
36        let maze_w = (w - 1) / step;
37        let maze_h = (h - 1) / step;
38        if maze_w < 2 || maze_h < 2 {
39            return;
40        }
41
42        let mut visited = vec![vec![false; maze_h]; maze_w];
43        let mut stack = vec![(0usize, 0usize)];
44        visited[0][0] = true;
45
46        while let Some(&(cx, cy)) = stack.last() {
47            let mut neighbors = Vec::new();
48            if cx > 0 && !visited[cx - 1][cy] {
49                neighbors.push((cx - 1, cy));
50            }
51            if cx + 1 < maze_w && !visited[cx + 1][cy] {
52                neighbors.push((cx + 1, cy));
53            }
54            if cy > 0 && !visited[cx][cy - 1] {
55                neighbors.push((cx, cy - 1));
56            }
57            if cy + 1 < maze_h && !visited[cx][cy + 1] {
58                neighbors.push((cx, cy + 1));
59            }
60
61            if neighbors.is_empty() {
62                stack.pop();
63            } else {
64                let &(nx, ny) = rng.pick(&neighbors).unwrap();
65                visited[nx][ny] = true;
66
67                let (gx, gy) = (1 + cx * step, 1 + cy * step);
68                let (gnx, gny) = (1 + nx * step, 1 + ny * step);
69
70                carve_cell(grid, gx, gy, self.config.corridor_width);
71                carve_cell(grid, gnx, gny, self.config.corridor_width);
72                carve_between(grid, gx, gy, gnx, gny, self.config.corridor_width);
73
74                stack.push((nx, ny));
75            }
76        }
77    }
78
79    fn name(&self) -> &'static str {
80        "Maze"
81    }
82}
83
84fn carve_cell(grid: &mut Grid<Tile>, x: usize, y: usize, size: usize) {
85    for dy in 0..size {
86        for dx in 0..size {
87            grid.set((x + dx) as i32, (y + dy) as i32, Tile::Floor);
88        }
89    }
90}
91
92fn carve_between(grid: &mut Grid<Tile>, x1: usize, y1: usize, x2: usize, y2: usize, size: usize) {
93    let (min_x, max_x) = (x1.min(x2), x1.max(x2));
94    let (min_y, max_y) = (y1.min(y2), y1.max(y2));
95    for y in min_y..=max_y {
96        for x in min_x..=max_x {
97            for dy in 0..size {
98                for dx in 0..size {
99                    grid.set((x + dx) as i32, (y + dy) as i32, Tile::Floor);
100                }
101            }
102        }
103    }
104}
terrain_forge/algorithms/maze.rs

terrain_forge/algorithms/
maze.rs
