src/worldgen.rs 18.4 K · 558 lines · raw · history

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