terrain_forge/algorithms/
glass_seam.rs

1use crate::{Algorithm, Grid, Rng, Tile};
2use std::collections::{HashSet, VecDeque};
3
4pub struct GlassSeam {
5    pub coverage_threshold: f64,
6}
7
8impl Default for GlassSeam {
9    fn default() -> Self { Self { coverage_threshold: 0.75 } }
10}
11
12impl Algorithm<Tile> for GlassSeam {
13    fn generate(&self, grid: &mut Grid<Tile>, seed: u64) {
14        let mut rng = Rng::new(seed);
15        let (w, h) = (grid.width(), grid.height());
16
17        // Initialize with pattern
18        for y in 0..h {
19            for x in 0..w {
20                if (x + y) % 7 < 3 {
21                    grid.set(x as i32, y as i32, Tile::Floor);
22                }
23            }
24        }
25
26        // Ensure connectivity
27        ensure_connectivity(grid, (5, 5), self.coverage_threshold, &mut rng);
28    }
29
30    fn name(&self) -> &'static str { "GlassSeam" }
31}
32
33fn ensure_connectivity(grid: &mut Grid<Tile>, spawn: (usize, usize), threshold: f64, _rng: &mut Rng) {
34    let regions = identify_regions(grid);
35    if regions.len() <= 1 { return; }
36
37    let spawn_region = regions.iter().position(|r| r.contains(&spawn)).unwrap_or(0);
38    let total_floor: usize = regions.iter().map(|r| r.len()).sum();
39    let mut coverage = regions[spawn_region].len() as f64 / total_floor as f64;
40
41    if coverage >= threshold { return; }
42
43    let mut connected = HashSet::new();
44    connected.insert(spawn_region);
45
46    while coverage < threshold && connected.len() < regions.len() {
47        let mut best = None;
48        let mut best_cost = usize::MAX;
49
50        for (i, region) in regions.iter().enumerate() {
51            if connected.contains(&i) { continue; }
52            for &ci in &connected {
53                let cost = connection_cost(&regions[ci], region);
54                if cost < best_cost {
55                    best_cost = cost;
56                    best = Some((i, ci));
57                }
58            }
59        }
60
61        if let Some((target, source)) = best {
62            connect_regions(grid, &regions[source], &regions[target]);
63            connected.insert(target);
64            coverage += regions[target].len() as f64 / total_floor as f64;
65        } else {
66            break;
67        }
68    }
69}
70
71fn identify_regions(grid: &Grid<Tile>) -> Vec<Vec<(usize, usize)>> {
72    let (w, h) = (grid.width(), grid.height());
73    let mut visited = vec![vec![false; h]; w];
74    let mut regions = Vec::new();
75
76    for x in 0..w {
77        for y in 0..h {
78            if !visited[x][y] && grid[(x, y)].is_floor() {
79                let region = flood_fill(grid, x, y, &mut visited);
80                if !region.is_empty() { regions.push(region); }
81            }
82        }
83    }
84    regions
85}
86
87fn flood_fill(grid: &Grid<Tile>, sx: usize, sy: usize, visited: &mut [Vec<bool>]) -> Vec<(usize, usize)> {
88    let (w, h) = (grid.width(), grid.height());
89    let mut region = Vec::new();
90    let mut queue = VecDeque::new();
91    queue.push_back((sx, sy));
92
93    while let Some((x, y)) = queue.pop_front() {
94        if x >= w || y >= h || visited[x][y] || !grid[(x, y)].is_floor() { continue; }
95        visited[x][y] = true;
96        region.push((x, y));
97
98        if x > 0 { queue.push_back((x - 1, y)); }
99        if x + 1 < w { queue.push_back((x + 1, y)); }
100        if y > 0 { queue.push_back((x, y - 1)); }
101        if y + 1 < h { queue.push_back((x, y + 1)); }
102    }
103    region
104}
105
106fn connection_cost(a: &[(usize, usize)], b: &[(usize, usize)]) -> usize {
107    let ca = centroid(a);
108    let cb = centroid(b);
109    ((ca.0 as i32 - cb.0 as i32).abs() + (ca.1 as i32 - cb.1 as i32).abs()) as usize
110}
111
112fn centroid(region: &[(usize, usize)]) -> (usize, usize) {
113    if region.is_empty() { return (0, 0); }
114    let sx: usize = region.iter().map(|p| p.0).sum();
115    let sy: usize = region.iter().map(|p| p.1).sum();
116    (sx / region.len(), sy / region.len())
117}
118
119fn connect_regions(grid: &mut Grid<Tile>, source: &[(usize, usize)], target: &[(usize, usize)]) {
120    let from = centroid(source);
121    let to = centroid(target);
122
123    let (mut x, mut y) = (from.0 as i32, from.1 as i32);
124    let (tx, ty) = (to.0 as i32, to.1 as i32);
125
126    while x != tx || y != ty {
127        grid.set(x, y, Tile::Floor);
128        if (x - tx).abs() > (y - ty).abs() {
129            x += if tx > x { 1 } else { -1 };
130        } else {
131            y += if ty > y { 1 } else { -1 };
132        }
133    }
134    grid.set(tx, ty, Tile::Floor);
135}
terrain_forge/algorithms/glass_seam.rs

terrain_forge/algorithms/
glass_seam.rs
