terrain_forge/algorithms/
maze.rs

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

terrain_forge/algorithms/
maze.rs
