terrain_forge/algorithms/
percolation.rs

1use crate::{Algorithm, Grid, Rng, Tile};
2
3#[derive(Debug, Clone)]
4pub struct PercolationConfig {
5    pub fill_probability: f64,
6    pub keep_largest: bool,
7}
8
9impl Default for PercolationConfig {
10    fn default() -> Self {
11        Self {
12            fill_probability: 0.45,
13            keep_largest: true,
14        }
15    }
16}
17
18pub struct Percolation {
19    config: PercolationConfig,
20}
21
22impl Percolation {
23    pub fn new(config: PercolationConfig) -> Self {
24        Self { config }
25    }
26}
27
28impl Default for Percolation {
29    fn default() -> Self {
30        Self::new(PercolationConfig::default())
31    }
32}
33
34impl Algorithm<Tile> for Percolation {
35    fn generate(&self, grid: &mut Grid<Tile>, seed: u64) {
36        let mut rng = Rng::new(seed);
37        let (w, h) = (grid.width(), grid.height());
38
39        for y in 1..h - 1 {
40            for x in 1..w - 1 {
41                if rng.chance(self.config.fill_probability) {
42                    grid.set(x as i32, y as i32, Tile::Floor);
43                }
44            }
45        }
46
47        if !self.config.keep_largest {
48            return;
49        }
50
51        // Find and keep largest region
52        let mut labels = vec![0u32; w * h];
53        let mut label = 0u32;
54        let mut sizes = vec![0usize];
55
56        for y in 0..h {
57            for x in 0..w {
58                if grid[(x, y)].is_floor() && labels[y * w + x] == 0 {
59                    label += 1;
60                    let size = flood_fill(grid, &mut labels, x, y, label, w, h);
61                    sizes.push(size);
62                }
63            }
64        }
65
66        if label > 0 {
67            let largest = sizes
68                .iter()
69                .enumerate()
70                .skip(1)
71                .max_by_key(|&(_, &s)| s)
72                .map(|(i, _)| i as u32)
73                .unwrap_or(1);
74
75            for y in 0..h {
76                for x in 0..w {
77                    if labels[y * w + x] != largest && labels[y * w + x] != 0 {
78                        grid.set(x as i32, y as i32, Tile::Wall);
79                    }
80                }
81            }
82        }
83    }
84
85    fn name(&self) -> &'static str {
86        "Percolation"
87    }
88}
89
90fn flood_fill(
91    grid: &Grid<Tile>,
92    labels: &mut [u32],
93    sx: usize,
94    sy: usize,
95    label: u32,
96    w: usize,
97    h: usize,
98) -> usize {
99    let mut stack = vec![(sx, sy)];
100    let mut count = 0;
101
102    while let Some((x, y)) = stack.pop() {
103        let idx = y * w + x;
104        if labels[idx] != 0 || !grid[(x, y)].is_floor() {
105            continue;
106        }
107
108        labels[idx] = label;
109        count += 1;
110
111        if x > 0 {
112            stack.push((x - 1, y));
113        }
114        if x + 1 < w {
115            stack.push((x + 1, y));
116        }
117        if y > 0 {
118            stack.push((x, y - 1));
119        }
120        if y + 1 < h {
121            stack.push((x, y + 1));
122        }
123    }
124    count
125}
terrain_forge/algorithms/percolation.rs

terrain_forge/algorithms/
percolation.rs
