terrain-forge 0.7.0

A modular procedural generation engine for terrain, dungeons, and maps
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

use crate::{Algorithm, Grid, Rng, Tile};
use serde::{Deserialize, Serialize};

#[derive(Debug, Clone, Serialize, Deserialize)]
/// Configuration for perfect maze generation.
pub struct MazeConfig {
    /// Width of corridors in cells. Default: 1.
    pub corridor_width: usize,
}

impl Default for MazeConfig {
    fn default() -> Self {
        Self { corridor_width: 1 }
    }
}

#[derive(Debug, Clone, Serialize, Deserialize)]
/// Perfect maze generator (recursive backtracker).
pub struct Maze {
    config: MazeConfig,
}

impl Maze {
    /// Creates a new maze generator with the given config.
    pub fn new(config: MazeConfig) -> Self {
        Self { config }
    }
}

impl Default for Maze {
    fn default() -> Self {
        Self::new(MazeConfig::default())
    }
}

impl Algorithm<Tile> for Maze {
    fn generate(&self, grid: &mut Grid<Tile>, seed: u64) {
        let mut rng = Rng::new(seed);
        let step = self.config.corridor_width + 1;
        let (w, h) = (grid.width(), grid.height());

        let maze_w = (w - 1) / step;
        let maze_h = (h - 1) / step;
        if maze_w < 2 || maze_h < 2 {
            return;
        }

        let mut visited = vec![vec![false; maze_h]; maze_w];
        let mut stack = vec![(0usize, 0usize)];
        visited[0][0] = true;

        while let Some(&(cx, cy)) = stack.last() {
            let mut neighbors = Vec::new();
            if cx > 0 && !visited[cx - 1][cy] {
                neighbors.push((cx - 1, cy));
            }
            if cx + 1 < maze_w && !visited[cx + 1][cy] {
                neighbors.push((cx + 1, cy));
            }
            if cy > 0 && !visited[cx][cy - 1] {
                neighbors.push((cx, cy - 1));
            }
            if cy + 1 < maze_h && !visited[cx][cy + 1] {
                neighbors.push((cx, cy + 1));
            }

            if neighbors.is_empty() {
                stack.pop();
            } else {
                let &(nx, ny) = rng.pick(&neighbors).unwrap();
                visited[nx][ny] = true;

                let (gx, gy) = (1 + cx * step, 1 + cy * step);
                let (gnx, gny) = (1 + nx * step, 1 + ny * step);

                carve_cell(grid, gx, gy, self.config.corridor_width);
                carve_cell(grid, gnx, gny, self.config.corridor_width);
                carve_between(grid, gx, gy, gnx, gny, self.config.corridor_width);

                stack.push((nx, ny));
            }
        }
    }

    fn name(&self) -> &'static str {
        "Maze"
    }
}

fn carve_cell(grid: &mut Grid<Tile>, x: usize, y: usize, size: usize) {
    for dy in 0..size {
        for dx in 0..size {
            grid.set((x + dx) as i32, (y + dy) as i32, Tile::Floor);
        }
    }
}

fn carve_between(grid: &mut Grid<Tile>, x1: usize, y1: usize, x2: usize, y2: usize, size: usize) {
    let (min_x, max_x) = (x1.min(x2), x1.max(x2));
    let (min_y, max_y) = (y1.min(y2), y1.max(y2));
    for y in min_y..=max_y {
        for x in min_x..=max_x {
            for dy in 0..size {
                for dx in 0..size {
                    grid.set((x + dx) as i32, (y + dy) as i32, Tile::Floor);
                }
            }
        }
    }
}