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

terrain_forge/algorithms/
glass_seam.rs
