src/worldgen.rs 17 K · 524 lines · raw · history

1 use std::{
2 cmp::Reverse,
3 collections::{BinaryHeap, VecDeque},
4 };
5
6 use bevy::prelude::*;
7
8 use crate::{
9 noise::Noise,
10 rng::SimRng,
11 world::{MAX_HEIGHT, Plant, Terrain, WorldMap, hash2},
12 };
13
14 pub const WORLD_SIZE: UVec2 = UVec2::new(256, 256);
15 pub const DEFAULT_SEED: u32 = 1;
16
17 const ELEVATION_SCALE: f32 = 1.0 / 48.0;
18 const FERTILITY_SCALE: f32 = 1.0 / 16.0;
19 const DEEP_WATER_SHARE: f32 = 0.10;
20 const SHALLOW_WATER_SHARE: f32 = 0.06;
21 const SAND_SHARE: f32 = 0.04;
22 const STONE_SHARE: f32 = 0.14;
23 const SOIL_SHARE: f32 = 0.20;
24 const ORE_SCALE: f32 = 1.0 / 6.0;
25 const IRON_SHARE_OF_ROCK: f32 = 0.10;
26 const GOLD_SHARE_OF_ROCK: f32 = 0.03;
27 const FOREST_SCALE: f32 = 1.0 / 32.0;
28 const FOREST_SHARE: f32 = 0.35;
29 const FOREST_TREE_PERCENT: u32 = 45;
30 const LONE_TREE_PERCENT: u32 = 3;
31 const RIVER_COUNT: usize = 4;
32 const RIVER_CANDIDATES: usize = 40;
33 const RIVER_SOURCE_SPACING: f32 = 40.0;
34
35 pub struct WorldGenPlugin;
36
37 impl Plugin for WorldGenPlugin {
38 fn build(&self, app: &mut App) {
39 app.insert_resource(WorldSeed(DEFAULT_SEED))
40 .insert_resource(generate(WORLD_SIZE, DEFAULT_SEED))
41 .add_message::<WorldGenerated>()
42 .add_systems(Startup, |mut generated: MessageWriter<WorldGenerated>| {
43 generated.write(WorldGenerated);
44 })
45 .add_systems(Update, regenerate_on_key);
46 }
47 }
48
49 #[derive(Resource, Debug, Clone, Copy, PartialEq)]
50 pub struct WorldSeed(pub u32);
51
52 #[derive(Message, Debug, Clone, Copy)]
53 pub struct WorldGenerated;
54
55 fn regenerate_on_key(
56 keys: Res<ButtonInput<KeyCode>>,
57 mut seed: ResMut<WorldSeed>,
58 mut map: ResMut<WorldMap>,
59 mut generated: MessageWriter<WorldGenerated>,
60 ) {
61 if keys.just_pressed(KeyCode::KeyR) {
62 seed.0 = seed.0.wrapping_add(1);
63 *map = generate(map.size, seed.0);
64 generated.write(WorldGenerated);
65 }
66 }
67
68 pub fn generate(size: UVec2, seed: u32) -> WorldMap {
69 let mut map = WorldMap::filled(size, Terrain::Grass);
70 let positions: Vec<UVec2> = map.positions().collect();
71 let sample = |offset: u32, scale: f32, octaves: u32| -> Vec<f32> {
72 let noise = Noise::new(seed.wrapping_add(offset));
73 positions
74 .iter()
75 .map(|p| noise.fbm(p.as_vec2() * scale, octaves))
76 .collect()
77 };
78 let elevation = sample(0, ELEVATION_SCALE, 5);
79 let fertility = sample(0x1000, FERTILITY_SCALE, 3);
80 let iron = sample(0x2000, ORE_SCALE, 2);
81 let gold = sample(0x3000, ORE_SCALE, 2);
82 let forest = sample(0x4000, FOREST_SCALE, 3);
83
84 let (low, high) = (quantile(&elevation, 0.0), quantile(&elevation, 1.0));
85 for (&pos, &e) in positions.iter().zip(&elevation) {
86 map.set_height(pos, (e - low) / (high - low).max(f32::EPSILON) * MAX_HEIGHT);
87 }
88
89 let deep = quantile(&elevation, DEEP_WATER_SHARE);
90 let shallow = quantile(&elevation, DEEP_WATER_SHARE + SHALLOW_WATER_SHARE);
91 let sand = quantile(
92 &elevation,
93 DEEP_WATER_SHARE + SHALLOW_WATER_SHARE + SAND_SHARE,
94 );
95 let stone = quantile(&elevation, 1.0 - STONE_SHARE);
96 let soil = quantile(&fertility, 1.0 - SOIL_SHARE);
97 let is_rock = |i: usize| elevation[i] >= stone;
98 let rock_values = |values: &[f32]| -> Vec<f32> {
99 (0..values.len())
100 .filter(|&i| is_rock(i))
101 .map(|i| values[i])
102 .collect()
103 };
104 let iron_min = quantile(&rock_values(&iron), 1.0 - IRON_SHARE_OF_ROCK);
105 let gold_min = quantile(&rock_values(&gold), 1.0 - GOLD_SHARE_OF_ROCK);
106
107 for (i, &pos) in positions.iter().enumerate() {
108 let e = elevation[i];
109 let terrain = if e < deep {
110 Terrain::DeepWater
111 } else if e < shallow {
112 Terrain::ShallowWater
113 } else if e < sand {
114 Terrain::Sand
115 } else if is_rock(i) && gold[i] >= gold_min {
116 Terrain::GoldOre
117 } else if is_rock(i) && iron[i] >= iron_min {
118 Terrain::IronOre
119 } else if is_rock(i) {
120 Terrain::Stone
121 } else if fertility[i] >= soil {
122 Terrain::Soil
123 } else {
124 Terrain::Grass
125 };
126 map.set(pos, terrain);
127 }
128
129 for river in pick_rivers(&map, seed) {
130 carve_river(&mut map, &river);
131 }
132
133 let forest_min = quantile(&forest, 1.0 - FOREST_SHARE);
134 for (i, &pos) in positions.iter().enumerate() {
135 let fertile = matches!(
136 map.get(pos.as_ivec2()),
137 Some(Terrain::Grass | Terrain::Soil)
138 );
139 let percent = if forest[i] >= forest_min {
140 FOREST_TREE_PERCENT
141 } else {
142 LONE_TREE_PERCENT
143 };
144 if fertile && hash2(pos.x ^ seed, pos.y) % 100 < percent {
145 map.set_plant(pos, Some(Plant::Tree));
146 }
147 }
148 map
149 }
150
151 fn mountain_feet(map: &WorldMap) -> Vec<UVec2> {
152 map.positions()
153 .filter(|p| {
154 let p = p.as_ivec2();
155 map.move_cost(p).is_some()
156 && !map.get(p).unwrap().is_water()
157 && [IVec2::X, IVec2::NEG_X, IVec2::Y, IVec2::NEG_Y]
158 .iter()
159 .any(|&d| map.get(p + d).is_some_and(Terrain::is_rock))
160 })
161 .collect()
162 }
163
164 pub fn pick_rivers(map: &WorldMap, seed: u32) -> Vec<Vec<UVec2>> {
165 let feet = mountain_feet(map);
166 if feet.is_empty() {
167 return Vec::new();
168 }
169 let flow = FlowField::new(map);
170 let mut rng = SimRng::new(u64::from(seed) ^ 0x5249_5645);
171 let mut rivers: Vec<Vec<UVec2>> = (0..RIVER_CANDIDATES)
172 .map(|_| feet[rng.range_i32(0..feet.len() as i32) as usize])
173 .map(|source| flow.trace(source))
174 .collect();
175 rivers.sort_by_key(|river| Reverse(river.len()));
176 let mut picked: Vec<Vec<UVec2>> = Vec::new();
177 for river in rivers {
178 if picked.len() == RIVER_COUNT {
179 break;
180 }
181 let spaced = picked
182 .iter()
183 .all(|other| other[0].as_vec2().distance(river[0].as_vec2()) >= RIVER_SOURCE_SPACING);
184 if spaced {
185 picked.push(river);
186 }
187 }
188 picked
189 }
190
191 pub struct FlowField {
192 size: UVec2,
193 downstream: Vec<Option<UVec2>>,
194 }
195
196 impl FlowField {
197 pub fn new(map: &WorldMap) -> Self {
198 let n = map.size.element_product() as usize;
199 let index = |p: UVec2| (p.y * map.size.x + p.x) as usize;
200 let mut downstream = vec![None; n];
201 let mut done = vec![false; n];
202 let mut open = BinaryHeap::new();
203 for pos in map.positions() {
204 let p = pos.as_ivec2();
205 let terrain = map.get(p).unwrap();
206 let at_edge =
207 pos.x == 0 || pos.y == 0 || pos.x == map.size.x - 1 || pos.y == map.size.y - 1;
208 if terrain.is_water() || (at_edge && !terrain.is_rock()) {
209 done[index(pos)] = true;
210 open.push(Reverse((map.height(p).unwrap().to_bits(), pos.x, pos.y)));
211 }
212 }
213 while let Some(Reverse((level, x, y))) = open.pop() {
214 let current = UVec2::new(x, y);
215 for step in [IVec2::X, IVec2::NEG_X, IVec2::Y, IVec2::NEG_Y] {
216 let next = current.as_ivec2() + step;
217 if !map.get(next).is_some_and(|t| !t.is_rock()) || done[index(next.as_uvec2())] {
218 continue;
219 }
220 let next = next.as_uvec2();
221 done[index(next)] = true;
222 downstream[index(next)] = Some(current);
223 let filled = map
224 .height(next.as_ivec2())
225 .unwrap()
226 .max(f32::from_bits(level));
227 open.push(Reverse((filled.to_bits(), next.x, next.y)));
228 }
229 }
230 Self {
231 size: map.size,
232 downstream,
233 }
234 }
235
236 fn downstream(&self, pos: UVec2) -> Option<UVec2> {
237 self.downstream[(pos.y * self.size.x + pos.x) as usize]
238 }
239
240 pub fn trace(&self, source: UVec2) -> Vec<UVec2> {
241 let mut path = vec![source];
242 while let Some(next) = self.downstream(*path.last().unwrap()) {
243 path.push(next);
244 }
245 path
246 }
247 }
248
249 fn carve_river(map: &mut WorldMap, path: &[UVec2]) {
250 for (i, &pos) in path.iter().enumerate() {
251 let mut tiles = vec![pos.as_ivec2()];
252 if i >= path.len() / 3 {
253 tiles.push(pos.as_ivec2() + IVec2::X);
254 }
255 if i >= path.len() * 2 / 3 {
256 tiles.push(pos.as_ivec2() + IVec2::Y);
257 }
258 for tile in tiles {
259 if map
260 .get(tile)
261 .is_some_and(|t| !t.is_rock() && t != Terrain::DeepWater)
262 {
263 map.set(tile.as_uvec2(), Terrain::ShallowWater);
264 }
265 }
266 }
267 }
268
269 pub fn quantile(values: &[f32], share: f32) -> f32 {
270 let mut sorted = values.to_vec();
271 sorted.sort_by(f32::total_cmp);
272 let i = ((sorted.len() as f32 * share) as usize).min(sorted.len() - 1);
273 sorted[i]
274 }
275
276 pub fn largest_region(map: &WorldMap) -> Vec<UVec2> {
277 let mut seen = vec![false; map.size.element_product() as usize];
278 let index = |p: UVec2| (p.y * map.size.x + p.x) as usize;
279 let mut best = Vec::new();
280 for start in map.positions() {
281 if seen[index(start)] || map.move_cost(start.as_ivec2()).is_none() {
282 continue;
283 }
284 let region = flood(map, start, |p| {
285 let fresh = !seen[index(p)];
286 seen[index(p)] = true;
287 fresh
288 });
289 if region.len() > best.len() {
290 best = region;
291 }
292 }
293 best
294 }
295
296 fn flood(map: &WorldMap, start: UVec2, mut visit: impl FnMut(UVec2) -> bool) -> Vec<UVec2> {
297 let mut region = Vec::new();
298 let mut queue = VecDeque::from([start]);
299 visit(start);
300 while let Some(pos) = queue.pop_front() {
301 region.push(pos);
302 for step in [IVec2::X, IVec2::NEG_X, IVec2::Y, IVec2::NEG_Y] {
303 let next = pos.as_ivec2() + step;
304 if map.move_cost(next).is_some() && visit(next.as_uvec2()) {
305 queue.push_back(next.as_uvec2());
306 }
307 }
308 }
309 region
310 }
311
312 pub fn spawn_tiles(map: &WorldMap, count: usize) -> Vec<UVec2> {
313 let center = map.size.as_vec2() / 2.0;
314 let Some(&origin) = largest_region(map).iter().min_by(|a, b| {
315 a.as_vec2()
316 .distance_squared(center)
317 .total_cmp(&b.as_vec2().distance_squared(center))
318 }) else {
319 return Vec::new();
320 };
321 let mut seen = std::collections::HashSet::new();
322 flood(map, origin, |p| seen.insert(p))
323 .into_iter()
324 .step_by(2)
325 .take(count)
326 .collect()
327 }
328
329 #[cfg(test)]
330 mod tests {
331 use super::*;
332 use crate::pathfinding::find_path;
333
334 const SIZE: UVec2 = UVec2::new(96, 64);
335
336 fn share(map: &WorldMap, terrain: Terrain) -> f32 {
337 let n = map
338 .positions()
339 .filter(|p| map.get(p.as_ivec2()) == Some(terrain))
340 .count();
341 n as f32 / map.size.element_product() as f32
342 }
343
344 #[test]
345 fn same_seed_generates_same_world() {
346 let (a, b, c) = (generate(SIZE, 7), generate(SIZE, 7), generate(SIZE, 8));
347 let tiles = |m: &WorldMap| {
348 m.positions()
349 .map(|p| {
350 let p = p.as_ivec2();
351 (m.get(p), m.plant(p), m.height(p).map(f32::to_bits))
352 })
353 .collect::<Vec<_>>()
354 };
355 assert_eq!(tiles(&a), tiles(&b));
356 assert_ne!(tiles(&a), tiles(&c));
357 }
358
359 // Elevation thresholds come from quantiles rather than fixed values, so every seed gets the
360 // same terrain mix instead of occasionally being all ocean or all mountain.
361 #[test]
362 fn terrain_shares_are_stable_across_seeds() {
363 for seed in 0..5 {
364 let map = generate(SIZE, seed);
365 assert!((share(&map, Terrain::DeepWater) - DEEP_WATER_SHARE).abs() < 0.02);
366 let rock: f32 = [Terrain::Stone, Terrain::IronOre, Terrain::GoldOre]
367 .iter()
368 .map(|&t| share(&map, t))
369 .sum();
370 assert!((rock - STONE_SHARE).abs() < 0.02);
371 for terrain in Terrain::ALL {
372 assert!(share(&map, terrain) > 0.0, "seed {seed} lacks {terrain:?}");
373 }
374 }
375 }
376
377 #[test]
378 fn gold_is_rarer_than_iron() {
379 let map = generate(SIZE, 3);
380 assert!(share(&map, Terrain::GoldOre) < share(&map, Terrain::IronOre));
381 }
382
383 #[test]
384 fn mountains_are_the_highest_ground() {
385 let map = generate(SIZE, 4);
386 let mean_height = |pred: fn(Terrain) -> bool| {
387 let hs: Vec<f32> = map
388 .positions()
389 .map(|p| p.as_ivec2())
390 .filter(|&p| pred(map.get(p).unwrap()))
391 .map(|p| map.height(p).unwrap())
392 .collect();
393 hs.iter().sum::<f32>() / hs.len() as f32
394 };
395 assert!(mean_height(Terrain::is_rock) > mean_height(|t| t == Terrain::Grass));
396 assert!(mean_height(|t| t == Terrain::Grass) > mean_height(|t| t == Terrain::DeepWater));
397 assert!(
398 map.positions()
399 .all(|p| (0.0..=MAX_HEIGHT).contains(&map.height(p.as_ivec2()).unwrap()))
400 );
401 }
402
403 #[test]
404 fn trees_only_grow_on_grass_and_soil() {
405 let map = generate(SIZE, 2);
406 let trees: Vec<_> = map
407 .positions()
408 .map(|p| p.as_ivec2())
409 .filter(|&p| map.plant(p) == Some(Plant::Tree))
410 .collect();
411 assert!(!trees.is_empty());
412 assert!(
413 trees
414 .iter()
415 .all(|&p| matches!(map.get(p), Some(Terrain::Grass | Terrain::Soil)))
416 );
417 }
418
419 fn slope_map() -> WorldMap {
420 let mut map = WorldMap::filled(UVec2::new(10, 5), Terrain::Grass);
421 for pos in map.positions() {
422 map.set_height(pos, pos.x as f32);
423 if pos.x == 0 {
424 map.set(pos, Terrain::DeepWater);
425 }
426 }
427 map
428 }
429
430 #[test]
431 fn rivers_flow_downhill_into_water() {
432 let map = slope_map();
433 let path = FlowField::new(&map).trace(UVec2::new(8, 2));
434 assert_eq!(
435 map.get(path.last().unwrap().as_ivec2()),
436 Some(Terrain::DeepWater)
437 );
438 assert!(path.windows(2).all(|w| w[1].x < w[0].x));
439 }
440
441 // Rivers are carved into the terrain after rock is placed; flowing through mountains would
442 // leave walkable water channels cutting through what should be solid stone.
443 #[test]
444 fn rivers_route_around_rock() {
445 let mut map = slope_map();
446 map.set(UVec2::new(5, 2), Terrain::Stone);
447 let path = FlowField::new(&map).trace(UVec2::new(8, 2));
448 assert!(
449 path.iter()
450 .all(|p| !map.get(p.as_ivec2()).unwrap().is_rock())
451 );
452 assert_eq!(
453 map.get(path.last().unwrap().as_ivec2()),
454 Some(Terrain::DeepWater)
455 );
456 }
457
458 // Noise terrain is full of small dips. Flow directions come from a priority flood that
459 // spills out of dips at their lowest rim, so rivers cross them instead of ending in (or
460 // meandering around inside) every depression.
461 #[test]
462 fn rivers_cross_depressions_to_reach_water() {
463 let mut map = slope_map();
464 map.set_height(UVec2::new(5, 2), 0.5);
465 let path = FlowField::new(&map).trace(UVec2::new(8, 2));
466 assert_eq!(
467 map.get(path.last().unwrap().as_ivec2()),
468 Some(Terrain::DeepWater)
469 );
470 assert!(path.len() <= 9);
471 }
472
473 #[test]
474 fn generated_worlds_have_rivers() {
475 let map = generate(WORLD_SIZE, 1);
476 assert!(share(&map, Terrain::ShallowWater) > SHALLOW_WATER_SHARE + 0.005);
477 }
478
479 #[test]
480 fn longest_candidate_rivers_are_picked() {
481 let map = generate(WORLD_SIZE, 1);
482 let rivers = pick_rivers(&map, 1);
483 assert!(!rivers.is_empty() && rivers.len() <= RIVER_COUNT);
484 assert!(rivers.windows(2).all(|w| w[0].len() >= w[1].len()));
485 }
486
487 #[test]
488 fn quantile_picks_value_at_share() {
489 let values: Vec<f32> = (0..10).rev().map(|v| v as f32).collect();
490 assert_eq!(quantile(&values, 0.0), 0.0);
491 assert_eq!(quantile(&values, 0.3), 3.0);
492 assert_eq!(quantile(&values, 1.0), 9.0);
493 }
494
495 #[test]
496 fn largest_region_picks_biggest_walkable_area() {
497 let mut map = WorldMap::filled(UVec2::new(6, 3), Terrain::Grass);
498 for y in 0..3 {
499 map.set(UVec2::new(2, y), Terrain::Stone);
500 }
501 let region = largest_region(&map);
502 assert_eq!(region.len(), 9);
503 assert!(region.iter().all(|p| p.x > 2));
504 }
505
506 // Colonists must start somewhere they can all reach each other and most of the map,
507 // not on a small island cut off by deep water or stone.
508 #[test]
509 fn spawn_tiles_are_distinct_walkable_and_mutually_reachable() {
510 for seed in 0..5 {
511 let map = generate(SIZE, seed);
512 let tiles = spawn_tiles(&map, 3);
513 assert_eq!(tiles.len(), 3);
514 let region = largest_region(&map);
515 for t in &tiles {
516 assert!(region.contains(t));
517 assert!(find_path(&map, tiles[0], *t).is_some());
518 }
519 let mut unique = tiles.clone();
520 unique.dedup();
521 assert_eq!(unique.len(), 3);
522 }
523 }
524 }