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

terrain_forge/algorithms/
maze.rs
