veloren_world/civ/
mod.rs

1#![expect(dead_code)]
2
3pub mod airship_travel;
4mod econ;
5
6use crate::{
7    Index, IndexRef, Land,
8    civ::airship_travel::Airships,
9    config::CONFIG,
10    sim::WorldSim,
11    site::{self, Site as WorldSite, SiteKind, SitesGenMeta, namegen::NameGen},
12    util::{DHashMap, NEIGHBORS, attempt, seed_expan},
13};
14use common::{
15    astar::Astar,
16    calendar::Calendar,
17    path::Path,
18    spiral::Spiral2d,
19    store::{Id, Store},
20    terrain::{BiomeKind, CoordinateConversions, MapSizeLg, TerrainChunkSize, uniform_idx_as_vec2},
21    vol::RectVolSize,
22};
23use common_base::prof_span;
24use core::{fmt, hash::BuildHasherDefault, ops::Range};
25use fxhash::FxHasher64;
26use rand::prelude::*;
27use rand_chacha::ChaChaRng;
28use tracing::{debug, info, warn};
29use vek::*;
30
31fn initial_civ_count(map_size_lg: MapSizeLg) -> u32 {
32    // NOTE: since map_size_lg's dimensions must fit in a u16, we can safely add
33    // them here.
34    //
35    // NOTE: 48 at "default" scale of 10 × 10 chunk bits (1024 × 1024 chunks).
36    let cnt = (3 << (map_size_lg.vec().x + map_size_lg.vec().y)) >> 16;
37    cnt.max(1) // we need at least one civ in order to generate a starting site
38}
39
40#[derive(Default)]
41pub struct Civs {
42    pub civs: Store<Civ>,
43    pub places: Store<Place>,
44    pub pois: Store<PointOfInterest>,
45
46    pub tracks: Store<Track>,
47    /// We use this hasher (FxHasher64) because
48    /// (1) we don't care about DDOS attacks (ruling out SipHash);
49    /// (2) we care about determinism across computers (ruling out AAHash);
50    /// (3) we have 8-byte keys (for which FxHash is fastest).
51    pub track_map: DHashMap<Id<Site>, DHashMap<Id<Site>, Id<Track>>>,
52
53    pub bridges: DHashMap<Vec2<i32>, (Vec2<i32>, Id<Site>)>,
54
55    pub sites: Store<Site>,
56    pub airships: Airships,
57}
58
59// Change this to get rid of particularly horrid seeds
60const SEED_SKIP: u8 = 5;
61const POI_THINNING_DIST_SQRD: i32 = 300;
62
63pub struct GenCtx<'a, R: Rng> {
64    sim: &'a mut WorldSim,
65    rng: R,
66}
67
68struct ProximitySpec {
69    location: Vec2<i32>,
70    min_distance: Option<i32>,
71    max_distance: Option<i32>,
72}
73
74impl ProximitySpec {
75    pub fn satisfied_by(&self, site: Vec2<i32>) -> bool {
76        let distance_squared = site.distance_squared(self.location);
77        let min_ok = self
78            .min_distance
79            .map(|mind| distance_squared > (mind * mind))
80            .unwrap_or(true);
81        let max_ok = self
82            .max_distance
83            .map(|maxd| distance_squared < (maxd * maxd))
84            .unwrap_or(true);
85        min_ok && max_ok
86    }
87
88    pub fn avoid(location: Vec2<i32>, min_distance: i32) -> Self {
89        ProximitySpec {
90            location,
91            min_distance: Some(min_distance),
92            max_distance: None,
93        }
94    }
95
96    pub fn be_near(location: Vec2<i32>, max_distance: i32) -> Self {
97        ProximitySpec {
98            location,
99            min_distance: None,
100            max_distance: Some(max_distance),
101        }
102    }
103}
104
105struct ProximityRequirementsBuilder {
106    all_of: Vec<ProximitySpec>,
107    any_of: Vec<ProximitySpec>,
108}
109
110impl ProximityRequirementsBuilder {
111    pub fn finalize(self, world_dims: &Aabr<i32>) -> ProximityRequirements {
112        let location_hint = self.location_hint(world_dims);
113        ProximityRequirements {
114            all_of: self.all_of,
115            any_of: self.any_of,
116            location_hint,
117        }
118    }
119
120    fn location_hint(&self, world_dims: &Aabr<i32>) -> Aabr<i32> {
121        let bounding_box_of_point = |point: Vec2<i32>, max_distance: i32| Aabr {
122            min: Vec2 {
123                x: point.x - max_distance,
124                y: point.y - max_distance,
125            },
126            max: Vec2 {
127                x: point.x + max_distance,
128                y: point.y + max_distance,
129            },
130        };
131        let any_of_hint = self
132            .any_of
133            .iter()
134            .fold(None, |acc, spec| match spec.max_distance {
135                None => acc,
136                Some(max_distance) => {
137                    let bounding_box_of_new_point =
138                        bounding_box_of_point(spec.location, max_distance);
139                    match acc {
140                        None => Some(bounding_box_of_new_point),
141                        Some(acc) => Some(acc.union(bounding_box_of_new_point)),
142                    }
143                },
144            })
145            .map(|hint| hint.intersection(*world_dims))
146            .unwrap_or_else(|| world_dims.to_owned());
147        let hint = self
148            .all_of
149            .iter()
150            .fold(any_of_hint, |acc, spec| match spec.max_distance {
151                None => acc,
152                Some(max_distance) => {
153                    let bounding_box_of_new_point =
154                        bounding_box_of_point(spec.location, max_distance);
155                    acc.intersection(bounding_box_of_new_point)
156                },
157            });
158        hint
159    }
160
161    pub fn new() -> Self {
162        Self {
163            all_of: Vec::new(),
164            any_of: Vec::new(),
165        }
166    }
167
168    pub fn avoid_all_of(
169        mut self,
170        locations: impl Iterator<Item = Vec2<i32>>,
171        distance: i32,
172    ) -> Self {
173        let specs = locations.map(|loc| ProximitySpec::avoid(loc, distance));
174        self.all_of.extend(specs);
175        self
176    }
177
178    pub fn close_to_one_of(
179        mut self,
180        locations: impl Iterator<Item = Vec2<i32>>,
181        distance: i32,
182    ) -> Self {
183        let specs = locations.map(|loc| ProximitySpec::be_near(loc, distance));
184        self.any_of.extend(specs);
185        self
186    }
187}
188
189struct ProximityRequirements {
190    all_of: Vec<ProximitySpec>,
191    any_of: Vec<ProximitySpec>,
192    location_hint: Aabr<i32>,
193}
194
195impl ProximityRequirements {
196    pub fn satisfied_by(&self, site: Vec2<i32>) -> bool {
197        if self.location_hint.contains_point(site) {
198            let all_of_compliance = self.all_of.iter().all(|spec| spec.satisfied_by(site));
199            let any_of_compliance =
200                self.any_of.is_empty() || self.any_of.iter().any(|spec| spec.satisfied_by(site));
201            all_of_compliance && any_of_compliance
202        } else {
203            false
204        }
205    }
206}
207
208impl<R: Rng> GenCtx<'_, R> {
209    pub fn reseed(&mut self) -> GenCtx<'_, impl Rng + use<R>> {
210        let mut entropy = self.rng.gen::<[u8; 32]>();
211        entropy[0] = entropy[0].wrapping_add(SEED_SKIP); // Skip bad seeds
212        GenCtx {
213            sim: self.sim,
214            rng: ChaChaRng::from_seed(entropy),
215        }
216    }
217}
218
219#[derive(Debug)]
220pub enum WorldCivStage {
221    /// Civilization creation, how many out of how many civilizations have been
222    /// generated yet
223    CivCreation(u32, u32),
224    SiteGeneration,
225}
226
227impl Civs {
228    pub fn generate(
229        seed: u32,
230        sim: &mut WorldSim,
231        index: &mut Index,
232        calendar: Option<&Calendar>,
233        report_stage: &dyn Fn(WorldCivStage),
234    ) -> Self {
235        prof_span!("Civs::generate");
236        let mut this = Self::default();
237        let rng = ChaChaRng::from_seed(seed_expan::rng_state(seed));
238        let name_rng = rng.clone();
239        let mut name_ctx = GenCtx { sim, rng: name_rng };
240        if index.features().peak_naming {
241            info!("starting peak naming");
242            this.name_peaks(&mut name_ctx);
243        }
244        if index.features().biome_naming {
245            info!("starting biome naming");
246            this.name_biomes(&mut name_ctx);
247        }
248
249        let initial_civ_count = initial_civ_count(sim.map_size_lg());
250        let mut ctx = GenCtx { sim, rng };
251
252        // info!("starting cave generation");
253        // this.generate_caves(&mut ctx);
254
255        info!("starting civilisation creation");
256        prof_span!(guard, "create civs");
257        for i in 0..initial_civ_count {
258            prof_span!("create civ");
259            debug!("Creating civilisation...");
260            if this.birth_civ(&mut ctx.reseed()).is_none() {
261                warn!("Failed to find starting site for civilisation.");
262            }
263            report_stage(WorldCivStage::CivCreation(i, initial_civ_count));
264        }
265        drop(guard);
266        info!(?initial_civ_count, "all civilisations created");
267
268        report_stage(WorldCivStage::SiteGeneration);
269        prof_span!(guard, "find locations and establish sites");
270        let world_dims = ctx.sim.get_aabr();
271        for _ in 0..initial_civ_count * 3 {
272            attempt(5, || {
273                let (loc, kind) = match ctx.rng.gen_range(0..116) {
274                    0..=4 => (
275                        find_site_loc(
276                            &mut ctx,
277                            &ProximityRequirementsBuilder::new()
278                                .avoid_all_of(this.tree_enemies(), 40)
279                                .finalize(&world_dims),
280                            &SiteKind::GiantTree,
281                        )?,
282                        SiteKind::GiantTree,
283                    ),
284                    5..=15 => (
285                        find_site_loc(
286                            &mut ctx,
287                            &ProximityRequirementsBuilder::new()
288                                .avoid_all_of(this.gnarling_enemies(), 40)
289                                .finalize(&world_dims),
290                            &SiteKind::Gnarling,
291                        )?,
292                        SiteKind::Gnarling,
293                    ),
294                    16..=20 => (
295                        find_site_loc(
296                            &mut ctx,
297                            &ProximityRequirementsBuilder::new()
298                                .avoid_all_of(this.chapel_site_enemies(), 40)
299                                .finalize(&world_dims),
300                            &SiteKind::ChapelSite,
301                        )?,
302                        SiteKind::ChapelSite,
303                    ),
304                    21..=27 => (
305                        find_site_loc(
306                            &mut ctx,
307                            &ProximityRequirementsBuilder::new()
308                                .avoid_all_of(this.gnarling_enemies(), 40)
309                                .finalize(&world_dims),
310                            &SiteKind::Adlet,
311                        )?,
312                        SiteKind::Adlet,
313                    ),
314                    28..=38 => (
315                        find_site_loc(
316                            &mut ctx,
317                            &ProximityRequirementsBuilder::new()
318                                .avoid_all_of(this.pirate_hideout_enemies(), 40)
319                                .finalize(&world_dims),
320                            &SiteKind::PirateHideout,
321                        )?,
322                        SiteKind::PirateHideout,
323                    ),
324                    39..=45 => (
325                        find_site_loc(
326                            &mut ctx,
327                            &ProximityRequirementsBuilder::new()
328                                .avoid_all_of(this.jungle_ruin_enemies(), 40)
329                                .finalize(&world_dims),
330                            &SiteKind::JungleRuin,
331                        )?,
332                        SiteKind::JungleRuin,
333                    ),
334                    46..=55 => (
335                        find_site_loc(
336                            &mut ctx,
337                            &ProximityRequirementsBuilder::new()
338                                .avoid_all_of(this.rock_circle_enemies(), 40)
339                                .finalize(&world_dims),
340                            &SiteKind::RockCircle,
341                        )?,
342                        SiteKind::RockCircle,
343                    ),
344                    56..=66 => (
345                        find_site_loc(
346                            &mut ctx,
347                            &ProximityRequirementsBuilder::new()
348                                .avoid_all_of(this.troll_cave_enemies(), 40)
349                                .finalize(&world_dims),
350                            &SiteKind::TrollCave,
351                        )?,
352                        SiteKind::TrollCave,
353                    ),
354                    67..=72 => (
355                        find_site_loc(
356                            &mut ctx,
357                            &ProximityRequirementsBuilder::new()
358                                .avoid_all_of(this.camp_enemies(), 40)
359                                .finalize(&world_dims),
360                            &SiteKind::Camp,
361                        )?,
362                        SiteKind::Camp,
363                    ),
364                    73..=76 => (
365                        find_site_loc(
366                            &mut ctx,
367                            &ProximityRequirementsBuilder::new()
368                                .avoid_all_of(this.mine_site_enemies(), 40)
369                                .finalize(&world_dims),
370                            &SiteKind::Haniwa,
371                        )?,
372                        SiteKind::Haniwa,
373                    ),
374                    77..=81 => (
375                        find_site_loc(
376                            &mut ctx,
377                            &ProximityRequirementsBuilder::new()
378                                .avoid_all_of(this.terracotta_enemies(), 40)
379                                .finalize(&world_dims),
380                            &SiteKind::Terracotta,
381                        )?,
382                        SiteKind::Terracotta,
383                    ),
384                    82..=87 => (
385                        find_site_loc(
386                            &mut ctx,
387                            &ProximityRequirementsBuilder::new()
388                                .avoid_all_of(this.mine_site_enemies(), 40)
389                                .finalize(&world_dims),
390                            &SiteKind::DwarvenMine,
391                        )?,
392                        SiteKind::DwarvenMine,
393                    ),
394                    88..=91 => (
395                        find_site_loc(
396                            &mut ctx,
397                            &ProximityRequirementsBuilder::new()
398                                .avoid_all_of(this.cultist_enemies(), 40)
399                                .finalize(&world_dims),
400                            &SiteKind::Cultist,
401                        )?,
402                        SiteKind::Cultist,
403                    ),
404                    92..=96 => (
405                        find_site_loc(
406                            &mut ctx,
407                            &ProximityRequirementsBuilder::new()
408                                .avoid_all_of(this.sahagin_enemies(), 40)
409                                .finalize(&world_dims),
410                            &SiteKind::Sahagin,
411                        )?,
412                        SiteKind::Sahagin,
413                    ),
414                    97..=102 => (
415                        find_site_loc(
416                            &mut ctx,
417                            &ProximityRequirementsBuilder::new()
418                                .avoid_all_of(this.vampire_castle_enemies(), 40)
419                                .finalize(&world_dims),
420                            &SiteKind::VampireCastle,
421                        )?,
422                        SiteKind::VampireCastle,
423                    ),
424                    103..108 => (
425                        find_site_loc(
426                            &mut ctx,
427                            &ProximityRequirementsBuilder::new().finalize(&world_dims),
428                            &SiteKind::GliderCourse,
429                        )?,
430                        SiteKind::GliderCourse,
431                    ),
432                    /*103..=108 => (
433                        find_site_loc(
434                            &mut ctx,
435                            &ProximityRequirementsBuilder::new()
436                                .avoid_all_of(this.castle_enemies(), 40)
437                                .close_to_one_of(this.towns(), 20)
438                                .finalize(&world_dims),
439                            &SiteKind::Castle,
440                        )?,
441                        SiteKind::Castle,
442                    ),
443                    109..=114 => (SiteKind::Citadel, (&castle_enemies, 20)),
444                    */
445                    _ => (
446                        find_site_loc(
447                            &mut ctx,
448                            &ProximityRequirementsBuilder::new()
449                                .avoid_all_of(this.myrmidon_enemies(), 40)
450                                .finalize(&world_dims),
451                            &SiteKind::Myrmidon,
452                        )?,
453                        SiteKind::Myrmidon,
454                    ),
455                };
456                Some(this.establish_site(&mut ctx.reseed(), loc, |place| Site {
457                    kind,
458                    center: loc,
459                    place,
460                    site_tmp: None,
461                }))
462            });
463        }
464        drop(guard);
465
466        // Tick
467        //=== old economy is gone
468
469        // Flatten ground around sites
470        prof_span!(guard, "Flatten ground around sites");
471        for site in this.sites.values() {
472            let wpos = site.center * TerrainChunkSize::RECT_SIZE.map(|e: u32| e as i32);
473
474            let (radius, flatten_radius) = match &site.kind {
475                SiteKind::Refactor => (32i32, 10.0),
476                SiteKind::CliffTown => (2i32, 1.0),
477                SiteKind::SavannahTown => (48i32, 25.0),
478                SiteKind::CoastalTown => (64i32, 35.0),
479                SiteKind::JungleRuin => (8i32, 3.0),
480                SiteKind::DesertCity => (64i32, 25.0),
481                SiteKind::ChapelSite => (36i32, 10.0),
482                SiteKind::Terracotta => (64i32, 35.0),
483                SiteKind::GiantTree => (12i32, 8.0),
484                SiteKind::Gnarling => (16i32, 10.0),
485                SiteKind::Citadel => (16i32, 0.0),
486                SiteKind::Bridge(_, _) => (0, 0.0),
487                SiteKind::Adlet => (16i32, 0.0),
488                SiteKind::Haniwa => (32i32, 16.0),
489                SiteKind::PirateHideout => (8i32, 3.0),
490                SiteKind::RockCircle => (8i32, 3.0),
491                SiteKind::TrollCave => (4i32, 1.5),
492                SiteKind::Camp => (4i32, 1.5),
493                SiteKind::DwarvenMine => (8i32, 3.0),
494                SiteKind::Cultist => (24i32, 10.0),
495                SiteKind::Sahagin => (8i32, 3.0),
496                SiteKind::VampireCastle => (10i32, 16.0),
497                SiteKind::GliderCourse => (0, 0.0),
498                SiteKind::Myrmidon => (64i32, 35.0),
499            };
500
501            // Flatten ground
502            if let Some(center_alt) = ctx.sim.get_alt_approx(wpos) {
503                for offs in Spiral2d::new().take(radius.pow(2) as usize) {
504                    let pos = site.center + offs;
505                    let factor = ((1.0
506                        - (site.center - pos).map(|e| e as f32).magnitude()
507                            / f32::max(flatten_radius, 0.01))
508                        * 1.25)
509                        .min(1.0);
510                    let rng = &mut ctx.rng;
511                    ctx.sim
512                        .get_mut(pos)
513                        // Don't disrupt chunks that are near water
514                        .filter(|chunk| !chunk.river.near_water())
515                        .map(|chunk| {
516                            let diff = Lerp::lerp_precise(chunk.alt, center_alt, factor) - chunk.alt;
517                            // Make sure we don't fall below sea level (fortunately, we don't have
518                            // to worry about the case where water_alt is already set to a correct
519                            // value higher than alt, since this chunk should have been filtered
520                            // out in that case).
521                            chunk.water_alt = CONFIG.sea_level.max(chunk.water_alt + diff);
522                            chunk.alt += diff;
523                            chunk.basement += diff;
524                            chunk.rockiness = 0.0;
525                            chunk.surface_veg *= 1.0 - factor * rng.gen_range(0.25..0.9);
526                        });
527                }
528            }
529        }
530        drop(guard);
531
532        // Place sites in world
533        prof_span!(guard, "Place sites in world");
534        let mut cnt = 0;
535        let mut gen_meta = SitesGenMeta::new(seed);
536        for sim_site in this.sites.values_mut() {
537            cnt += 1;
538            let wpos = sim_site
539                .center
540                .map2(TerrainChunkSize::RECT_SIZE, |e, sz: u32| {
541                    e * sz as i32 + sz as i32 / 2
542                });
543
544            let mut rng = ctx.reseed().rng;
545            let site = index.sites.insert({
546                let index_ref = IndexRef {
547                    colors: &index.colors(),
548                    features: &index.features(),
549                    index,
550                };
551                match &sim_site.kind {
552                    SiteKind::Refactor => {
553                        let size = Lerp::lerp(0.03, 1.0, rng.gen_range(0.0..1f32).powi(5));
554                        WorldSite::generate_city(
555                            &Land::from_sim(ctx.sim),
556                            index_ref,
557                            &mut rng,
558                            wpos,
559                            size,
560                            calendar,
561                            &mut gen_meta,
562                        )
563                    },
564                    SiteKind::GliderCourse => WorldSite::generate_glider_course(
565                        &Land::from_sim(ctx.sim),
566                        index_ref,
567                        &mut rng,
568                        wpos,
569                    ),
570                    SiteKind::CliffTown => WorldSite::generate_cliff_town(
571                        &Land::from_sim(ctx.sim),
572                        index_ref,
573                        &mut rng,
574                        wpos,
575                        &mut gen_meta,
576                    ),
577                    SiteKind::SavannahTown => WorldSite::generate_savannah_town(
578                        &Land::from_sim(ctx.sim),
579                        index_ref,
580                        &mut rng,
581                        wpos,
582                        &mut gen_meta,
583                    ),
584                    SiteKind::CoastalTown => WorldSite::generate_coastal_town(
585                        &Land::from_sim(ctx.sim),
586                        index_ref,
587                        &mut rng,
588                        wpos,
589                        &mut gen_meta,
590                    ),
591                    SiteKind::PirateHideout => {
592                        WorldSite::generate_pirate_hideout(&Land::from_sim(ctx.sim), &mut rng, wpos)
593                    },
594                    SiteKind::JungleRuin => {
595                        WorldSite::generate_jungle_ruin(&Land::from_sim(ctx.sim), &mut rng, wpos)
596                    },
597                    SiteKind::RockCircle => {
598                        WorldSite::generate_rock_circle(&Land::from_sim(ctx.sim), &mut rng, wpos)
599                    },
600
601                    SiteKind::TrollCave => {
602                        WorldSite::generate_troll_cave(&Land::from_sim(ctx.sim), &mut rng, wpos)
603                    },
604                    SiteKind::Camp => {
605                        WorldSite::generate_camp(&Land::from_sim(ctx.sim), &mut rng, wpos)
606                    },
607                    SiteKind::DesertCity => WorldSite::generate_desert_city(
608                        &Land::from_sim(ctx.sim),
609                        index_ref,
610                        &mut rng,
611                        wpos,
612                        &mut gen_meta,
613                    ),
614                    SiteKind::GiantTree => {
615                        WorldSite::generate_giant_tree(&Land::from_sim(ctx.sim), &mut rng, wpos)
616                    },
617                    SiteKind::Gnarling => {
618                        WorldSite::generate_gnarling(&Land::from_sim(ctx.sim), &mut rng, wpos)
619                    },
620                    SiteKind::DwarvenMine => {
621                        WorldSite::generate_mine(&Land::from_sim(ctx.sim), &mut rng, wpos)
622                    },
623                    SiteKind::ChapelSite => {
624                        WorldSite::generate_chapel_site(&Land::from_sim(ctx.sim), &mut rng, wpos)
625                    },
626                    SiteKind::Terracotta => WorldSite::generate_terracotta(
627                        &Land::from_sim(ctx.sim),
628                        index_ref,
629                        &mut rng,
630                        wpos,
631                        &mut gen_meta,
632                    ),
633                    SiteKind::Citadel => {
634                        WorldSite::generate_citadel(&Land::from_sim(ctx.sim), &mut rng, wpos)
635                    },
636                    SiteKind::Bridge(a, b) => {
637                        let mut bridge_site = WorldSite::generate_bridge(
638                            &Land::from_sim(ctx.sim),
639                            index_ref,
640                            &mut rng,
641                            *a,
642                            *b,
643                        );
644
645                        // Update the path connecting to the bridge to line up better.
646                        if let Some(bridge) =
647                            bridge_site
648                                .plots
649                                .values()
650                                .find_map(|plot| match &plot.kind {
651                                    site::PlotKind::Bridge(bridge) => Some(bridge),
652                                    _ => None,
653                                })
654                        {
655                            let mut update_offset = |original: Vec2<i32>, new: Vec2<i32>| {
656                                let chunk = original.wpos_to_cpos();
657                                if let Some(c) = ctx.sim.get_mut(chunk) {
658                                    c.path.0.offset = (new - chunk.cpos_to_wpos_center())
659                                        .map(|e| e.clamp(-16, 16) as i8);
660                                }
661                            };
662
663                            update_offset(bridge.original_start, bridge.start.xy());
664                            update_offset(bridge.original_end, bridge.end.xy());
665                        }
666                        bridge_site.demarcate_obstacles(&Land::from_sim(ctx.sim));
667                        bridge_site
668                    },
669                    SiteKind::Adlet => WorldSite::generate_adlet(
670                        &Land::from_sim(ctx.sim),
671                        &mut rng,
672                        wpos,
673                        index_ref,
674                    ),
675                    SiteKind::Haniwa => {
676                        WorldSite::generate_haniwa(&Land::from_sim(ctx.sim), &mut rng, wpos)
677                    },
678                    SiteKind::Cultist => {
679                        WorldSite::generate_cultist(&Land::from_sim(ctx.sim), &mut rng, wpos)
680                    },
681                    SiteKind::Myrmidon => WorldSite::generate_myrmidon(
682                        &Land::from_sim(ctx.sim),
683                        index_ref,
684                        &mut rng,
685                        wpos,
686                        &mut gen_meta,
687                    ),
688                    SiteKind::Sahagin => WorldSite::generate_sahagin(
689                        &Land::from_sim(ctx.sim),
690                        index_ref,
691                        &mut rng,
692                        wpos,
693                    ),
694                    SiteKind::VampireCastle => {
695                        WorldSite::generate_vampire_castle(&Land::from_sim(ctx.sim), &mut rng, wpos)
696                    },
697                }
698            });
699            sim_site.site_tmp = Some(site);
700            let site_ref = &index.sites[site];
701
702            let radius_chunks =
703                (site_ref.radius() / TerrainChunkSize::RECT_SIZE.x as f32).ceil() as usize;
704            for pos in Spiral2d::new()
705                .map(|offs| sim_site.center + offs)
706                .take((radius_chunks * 2).pow(2))
707            {
708                ctx.sim.get_mut(pos).map(|chunk| chunk.sites.push(site));
709            }
710            debug!(?sim_site.center, "Placed site at location");
711        }
712        drop(guard);
713        info!(?cnt, "all sites placed");
714        gen_meta.log();
715
716        //this.display_info();
717
718        // remember neighbor information in economy
719        for (s1, val) in this.track_map.iter() {
720            if let Some(index1) = this.sites.get(*s1).site_tmp {
721                for (s2, t) in val.iter() {
722                    if let Some(index2) = this.sites.get(*s2).site_tmp {
723                        if index.sites.get(index1).do_economic_simulation()
724                            && index.sites.get(index2).do_economic_simulation()
725                        {
726                            let cost = this.tracks.get(*t).path.len();
727                            index
728                                .sites
729                                .get_mut(index1)
730                                .economy_mut()
731                                .add_neighbor(index2, cost);
732                            index
733                                .sites
734                                .get_mut(index2)
735                                .economy_mut()
736                                .add_neighbor(index1, cost);
737                        }
738                    }
739                }
740            }
741        }
742
743        // TODO: this looks optimizable
744
745        // collect natural resources
746        prof_span!(guard, "collect natural resources");
747        let sites = &mut index.sites;
748        (0..ctx.sim.map_size_lg().chunks_len()).for_each(|posi| {
749            let chpos = uniform_idx_as_vec2(ctx.sim.map_size_lg(), posi);
750            let wpos = chpos.map(|e| e as i64) * TerrainChunkSize::RECT_SIZE.map(|e| e as i64);
751            let closest_site = (*sites)
752                .iter_mut()
753                .filter(|s| !matches!(s.1.kind, Some(crate::site::SiteKind::Myrmidon)))
754                .min_by_key(|(_id, s)| s.origin.map(|e| e as i64).distance_squared(wpos));
755            if let Some((_id, s)) = closest_site
756                && s.do_economic_simulation()
757            {
758                let distance_squared = s.origin.map(|e| e as i64).distance_squared(wpos);
759                s.economy_mut()
760                    .add_chunk(ctx.sim.get(chpos).unwrap(), distance_squared);
761            }
762        });
763        drop(guard);
764
765        prof_span!(guard, "generate airship routes");
766        this.airships
767            .generate_airship_routes(sites, sim, index.seed);
768        drop(guard);
769
770        sites.iter_mut().for_each(|(_, s)| {
771            if let Some(econ) = s.economy.as_mut() {
772                econ.cache_economy()
773            }
774        });
775
776        this
777    }
778
779    pub fn place(&self, id: Id<Place>) -> &Place { self.places.get(id) }
780
781    pub fn sites(&self) -> impl Iterator<Item = &Site> + '_ { self.sites.values() }
782
783    #[expect(dead_code)]
784    fn display_info(&self) {
785        for (id, civ) in self.civs.iter() {
786            println!("# Civilisation {:?}", id);
787            println!("Name: <unnamed>");
788            println!("Homeland: {:#?}", self.places.get(civ.homeland));
789        }
790
791        for (id, site) in self.sites.iter() {
792            println!("# Site {:?}", id);
793            println!("{:#?}", site);
794        }
795    }
796
797    /// Return the direct track between two places, bool if the track should be
798    /// reversed or not
799    pub fn track_between(&self, a: Id<Site>, b: Id<Site>) -> Option<(Id<Track>, bool)> {
800        self.track_map
801            .get(&a)
802            .and_then(|dests| Some((*dests.get(&b)?, false)))
803            .or_else(|| {
804                self.track_map
805                    .get(&b)
806                    .and_then(|dests| Some((*dests.get(&a)?, true)))
807            })
808    }
809
810    /// Return an iterator over a site's neighbors
811    pub fn neighbors(&self, site: Id<Site>) -> impl Iterator<Item = Id<Site>> + '_ {
812        let to = self
813            .track_map
814            .get(&site)
815            .map(|dests| dests.keys())
816            .into_iter()
817            .flatten();
818        let fro = self
819            .track_map
820            .iter()
821            .filter(move |(_, dests)| dests.contains_key(&site))
822            .map(|(p, _)| p);
823        to.chain(fro).filter(move |p| **p != site).copied()
824    }
825
826    /// Find the cheapest route between two places
827    fn route_between(&self, a: Id<Site>, b: Id<Site>) -> Option<(Path<Id<Site>>, f32)> {
828        let heuristic = move |p: &Id<Site>| {
829            (self
830                .sites
831                .get(*p)
832                .center
833                .distance_squared(self.sites.get(b).center) as f32)
834                .sqrt()
835        };
836        let transition =
837            |a: Id<Site>, b: Id<Site>| self.tracks.get(self.track_between(a, b).unwrap().0).cost;
838        let neighbors = |p: &Id<Site>| {
839            let p = *p;
840            self.neighbors(p)
841                .map(move |neighbor| (neighbor, transition(p, neighbor)))
842        };
843        let satisfied = |p: &Id<Site>| *p == b;
844        // We use this hasher (FxHasher64) because
845        // (1) we don't care about DDOS attacks (ruling out SipHash);
846        // (2) we care about determinism across computers (ruling out AAHash);
847        // (3) we have 8-byte keys (for which FxHash is fastest).
848        let mut astar = Astar::new(100, a, BuildHasherDefault::<FxHasher64>::default());
849        astar.poll(100, heuristic, neighbors, satisfied).into_path()
850    }
851
852    fn birth_civ(&mut self, ctx: &mut GenCtx<impl Rng>) -> Option<Id<Civ>> {
853        // TODO: specify SiteKind based on where a suitable location is found
854        let kind = match ctx.rng.gen_range(0..64) {
855            0..=8 => SiteKind::CliffTown,
856            9..=17 => SiteKind::DesertCity,
857            18..=23 => SiteKind::SavannahTown,
858            24..=33 => SiteKind::CoastalTown,
859            _ => SiteKind::Refactor,
860        };
861        let world_dims = ctx.sim.get_aabr();
862        let avoid_town_enemies = ProximityRequirementsBuilder::new()
863            .avoid_all_of(self.town_enemies(), 60)
864            .finalize(&world_dims);
865        let loc = (0..100)
866            .flat_map(|_| {
867                find_site_loc(ctx, &avoid_town_enemies, &kind).and_then(|loc| {
868                    town_attributes_of_site(loc, ctx.sim)
869                        .map(|town_attrs| (loc, town_attrs.score()))
870                })
871            })
872            .reduce(|a, b| if a.1 > b.1 { a } else { b })?
873            .0;
874
875        let site = self.establish_site(ctx, loc, |place| Site {
876            kind,
877            site_tmp: None,
878            center: loc,
879            place,
880            /* most economic members have moved to site/Economy */
881            /* last_exports: Stocks::from_default(0.0),
882             * export_targets: Stocks::from_default(0.0),
883             * //trade_states: Stocks::default(), */
884        });
885
886        let civ = self.civs.insert(Civ {
887            capital: site,
888            homeland: self.sites.get(site).place,
889        });
890
891        Some(civ)
892    }
893
894    fn establish_place(
895        &mut self,
896        _ctx: &mut GenCtx<impl Rng>,
897        loc: Vec2<i32>,
898        _area: Range<usize>,
899    ) -> Id<Place> {
900        self.places.insert(Place { center: loc })
901    }
902
903    /// Adds lake POIs and names them
904    fn name_biomes(&mut self, ctx: &mut GenCtx<impl Rng>) {
905        prof_span!("name_biomes");
906        let map_size_lg = ctx.sim.map_size_lg();
907        let world_size = map_size_lg.chunks();
908        let mut biomes: Vec<(common::terrain::BiomeKind, Vec<usize>)> = Vec::new();
909        let mut explored = vec![false; world_size.x as usize * world_size.y as usize];
910        let mut to_floodfill = Vec::new();
911        let mut to_explore = Vec::new();
912        // TODO: have start point in center and ignore ocean?
913        let start_point = 0;
914        to_explore.push(start_point);
915
916        while let Some(exploring) = to_explore.pop() {
917            if explored[exploring] {
918                continue;
919            }
920            to_floodfill.push(exploring);
921            // Should always be a chunk on the map
922            let biome = ctx.sim.chunks[exploring].get_biome();
923            let mut filled = Vec::new();
924
925            while let Some(filling) = to_floodfill.pop() {
926                explored[filling] = true;
927                filled.push(filling);
928                for neighbour in common::terrain::neighbors(map_size_lg, filling) {
929                    if explored[neighbour] {
930                        continue;
931                    }
932                    let n_biome = ctx.sim.chunks[neighbour].get_biome();
933                    if n_biome == biome {
934                        to_floodfill.push(neighbour);
935                    } else {
936                        to_explore.push(neighbour);
937                    }
938                }
939            }
940
941            biomes.push((biome, filled));
942        }
943
944        prof_span!("after flood fill");
945        let mut biome_count = 0;
946        for biome in biomes {
947            let name = match biome.0 {
948                common::terrain::BiomeKind::Lake if biome.1.len() as u32 > 200 => Some(format!(
949                    "{} {}",
950                    ["Lake", "Loch"].choose(&mut ctx.rng).unwrap(),
951                    NameGen::location(&mut ctx.rng).generate_lake_custom()
952                )),
953                common::terrain::BiomeKind::Lake if biome.1.len() as u32 > 10 => Some(format!(
954                    "{} {}",
955                    NameGen::location(&mut ctx.rng).generate_lake_custom(),
956                    ["Pool", "Well", "Pond"].choose(&mut ctx.rng).unwrap()
957                )),
958                common::terrain::BiomeKind::Grassland if biome.1.len() as u32 > 750 => {
959                    Some(format!(
960                        "{} {}",
961                        [
962                            NameGen::location(&mut ctx.rng).generate_grassland_engl(),
963                            NameGen::location(&mut ctx.rng).generate_grassland_custom()
964                        ]
965                        .choose(&mut ctx.rng)
966                        .unwrap(),
967                        [
968                            "Grasslands",
969                            "Plains",
970                            "Meadows",
971                            "Fields",
972                            "Heath",
973                            "Hills",
974                            "Prairie",
975                            "Lowlands",
976                            "Steppe",
977                            "Downs",
978                            "Greens",
979                        ]
980                        .choose(&mut ctx.rng)
981                        .unwrap()
982                    ))
983                },
984                common::terrain::BiomeKind::Ocean if biome.1.len() as u32 > 750 => Some(format!(
985                    "{} {}",
986                    [
987                        NameGen::location(&mut ctx.rng).generate_ocean_engl(),
988                        NameGen::location(&mut ctx.rng).generate_ocean_custom()
989                    ]
990                    .choose(&mut ctx.rng)
991                    .unwrap(),
992                    ["Sea", "Bay", "Gulf", "Deep", "Depths", "Ocean", "Blue",]
993                        .choose(&mut ctx.rng)
994                        .unwrap()
995                )),
996                common::terrain::BiomeKind::Mountain if biome.1.len() as u32 > 750 => {
997                    Some(format!(
998                        "{} {}",
999                        [
1000                            NameGen::location(&mut ctx.rng).generate_mountain_engl(),
1001                            NameGen::location(&mut ctx.rng).generate_mountain_custom()
1002                        ]
1003                        .choose(&mut ctx.rng)
1004                        .unwrap(),
1005                        [
1006                            "Mountains",
1007                            "Range",
1008                            "Reach",
1009                            "Massif",
1010                            "Rocks",
1011                            "Cliffs",
1012                            "Peaks",
1013                            "Heights",
1014                            "Bluffs",
1015                            "Ridge",
1016                            "Canyon",
1017                            "Plateau",
1018                        ]
1019                        .choose(&mut ctx.rng)
1020                        .unwrap()
1021                    ))
1022                },
1023                common::terrain::BiomeKind::Snowland if biome.1.len() as u32 > 750 => {
1024                    Some(format!(
1025                        "{} {}",
1026                        [
1027                            NameGen::location(&mut ctx.rng).generate_snowland_engl(),
1028                            NameGen::location(&mut ctx.rng).generate_snowland_custom()
1029                        ]
1030                        .choose(&mut ctx.rng)
1031                        .unwrap(),
1032                        [
1033                            "Snowlands",
1034                            "Glacier",
1035                            "Tundra",
1036                            "Drifts",
1037                            "Snowfields",
1038                            "Hills",
1039                            "Downs",
1040                            "Uplands",
1041                            "Highlands",
1042                        ]
1043                        .choose(&mut ctx.rng)
1044                        .unwrap()
1045                    ))
1046                },
1047                common::terrain::BiomeKind::Desert if biome.1.len() as u32 > 750 => Some(format!(
1048                    "{} {}",
1049                    [
1050                        NameGen::location(&mut ctx.rng).generate_desert_engl(),
1051                        NameGen::location(&mut ctx.rng).generate_desert_custom()
1052                    ]
1053                    .choose(&mut ctx.rng)
1054                    .unwrap(),
1055                    [
1056                        "Desert", "Sands", "Sandsea", "Drifts", "Dunes", "Droughts", "Flats",
1057                    ]
1058                    .choose(&mut ctx.rng)
1059                    .unwrap()
1060                )),
1061                common::terrain::BiomeKind::Swamp if biome.1.len() as u32 > 200 => Some(format!(
1062                    "{} {}",
1063                    NameGen::location(&mut ctx.rng).generate_swamp_engl(),
1064                    [
1065                        "Swamp",
1066                        "Swamps",
1067                        "Swamplands",
1068                        "Marsh",
1069                        "Marshlands",
1070                        "Morass",
1071                        "Mire",
1072                        "Bog",
1073                        "Wetlands",
1074                        "Fen",
1075                        "Moors",
1076                    ]
1077                    .choose(&mut ctx.rng)
1078                    .unwrap()
1079                )),
1080                common::terrain::BiomeKind::Jungle if biome.1.len() as u32 > 85 => Some(format!(
1081                    "{} {}",
1082                    [
1083                        NameGen::location(&mut ctx.rng).generate_jungle_engl(),
1084                        NameGen::location(&mut ctx.rng).generate_jungle_custom()
1085                    ]
1086                    .choose(&mut ctx.rng)
1087                    .unwrap(),
1088                    [
1089                        "Jungle",
1090                        "Rainforest",
1091                        "Greatwood",
1092                        "Wilds",
1093                        "Wildwood",
1094                        "Tangle",
1095                        "Tanglewood",
1096                        "Bush",
1097                    ]
1098                    .choose(&mut ctx.rng)
1099                    .unwrap()
1100                )),
1101                common::terrain::BiomeKind::Forest if biome.1.len() as u32 > 750 => Some(format!(
1102                    "{} {}",
1103                    [
1104                        NameGen::location(&mut ctx.rng).generate_forest_engl(),
1105                        NameGen::location(&mut ctx.rng).generate_forest_custom()
1106                    ]
1107                    .choose(&mut ctx.rng)
1108                    .unwrap(),
1109                    ["Forest", "Woodlands", "Woods", "Glades", "Grove", "Weald",]
1110                        .choose(&mut ctx.rng)
1111                        .unwrap()
1112                )),
1113                common::terrain::BiomeKind::Savannah if biome.1.len() as u32 > 750 => {
1114                    Some(format!(
1115                        "{} {}",
1116                        [
1117                            NameGen::location(&mut ctx.rng).generate_savannah_engl(),
1118                            NameGen::location(&mut ctx.rng).generate_savannah_custom()
1119                        ]
1120                        .choose(&mut ctx.rng)
1121                        .unwrap(),
1122                        [
1123                            "Savannah",
1124                            "Shrublands",
1125                            "Sierra",
1126                            "Prairie",
1127                            "Lowlands",
1128                            "Flats",
1129                        ]
1130                        .choose(&mut ctx.rng)
1131                        .unwrap()
1132                    ))
1133                },
1134                common::terrain::BiomeKind::Taiga if biome.1.len() as u32 > 750 => Some(format!(
1135                    "{} {}",
1136                    [
1137                        NameGen::location(&mut ctx.rng).generate_taiga_engl(),
1138                        NameGen::location(&mut ctx.rng).generate_taiga_custom()
1139                    ]
1140                    .choose(&mut ctx.rng)
1141                    .unwrap(),
1142                    [
1143                        "Forest",
1144                        "Woodlands",
1145                        "Woods",
1146                        "Timberlands",
1147                        "Highlands",
1148                        "Uplands",
1149                    ]
1150                    .choose(&mut ctx.rng)
1151                    .unwrap()
1152                )),
1153                _ => None,
1154            };
1155            if let Some(name) = name {
1156                // find average center of the biome
1157                let center = biome
1158                    .1
1159                    .iter()
1160                    .map(|b| {
1161                        uniform_idx_as_vec2(map_size_lg, *b).as_::<f32>() / biome.1.len() as f32
1162                    })
1163                    .sum::<Vec2<f32>>()
1164                    .as_::<i32>();
1165                // Select the point closest to the center
1166                let idx = *biome
1167                    .1
1168                    .iter()
1169                    .min_by_key(|&b| center.distance_squared(uniform_idx_as_vec2(map_size_lg, *b)))
1170                    .unwrap();
1171                let id = self.pois.insert(PointOfInterest {
1172                    name,
1173                    loc: uniform_idx_as_vec2(map_size_lg, idx),
1174                    kind: PoiKind::Biome(biome.1.len() as u32),
1175                });
1176                for chunk in biome.1 {
1177                    ctx.sim.chunks[chunk].poi = Some(id);
1178                }
1179                biome_count += 1;
1180            }
1181        }
1182
1183        info!(?biome_count, "all biomes named");
1184    }
1185
1186    /// Adds mountain POIs and name them
1187    fn name_peaks(&mut self, ctx: &mut GenCtx<impl Rng>) {
1188        prof_span!("name_peaks");
1189        let map_size_lg = ctx.sim.map_size_lg();
1190        const MIN_MOUNTAIN_ALT: f32 = 600.0;
1191        const MIN_MOUNTAIN_CHAOS: f32 = 0.35;
1192        let rng = &mut ctx.rng;
1193        let sim_chunks = &ctx.sim.chunks;
1194        let peaks = sim_chunks
1195            .iter()
1196            .enumerate()
1197            .filter(|(posi, chunk)| {
1198                let neighbor_alts_max = common::terrain::neighbors(map_size_lg, *posi)
1199                    .map(|i| sim_chunks[i].alt as u32)
1200                    .max();
1201                chunk.alt > MIN_MOUNTAIN_ALT
1202                    && chunk.chaos > MIN_MOUNTAIN_CHAOS
1203                    && neighbor_alts_max.is_some_and(|n_alt| chunk.alt as u32 > n_alt)
1204            })
1205            .map(|(posi, chunk)| {
1206                (
1207                    posi,
1208                    uniform_idx_as_vec2(map_size_lg, posi),
1209                    (chunk.alt - CONFIG.sea_level) as u32,
1210                )
1211            })
1212            .collect::<Vec<(usize, Vec2<i32>, u32)>>();
1213        let mut num_peaks = 0;
1214        let mut removals = vec![false; peaks.len()];
1215        for (i, peak) in peaks.iter().enumerate() {
1216            for (k, n_peak) in peaks.iter().enumerate() {
1217                // If the difference in position of this peak and another is
1218                // below a threshold and this peak's altitude is lower, remove the
1219                // peak from the list
1220                if i != k
1221                    && (peak.1).distance_squared(n_peak.1) < POI_THINNING_DIST_SQRD
1222                    && peak.2 <= n_peak.2
1223                {
1224                    // Remove this peak
1225                    // This cannot panic as `removals` is the same length as `peaks`
1226                    // i is the index in `peaks`
1227                    removals[i] = true;
1228                }
1229            }
1230        }
1231        peaks
1232            .iter()
1233            .enumerate()
1234            .filter(|&(i, _)| !removals[i])
1235            .for_each(|(_, (_, loc, alt))| {
1236                num_peaks += 1;
1237                self.pois.insert(PointOfInterest {
1238                    name: {
1239                        let name = NameGen::location(rng).generate();
1240                        if *alt < 1000 {
1241                            match rng.gen_range(0..6) {
1242                                0 => format!("{} Bluff", name),
1243                                1 => format!("{} Crag", name),
1244                                _ => format!("{} Hill", name),
1245                            }
1246                        } else {
1247                            match rng.gen_range(0..8) {
1248                                0 => format!("{}'s Peak", name),
1249                                1 => format!("{} Peak", name),
1250                                2 => format!("{} Summit", name),
1251                                _ => format!("Mount {}", name),
1252                            }
1253                        }
1254                    },
1255                    kind: PoiKind::Peak(*alt),
1256                    loc: *loc,
1257                });
1258            });
1259        info!(?num_peaks, "all peaks named");
1260    }
1261
1262    fn establish_site(
1263        &mut self,
1264        ctx: &mut GenCtx<impl Rng>,
1265        loc: Vec2<i32>,
1266        site_fn: impl FnOnce(Id<Place>) -> Site,
1267    ) -> Id<Site> {
1268        prof_span!("establish_site");
1269        const SITE_AREA: Range<usize> = 1..4; //64..256;
1270
1271        fn establish_site(
1272            civs: &mut Civs,
1273            ctx: &mut GenCtx<impl Rng>,
1274            loc: Vec2<i32>,
1275            site_fn: impl FnOnce(Id<Place>) -> Site,
1276        ) -> Id<Site> {
1277            let place = match ctx.sim.get(loc).and_then(|site| site.place) {
1278                Some(place) => place,
1279                None => civs.establish_place(ctx, loc, SITE_AREA),
1280            };
1281
1282            civs.sites.insert(site_fn(place))
1283        }
1284
1285        let site = establish_site(self, ctx, loc, site_fn);
1286
1287        // Find neighbors
1288        // Note, the maximum distance that I have so far observed not hitting the
1289        // iteration limit in `find_path` is 364. So I think this is a reasonable
1290        // limit (although the relationship between distance and pathfinding iterations
1291        // can be a bit variable). Note, I have seen paths reach the iteration limit
1292        // with distances as small as 137, so this certainly doesn't catch all
1293        // cases that would fail.
1294        const MAX_NEIGHBOR_DISTANCE: f32 = 400.0;
1295        let mut nearby = self
1296            .sites
1297            .iter()
1298            .filter(|&(id, _)| id != site)
1299            .filter(|(_, p)| {
1300                matches!(
1301                    p.kind,
1302                    SiteKind::Refactor
1303                        | SiteKind::CliffTown
1304                        | SiteKind::SavannahTown
1305                        | SiteKind::CoastalTown
1306                        | SiteKind::DesertCity
1307                )
1308            })
1309            .map(|(id, p)| (id, (p.center.distance_squared(loc) as f32).sqrt()))
1310            .filter(|(_, dist)| *dist < MAX_NEIGHBOR_DISTANCE)
1311            .collect::<Vec<_>>();
1312        nearby.sort_by_key(|(_, dist)| *dist as i32);
1313
1314        if let SiteKind::Refactor
1315        | SiteKind::CliffTown
1316        | SiteKind::SavannahTown
1317        | SiteKind::CoastalTown
1318        | SiteKind::DesertCity = self.sites[site].kind
1319        {
1320            for (nearby, _) in nearby.into_iter().take(4) {
1321                prof_span!("for nearby");
1322                // Find a route using existing paths
1323                //
1324                // If the novel path isn't efficient compared to this, don't use it
1325                let max_novel_cost = self
1326                    .route_between(site, nearby)
1327                    .map_or(f32::MAX, |(_, route_cost)| route_cost / 3.0);
1328
1329                let start = loc;
1330                let end = self.sites.get(nearby).center;
1331                // Find a novel path.
1332                let get_bridge = |start| self.bridges.get(&start).map(|(end, _)| *end);
1333                if let Some((path, cost)) = find_path(ctx, get_bridge, start, end, max_novel_cost) {
1334                    // Write the track to the world as a path
1335                    for locs in path.nodes().windows(3) {
1336                        if let Some((i, _)) = NEIGHBORS
1337                            .iter()
1338                            .enumerate()
1339                            .find(|(_, dir)| **dir == locs[0] - locs[1])
1340                        {
1341                            ctx.sim.get_mut(locs[0]).unwrap().path.0.neighbors |=
1342                                1 << ((i as u8 + 4) % 8);
1343                            ctx.sim.get_mut(locs[1]).unwrap().path.0.neighbors |= 1 << (i as u8);
1344                        }
1345
1346                        if let Some((i, _)) = NEIGHBORS
1347                            .iter()
1348                            .enumerate()
1349                            .find(|(_, dir)| **dir == locs[2] - locs[1])
1350                        {
1351                            ctx.sim.get_mut(locs[2]).unwrap().path.0.neighbors |=
1352                                1 << ((i as u8 + 4) % 8);
1353
1354                            ctx.sim.get_mut(locs[1]).unwrap().path.0.neighbors |= 1 << (i as u8);
1355                            ctx.sim.get_mut(locs[1]).unwrap().path.0.offset =
1356                                Vec2::new(ctx.rng.gen_range(-16..17), ctx.rng.gen_range(-16..17));
1357                        } else if !self.bridges.contains_key(&locs[1]) {
1358                            let center = (locs[1] + locs[2]) / 2;
1359                            let id =
1360                                establish_site(self, &mut ctx.reseed(), center, move |place| {
1361                                    Site {
1362                                        kind: SiteKind::Bridge(locs[1], locs[2]),
1363                                        site_tmp: None,
1364                                        center,
1365                                        place,
1366                                    }
1367                                });
1368                            self.bridges.insert(locs[1], (locs[2], id));
1369                            self.bridges.insert(locs[2], (locs[1], id));
1370                        }
1371                        /*
1372                        let to_prev_idx = NEIGHBORS
1373                            .iter()
1374                            .enumerate()
1375                            .find(|(_, dir)| **dir == (locs[0] - locs[1]).map(|e| e.signum()))
1376                            .expect("Track locations must be neighbors")
1377                            .0;
1378
1379                        let to_next_idx = NEIGHBORS
1380                            .iter()
1381                            .enumerate()
1382                            .find(|(_, dir)| **dir == (locs[2] - locs[1]).map(|e| e.signum()))
1383                            .expect("Track locations must be neighbors")
1384                            .0;
1385
1386                        ctx.sim.get_mut(locs[0]).unwrap().path.0.neighbors |=
1387                            1 << ((to_prev_idx as u8 + 4) % 8);
1388                        ctx.sim.get_mut(locs[2]).unwrap().path.0.neighbors |=
1389                            1 << ((to_next_idx as u8 + 4) % 8);
1390                        let mut chunk = ctx.sim.get_mut(locs[1]).unwrap();
1391                        chunk.path.0.neighbors |=
1392                            (1 << (to_prev_idx as u8)) | (1 << (to_next_idx as u8));
1393                        */
1394                    }
1395
1396                    // Take note of the track
1397                    let track = self.tracks.insert(Track { cost, path });
1398                    self.track_map
1399                        .entry(site)
1400                        .or_default()
1401                        .insert(nearby, track);
1402                }
1403            }
1404        }
1405
1406        site
1407    }
1408
1409    fn gnarling_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1410        self.sites().filter_map(|s| match s.kind {
1411            SiteKind::GiantTree => None,
1412            _ => Some(s.center),
1413        })
1414    }
1415
1416    fn adlet_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1417        self.sites().map(|s| s.center)
1418    }
1419
1420    fn haniwa_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1421        self.sites().map(|s| s.center)
1422    }
1423
1424    fn chapel_site_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1425        self.sites().map(|s| s.center)
1426    }
1427
1428    fn mine_site_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1429        self.sites().map(|s| s.center)
1430    }
1431
1432    fn terracotta_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1433        self.sites().map(|s| s.center)
1434    }
1435
1436    fn cultist_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1437        self.sites().map(|s| s.center)
1438    }
1439
1440    fn myrmidon_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1441        self.sites().map(|s| s.center)
1442    }
1443
1444    fn vampire_castle_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1445        self.sites().map(|s| s.center)
1446    }
1447
1448    fn tree_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1449        self.sites().map(|s| s.center)
1450    }
1451
1452    fn castle_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1453        self.sites().filter_map(|s| {
1454            if s.is_settlement() {
1455                None
1456            } else {
1457                Some(s.center)
1458            }
1459        })
1460    }
1461
1462    fn jungle_ruin_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1463        self.sites().map(|s| s.center)
1464    }
1465
1466    fn town_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1467        self.sites().filter_map(|s| match s.kind {
1468            SiteKind::Citadel => None,
1469            _ => Some(s.center),
1470        })
1471    }
1472
1473    fn towns(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1474        self.sites().filter_map(|s| {
1475            if s.is_settlement() {
1476                Some(s.center)
1477            } else {
1478                None
1479            }
1480        })
1481    }
1482
1483    fn pirate_hideout_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1484        self.sites().map(|s| s.center)
1485    }
1486
1487    fn sahagin_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1488        self.sites().map(|s| s.center)
1489    }
1490
1491    fn rock_circle_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1492        self.sites().map(|s| s.center)
1493    }
1494
1495    fn troll_cave_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1496        self.sites().map(|s| s.center)
1497    }
1498
1499    fn camp_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1500        self.sites().map(|s| s.center)
1501    }
1502}
1503
1504/// Attempt to find a path between two locations
1505fn find_path(
1506    ctx: &mut GenCtx<impl Rng>,
1507    get_bridge: impl Fn(Vec2<i32>) -> Option<Vec2<i32>>,
1508    a: Vec2<i32>,
1509    b: Vec2<i32>,
1510    max_path_cost: f32,
1511) -> Option<(Path<Vec2<i32>>, f32)> {
1512    prof_span!("find_path");
1513    const MAX_PATH_ITERS: usize = 100_000;
1514    let sim = &ctx.sim;
1515    // NOTE: If heuristic overestimates the actual cost, then A* is not guaranteed
1516    // to produce the least-cost path (since it will explore partially based on
1517    // the heuristic).
1518    // TODO: heuristic can be larger than actual cost, since existing bridges cost
1519    // 1.0 (after the 1.0 that is added to everthting), but they can cover
1520    // multiple chunks.
1521    let heuristic = move |l: &Vec2<i32>| (l.distance_squared(b) as f32).sqrt();
1522    let neighbors = |l: &Vec2<i32>| {
1523        let l = *l;
1524        let bridge = get_bridge(l);
1525        let potential = walk_in_all_dirs(sim, bridge, l);
1526        potential
1527            .into_iter()
1528            .filter_map(|p| p.map(|(node, cost)| (node, cost + 1.0)))
1529    };
1530    let satisfied = |l: &Vec2<i32>| *l == b;
1531    // We use this hasher (FxHasher64) because
1532    // (1) we don't care about DDOS attacks (ruling out SipHash);
1533    // (2) we care about determinism across computers (ruling out AAHash);
1534    // (3) we have 8-byte keys (for which FxHash is fastest).
1535    let mut astar = Astar::new(
1536        MAX_PATH_ITERS,
1537        a,
1538        BuildHasherDefault::<FxHasher64>::default(),
1539    )
1540    .with_max_cost(max_path_cost);
1541    astar
1542        .poll(MAX_PATH_ITERS, heuristic, neighbors, satisfied)
1543        .into_path()
1544}
1545
1546/// Return Some if travel between a location and a chunk next to it is permitted
1547/// If permitted, the approximate relative const of traversal is given
1548// (TODO: by whom?)
1549/// Return tuple: (final location, cost)
1550///
1551/// For efficiency, this computes for all 8 directions at once.
1552fn walk_in_all_dirs(
1553    sim: &WorldSim,
1554    bridge: Option<Vec2<i32>>,
1555    a: Vec2<i32>,
1556) -> [Option<(Vec2<i32>, f32)>; 8] {
1557    let mut potential = [None; 8];
1558
1559    let adjacents = NEIGHBORS.map(|dir| a + dir);
1560
1561    let Some(a_chunk) = sim.get(a) else {
1562        return potential;
1563    };
1564    let mut chunks = [None; 8];
1565    for i in 0..8 {
1566        if loc_suitable_for_walking(sim, adjacents[i]) {
1567            chunks[i] = sim.get(adjacents[i]);
1568        }
1569    }
1570
1571    for i in 0..8 {
1572        let Some(b_chunk) = chunks[i] else { continue };
1573
1574        let hill_cost = ((b_chunk.alt - a_chunk.alt).abs() / 5.0).powi(2);
1575        let water_cost = (b_chunk.water_alt - b_chunk.alt + 8.0).clamped(0.0, 8.0) * 3.0; // Try not to path swamps / tidal areas
1576        let wild_cost = if b_chunk.path.0.is_way() {
1577            0.0 // Traversing existing paths has no additional cost!
1578        } else {
1579            3.0 // + (1.0 - b_chunk.tree_density) * 20.0 // Prefer going through forests, for aesthetics
1580        };
1581
1582        let cost = 1.0 + hill_cost + water_cost + wild_cost;
1583        potential[i] = Some((adjacents[i], cost));
1584    }
1585
1586    // Look for potential bridge spots in the cardinal directions if
1587    // `loc_suitable_for_wallking` was false for the adjacent chunk.
1588    for (i, &dir) in NEIGHBORS.iter().enumerate() {
1589        let is_cardinal_dir = dir.x == 0 || dir.y == 0;
1590        if is_cardinal_dir && potential[i].is_none() {
1591            // if we can skip over unsuitable area with a bridge
1592            potential[i] = (4..=5).find_map(|i| {
1593                loc_suitable_for_walking(sim, a + dir * i)
1594                    .then(|| (a + dir * i, 120.0 + (i - 4) as f32 * 10.0))
1595            });
1596        }
1597    }
1598
1599    // If current position is a bridge, skip to its destination.
1600    if let Some(p) = bridge {
1601        let dir = (p - a).map(|e| e.signum());
1602        if let Some((dir_index, _)) = NEIGHBORS
1603            .iter()
1604            .enumerate()
1605            .find(|(_, n_dir)| **n_dir == dir)
1606        {
1607            potential[dir_index] = Some((p, (p - a).map(|e| e.abs()).reduce_max() as f32));
1608        }
1609    }
1610
1611    potential
1612}
1613
1614/// Return true if a position is suitable for walking on
1615fn loc_suitable_for_walking(sim: &WorldSim, loc: Vec2<i32>) -> bool {
1616    if sim.get(loc).is_some() {
1617        NEIGHBORS.iter().all(|n| {
1618            sim.get(loc + *n)
1619                .is_some_and(|chunk| !chunk.river.near_water())
1620        })
1621    } else {
1622        false
1623    }
1624}
1625
1626/// Attempt to search for a location that's suitable for site construction
1627// FIXME when a `close_to_one_of` requirement is passed in, we should start with
1628// just the chunks around those locations instead of random sampling the entire
1629// map
1630fn find_site_loc(
1631    ctx: &mut GenCtx<impl Rng>,
1632    proximity_reqs: &ProximityRequirements,
1633    site_kind: &SiteKind,
1634) -> Option<Vec2<i32>> {
1635    prof_span!("find_site_loc");
1636    const MAX_ATTEMPTS: usize = 10000;
1637    let mut loc = None;
1638    let location_hint = proximity_reqs.location_hint;
1639    for _ in 0..MAX_ATTEMPTS {
1640        let test_loc = loc.unwrap_or_else(|| {
1641            Vec2::new(
1642                ctx.rng.gen_range(location_hint.min.x..location_hint.max.x),
1643                ctx.rng.gen_range(location_hint.min.y..location_hint.max.y),
1644            )
1645        });
1646
1647        let is_suitable_loc = site_kind.is_suitable_loc(test_loc, ctx.sim);
1648        if is_suitable_loc && proximity_reqs.satisfied_by(test_loc) {
1649            if site_kind.exclusion_radius_clear(ctx.sim, test_loc) {
1650                return Some(test_loc);
1651            }
1652
1653            // If the current location is suitable and meets proximity requirements,
1654            // try nearby spot downhill.
1655            loc = ctx.sim.get(test_loc).and_then(|c| c.downhill);
1656        }
1657    }
1658
1659    debug!("Failed to place site {:?}.", site_kind);
1660    None
1661}
1662
1663fn town_attributes_of_site(loc: Vec2<i32>, sim: &WorldSim) -> Option<TownSiteAttributes> {
1664    sim.get(loc).map(|chunk| {
1665        const RESOURCE_RADIUS: i32 = 1;
1666        let mut river_chunks = 0;
1667        let mut lake_chunks = 0;
1668        let mut ocean_chunks = 0;
1669        let mut rock_chunks = 0;
1670        let mut tree_chunks = 0;
1671        let mut farmable_chunks = 0;
1672        let mut farmable_needs_irrigation_chunks = 0;
1673        let mut land_chunks = 0;
1674        for x in (-RESOURCE_RADIUS)..RESOURCE_RADIUS {
1675            for y in (-RESOURCE_RADIUS)..RESOURCE_RADIUS {
1676                let check_loc = loc + Vec2::new(x, y).cpos_to_wpos();
1677                sim.get(check_loc).map(|c| {
1678                    if num::abs(chunk.alt - c.alt) < 200.0 {
1679                        if c.river.is_river() {
1680                            river_chunks += 1;
1681                        }
1682                        if c.river.is_lake() {
1683                            lake_chunks += 1;
1684                        }
1685                        if c.river.is_ocean() {
1686                            ocean_chunks += 1;
1687                        }
1688                        if c.tree_density > 0.7 {
1689                            tree_chunks += 1;
1690                        }
1691                        if c.rockiness < 0.3 && c.temp > CONFIG.snow_temp {
1692                            if c.surface_veg > 0.5 {
1693                                farmable_chunks += 1;
1694                            } else {
1695                                match c.get_biome() {
1696                                    common::terrain::BiomeKind::Savannah => {
1697                                        farmable_needs_irrigation_chunks += 1
1698                                    },
1699                                    common::terrain::BiomeKind::Desert => {
1700                                        farmable_needs_irrigation_chunks += 1
1701                                    },
1702                                    _ => (),
1703                                }
1704                            }
1705                        }
1706                        if !c.river.is_river() && !c.river.is_lake() && !c.river.is_ocean() {
1707                            land_chunks += 1;
1708                        }
1709                    }
1710                    // Mining is different since presumably you dig into the hillside
1711                    if c.rockiness > 0.7 && c.alt - chunk.alt > -10.0 {
1712                        rock_chunks += 1;
1713                    }
1714                });
1715            }
1716        }
1717        let has_river = river_chunks > 1;
1718        let has_lake = lake_chunks > 1;
1719        let vegetation_implies_potable_water = chunk.tree_density > 0.4
1720            && !matches!(chunk.get_biome(), common::terrain::BiomeKind::Swamp);
1721        let has_many_rocks = chunk.rockiness > 1.2;
1722        let warm_or_firewood = chunk.temp > CONFIG.snow_temp || tree_chunks > 2;
1723        let has_potable_water =
1724            { has_river || (has_lake && chunk.alt > 100.0) || vegetation_implies_potable_water };
1725        let has_building_materials = tree_chunks > 0
1726            || rock_chunks > 0
1727            || chunk.temp > CONFIG.tropical_temp && (has_river || has_lake);
1728        let water_rich = lake_chunks + river_chunks > 2;
1729        let can_grow_rice = water_rich
1730            && chunk.humidity + 1.0 > CONFIG.jungle_hum
1731            && chunk.temp + 1.0 > CONFIG.tropical_temp;
1732        let farming_score = if can_grow_rice {
1733            farmable_chunks * 2
1734        } else {
1735            farmable_chunks
1736        } + if water_rich {
1737            farmable_needs_irrigation_chunks
1738        } else {
1739            0
1740        };
1741        let fish_score = lake_chunks + ocean_chunks;
1742        let food_score = farming_score + fish_score;
1743        let mining_score = if tree_chunks > 1 { rock_chunks } else { 0 };
1744        let forestry_score = if has_river { tree_chunks } else { 0 };
1745        let trading_score = std::cmp::min(std::cmp::min(land_chunks, ocean_chunks), river_chunks);
1746        TownSiteAttributes {
1747            food_score,
1748            mining_score,
1749            forestry_score,
1750            trading_score,
1751            heating: warm_or_firewood,
1752            potable_water: has_potable_water,
1753            building_materials: has_building_materials,
1754            aquifer: has_many_rocks,
1755        }
1756    })
1757}
1758
1759pub struct TownSiteAttributes {
1760    food_score: i32,
1761    mining_score: i32,
1762    forestry_score: i32,
1763    trading_score: i32,
1764    heating: bool,
1765    potable_water: bool,
1766    building_materials: bool,
1767    aquifer: bool,
1768}
1769
1770impl TownSiteAttributes {
1771    pub fn score(&self) -> f32 {
1772        3.0 * (self.food_score as f32 + 1.0).log2()
1773            + 2.0 * (self.forestry_score as f32 + 1.0).log2()
1774            + (self.mining_score as f32 + 1.0).log2()
1775            + (self.trading_score as f32 + 1.0).log2()
1776    }
1777}
1778
1779#[derive(Debug)]
1780pub struct Civ {
1781    capital: Id<Site>,
1782    homeland: Id<Place>,
1783}
1784
1785#[derive(Debug)]
1786pub struct Place {
1787    pub center: Vec2<i32>,
1788    /* act sort of like territory with sites belonging to it
1789     * nat_res/NaturalResources was moved to Economy
1790     *    nat_res: NaturalResources, */
1791}
1792
1793pub struct Track {
1794    /// Cost of using this track relative to other paths. This cost is an
1795    /// arbitrary unit and doesn't make sense unless compared to other track
1796    /// costs.
1797    pub cost: f32,
1798    path: Path<Vec2<i32>>,
1799}
1800
1801impl Track {
1802    pub fn path(&self) -> &Path<Vec2<i32>> { &self.path }
1803}
1804
1805#[derive(Debug)]
1806pub struct Site {
1807    pub kind: SiteKind,
1808    // TODO: Remove this field when overhauling
1809    pub site_tmp: Option<Id<crate::site::Site>>,
1810    pub center: Vec2<i32>,
1811    pub place: Id<Place>,
1812}
1813
1814impl fmt::Display for Site {
1815    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1816        writeln!(f, "{:?}", self.kind)?;
1817
1818        Ok(())
1819    }
1820}
1821
1822impl SiteKind {
1823    pub fn is_suitable_loc(&self, loc: Vec2<i32>, sim: &WorldSim) -> bool {
1824        let on_land = || -> bool {
1825            if let Some(chunk) = sim.get(loc) {
1826                !chunk.river.is_ocean()
1827                    && !chunk.river.is_lake()
1828                    && !chunk.river.is_river()
1829                    && !chunk.is_underwater()
1830                    && !matches!(
1831                        chunk.get_biome(),
1832                        common::terrain::BiomeKind::Lake | common::terrain::BiomeKind::Ocean
1833                    )
1834            } else {
1835                false
1836            }
1837        };
1838        let on_flat_terrain = || -> bool {
1839            sim.get_gradient_approx(loc)
1840                .map(|grad| grad < 1.0)
1841                .unwrap_or(false)
1842        };
1843
1844        sim.get(loc).is_some_and(|chunk| {
1845            let suitable_for_town = || -> bool {
1846                let attributes = town_attributes_of_site(loc, sim);
1847                attributes.is_some_and(|attributes| {
1848                    // aquifer and has_many_rocks was added to make mesa clifftowns suitable for towns
1849                    (attributes.potable_water || (attributes.aquifer && matches!(self, SiteKind::CliffTown)))
1850                        && attributes.building_materials
1851                        && attributes.heating
1852                        // Because of how the algorithm for site towns work, they have to start on land.
1853                        && on_land()
1854                })
1855            };
1856            match self {
1857                SiteKind::Gnarling => {
1858                    on_land()
1859                        && on_flat_terrain()
1860                        && (-0.3..0.4).contains(&chunk.temp)
1861                        && chunk.tree_density > 0.75
1862                },
1863                SiteKind::Adlet => chunk.temp < -0.2 && chunk.cliff_height > 25.0,
1864                SiteKind::DwarvenMine => {
1865                    matches!(chunk.get_biome(), BiomeKind::Forest | BiomeKind::Desert)
1866                        && !chunk.near_cliffs()
1867                        && !chunk.river.near_water()
1868                        && on_flat_terrain()
1869                },
1870                SiteKind::Haniwa => {
1871                    on_land()
1872                        && on_flat_terrain()
1873                        && (-0.3..0.4).contains(&chunk.temp)
1874                },
1875                SiteKind::GiantTree => {
1876                    on_land()
1877                        && on_flat_terrain()
1878                        && chunk.tree_density > 0.4
1879                        && (-0.3..0.4).contains(&chunk.temp)
1880                },
1881                SiteKind::Citadel => true,
1882                SiteKind::CliffTown => {
1883                    chunk.temp >= CONFIG.desert_temp
1884                        && chunk.cliff_height > 40.0
1885                        && chunk.rockiness > 1.2
1886                        && suitable_for_town()
1887                },
1888                SiteKind::GliderCourse => {
1889                    chunk.alt > 1400.0
1890                },
1891                SiteKind::SavannahTown => {
1892                    matches!(chunk.get_biome(), BiomeKind::Savannah)
1893                        && !chunk.near_cliffs()
1894                        && !chunk.river.near_water()
1895                        && suitable_for_town()
1896                },
1897                SiteKind::CoastalTown => {
1898                    (2.0..3.5).contains(&(chunk.water_alt - CONFIG.sea_level))
1899                        && suitable_for_town()
1900                },
1901                SiteKind::PirateHideout => {
1902                    (0.5..3.5).contains(&(chunk.water_alt - CONFIG.sea_level))
1903                },
1904                SiteKind::Sahagin => {
1905                    matches!(chunk.get_biome(), BiomeKind::Ocean)
1906                    && (40.0..45.0).contains(&(CONFIG.sea_level - chunk.alt))
1907                },
1908                SiteKind::JungleRuin => {
1909                    matches!(chunk.get_biome(), BiomeKind::Jungle)
1910                },
1911                SiteKind::RockCircle => !chunk.near_cliffs() && !chunk.river.near_water(),
1912                SiteKind::TrollCave => {
1913                    !chunk.near_cliffs()
1914                        && on_flat_terrain()
1915                        && !chunk.river.near_water()
1916                        && chunk.temp < 0.6
1917                },
1918                SiteKind::Camp => {
1919                    !chunk.near_cliffs() && on_flat_terrain() && !chunk.river.near_water()
1920                },
1921                SiteKind::DesertCity => {
1922                    (0.9..1.0).contains(&chunk.temp) && !chunk.near_cliffs() && suitable_for_town()
1923                        && on_land()
1924                        && !chunk.river.near_water()
1925                },
1926                SiteKind::ChapelSite => {
1927                    matches!(chunk.get_biome(), BiomeKind::Ocean)
1928                        && CONFIG.sea_level < chunk.alt + 1.0
1929                },
1930                SiteKind::Terracotta => {
1931                    (0.9..1.0).contains(&chunk.temp)
1932                        && on_land()
1933                        && (chunk.water_alt - CONFIG.sea_level) > 50.0
1934                        && on_flat_terrain()
1935                        && !chunk.river.near_water()
1936                        && !chunk.near_cliffs()
1937                },
1938                SiteKind::Myrmidon => {
1939                    (0.9..1.0).contains(&chunk.temp)
1940                        && on_land()
1941                        && (chunk.water_alt - CONFIG.sea_level) > 50.0
1942                        && on_flat_terrain()
1943                        && !chunk.river.near_water()
1944                        && !chunk.near_cliffs()
1945                },
1946                SiteKind::Cultist => on_land() && chunk.temp < 0.5 && chunk.near_cliffs(),
1947                SiteKind::VampireCastle => on_land() && chunk.temp <= -0.8 && chunk.near_cliffs(),
1948                SiteKind::Refactor => suitable_for_town(),
1949                SiteKind::Bridge(_, _) => true,
1950            }
1951        })
1952    }
1953
1954    pub fn exclusion_radius(&self) -> i32 {
1955        // FIXME: Provide specific values for each individual SiteKind
1956        match self {
1957            SiteKind::Myrmidon => 7,
1958            _ => 8, // This is just an arbitrary value
1959        }
1960    }
1961
1962    pub fn exclusion_radius_clear(&self, sim: &WorldSim, loc: Vec2<i32>) -> bool {
1963        let radius = self.exclusion_radius();
1964        for x in (-radius)..radius {
1965            for y in (-radius)..radius {
1966                let check_loc = loc + Vec2::new(x, y);
1967                if sim.get(check_loc).is_some_and(|c| !c.sites.is_empty()) {
1968                    return false;
1969                }
1970            }
1971        }
1972        true
1973    }
1974}
1975
1976impl Site {
1977    pub fn is_dungeon(&self) -> bool {
1978        matches!(
1979            self.kind,
1980            SiteKind::Adlet
1981                | SiteKind::Gnarling
1982                | SiteKind::ChapelSite
1983                | SiteKind::Terracotta
1984                | SiteKind::Haniwa
1985                | SiteKind::Myrmidon
1986                | SiteKind::DwarvenMine
1987                | SiteKind::Cultist
1988                | SiteKind::Sahagin
1989                | SiteKind::VampireCastle
1990        )
1991    }
1992
1993    pub fn is_settlement(&self) -> bool {
1994        matches!(
1995            self.kind,
1996            SiteKind::Refactor
1997                | SiteKind::CliffTown
1998                | SiteKind::DesertCity
1999                | SiteKind::SavannahTown
2000                | SiteKind::CoastalTown
2001        )
2002    }
2003
2004    pub fn is_bridge(&self) -> bool { matches!(self.kind, SiteKind::Bridge(_, _)) }
2005}
2006
2007#[derive(PartialEq, Eq, Debug, Clone)]
2008pub struct PointOfInterest {
2009    pub name: String,
2010    pub kind: PoiKind,
2011    pub loc: Vec2<i32>,
2012}
2013
2014#[derive(PartialEq, Eq, Debug, Clone)]
2015pub enum PoiKind {
2016    /// Peak stores the altitude
2017    Peak(u32),
2018    /// Lake stores a metric relating to size
2019    Biome(u32),
2020}
2021
2022#[cfg(test)]
2023mod tests {
2024    use super::*;
2025
2026    #[test]
2027    fn empty_proximity_requirements() {
2028        let world_dims = Aabr {
2029            min: Vec2 { x: 0, y: 0 },
2030            max: Vec2 {
2031                x: 200_i32,
2032                y: 200_i32,
2033            },
2034        };
2035        let reqs = ProximityRequirementsBuilder::new().finalize(&world_dims);
2036        assert!(reqs.satisfied_by(Vec2 { x: 0, y: 0 }));
2037    }
2038
2039    #[test]
2040    fn avoid_proximity_requirements() {
2041        let world_dims = Aabr {
2042            min: Vec2 {
2043                x: -200_i32,
2044                y: -200_i32,
2045            },
2046            max: Vec2 {
2047                x: 200_i32,
2048                y: 200_i32,
2049            },
2050        };
2051        let reqs = ProximityRequirementsBuilder::new()
2052            .avoid_all_of(vec![Vec2 { x: 0, y: 0 }].into_iter(), 10)
2053            .finalize(&world_dims);
2054        assert!(reqs.satisfied_by(Vec2 { x: 8, y: -8 }));
2055        assert!(!reqs.satisfied_by(Vec2 { x: -1, y: 1 }));
2056    }
2057
2058    #[test]
2059    fn near_proximity_requirements() {
2060        let world_dims = Aabr {
2061            min: Vec2 {
2062                x: -200_i32,
2063                y: -200_i32,
2064            },
2065            max: Vec2 {
2066                x: 200_i32,
2067                y: 200_i32,
2068            },
2069        };
2070        let reqs = ProximityRequirementsBuilder::new()
2071            .close_to_one_of(vec![Vec2 { x: 0, y: 0 }].into_iter(), 10)
2072            .finalize(&world_dims);
2073        assert!(reqs.satisfied_by(Vec2 { x: 1, y: -1 }));
2074        assert!(!reqs.satisfied_by(Vec2 { x: -8, y: 8 }));
2075    }
2076
2077    #[test]
2078    fn complex_proximity_requirements() {
2079        let a_site = Vec2 { x: 572, y: 724 };
2080        let world_dims = Aabr {
2081            min: Vec2 { x: 0, y: 0 },
2082            max: Vec2 {
2083                x: 1000_i32,
2084                y: 1000_i32,
2085            },
2086        };
2087        let reqs = ProximityRequirementsBuilder::new()
2088            .close_to_one_of(vec![a_site].into_iter(), 60)
2089            .avoid_all_of(vec![a_site].into_iter(), 40)
2090            .finalize(&world_dims);
2091        assert!(reqs.satisfied_by(Vec2 { x: 572, y: 774 }));
2092        assert!(!reqs.satisfied_by(a_site));
2093    }
2094
2095    #[test]
2096    fn location_hint() {
2097        let reqs = ProximityRequirementsBuilder::new().close_to_one_of(
2098            vec![Vec2 { x: 1, y: 0 }, Vec2 { x: 13, y: 12 }].into_iter(),
2099            10,
2100        );
2101        let expected = Aabr {
2102            min: Vec2 { x: 0, y: 0 },
2103            max: Vec2 { x: 23, y: 22 },
2104        };
2105        let map_dims = Aabr {
2106            min: Vec2 { x: 0, y: 0 },
2107            max: Vec2 { x: 200, y: 300 },
2108        };
2109        assert_eq!(expected, reqs.location_hint(&map_dims));
2110    }
2111}