veloren_world/civ/
mod.rs

1#![expect(dead_code)]
2
3pub mod airship_travel;
4mod econ;
5
6#[cfg(feature = "airship_maps")]
7pub mod airship_route_map;
8
9use crate::{
10    Index, IndexRef, Land,
11    civ::airship_travel::Airships,
12    config::CONFIG,
13    sim::WorldSim,
14    site::{self, Site as WorldSite, SiteKind, SitesGenMeta, namegen::NameGen},
15    util::{DHashMap, NEIGHBORS, attempt, seed_expan},
16};
17use common::{
18    astar::Astar,
19    calendar::Calendar,
20    path::Path,
21    spiral::Spiral2d,
22    store::{Id, Store},
23    terrain::{BiomeKind, CoordinateConversions, MapSizeLg, TerrainChunkSize, uniform_idx_as_vec2},
24    vol::RectVolSize,
25};
26use common_base::prof_span;
27use core::{fmt, hash::BuildHasherDefault, ops::Range};
28use fxhash::FxHasher64;
29use rand::{SeedableRng, prelude::*};
30use rand_chacha::ChaChaRng;
31use tracing::{debug, info, warn};
32use vek::*;
33
34fn initial_civ_count(map_size_lg: MapSizeLg) -> u32 {
35    // NOTE: since map_size_lg's dimensions must fit in a u16, we can safely add
36    // them here.
37    //
38    // NOTE: 48 at "default" scale of 10 × 10 chunk bits (1024 × 1024 chunks).
39    let cnt = (3 << (map_size_lg.vec().x + map_size_lg.vec().y)) >> 16;
40    cnt.max(1) // we need at least one civ in order to generate a starting site
41}
42
43#[derive(Default)]
44pub struct Civs {
45    pub civs: Store<Civ>,
46    pub places: Store<Place>,
47    pub pois: Store<PointOfInterest>,
48
49    pub tracks: Store<Track>,
50    /// We use this hasher (FxHasher64) because
51    /// (1) we don't care about DDOS attacks (ruling out SipHash);
52    /// (2) we care about determinism across computers (ruling out AAHash);
53    /// (3) we have 8-byte keys (for which FxHash is fastest).
54    pub track_map: DHashMap<Id<Site>, DHashMap<Id<Site>, Id<Track>>>,
55
56    pub bridges: DHashMap<Vec2<i32>, (Vec2<i32>, Id<Site>)>,
57
58    pub sites: Store<Site>,
59    pub airships: Airships,
60}
61
62// Change this to get rid of particularly horrid seeds
63const SEED_SKIP: u8 = 5;
64const POI_THINNING_DIST_SQRD: i32 = 300;
65
66pub struct GenCtx<'a, R: Rng> {
67    sim: &'a mut WorldSim,
68    rng: R,
69}
70
71struct ProximitySpec {
72    location: Vec2<i32>,
73    min_distance: Option<i32>,
74    max_distance: Option<i32>,
75}
76
77impl ProximitySpec {
78    pub fn satisfied_by(&self, site: Vec2<i32>) -> bool {
79        let distance_squared = site.distance_squared(self.location);
80        let min_ok = self
81            .min_distance
82            .map(|mind| distance_squared > (mind * mind))
83            .unwrap_or(true);
84        let max_ok = self
85            .max_distance
86            .map(|maxd| distance_squared < (maxd * maxd))
87            .unwrap_or(true);
88        min_ok && max_ok
89    }
90
91    pub fn avoid(location: Vec2<i32>, min_distance: i32) -> Self {
92        ProximitySpec {
93            location,
94            min_distance: Some(min_distance),
95            max_distance: None,
96        }
97    }
98
99    pub fn be_near(location: Vec2<i32>, max_distance: i32) -> Self {
100        ProximitySpec {
101            location,
102            min_distance: None,
103            max_distance: Some(max_distance),
104        }
105    }
106}
107
108struct ProximityRequirementsBuilder {
109    all_of: Vec<ProximitySpec>,
110    any_of: Vec<ProximitySpec>,
111}
112
113impl ProximityRequirementsBuilder {
114    pub fn finalize(self, world_dims: &Aabr<i32>) -> ProximityRequirements {
115        let location_hint = self.location_hint(world_dims);
116        ProximityRequirements {
117            all_of: self.all_of,
118            any_of: self.any_of,
119            location_hint,
120        }
121    }
122
123    fn location_hint(&self, world_dims: &Aabr<i32>) -> Aabr<i32> {
124        let bounding_box_of_point = |point: Vec2<i32>, max_distance: i32| Aabr {
125            min: Vec2 {
126                x: point.x - max_distance,
127                y: point.y - max_distance,
128            },
129            max: Vec2 {
130                x: point.x + max_distance,
131                y: point.y + max_distance,
132            },
133        };
134        let any_of_hint = self
135            .any_of
136            .iter()
137            .fold(None, |acc, spec| match spec.max_distance {
138                None => acc,
139                Some(max_distance) => {
140                    let bounding_box_of_new_point =
141                        bounding_box_of_point(spec.location, max_distance);
142                    match acc {
143                        None => Some(bounding_box_of_new_point),
144                        Some(acc) => Some(acc.union(bounding_box_of_new_point)),
145                    }
146                },
147            })
148            .map(|hint| hint.intersection(*world_dims))
149            .unwrap_or_else(|| world_dims.to_owned());
150
151        self.all_of
152            .iter()
153            .fold(any_of_hint, |acc, spec| match spec.max_distance {
154                None => acc,
155                Some(max_distance) => {
156                    let bounding_box_of_new_point =
157                        bounding_box_of_point(spec.location, max_distance);
158                    acc.intersection(bounding_box_of_new_point)
159                },
160            })
161    }
162
163    pub fn new() -> Self {
164        Self {
165            all_of: Vec::new(),
166            any_of: Vec::new(),
167        }
168    }
169
170    pub fn avoid_all_of(
171        mut self,
172        locations: impl Iterator<Item = Vec2<i32>>,
173        distance: i32,
174    ) -> Self {
175        let specs = locations.map(|loc| ProximitySpec::avoid(loc, distance));
176        self.all_of.extend(specs);
177        self
178    }
179
180    pub fn close_to_one_of(
181        mut self,
182        locations: impl Iterator<Item = Vec2<i32>>,
183        distance: i32,
184    ) -> Self {
185        let specs = locations.map(|loc| ProximitySpec::be_near(loc, distance));
186        self.any_of.extend(specs);
187        self
188    }
189}
190
191struct ProximityRequirements {
192    all_of: Vec<ProximitySpec>,
193    any_of: Vec<ProximitySpec>,
194    location_hint: Aabr<i32>,
195}
196
197impl ProximityRequirements {
198    pub fn satisfied_by(&self, site: Vec2<i32>) -> bool {
199        if self.location_hint.contains_point(site) {
200            let all_of_compliance = self.all_of.iter().all(|spec| spec.satisfied_by(site));
201            let any_of_compliance =
202                self.any_of.is_empty() || self.any_of.iter().any(|spec| spec.satisfied_by(site));
203            all_of_compliance && any_of_compliance
204        } else {
205            false
206        }
207    }
208}
209
210impl<R: Rng> GenCtx<'_, R> {
211    pub fn reseed(&mut self) -> GenCtx<'_, impl Rng + use<R>> {
212        let mut entropy = self.rng.random::<[u8; 32]>();
213        entropy[0] = entropy[0].wrapping_add(SEED_SKIP); // Skip bad seeds
214        GenCtx {
215            sim: self.sim,
216            rng: ChaChaRng::from_seed(entropy),
217        }
218    }
219}
220
221#[derive(Debug)]
222pub enum WorldCivStage {
223    /// Civilization creation, how many out of how many civilizations have been
224    /// generated yet
225    CivCreation(u32, u32),
226    SiteGeneration,
227}
228
229impl Civs {
230    pub fn generate(
231        seed: u32,
232        sim: &mut WorldSim,
233        index: &mut Index,
234        calendar: Option<&Calendar>,
235        report_stage: &dyn Fn(WorldCivStage),
236    ) -> Self {
237        prof_span!("Civs::generate");
238        let mut this = Self::default();
239        let rng = ChaChaRng::from_seed(seed_expan::rng_state(seed));
240        let name_rng = rng.clone();
241        let mut name_ctx = GenCtx { sim, rng: name_rng };
242        if index.features().peak_naming {
243            info!("starting peak naming");
244            this.name_peaks(&mut name_ctx);
245        }
246        if index.features().biome_naming {
247            info!("starting biome naming");
248            this.name_biomes(&mut name_ctx);
249        }
250
251        let initial_civ_count = initial_civ_count(sim.map_size_lg());
252        let mut ctx = GenCtx { sim, rng };
253
254        // info!("starting cave generation");
255        // this.generate_caves(&mut ctx);
256
257        info!("starting civilisation creation");
258        prof_span!(guard, "create civs");
259        for i in 0..initial_civ_count {
260            prof_span!("create civ");
261            debug!("Creating civilisation...");
262            if this.birth_civ(&mut ctx.reseed()).is_none() {
263                warn!("Failed to find starting site for civilisation.");
264            }
265            report_stage(WorldCivStage::CivCreation(i, initial_civ_count));
266        }
267        drop(guard);
268        info!(?initial_civ_count, "all civilisations created");
269
270        report_stage(WorldCivStage::SiteGeneration);
271        prof_span!(guard, "find locations and establish sites");
272        let world_dims = ctx.sim.get_aabr();
273        for _ in 0..initial_civ_count * 3 {
274            attempt(5, || {
275                let (loc, kind) = match ctx.rng.random_range(0..116) {
276                    0..=4 => (
277                        find_site_loc(
278                            &mut ctx,
279                            &ProximityRequirementsBuilder::new()
280                                .avoid_all_of(this.tree_enemies(), 40)
281                                .finalize(&world_dims),
282                            &SiteKind::GiantTree,
283                        )?,
284                        SiteKind::GiantTree,
285                    ),
286                    5..=15 => (
287                        find_site_loc(
288                            &mut ctx,
289                            &ProximityRequirementsBuilder::new()
290                                .avoid_all_of(this.gnarling_enemies(), 40)
291                                .finalize(&world_dims),
292                            &SiteKind::Gnarling,
293                        )?,
294                        SiteKind::Gnarling,
295                    ),
296                    16..=20 => (
297                        find_site_loc(
298                            &mut ctx,
299                            &ProximityRequirementsBuilder::new()
300                                .avoid_all_of(this.chapel_site_enemies(), 40)
301                                .finalize(&world_dims),
302                            &SiteKind::ChapelSite,
303                        )?,
304                        SiteKind::ChapelSite,
305                    ),
306                    21..=27 => (
307                        find_site_loc(
308                            &mut ctx,
309                            &ProximityRequirementsBuilder::new()
310                                .avoid_all_of(this.gnarling_enemies(), 40)
311                                .finalize(&world_dims),
312                            &SiteKind::Adlet,
313                        )?,
314                        SiteKind::Adlet,
315                    ),
316                    28..=38 => (
317                        find_site_loc(
318                            &mut ctx,
319                            &ProximityRequirementsBuilder::new()
320                                .avoid_all_of(this.pirate_hideout_enemies(), 40)
321                                .finalize(&world_dims),
322                            &SiteKind::PirateHideout,
323                        )?,
324                        SiteKind::PirateHideout,
325                    ),
326                    39..=45 => (
327                        find_site_loc(
328                            &mut ctx,
329                            &ProximityRequirementsBuilder::new()
330                                .avoid_all_of(this.jungle_ruin_enemies(), 40)
331                                .finalize(&world_dims),
332                            &SiteKind::JungleRuin,
333                        )?,
334                        SiteKind::JungleRuin,
335                    ),
336                    46..=55 => (
337                        find_site_loc(
338                            &mut ctx,
339                            &ProximityRequirementsBuilder::new()
340                                .avoid_all_of(this.rock_circle_enemies(), 40)
341                                .finalize(&world_dims),
342                            &SiteKind::RockCircle,
343                        )?,
344                        SiteKind::RockCircle,
345                    ),
346                    56..=66 => (
347                        find_site_loc(
348                            &mut ctx,
349                            &ProximityRequirementsBuilder::new()
350                                .avoid_all_of(this.troll_cave_enemies(), 40)
351                                .finalize(&world_dims),
352                            &SiteKind::TrollCave,
353                        )?,
354                        SiteKind::TrollCave,
355                    ),
356                    67..=72 => (
357                        find_site_loc(
358                            &mut ctx,
359                            &ProximityRequirementsBuilder::new()
360                                .avoid_all_of(this.camp_enemies(), 40)
361                                .finalize(&world_dims),
362                            &SiteKind::Camp,
363                        )?,
364                        SiteKind::Camp,
365                    ),
366                    73..=76 => (
367                        find_site_loc(
368                            &mut ctx,
369                            &ProximityRequirementsBuilder::new()
370                                .avoid_all_of(this.mine_site_enemies(), 40)
371                                .finalize(&world_dims),
372                            &SiteKind::Haniwa,
373                        )?,
374                        SiteKind::Haniwa,
375                    ),
376                    77..=81 => (
377                        find_site_loc(
378                            &mut ctx,
379                            &ProximityRequirementsBuilder::new()
380                                .avoid_all_of(this.terracotta_enemies(), 40)
381                                .finalize(&world_dims),
382                            &SiteKind::Terracotta,
383                        )?,
384                        SiteKind::Terracotta,
385                    ),
386                    82..=87 => (
387                        find_site_loc(
388                            &mut ctx,
389                            &ProximityRequirementsBuilder::new()
390                                .avoid_all_of(this.mine_site_enemies(), 40)
391                                .finalize(&world_dims),
392                            &SiteKind::DwarvenMine,
393                        )?,
394                        SiteKind::DwarvenMine,
395                    ),
396                    88..=91 => (
397                        find_site_loc(
398                            &mut ctx,
399                            &ProximityRequirementsBuilder::new()
400                                .avoid_all_of(this.cultist_enemies(), 40)
401                                .finalize(&world_dims),
402                            &SiteKind::Cultist,
403                        )?,
404                        SiteKind::Cultist,
405                    ),
406                    92..=96 => (
407                        find_site_loc(
408                            &mut ctx,
409                            &ProximityRequirementsBuilder::new()
410                                .avoid_all_of(this.sahagin_enemies(), 40)
411                                .finalize(&world_dims),
412                            &SiteKind::Sahagin,
413                        )?,
414                        SiteKind::Sahagin,
415                    ),
416                    97..=102 => (
417                        find_site_loc(
418                            &mut ctx,
419                            &ProximityRequirementsBuilder::new()
420                                .avoid_all_of(this.vampire_castle_enemies(), 40)
421                                .finalize(&world_dims),
422                            &SiteKind::VampireCastle,
423                        )?,
424                        SiteKind::VampireCastle,
425                    ),
426                    103..108 => (
427                        find_site_loc(
428                            &mut ctx,
429                            &ProximityRequirementsBuilder::new().finalize(&world_dims),
430                            &SiteKind::GliderCourse,
431                        )?,
432                        SiteKind::GliderCourse,
433                    ),
434                    /*103..=108 => (
435                        find_site_loc(
436                            &mut ctx,
437                            &ProximityRequirementsBuilder::new()
438                                .avoid_all_of(this.castle_enemies(), 40)
439                                .close_to_one_of(this.towns(), 20)
440                                .finalize(&world_dims),
441                            &SiteKind::Castle,
442                        )?,
443                        SiteKind::Castle,
444                    ),
445                    109..=114 => (SiteKind::Citadel, (&castle_enemies, 20)),
446                    */
447                    _ => (
448                        find_site_loc(
449                            &mut ctx,
450                            &ProximityRequirementsBuilder::new()
451                                .avoid_all_of(this.myrmidon_enemies(), 40)
452                                .finalize(&world_dims),
453                            &SiteKind::Myrmidon,
454                        )?,
455                        SiteKind::Myrmidon,
456                    ),
457                };
458                Some(this.establish_site(&mut ctx.reseed(), loc, |place| Site {
459                    kind,
460                    center: loc,
461                    place,
462                    site_tmp: None,
463                }))
464            });
465        }
466        drop(guard);
467
468        // Tick
469        //=== old economy is gone
470
471        // Flatten ground around sites
472        prof_span!(guard, "Flatten ground around sites");
473        for site in this.sites.values() {
474            let wpos = site.center * TerrainChunkSize::RECT_SIZE.map(|e: u32| e as i32);
475
476            let (radius, flatten_radius) = match &site.kind {
477                SiteKind::Refactor => (32i32, 10.0),
478                SiteKind::CliffTown => (2i32, 1.0),
479                SiteKind::SavannahTown => (48i32, 25.0),
480                SiteKind::CoastalTown => (64i32, 35.0),
481                SiteKind::JungleRuin => (8i32, 3.0),
482                SiteKind::DesertCity => (64i32, 25.0),
483                SiteKind::ChapelSite => (36i32, 10.0),
484                SiteKind::Terracotta => (64i32, 35.0),
485                SiteKind::GiantTree => (12i32, 8.0),
486                SiteKind::Gnarling => (16i32, 10.0),
487                SiteKind::Citadel => (16i32, 0.0),
488                SiteKind::Bridge(_, _) => (0, 0.0),
489                SiteKind::Adlet => (16i32, 0.0),
490                SiteKind::Haniwa => (32i32, 16.0),
491                SiteKind::PirateHideout => (8i32, 3.0),
492                SiteKind::RockCircle => (8i32, 3.0),
493                SiteKind::TrollCave => (4i32, 1.5),
494                SiteKind::Camp => (4i32, 1.5),
495                SiteKind::DwarvenMine => (8i32, 3.0),
496                SiteKind::Cultist => (24i32, 10.0),
497                SiteKind::Sahagin => (8i32, 3.0),
498                SiteKind::VampireCastle => (10i32, 16.0),
499                SiteKind::GliderCourse => (0, 0.0),
500                SiteKind::Myrmidon => (64i32, 35.0),
501            };
502
503            // Flatten ground
504            if let Some(center_alt) = ctx.sim.get_alt_approx(wpos) {
505                for offs in Spiral2d::new().take(radius.pow(2) as usize) {
506                    let pos = site.center + offs;
507                    let factor = ((1.0
508                        - (site.center - pos).map(|e| e as f32).magnitude()
509                            / f32::max(flatten_radius, 0.01))
510                        * 1.25)
511                        .min(1.0);
512                    let rng = &mut ctx.rng;
513                    ctx.sim
514                        .get_mut(pos)
515                        // Don't disrupt chunks that are near water
516                        .filter(|chunk| !chunk.river.near_water())
517                        .map(|chunk| {
518                            let diff = Lerp::lerp_precise(chunk.alt, center_alt, factor) - chunk.alt;
519                            // Make sure we don't fall below sea level (fortunately, we don't have
520                            // to worry about the case where water_alt is already set to a correct
521                            // value higher than alt, since this chunk should have been filtered
522                            // out in that case).
523                            chunk.water_alt = CONFIG.sea_level.max(chunk.water_alt + diff);
524                            chunk.alt += diff;
525                            chunk.basement += diff;
526                            chunk.rockiness = 0.0;
527                            chunk.surface_veg *= 1.0 - factor * rng.random_range(0.25..0.9);
528                        });
529                }
530            }
531        }
532        drop(guard);
533
534        // Place sites in world
535        prof_span!(guard, "Place sites in world");
536        let mut cnt = 0;
537        let mut gen_meta = SitesGenMeta::new(seed);
538        for sim_site in this.sites.values_mut() {
539            cnt += 1;
540            let wpos = sim_site
541                .center
542                .map2(TerrainChunkSize::RECT_SIZE, |e, sz: u32| {
543                    e * sz as i32 + sz as i32 / 2
544                });
545
546            let mut rng = ctx.reseed().rng;
547            let site = index.sites.insert({
548                let index_ref = IndexRef {
549                    colors: &index.colors(),
550                    features: &index.features(),
551                    index,
552                };
553                match &sim_site.kind {
554                    SiteKind::Refactor => {
555                        let size = Lerp::lerp(0.03, 1.0, rng.random_range(0.0..1f32).powi(5));
556                        WorldSite::generate_city(
557                            &Land::from_sim(ctx.sim),
558                            index_ref,
559                            &mut rng,
560                            wpos,
561                            size,
562                            calendar,
563                            &mut gen_meta,
564                        )
565                    },
566                    SiteKind::GliderCourse => WorldSite::generate_glider_course(
567                        &Land::from_sim(ctx.sim),
568                        index_ref,
569                        &mut rng,
570                        wpos,
571                    ),
572                    SiteKind::CliffTown => WorldSite::generate_cliff_town(
573                        &Land::from_sim(ctx.sim),
574                        index_ref,
575                        &mut rng,
576                        wpos,
577                        &mut gen_meta,
578                    ),
579                    SiteKind::SavannahTown => WorldSite::generate_savannah_town(
580                        &Land::from_sim(ctx.sim),
581                        index_ref,
582                        &mut rng,
583                        wpos,
584                        &mut gen_meta,
585                    ),
586                    SiteKind::CoastalTown => WorldSite::generate_coastal_town(
587                        &Land::from_sim(ctx.sim),
588                        index_ref,
589                        &mut rng,
590                        wpos,
591                        &mut gen_meta,
592                    ),
593                    SiteKind::PirateHideout => {
594                        WorldSite::generate_pirate_hideout(&Land::from_sim(ctx.sim), &mut rng, wpos)
595                    },
596                    SiteKind::JungleRuin => {
597                        WorldSite::generate_jungle_ruin(&Land::from_sim(ctx.sim), &mut rng, wpos)
598                    },
599                    SiteKind::RockCircle => {
600                        WorldSite::generate_rock_circle(&Land::from_sim(ctx.sim), &mut rng, wpos)
601                    },
602
603                    SiteKind::TrollCave => {
604                        WorldSite::generate_troll_cave(&Land::from_sim(ctx.sim), &mut rng, wpos)
605                    },
606                    SiteKind::Camp => {
607                        WorldSite::generate_camp(&Land::from_sim(ctx.sim), &mut rng, wpos)
608                    },
609                    SiteKind::DesertCity => WorldSite::generate_desert_city(
610                        &Land::from_sim(ctx.sim),
611                        index_ref,
612                        &mut rng,
613                        wpos,
614                        &mut gen_meta,
615                    ),
616                    SiteKind::GiantTree => {
617                        WorldSite::generate_giant_tree(&Land::from_sim(ctx.sim), &mut rng, wpos)
618                    },
619                    SiteKind::Gnarling => {
620                        WorldSite::generate_gnarling(&Land::from_sim(ctx.sim), &mut rng, wpos)
621                    },
622                    SiteKind::DwarvenMine => {
623                        WorldSite::generate_mine(&Land::from_sim(ctx.sim), &mut rng, wpos)
624                    },
625                    SiteKind::ChapelSite => {
626                        WorldSite::generate_chapel_site(&Land::from_sim(ctx.sim), &mut rng, wpos)
627                    },
628                    SiteKind::Terracotta => WorldSite::generate_terracotta(
629                        &Land::from_sim(ctx.sim),
630                        index_ref,
631                        &mut rng,
632                        wpos,
633                        &mut gen_meta,
634                    ),
635                    SiteKind::Citadel => {
636                        WorldSite::generate_citadel(&Land::from_sim(ctx.sim), &mut rng, wpos)
637                    },
638                    SiteKind::Bridge(a, b) => {
639                        let mut bridge_site = WorldSite::generate_bridge(
640                            &Land::from_sim(ctx.sim),
641                            index_ref,
642                            &mut rng,
643                            *a,
644                            *b,
645                        );
646
647                        // Update the path connecting to the bridge to line up better.
648                        if let Some(bridge) =
649                            bridge_site
650                                .plots
651                                .values()
652                                .find_map(|plot| match &plot.kind {
653                                    site::PlotKind::Bridge(bridge) => Some(bridge),
654                                    _ => None,
655                                })
656                        {
657                            let mut update_offset = |original: Vec2<i32>, new: Vec2<i32>| {
658                                let chunk = original.wpos_to_cpos();
659                                if let Some(c) = ctx.sim.get_mut(chunk) {
660                                    c.path.0.offset = (new - chunk.cpos_to_wpos_center())
661                                        .map(|e| e.clamp(-16, 16) as i8);
662                                }
663                            };
664
665                            update_offset(bridge.original_start, bridge.start.xy());
666                            update_offset(bridge.original_end, bridge.end.xy());
667                        }
668                        bridge_site.demarcate_obstacles(&Land::from_sim(ctx.sim));
669                        bridge_site
670                    },
671                    SiteKind::Adlet => WorldSite::generate_adlet(
672                        &Land::from_sim(ctx.sim),
673                        &mut rng,
674                        wpos,
675                        index_ref,
676                    ),
677                    SiteKind::Haniwa => {
678                        WorldSite::generate_haniwa(&Land::from_sim(ctx.sim), &mut rng, wpos)
679                    },
680                    SiteKind::Cultist => {
681                        WorldSite::generate_cultist(&Land::from_sim(ctx.sim), &mut rng, wpos)
682                    },
683                    SiteKind::Myrmidon => WorldSite::generate_myrmidon(
684                        &Land::from_sim(ctx.sim),
685                        index_ref,
686                        &mut rng,
687                        wpos,
688                        &mut gen_meta,
689                    ),
690                    SiteKind::Sahagin => WorldSite::generate_sahagin(
691                        &Land::from_sim(ctx.sim),
692                        index_ref,
693                        &mut rng,
694                        wpos,
695                    ),
696                    SiteKind::VampireCastle => {
697                        WorldSite::generate_vampire_castle(&Land::from_sim(ctx.sim), &mut rng, wpos)
698                    },
699                }
700            });
701            sim_site.site_tmp = Some(site);
702            let site_ref = &index.sites[site];
703
704            let radius_chunks =
705                (site_ref.radius() / TerrainChunkSize::RECT_SIZE.x as f32).ceil() as usize;
706            for pos in Spiral2d::new()
707                .map(|offs| sim_site.center + offs)
708                .take((radius_chunks * 2).pow(2))
709            {
710                ctx.sim.get_mut(pos).map(|chunk| chunk.sites.push(site));
711            }
712            debug!(?sim_site.center, "Placed site at location");
713        }
714        drop(guard);
715        info!(?cnt, "all sites placed");
716        gen_meta.log();
717
718        //this.display_info();
719
720        // remember neighbor information in economy
721        for (s1, val) in this.track_map.iter() {
722            if let Some(index1) = this.sites.get(*s1).site_tmp {
723                for (s2, t) in val.iter() {
724                    if let Some(index2) = this.sites.get(*s2).site_tmp
725                        && index.sites.get(index1).do_economic_simulation()
726                        && index.sites.get(index2).do_economic_simulation()
727                    {
728                        let cost = this.tracks.get(*t).path.len();
729                        index
730                            .sites
731                            .get_mut(index1)
732                            .economy_mut()
733                            .add_neighbor(index2, cost);
734                        index
735                            .sites
736                            .get_mut(index2)
737                            .economy_mut()
738                            .add_neighbor(index1, cost);
739                    }
740                }
741            }
742        }
743
744        prof_span!(guard, "generate airship routes");
745        this.airships.generate_airship_routes(ctx.sim, index);
746        drop(guard);
747
748        // TODO: this looks optimizable
749
750        // collect natural resources
751        prof_span!(guard, "collect natural resources");
752        let sites = &mut index.sites;
753        (0..ctx.sim.map_size_lg().chunks_len()).for_each(|posi| {
754            let chpos = uniform_idx_as_vec2(ctx.sim.map_size_lg(), posi);
755            let wpos = chpos.map(|e| e as i64) * TerrainChunkSize::RECT_SIZE.map(|e| e as i64);
756            let closest_site = (*sites)
757                .iter_mut()
758                .filter(|s| !matches!(s.1.kind, Some(crate::site::SiteKind::Myrmidon)))
759                .min_by_key(|(_id, s)| s.origin.map(|e| e as i64).distance_squared(wpos));
760            if let Some((_id, s)) = closest_site
761                && s.do_economic_simulation()
762            {
763                let distance_squared = s.origin.map(|e| e as i64).distance_squared(wpos);
764                s.economy_mut()
765                    .add_chunk(ctx.sim.get(chpos).unwrap(), distance_squared);
766            }
767        });
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.random_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(&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(&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(&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(&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(&mut ctx.rng)
991                    .unwrap(),
992                    ["Sea", "Bay", "Gulf", "Deep", "Depths", "Ocean", "Blue",]
993                        .choose_mut(&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(&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(&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(&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(&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(&mut ctx.rng)
1054                    .unwrap(),
1055                    [
1056                        "Desert", "Sands", "Sandsea", "Drifts", "Dunes", "Droughts", "Flats",
1057                    ]
1058                    .choose_mut(&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(&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(&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(&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(&mut ctx.rng)
1108                    .unwrap(),
1109                    ["Forest", "Woodlands", "Woods", "Glades", "Grove", "Weald",]
1110                        .choose_mut(&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(&mut ctx.rng)
1121                        .unwrap(),
1122                        [
1123                            "Savannah",
1124                            "Shrublands",
1125                            "Sierra",
1126                            "Prairie",
1127                            "Lowlands",
1128                            "Flats",
1129                        ]
1130                        .choose_mut(&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(&mut ctx.rng)
1141                    .unwrap(),
1142                    [
1143                        "Forest",
1144                        "Woodlands",
1145                        "Woods",
1146                        "Timberlands",
1147                        "Highlands",
1148                        "Uplands",
1149                    ]
1150                    .choose_mut(&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.random_range(0..6) {
1242                                0 => format!("{} Bluff", name),
1243                                1 => format!("{} Crag", name),
1244                                _ => format!("{} Hill", name),
1245                            }
1246                        } else {
1247                            match rng.random_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 = Vec2::new(
1356                                ctx.rng.random_range(-16..17),
1357                                ctx.rng.random_range(-16..17),
1358                            );
1359                        } else if !self.bridges.contains_key(&locs[1]) {
1360                            let center = (locs[1] + locs[2]) / 2;
1361                            let id =
1362                                establish_site(self, &mut ctx.reseed(), center, move |place| {
1363                                    Site {
1364                                        kind: SiteKind::Bridge(locs[1], locs[2]),
1365                                        site_tmp: None,
1366                                        center,
1367                                        place,
1368                                    }
1369                                });
1370                            self.bridges.insert(locs[1], (locs[2], id));
1371                            self.bridges.insert(locs[2], (locs[1], id));
1372                        }
1373                        /*
1374                        let to_prev_idx = NEIGHBORS
1375                            .iter()
1376                            .enumerate()
1377                            .find(|(_, dir)| **dir == (locs[0] - locs[1]).map(|e| e.signum()))
1378                            .expect("Track locations must be neighbors")
1379                            .0;
1380
1381                        let to_next_idx = NEIGHBORS
1382                            .iter()
1383                            .enumerate()
1384                            .find(|(_, dir)| **dir == (locs[2] - locs[1]).map(|e| e.signum()))
1385                            .expect("Track locations must be neighbors")
1386                            .0;
1387
1388                        ctx.sim.get_mut(locs[0]).unwrap().path.0.neighbors |=
1389                            1 << ((to_prev_idx as u8 + 4) % 8);
1390                        ctx.sim.get_mut(locs[2]).unwrap().path.0.neighbors |=
1391                            1 << ((to_next_idx as u8 + 4) % 8);
1392                        let mut chunk = ctx.sim.get_mut(locs[1]).unwrap();
1393                        chunk.path.0.neighbors |=
1394                            (1 << (to_prev_idx as u8)) | (1 << (to_next_idx as u8));
1395                        */
1396                    }
1397
1398                    // Take note of the track
1399                    let track = self.tracks.insert(Track { cost, path });
1400                    self.track_map
1401                        .entry(site)
1402                        .or_default()
1403                        .insert(nearby, track);
1404                }
1405            }
1406        }
1407
1408        site
1409    }
1410
1411    fn gnarling_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1412        self.sites().filter_map(|s| match s.kind {
1413            SiteKind::GiantTree => None,
1414            _ => Some(s.center),
1415        })
1416    }
1417
1418    fn adlet_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1419        self.sites().map(|s| s.center)
1420    }
1421
1422    fn haniwa_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1423        self.sites().map(|s| s.center)
1424    }
1425
1426    fn chapel_site_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1427        self.sites().map(|s| s.center)
1428    }
1429
1430    fn mine_site_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1431        self.sites().map(|s| s.center)
1432    }
1433
1434    fn terracotta_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1435        self.sites().map(|s| s.center)
1436    }
1437
1438    fn cultist_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1439        self.sites().map(|s| s.center)
1440    }
1441
1442    fn myrmidon_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1443        self.sites().map(|s| s.center)
1444    }
1445
1446    fn vampire_castle_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1447        self.sites().map(|s| s.center)
1448    }
1449
1450    fn tree_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1451        self.sites().map(|s| s.center)
1452    }
1453
1454    fn castle_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1455        self.sites().filter_map(|s| {
1456            if s.is_settlement() {
1457                None
1458            } else {
1459                Some(s.center)
1460            }
1461        })
1462    }
1463
1464    fn jungle_ruin_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1465        self.sites().map(|s| s.center)
1466    }
1467
1468    fn town_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1469        self.sites().filter_map(|s| match s.kind {
1470            SiteKind::Citadel => None,
1471            _ => Some(s.center),
1472        })
1473    }
1474
1475    fn towns(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1476        self.sites().filter_map(|s| {
1477            if s.is_settlement() {
1478                Some(s.center)
1479            } else {
1480                None
1481            }
1482        })
1483    }
1484
1485    fn pirate_hideout_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1486        self.sites().map(|s| s.center)
1487    }
1488
1489    fn sahagin_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1490        self.sites().map(|s| s.center)
1491    }
1492
1493    fn rock_circle_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1494        self.sites().map(|s| s.center)
1495    }
1496
1497    fn troll_cave_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1498        self.sites().map(|s| s.center)
1499    }
1500
1501    fn camp_enemies(&self) -> impl Iterator<Item = Vec2<i32>> + '_ {
1502        self.sites().map(|s| s.center)
1503    }
1504}
1505
1506/// Attempt to find a path between two locations
1507fn find_path(
1508    ctx: &mut GenCtx<impl Rng>,
1509    get_bridge: impl Fn(Vec2<i32>) -> Option<Vec2<i32>>,
1510    a: Vec2<i32>,
1511    b: Vec2<i32>,
1512    max_path_cost: f32,
1513) -> Option<(Path<Vec2<i32>>, f32)> {
1514    prof_span!("find_path");
1515    const MAX_PATH_ITERS: usize = 100_000;
1516    let sim = &ctx.sim;
1517    // NOTE: If heuristic overestimates the actual cost, then A* is not guaranteed
1518    // to produce the least-cost path (since it will explore partially based on
1519    // the heuristic).
1520    // TODO: heuristic can be larger than actual cost, since existing bridges cost
1521    // 1.0 (after the 1.0 that is added to everthting), but they can cover
1522    // multiple chunks.
1523    let heuristic = move |l: &Vec2<i32>| (l.distance_squared(b) as f32).sqrt();
1524    let neighbors = |l: &Vec2<i32>| {
1525        let l = *l;
1526        let bridge = get_bridge(l);
1527        let potential = walk_in_all_dirs(sim, bridge, l);
1528        potential
1529            .into_iter()
1530            .filter_map(|p| p.map(|(node, cost)| (node, cost + 1.0)))
1531    };
1532    let satisfied = |l: &Vec2<i32>| *l == b;
1533    // We use this hasher (FxHasher64) because
1534    // (1) we don't care about DDOS attacks (ruling out SipHash);
1535    // (2) we care about determinism across computers (ruling out AAHash);
1536    // (3) we have 8-byte keys (for which FxHash is fastest).
1537    let mut astar = Astar::new(
1538        MAX_PATH_ITERS,
1539        a,
1540        BuildHasherDefault::<FxHasher64>::default(),
1541    )
1542    .with_max_cost(max_path_cost);
1543    astar
1544        .poll(MAX_PATH_ITERS, heuristic, neighbors, satisfied)
1545        .into_path()
1546}
1547
1548/// Return Some if travel between a location and a chunk next to it is permitted
1549/// If permitted, the approximate relative const of traversal is given
1550// (TODO: by whom?)
1551/// Return tuple: (final location, cost)
1552///
1553/// For efficiency, this computes for all 8 directions at once.
1554fn walk_in_all_dirs(
1555    sim: &WorldSim,
1556    bridge: Option<Vec2<i32>>,
1557    a: Vec2<i32>,
1558) -> [Option<(Vec2<i32>, f32)>; 8] {
1559    let mut potential = [None; 8];
1560
1561    let adjacents = NEIGHBORS.map(|dir| a + dir);
1562
1563    let Some(a_chunk) = sim.get(a) else {
1564        return potential;
1565    };
1566    let mut chunks = [None; 8];
1567    for i in 0..8 {
1568        if loc_suitable_for_walking(sim, adjacents[i]) {
1569            chunks[i] = sim.get(adjacents[i]);
1570        }
1571    }
1572
1573    for i in 0..8 {
1574        let Some(b_chunk) = chunks[i] else { continue };
1575
1576        let hill_cost = ((b_chunk.alt - a_chunk.alt).abs() / 5.0).powi(2);
1577        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
1578        let wild_cost = if b_chunk.path.0.is_way() {
1579            0.0 // Traversing existing paths has no additional cost!
1580        } else {
1581            3.0 // + (1.0 - b_chunk.tree_density) * 20.0 // Prefer going through forests, for aesthetics
1582        };
1583
1584        let cost = 1.0 + hill_cost + water_cost + wild_cost;
1585        potential[i] = Some((adjacents[i], cost));
1586    }
1587
1588    // Look for potential bridge spots in the cardinal directions if
1589    // `loc_suitable_for_wallking` was false for the adjacent chunk.
1590    for (i, &dir) in NEIGHBORS.iter().enumerate() {
1591        let is_cardinal_dir = dir.x == 0 || dir.y == 0;
1592        if is_cardinal_dir && potential[i].is_none() {
1593            // if we can skip over unsuitable area with a bridge
1594            potential[i] = (4..=5).find_map(|i| {
1595                loc_suitable_for_walking(sim, a + dir * i)
1596                    .then(|| (a + dir * i, 120.0 + (i - 4) as f32 * 10.0))
1597            });
1598        }
1599    }
1600
1601    // If current position is a bridge, skip to its destination.
1602    if let Some(p) = bridge {
1603        let dir = (p - a).map(|e| e.signum());
1604        if let Some((dir_index, _)) = NEIGHBORS
1605            .iter()
1606            .enumerate()
1607            .find(|(_, n_dir)| **n_dir == dir)
1608        {
1609            potential[dir_index] = Some((p, (p - a).map(|e| e.abs()).reduce_max() as f32));
1610        }
1611    }
1612
1613    potential
1614}
1615
1616/// Return true if a position is suitable for walking on
1617fn loc_suitable_for_walking(sim: &WorldSim, loc: Vec2<i32>) -> bool {
1618    if sim.get(loc).is_some() {
1619        NEIGHBORS.iter().all(|n| {
1620            sim.get(loc + *n)
1621                .is_some_and(|chunk| !chunk.river.near_water())
1622        })
1623    } else {
1624        false
1625    }
1626}
1627
1628/// Attempt to search for a location that's suitable for site construction
1629// FIXME when a `close_to_one_of` requirement is passed in, we should start with
1630// just the chunks around those locations instead of random sampling the entire
1631// map
1632fn find_site_loc(
1633    ctx: &mut GenCtx<impl Rng>,
1634    proximity_reqs: &ProximityRequirements,
1635    site_kind: &SiteKind,
1636) -> Option<Vec2<i32>> {
1637    prof_span!("find_site_loc");
1638    const MAX_ATTEMPTS: usize = 10000;
1639    let mut loc = None;
1640    let location_hint = proximity_reqs.location_hint;
1641    for _ in 0..MAX_ATTEMPTS {
1642        let test_loc = loc.unwrap_or_else(|| {
1643            Vec2::new(
1644                ctx.rng
1645                    .random_range(location_hint.min.x..location_hint.max.x),
1646                ctx.rng
1647                    .random_range(location_hint.min.y..location_hint.max.y),
1648            )
1649        });
1650
1651        let is_suitable_loc = site_kind.is_suitable_loc(test_loc, ctx.sim);
1652        if is_suitable_loc && proximity_reqs.satisfied_by(test_loc) {
1653            if site_kind.exclusion_radius_clear(ctx.sim, test_loc) {
1654                return Some(test_loc);
1655            }
1656
1657            // If the current location is suitable and meets proximity requirements,
1658            // try nearby spot downhill.
1659            loc = ctx.sim.get(test_loc).and_then(|c| c.downhill);
1660        }
1661    }
1662
1663    debug!("Failed to place site {:?}.", site_kind);
1664    None
1665}
1666
1667fn town_attributes_of_site(loc: Vec2<i32>, sim: &WorldSim) -> Option<TownSiteAttributes> {
1668    sim.get(loc).map(|chunk| {
1669        const RESOURCE_RADIUS: i32 = 1;
1670        let mut river_chunks = 0;
1671        let mut lake_chunks = 0;
1672        let mut ocean_chunks = 0;
1673        let mut rock_chunks = 0;
1674        let mut tree_chunks = 0;
1675        let mut farmable_chunks = 0;
1676        let mut farmable_needs_irrigation_chunks = 0;
1677        let mut land_chunks = 0;
1678        for x in (-RESOURCE_RADIUS)..RESOURCE_RADIUS {
1679            for y in (-RESOURCE_RADIUS)..RESOURCE_RADIUS {
1680                let check_loc = loc + Vec2::new(x, y).cpos_to_wpos();
1681                sim.get(check_loc).map(|c| {
1682                    if num::abs(chunk.alt - c.alt) < 200.0 {
1683                        if c.river.is_river() {
1684                            river_chunks += 1;
1685                        }
1686                        if c.river.is_lake() {
1687                            lake_chunks += 1;
1688                        }
1689                        if c.river.is_ocean() {
1690                            ocean_chunks += 1;
1691                        }
1692                        if c.tree_density > 0.7 {
1693                            tree_chunks += 1;
1694                        }
1695                        if c.rockiness < 0.3 && c.temp > CONFIG.snow_temp {
1696                            if c.surface_veg > 0.5 {
1697                                farmable_chunks += 1;
1698                            } else {
1699                                match c.get_biome() {
1700                                    common::terrain::BiomeKind::Savannah => {
1701                                        farmable_needs_irrigation_chunks += 1
1702                                    },
1703                                    common::terrain::BiomeKind::Desert => {
1704                                        farmable_needs_irrigation_chunks += 1
1705                                    },
1706                                    _ => (),
1707                                }
1708                            }
1709                        }
1710                        if !c.river.is_river() && !c.river.is_lake() && !c.river.is_ocean() {
1711                            land_chunks += 1;
1712                        }
1713                    }
1714                    // Mining is different since presumably you dig into the hillside
1715                    if c.rockiness > 0.7 && c.alt - chunk.alt > -10.0 {
1716                        rock_chunks += 1;
1717                    }
1718                });
1719            }
1720        }
1721        let has_river = river_chunks > 1;
1722        let has_lake = lake_chunks > 1;
1723        let vegetation_implies_potable_water = chunk.tree_density > 0.4
1724            && !matches!(chunk.get_biome(), common::terrain::BiomeKind::Swamp);
1725        let has_many_rocks = chunk.rockiness > 1.2;
1726        let warm_or_firewood = chunk.temp > CONFIG.snow_temp || tree_chunks > 2;
1727        let has_potable_water =
1728            { has_river || (has_lake && chunk.alt > 100.0) || vegetation_implies_potable_water };
1729        let has_building_materials = tree_chunks > 0
1730            || rock_chunks > 0
1731            || chunk.temp > CONFIG.tropical_temp && (has_river || has_lake);
1732        let water_rich = lake_chunks + river_chunks > 2;
1733        let can_grow_rice = water_rich
1734            && chunk.humidity + 1.0 > CONFIG.jungle_hum
1735            && chunk.temp + 1.0 > CONFIG.tropical_temp;
1736        let farming_score = if can_grow_rice {
1737            farmable_chunks * 2
1738        } else {
1739            farmable_chunks
1740        } + if water_rich {
1741            farmable_needs_irrigation_chunks
1742        } else {
1743            0
1744        };
1745        let fish_score = lake_chunks + ocean_chunks;
1746        let food_score = farming_score + fish_score;
1747        let mining_score = if tree_chunks > 1 { rock_chunks } else { 0 };
1748        let forestry_score = if has_river { tree_chunks } else { 0 };
1749        let trading_score = std::cmp::min(std::cmp::min(land_chunks, ocean_chunks), river_chunks);
1750        TownSiteAttributes {
1751            food_score,
1752            mining_score,
1753            forestry_score,
1754            trading_score,
1755            heating: warm_or_firewood,
1756            potable_water: has_potable_water,
1757            building_materials: has_building_materials,
1758            aquifer: has_many_rocks,
1759        }
1760    })
1761}
1762
1763pub struct TownSiteAttributes {
1764    food_score: i32,
1765    mining_score: i32,
1766    forestry_score: i32,
1767    trading_score: i32,
1768    heating: bool,
1769    potable_water: bool,
1770    building_materials: bool,
1771    aquifer: bool,
1772}
1773
1774impl TownSiteAttributes {
1775    pub fn score(&self) -> f32 {
1776        3.0 * (self.food_score as f32 + 1.0).log2()
1777            + 2.0 * (self.forestry_score as f32 + 1.0).log2()
1778            + (self.mining_score as f32 + 1.0).log2()
1779            + (self.trading_score as f32 + 1.0).log2()
1780    }
1781}
1782
1783#[derive(Debug)]
1784pub struct Civ {
1785    capital: Id<Site>,
1786    homeland: Id<Place>,
1787}
1788
1789#[derive(Debug)]
1790pub struct Place {
1791    pub center: Vec2<i32>,
1792    /* act sort of like territory with sites belonging to it
1793     * nat_res/NaturalResources was moved to Economy
1794     *    nat_res: NaturalResources, */
1795}
1796
1797pub struct Track {
1798    /// Cost of using this track relative to other paths. This cost is an
1799    /// arbitrary unit and doesn't make sense unless compared to other track
1800    /// costs.
1801    pub cost: f32,
1802    path: Path<Vec2<i32>>,
1803}
1804
1805impl Track {
1806    pub fn path(&self) -> &Path<Vec2<i32>> { &self.path }
1807}
1808
1809#[derive(Debug)]
1810pub struct Site {
1811    pub kind: SiteKind,
1812    // TODO: Remove this field when overhauling
1813    pub site_tmp: Option<Id<crate::site::Site>>,
1814    pub center: Vec2<i32>,
1815    pub place: Id<Place>,
1816}
1817
1818impl fmt::Display for Site {
1819    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1820        writeln!(f, "{:?}", self.kind)?;
1821
1822        Ok(())
1823    }
1824}
1825
1826impl SiteKind {
1827    pub fn is_suitable_loc(&self, loc: Vec2<i32>, sim: &WorldSim) -> bool {
1828        let on_land = || -> bool {
1829            if let Some(chunk) = sim.get(loc) {
1830                !chunk.river.is_ocean()
1831                    && !chunk.river.is_lake()
1832                    && !chunk.river.is_river()
1833                    && !chunk.is_underwater()
1834                    && !matches!(
1835                        chunk.get_biome(),
1836                        common::terrain::BiomeKind::Lake | common::terrain::BiomeKind::Ocean
1837                    )
1838            } else {
1839                false
1840            }
1841        };
1842        let on_flat_terrain = || -> bool {
1843            sim.get_gradient_approx(loc)
1844                .map(|grad| grad < 1.0)
1845                .unwrap_or(false)
1846        };
1847
1848        sim.get(loc).is_some_and(|chunk| {
1849            let suitable_for_town = || -> bool {
1850                let attributes = town_attributes_of_site(loc, sim);
1851                attributes.is_some_and(|attributes| {
1852                    // aquifer and has_many_rocks was added to make mesa clifftowns suitable for towns
1853                    (attributes.potable_water || (attributes.aquifer && matches!(self, SiteKind::CliffTown)))
1854                        && attributes.building_materials
1855                        && attributes.heating
1856                        // Because of how the algorithm for site towns work, they have to start on land.
1857                        && on_land()
1858                })
1859            };
1860            match self {
1861                SiteKind::Gnarling => {
1862                    on_land()
1863                        && on_flat_terrain()
1864                        && (-0.3..0.4).contains(&chunk.temp)
1865                        && chunk.tree_density > 0.75
1866                },
1867                SiteKind::Adlet => chunk.temp < -0.2 && chunk.cliff_height > 25.0,
1868                SiteKind::DwarvenMine => {
1869                    matches!(chunk.get_biome(), BiomeKind::Forest | BiomeKind::Desert)
1870                        && !chunk.near_cliffs()
1871                        && !chunk.river.near_water()
1872                        && on_flat_terrain()
1873                },
1874                SiteKind::Haniwa => {
1875                    on_land()
1876                        && on_flat_terrain()
1877                        && (-0.3..0.4).contains(&chunk.temp)
1878                },
1879                SiteKind::GiantTree => {
1880                    on_land()
1881                        && on_flat_terrain()
1882                        && chunk.tree_density > 0.4
1883                        && (-0.3..0.4).contains(&chunk.temp)
1884                },
1885                SiteKind::Citadel => true,
1886                SiteKind::CliffTown => {
1887                    chunk.temp >= CONFIG.desert_temp
1888                        && chunk.cliff_height > 40.0
1889                        && chunk.rockiness > 1.2
1890                        && suitable_for_town()
1891                },
1892                SiteKind::GliderCourse => {
1893                    chunk.alt > 1400.0
1894                },
1895                SiteKind::SavannahTown => {
1896                    matches!(chunk.get_biome(), BiomeKind::Savannah)
1897                        && !chunk.near_cliffs()
1898                        && !chunk.river.near_water()
1899                        && suitable_for_town()
1900                },
1901                SiteKind::CoastalTown => {
1902                    (2.0..3.5).contains(&(chunk.water_alt - CONFIG.sea_level))
1903                        && suitable_for_town()
1904                },
1905                SiteKind::PirateHideout => {
1906                    (0.5..3.5).contains(&(chunk.water_alt - CONFIG.sea_level))
1907                },
1908                SiteKind::Sahagin => {
1909                    matches!(chunk.get_biome(), BiomeKind::Ocean)
1910                    && (40.0..45.0).contains(&(CONFIG.sea_level - chunk.alt))
1911                },
1912                SiteKind::JungleRuin => {
1913                    matches!(chunk.get_biome(), BiomeKind::Jungle)
1914                },
1915                SiteKind::RockCircle => !chunk.near_cliffs() && !chunk.river.near_water(),
1916                SiteKind::TrollCave => {
1917                    !chunk.near_cliffs()
1918                        && on_flat_terrain()
1919                        && !chunk.river.near_water()
1920                        && chunk.temp < 0.6
1921                },
1922                SiteKind::Camp => {
1923                    !chunk.near_cliffs() && on_flat_terrain() && !chunk.river.near_water()
1924                },
1925                SiteKind::DesertCity => {
1926                    (0.9..1.0).contains(&chunk.temp) && !chunk.near_cliffs() && suitable_for_town()
1927                        && on_land()
1928                        && !chunk.river.near_water()
1929                },
1930                SiteKind::ChapelSite => {
1931                    matches!(chunk.get_biome(), BiomeKind::Ocean)
1932                        && CONFIG.sea_level < chunk.alt + 1.0
1933                },
1934                SiteKind::Terracotta => {
1935                    (0.9..1.0).contains(&chunk.temp)
1936                        && on_land()
1937                        && (chunk.water_alt - CONFIG.sea_level) > 50.0
1938                        && on_flat_terrain()
1939                        && !chunk.river.near_water()
1940                        && !chunk.near_cliffs()
1941                },
1942                SiteKind::Myrmidon => {
1943                    (0.9..1.0).contains(&chunk.temp)
1944                        && on_land()
1945                        && (chunk.water_alt - CONFIG.sea_level) > 50.0
1946                        && on_flat_terrain()
1947                        && !chunk.river.near_water()
1948                        && !chunk.near_cliffs()
1949                },
1950                SiteKind::Cultist => on_land() && chunk.temp < 0.5 && chunk.near_cliffs(),
1951                SiteKind::VampireCastle => on_land() && chunk.temp <= -0.8 && chunk.near_cliffs(),
1952                SiteKind::Refactor => suitable_for_town(),
1953                SiteKind::Bridge(_, _) => true,
1954            }
1955        })
1956    }
1957
1958    pub fn exclusion_radius(&self) -> i32 {
1959        // FIXME: Provide specific values for each individual SiteKind
1960        match self {
1961            SiteKind::Myrmidon => 7,
1962            _ => 8, // This is just an arbitrary value
1963        }
1964    }
1965
1966    pub fn exclusion_radius_clear(&self, sim: &WorldSim, loc: Vec2<i32>) -> bool {
1967        let radius = self.exclusion_radius();
1968        for x in (-radius)..radius {
1969            for y in (-radius)..radius {
1970                let check_loc = loc + Vec2::new(x, y);
1971                if sim.get(check_loc).is_some_and(|c| !c.sites.is_empty()) {
1972                    return false;
1973                }
1974            }
1975        }
1976        true
1977    }
1978}
1979
1980impl Site {
1981    pub fn is_dungeon(&self) -> bool {
1982        matches!(
1983            self.kind,
1984            SiteKind::Adlet
1985                | SiteKind::Gnarling
1986                | SiteKind::ChapelSite
1987                | SiteKind::Terracotta
1988                | SiteKind::Haniwa
1989                | SiteKind::Myrmidon
1990                | SiteKind::DwarvenMine
1991                | SiteKind::Cultist
1992                | SiteKind::Sahagin
1993                | SiteKind::VampireCastle
1994        )
1995    }
1996
1997    pub fn is_settlement(&self) -> bool {
1998        matches!(
1999            self.kind,
2000            SiteKind::Refactor
2001                | SiteKind::CliffTown
2002                | SiteKind::DesertCity
2003                | SiteKind::SavannahTown
2004                | SiteKind::CoastalTown
2005        )
2006    }
2007
2008    pub fn is_bridge(&self) -> bool { matches!(self.kind, SiteKind::Bridge(_, _)) }
2009}
2010
2011#[derive(PartialEq, Eq, Debug, Clone)]
2012pub struct PointOfInterest {
2013    pub name: String,
2014    pub kind: PoiKind,
2015    pub loc: Vec2<i32>,
2016}
2017
2018#[derive(PartialEq, Eq, Debug, Clone)]
2019pub enum PoiKind {
2020    /// Peak stores the altitude
2021    Peak(u32),
2022    /// Lake stores a metric relating to size
2023    Biome(u32),
2024}
2025
2026#[cfg(test)]
2027mod tests {
2028    use super::*;
2029
2030    #[test]
2031    fn empty_proximity_requirements() {
2032        let world_dims = Aabr {
2033            min: Vec2 { x: 0, y: 0 },
2034            max: Vec2 {
2035                x: 200_i32,
2036                y: 200_i32,
2037            },
2038        };
2039        let reqs = ProximityRequirementsBuilder::new().finalize(&world_dims);
2040        assert!(reqs.satisfied_by(Vec2 { x: 0, y: 0 }));
2041    }
2042
2043    #[test]
2044    fn avoid_proximity_requirements() {
2045        let world_dims = Aabr {
2046            min: Vec2 {
2047                x: -200_i32,
2048                y: -200_i32,
2049            },
2050            max: Vec2 {
2051                x: 200_i32,
2052                y: 200_i32,
2053            },
2054        };
2055        let reqs = ProximityRequirementsBuilder::new()
2056            .avoid_all_of(vec![Vec2 { x: 0, y: 0 }].into_iter(), 10)
2057            .finalize(&world_dims);
2058        assert!(reqs.satisfied_by(Vec2 { x: 8, y: -8 }));
2059        assert!(!reqs.satisfied_by(Vec2 { x: -1, y: 1 }));
2060    }
2061
2062    #[test]
2063    fn near_proximity_requirements() {
2064        let world_dims = Aabr {
2065            min: Vec2 {
2066                x: -200_i32,
2067                y: -200_i32,
2068            },
2069            max: Vec2 {
2070                x: 200_i32,
2071                y: 200_i32,
2072            },
2073        };
2074        let reqs = ProximityRequirementsBuilder::new()
2075            .close_to_one_of(vec![Vec2 { x: 0, y: 0 }].into_iter(), 10)
2076            .finalize(&world_dims);
2077        assert!(reqs.satisfied_by(Vec2 { x: 1, y: -1 }));
2078        assert!(!reqs.satisfied_by(Vec2 { x: -8, y: 8 }));
2079    }
2080
2081    #[test]
2082    fn complex_proximity_requirements() {
2083        let a_site = Vec2 { x: 572, y: 724 };
2084        let world_dims = Aabr {
2085            min: Vec2 { x: 0, y: 0 },
2086            max: Vec2 {
2087                x: 1000_i32,
2088                y: 1000_i32,
2089            },
2090        };
2091        let reqs = ProximityRequirementsBuilder::new()
2092            .close_to_one_of(vec![a_site].into_iter(), 60)
2093            .avoid_all_of(vec![a_site].into_iter(), 40)
2094            .finalize(&world_dims);
2095        assert!(reqs.satisfied_by(Vec2 { x: 572, y: 774 }));
2096        assert!(!reqs.satisfied_by(a_site));
2097    }
2098
2099    #[test]
2100    fn location_hint() {
2101        let reqs = ProximityRequirementsBuilder::new().close_to_one_of(
2102            vec![Vec2 { x: 1, y: 0 }, Vec2 { x: 13, y: 12 }].into_iter(),
2103            10,
2104        );
2105        let expected = Aabr {
2106            min: Vec2 { x: 0, y: 0 },
2107            max: Vec2 { x: 23, y: 22 },
2108        };
2109        let map_dims = Aabr {
2110            min: Vec2 { x: 0, y: 0 },
2111            max: Vec2 { x: 200, y: 300 },
2112        };
2113        assert_eq!(expected, reqs.location_hint(&map_dims));
2114    }
2115}