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 { Self { fill_probability: 0.45, keep_largest: true } }
11}
12
13pub struct Percolation {
14    config: PercolationConfig,
15}
16
17impl Percolation {
18    pub fn new(config: PercolationConfig) -> Self { Self { config } }
19}
20
21impl Default for Percolation {
22    fn default() -> Self { Self::new(PercolationConfig::default()) }
23}
24
25impl Algorithm<Tile> for Percolation {
26    fn generate(&self, grid: &mut Grid<Tile>, seed: u64) {
27        let mut rng = Rng::new(seed);
28        let (w, h) = (grid.width(), grid.height());
29
30        for y in 1..h - 1 {
31            for x in 1..w - 1 {
32                if rng.chance(self.config.fill_probability) {
33                    grid.set(x as i32, y as i32, Tile::Floor);
34                }
35            }
36        }
37
38        if !self.config.keep_largest { return; }
39
40        // Find and keep largest region
41        let mut labels = vec![0u32; w * h];
42        let mut label = 0u32;
43        let mut sizes = vec![0usize];
44
45        for y in 0..h {
46            for x in 0..w {
47                if grid[(x, y)].is_floor() && labels[y * w + x] == 0 {
48                    label += 1;
49                    let size = flood_fill(grid, &mut labels, x, y, label, w, h);
50                    sizes.push(size);
51                }
52            }
53        }
54
55        if label > 0 {
56            let largest = sizes.iter().enumerate().skip(1)
57                .max_by_key(|&(_, &s)| s).map(|(i, _)| i as u32).unwrap_or(1);
58
59            for y in 0..h {
60                for x in 0..w {
61                    if labels[y * w + x] != largest && labels[y * w + x] != 0 {
62                        grid.set(x as i32, y as i32, Tile::Wall);
63                    }
64                }
65            }
66        }
67    }
68
69    fn name(&self) -> &'static str { "Percolation" }
70}
71
72fn flood_fill(grid: &Grid<Tile>, labels: &mut [u32], sx: usize, sy: usize, label: u32, w: usize, h: usize) -> usize {
73    let mut stack = vec![(sx, sy)];
74    let mut count = 0;
75
76    while let Some((x, y)) = stack.pop() {
77        let idx = y * w + x;
78        if labels[idx] != 0 || !grid[(x, y)].is_floor() { continue; }
79
80        labels[idx] = label;
81        count += 1;
82
83        if x > 0 { stack.push((x - 1, y)); }
84        if x + 1 < w { stack.push((x + 1, y)); }
85        if y > 0 { stack.push((x, y - 1)); }
86        if y + 1 < h { stack.push((x, y + 1)); }
87    }
88    count
89}
terrain_forge/algorithms/percolation.rs

terrain_forge/algorithms/
percolation.rs
