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