src/worldgen.rs 7.3 K · 234 lines · raw · history

1 use std::collections::VecDeque;
2
3 use bevy::prelude::*;
4
5 use crate::{
6 noise::Noise,
7 world::{Terrain, WorldMap},
8 };
9
10 pub const WORLD_SIZE: UVec2 = UVec2::new(256, 256);
11 pub const DEFAULT_SEED: u32 = 1;
12
13 const ELEVATION_SCALE: f32 = 1.0 / 48.0;
14 const FERTILITY_SCALE: f32 = 1.0 / 16.0;
15 const DEEP_WATER_SHARE: f32 = 0.10;
16 const SHALLOW_WATER_SHARE: f32 = 0.06;
17 const SAND_SHARE: f32 = 0.04;
18 const STONE_SHARE: f32 = 0.14;
19 const SOIL_SHARE: f32 = 0.20;
20
21 pub struct WorldGenPlugin;
22
23 impl Plugin for WorldGenPlugin {
24 fn build(&self, app: &mut App) {
25 app.insert_resource(WorldSeed(DEFAULT_SEED))
26 .insert_resource(generate(WORLD_SIZE, DEFAULT_SEED))
27 .add_message::<WorldGenerated>()
28 .add_systems(Startup, |mut generated: MessageWriter<WorldGenerated>| {
29 generated.write(WorldGenerated);
30 })
31 .add_systems(Update, regenerate_on_key);
32 }
33 }
34
35 #[derive(Resource, Debug, Clone, Copy, PartialEq)]
36 pub struct WorldSeed(pub u32);
37
38 #[derive(Message, Debug, Clone, Copy)]
39 pub struct WorldGenerated;
40
41 fn regenerate_on_key(
42 keys: Res<ButtonInput<KeyCode>>,
43 mut seed: ResMut<WorldSeed>,
44 mut map: ResMut<WorldMap>,
45 mut generated: MessageWriter<WorldGenerated>,
46 ) {
47 if keys.just_pressed(KeyCode::KeyR) {
48 seed.0 = seed.0.wrapping_add(1);
49 *map = generate(map.size, seed.0);
50 generated.write(WorldGenerated);
51 }
52 }
53
54 pub fn generate(size: UVec2, seed: u32) -> WorldMap {
55 let elevation_noise = Noise::new(seed);
56 let fertility_noise = Noise::new(seed.wrapping_add(0x1000));
57 let mut map = WorldMap::filled(size, Terrain::Grass);
58 let positions: Vec<UVec2> = map.positions().collect();
59 let elevation: Vec<f32> = positions
60 .iter()
61 .map(|p| elevation_noise.fbm(p.as_vec2() * ELEVATION_SCALE, 5))
62 .collect();
63 let fertility: Vec<f32> = positions
64 .iter()
65 .map(|p| fertility_noise.fbm(p.as_vec2() * FERTILITY_SCALE, 3))
66 .collect();
67
68 let deep = quantile(&elevation, DEEP_WATER_SHARE);
69 let shallow = quantile(&elevation, DEEP_WATER_SHARE + SHALLOW_WATER_SHARE);
70 let sand = quantile(
71 &elevation,
72 DEEP_WATER_SHARE + SHALLOW_WATER_SHARE + SAND_SHARE,
73 );
74 let stone = quantile(&elevation, 1.0 - STONE_SHARE);
75 let soil = quantile(&fertility, 1.0 - SOIL_SHARE);
76
77 for ((&pos, &e), &f) in positions.iter().zip(&elevation).zip(&fertility) {
78 let terrain = if e < deep {
79 Terrain::DeepWater
80 } else if e < shallow {
81 Terrain::ShallowWater
82 } else if e < sand {
83 Terrain::Sand
84 } else if e >= stone {
85 Terrain::Stone
86 } else if f >= soil {
87 Terrain::Soil
88 } else {
89 Terrain::Grass
90 };
91 map.set(pos, terrain);
92 }
93 map
94 }
95
96 pub fn quantile(values: &[f32], share: f32) -> f32 {
97 let mut sorted = values.to_vec();
98 sorted.sort_by(f32::total_cmp);
99 let i = ((sorted.len() as f32 * share) as usize).min(sorted.len() - 1);
100 sorted[i]
101 }
102
103 pub fn largest_region(map: &WorldMap) -> Vec<UVec2> {
104 let mut seen = vec![false; map.size.element_product() as usize];
105 let index = |p: UVec2| (p.y * map.size.x + p.x) as usize;
106 let mut best = Vec::new();
107 for start in map.positions() {
108 if seen[index(start)] || map.move_cost(start.as_ivec2()).is_none() {
109 continue;
110 }
111 let region = flood(map, start, |p| {
112 let fresh = !seen[index(p)];
113 seen[index(p)] = true;
114 fresh
115 });
116 if region.len() > best.len() {
117 best = region;
118 }
119 }
120 best
121 }
122
123 fn flood(map: &WorldMap, start: UVec2, mut visit: impl FnMut(UVec2) -> bool) -> Vec<UVec2> {
124 let mut region = Vec::new();
125 let mut queue = VecDeque::from([start]);
126 visit(start);
127 while let Some(pos) = queue.pop_front() {
128 region.push(pos);
129 for step in [IVec2::X, IVec2::NEG_X, IVec2::Y, IVec2::NEG_Y] {
130 let next = pos.as_ivec2() + step;
131 if map.move_cost(next).is_some() && visit(next.as_uvec2()) {
132 queue.push_back(next.as_uvec2());
133 }
134 }
135 }
136 region
137 }
138
139 pub fn spawn_tiles(map: &WorldMap, count: usize) -> Vec<UVec2> {
140 let center = map.size.as_vec2() / 2.0;
141 let Some(&origin) = largest_region(map).iter().min_by(|a, b| {
142 a.as_vec2()
143 .distance_squared(center)
144 .total_cmp(&b.as_vec2().distance_squared(center))
145 }) else {
146 return Vec::new();
147 };
148 let mut seen = std::collections::HashSet::new();
149 flood(map, origin, |p| seen.insert(p))
150 .into_iter()
151 .step_by(2)
152 .take(count)
153 .collect()
154 }
155
156 #[cfg(test)]
157 mod tests {
158 use super::*;
159 use crate::pathfinding::find_path;
160
161 const SIZE: UVec2 = UVec2::new(96, 64);
162
163 fn share(map: &WorldMap, terrain: Terrain) -> f32 {
164 let n = map
165 .positions()
166 .filter(|p| map.get(p.as_ivec2()) == Some(terrain))
167 .count();
168 n as f32 / map.size.element_product() as f32
169 }
170
171 #[test]
172 fn same_seed_generates_same_world() {
173 let (a, b, c) = (generate(SIZE, 7), generate(SIZE, 7), generate(SIZE, 8));
174 let tiles = |m: &WorldMap| {
175 m.positions()
176 .map(|p| m.get(p.as_ivec2()))
177 .collect::<Vec<_>>()
178 };
179 assert_eq!(tiles(&a), tiles(&b));
180 assert_ne!(tiles(&a), tiles(&c));
181 }
182
183 // Elevation thresholds come from quantiles rather than fixed values, so every seed gets the
184 // same terrain mix instead of occasionally being all ocean or all mountain.
185 #[test]
186 fn terrain_shares_are_stable_across_seeds() {
187 for seed in 0..5 {
188 let map = generate(SIZE, seed);
189 assert!((share(&map, Terrain::DeepWater) - DEEP_WATER_SHARE).abs() < 0.02);
190 assert!((share(&map, Terrain::Stone) - STONE_SHARE).abs() < 0.02);
191 for terrain in Terrain::ALL {
192 assert!(share(&map, terrain) > 0.0, "seed {seed} lacks {terrain:?}");
193 }
194 }
195 }
196
197 #[test]
198 fn quantile_picks_value_at_share() {
199 let values: Vec<f32> = (0..10).rev().map(|v| v as f32).collect();
200 assert_eq!(quantile(&values, 0.0), 0.0);
201 assert_eq!(quantile(&values, 0.3), 3.0);
202 assert_eq!(quantile(&values, 1.0), 9.0);
203 }
204
205 #[test]
206 fn largest_region_picks_biggest_walkable_area() {
207 let mut map = WorldMap::filled(UVec2::new(6, 3), Terrain::Grass);
208 for y in 0..3 {
209 map.set(UVec2::new(2, y), Terrain::Stone);
210 }
211 let region = largest_region(&map);
212 assert_eq!(region.len(), 9);
213 assert!(region.iter().all(|p| p.x > 2));
214 }
215
216 // Colonists must start somewhere they can all reach each other and most of the map,
217 // not on a small island cut off by deep water or stone.
218 #[test]
219 fn spawn_tiles_are_distinct_walkable_and_mutually_reachable() {
220 for seed in 0..5 {
221 let map = generate(SIZE, seed);
222 let tiles = spawn_tiles(&map, 3);
223 assert_eq!(tiles.len(), 3);
224 let region = largest_region(&map);
225 for t in &tiles {
226 assert!(region.contains(t));
227 assert!(find_path(&map, tiles[0], *t).is_some());
228 }
229 let mut unique = tiles.clone();
230 unique.dedup();
231 assert_eq!(unique.len(), 3);
232 }
233 }
234 }