path: root/src/space/galaxy.rs

//! The galaxy: about ninety star systems, the lanes between them, and the
//! four peoples' territories.
//!
//! You can't fly between systems; you jump, and only along a lane. Lanes
//! join near neighbours: every pair in the relative neighbourhood graph
//! (no third star closer to both than they are to each other), which keeps
//! the map connected and its lanes from crossing, plus some of the extra
//! pairs of the Gabriel graph, for a few loops. To reach a far system you
//! jump through the ones between.
//!
//! Stars are scattered across a lopsided disc, denser in some places than
//! others, with a few empty voids that the lanes have to bridge.
//!
//! Each people has a seat: the system the universe started you in is one,
//! for whoever holds it, and the other three are spread out from it.
//! Territory grows from each seat along the lanes, each people at its own
//! pace, so territories come out in ragged blobs of different sizes. Every
//! system ends up held by someone.
//!
//! What a system is like (its kind) depends on where it lies: settled
//! systems around the seats, frontier and desolate ones further out, and
//! old battlefields along the borders, where the neighbours settle too.
//!
//! A galaxy only knows what it takes to draw the map. Each system is
//! generated whole when you need it, from its `Site`.

use std::cmp::Reverse;
use std::collections::{BTreeSet, BinaryHeap};
use std::f64::consts::TAU;

use rand::RngExt;
use rand::seq::{IndexedRandom, SliceRandom};

use super::Vec2;
use super::system::{self, Profile, StarKind, System, SystemKind};
use crate::names::Culture;
use crate::seed::{self, Rng};

/// How many systems a galaxy has, if they all fit.
pub const SYSTEMS: usize = 90;
/// Half the galaxy's width and height, in light-years.
pub const HALF_WIDTH: f64 = 100.0;
pub const HALF_HEIGHT: f64 = 62.0;
/// No two stars are closer than this, in light-years.
const SPACING: f64 = 9.0;
/// Lanes per system, at most, counting only the extra loops.
const MAX_LANES: usize = 4;

/// A star system as the map knows it, before it's generated.
pub struct Site {
    pub name: String,
    /// In light-years from the middle of the galaxy, y up.
    pub pos: Vec2,
    /// Who holds it.
    pub culture: Culture,
    pub kind: SystemKind,
    pub star: &'static StarKind,
    /// The systems a lane joins it to.
    pub lanes: Vec<usize>,
    /// For a system on a border: the people across it.
    pub neighbour: Option<Culture>,
    seed: u64,
}

pub struct Galaxy {
    pub sites: Vec<Site>,
    /// The system the universe started everyone in, before there was a
    /// galaxy. Saves from then are there.
    pub home: usize,
    /// Each people's seat, in `Culture::ALL` order.
    seats: [usize; 4],
}

impl Galaxy {
    /// Generates a system in full.
    pub fn system(&self, site: usize) -> System {
        let s = &self.sites[site];
        if site == self.home {
            return system::generate(s.seed);
        }
        let profile = Profile {
            name: s.name.clone(),
            culture: s.culture,
            star: s.star,
            kind: s.kind,
            neighbour: s.neighbour,
        };
        system::generate_as(s.seed, &profile)
    }

    /// The seat of a people.
    pub fn seat(&self, culture: Culture) -> usize {
        self.seats[culture as usize]
    }

    pub fn is_seat(&self, site: usize) -> bool {
        self.seats.contains(&site)
    }

    /// Light-years between two systems.
    pub fn distance(&self, a: usize, b: usize) -> f64 {
        self.sites[a].pos.distance(self.sites[b].pos)
    }

    /// Days a jump takes from one system to another, along a lane.
    pub fn jump_days(&self, a: usize, b: usize) -> f64 {
        1.0 + self.distance(a, b) / 5.0
    }

    /// Days to jump along a route from `from`.
    pub fn route_days(&self, from: usize, route: &[usize]) -> f64 {
        let mut at = from;
        let mut days = 0.0;
        for &next in route {
            days += self.jump_days(at, next);
            at = next;
        }
        days
    }

    /// The systems you know the way to: those you've been to, and those a
    /// lane joins to them.
    pub fn charted(&self, visited: &BTreeSet<usize>) -> Vec<bool> {
        let mut charted = vec![false; self.sites.len()];
        for &v in visited.iter().filter(|&&v| v < self.sites.len()) {
            charted[v] = true;
            for &n in &self.sites[v].lanes {
                charted[n] = true;
            }
        }
        charted
    }

    /// The fewest jumps from `from` to `to`, going only through systems
    /// that are `passable`, and the shortest such way. Doesn't include
    /// `from`, ends with `to`, and is empty if they're the same.
    pub fn route(
        &self,
        from: usize,
        to: usize,
        passable: impl Fn(usize) -> bool,
    ) -> Option<Vec<usize>> {
        self.search(from, passable, |s| s == to)
    }

    /// The fewest jumps to the nearest system that is `wanted`, through any
    /// system at all.
    pub fn nearest(&self, from: usize, wanted: impl Fn(usize) -> bool) -> Option<Vec<usize>> {
        self.search(from, |_| true, wanted)
    }

    fn search(
        &self,
        from: usize,
        passable: impl Fn(usize) -> bool,
        goal: impl Fn(usize) -> bool,
    ) -> Option<Vec<usize>> {
        let n = self.sites.len();
        // Jumps first, then distance, in hundredths of a light-year.
        let cost = |jumps: u64, ly: f64| jumps * 1_000_000_000 + (ly * 100.0) as u64;
        let mut best = vec![u64::MAX; n];
        let mut came_from = vec![usize::MAX; n];
        let mut queue = BinaryHeap::new();
        best[from] = 0;
        queue.push(Reverse((0, 0u64, 0.0f64.to_bits(), from)));
        while let Some(Reverse((c, jumps, ly, at))) = queue.pop() {
            if c > best[at] {
                continue;
            }
            if goal(at) {
                let mut route = vec![];
                let mut step = at;
                while step != from {
                    route.push(step);
                    step = came_from[step];
                }
                route.reverse();
                return Some(route);
            }
            for &next in &self.sites[at].lanes {
                if !passable(next) {
                    continue;
                }
                let ly = f64::from_bits(ly) + self.distance(at, next);
                let c = cost(jumps + 1, ly);
                if c < best[next] {
                    best[next] = c;
                    came_from[next] = at;
                    queue.push(Reverse((c, jumps + 1, ly.to_bits(), next)));
                }
            }
        }
        None
    }

    /// The corners of a box round every star, in light-years.
    pub fn bounds(&self) -> (Vec2, Vec2) {
        let mut low = Vec2::new(f64::MAX, f64::MAX);
        let mut high = Vec2::new(f64::MIN, f64::MIN);
        for s in &self.sites {
            low = Vec2::new(low.x.min(s.pos.x), low.y.min(s.pos.y));
            high = Vec2::new(high.x.max(s.pos.x), high.y.max(s.pos.y));
        }
        (low, high)
    }
}

pub fn generate(universe: u64) -> Galaxy {
    let home_seed = seed::derive(universe, "system", 0);
    let home_system = system::generate(home_seed);
    let mut rng = seed::rng(seed::derive(universe, "galaxy", 0));

    let points = scatter(&mut rng);
    let n = points.len();
    let lanes = join(&points, &mut rng);

    // The seats, as far apart as can be without crowding the rim.
    let seat_sites = place_seats(&points, &mut rng);
    let mut cultures = Culture::ALL;
    cultures.shuffle(&mut rng);
    // Whoever holds the original system has their seat there.
    let mut seats = [0; 4];
    for (&site, &culture) in seat_sites.iter().zip(&cultures) {
        seats[culture as usize] = site;
    }
    let home = seats[home_system.culture as usize];

    let owner = grow(&lanes, &points, &seats, universe, &mut rng);

    // What each system is, given where it lies.
    let hops_from_seat = |i: usize| {
        let seat = seats[owner[i] as usize];
        if i == seat {
            0
        } else if lanes[i].contains(&seat) {
            1
        } else {
            2
        }
    };
    let mut names: BTreeSet<String> = BTreeSet::new();
    names.insert(home_system.name.clone());
    let mut sites = Vec::with_capacity(n);
    for i in 0..n {
        let culture = owner[i];
        let mut across: Vec<Culture> =
            lanes[i].iter().map(|&j| owner[j]).filter(|&c| c != culture).collect();
        across.sort_by_key(|&c| c as usize);
        // The people most of its foreign lanes lead to.
        let neighbour = Culture::ALL
            .into_iter()
            .filter(|c| across.contains(c))
            .max_by_key(|&c| across.iter().filter(|&&x| x == c).count());
        let kind = if seats.contains(&i) {
            SystemKind::Seat
        } else {
            pick_kind(hops_from_seat(i), neighbour.is_some(), lanes[i].len() == 1, &mut rng)
        };
        let (name, star, seed) = if i == home {
            (home_system.name.clone(), home_system.star, home_seed)
        } else {
            let name = loop {
                let name = culture.word(&mut rng);
                if names.insert(name.clone()) {
                    break name;
                }
            };
            let star = system::random_star(kind, &mut rng);
            (name, star, seed::derive(universe, "system", i as u64 + 1))
        };
        sites.push(Site {
            name,
            pos: points[i],
            culture,
            kind,
            star,
            lanes: lanes[i].clone(),
            neighbour,
            seed,
        });
    }
    Galaxy { sites, home, seats }
}

/// Where the stars are: scattered over a lopsided disc, clumped here and
/// thin there, with a few empty voids.
fn scatter(rng: &mut Rng) -> Vec<Vec2> {
    let lobes = [
        (rng.random_range(0.06..0.14), rng.random_range(0.0..TAU)),
        (rng.random_range(0.03..0.08), rng.random_range(0.0..TAU)),
    ];
    let inside = |p: Vec2| {
        let (x, y) = (p.x / HALF_WIDTH, p.y / HALF_HEIGHT);
        let angle = y.atan2(x);
        let edge = 1.0
            + lobes[0].0 * (2.0 * angle + lobes[0].1).sin()
            + lobes[1].0 * (3.0 * angle + lobes[1].1).sin();
        x.hypot(y) < edge
    };
    let voids: Vec<(Vec2, f64)> = (0..rng.random_range(2..=3))
        .map(|_| {
            let angle = rng.random_range(0.0..TAU);
            let r = rng.random_range(0.2..0.7);
            let at = Vec2::new(angle.cos() * r * HALF_WIDTH, angle.sin() * r * HALF_HEIGHT);
            (at, rng.random_range(9.0..15.0))
        })
        .collect();
    let phase = (rng.random_range(0.0..TAU), rng.random_range(0.0..TAU));
    let clumping = |p: Vec2| {
        let wave = (p.x / 23.0 + phase.0).sin() * (p.y / 17.0 + phase.1).sin();
        0.45 + 0.55 * (0.5 + 0.5 * wave)
    };
    let mut points: Vec<Vec2> = Vec::new();
    for _ in 0..200_000 {
        if points.len() == SYSTEMS {
            break;
        }
        let p = Vec2::new(
            rng.random_range(-1.2 * HALF_WIDTH..1.2 * HALF_WIDTH),
            rng.random_range(-1.2 * HALF_HEIGHT..1.2 * HALF_HEIGHT),
        );
        if !inside(p)
            || !rng.random_bool(clumping(p))
            || voids.iter().any(|&(c, r)| p.distance(c) < r)
            || points.iter().any(|q| q.distance(p) < SPACING)
        {
            continue;
        }
        points.push(p);
    }
    points
}

/// The lanes: every pair in the relative neighbourhood graph, and some of
/// the Gabriel graph's extra pairs, shortest first. Each system's list is
/// sorted, so it's the same every time.
fn join(points: &[Vec2], rng: &mut Rng) -> Vec<Vec<usize>> {
    let n = points.len();
    let d = |i: usize, j: usize| points[i].distance(points[j]);
    let mut lanes = vec![Vec::new(); n];
    let mut extras = Vec::new();
    for i in 0..n {
        for j in i + 1..n {
            let dij = d(i, j);
            let others = (0..n).filter(|&k| k != i && k != j);
            if !others.clone().any(|k| d(i, k).max(d(j, k)) < dij) {
                lanes[i].push(j);
                lanes[j].push(i);
            } else if !others.into_iter().any(|k| d(i, k).powi(2) + d(j, k).powi(2) < dij * dij) {
                extras.push((dij, i, j));
            }
        }
    }
    extras.sort_by(|a, b| a.0.total_cmp(&b.0));
    for (_, i, j) in extras {
        if lanes[i].len() < MAX_LANES && lanes[j].len() < MAX_LANES && rng.random_bool(0.45) {
            lanes[i].push(j);
            lanes[j].push(i);
        }
    }
    for l in &mut lanes {
        l.sort_unstable();
    }
    lanes
}

/// Four seats spread as far apart as they'll go, none of them out on the
/// very rim.
fn place_seats(points: &[Vec2], rng: &mut Rng) -> [usize; 4] {
    let rim = |p: Vec2| (p.x / HALF_WIDTH).hypot(p.y / HALF_HEIGHT);
    let mut pool: Vec<usize> = (0..points.len()).filter(|&i| rim(points[i]) < 0.7).collect();
    if pool.len() < 4 {
        pool = (0..points.len()).collect();
    }
    let mut best = [0, 1, 2, 3];
    let mut best_gap = f64::MIN;
    for _ in 0..400 {
        pool.shuffle(rng);
        let pick = [pool[0], pool[1], pool[2], pool[3]];
        let mut gap = f64::MAX;
        for a in 0..4 {
            for b in a + 1..4 {
                gap = gap.min(points[pick[a]].distance(points[pick[b]]));
            }
        }
        if gap > best_gap {
            best_gap = gap;
            best = pick;
        }
    }
    best
}

/// Who holds each system: each people spreads out from its seat along the
/// lanes, at a pace of its own, and claims whatever it reaches first.
fn grow(
    lanes: &[Vec<usize>],
    points: &[Vec2],
    seats: &[usize; 4],
    universe: u64,
    rng: &mut Rng,
) -> Vec<Culture> {
    let pace: Vec<f64> = (0..4).map(|_| rng.random_range(0.75..1.3)).collect();
    let mut owner: Vec<Option<Culture>> = vec![None; points.len()];
    let mut queue = BinaryHeap::new();
    for c in Culture::ALL {
        queue.push(Reverse((0u64, seats[c as usize], c as usize)));
    }
    while let Some(Reverse((cost, at, c))) = queue.pop() {
        if owner[at].is_some() {
            continue;
        }
        owner[at] = Some(Culture::ALL[c]);
        for &next in &lanes[at] {
            if owner[next].is_some() {
                continue;
            }
            // Some lanes are harder going for some peoples than others.
            let rough = seed::derive(universe, "border", (at * points.len() + next) as u64 * 4);
            let rough = 0.65 + 0.8 * ((rough >> 11) as f64 / (1u64 << 53) as f64);
            let step = points[at].distance(points[next]) * pace[c] * rough;
            queue.push(Reverse((cost + (step * 1000.0) as u64, next, c)));
        }
    }
    // The lanes join everything, so everything is reached; but just in case.
    owner.into_iter().map(|o| o.unwrap_or(Culture::Drift)).collect()
}

/// A kind for a system `hops` from its own seat (two meaning two or more),
/// maybe on a border, maybe at the end of a lane to nowhere else.
fn pick_kind(hops: u32, border: bool, dead_end: bool, rng: &mut Rng) -> SystemKind {
    use SystemKind::*;
    let mut weights: Vec<(SystemKind, u32)> = if hops <= 1 {
        vec![(Settled, 70), (Frontier, 8), (Rubble, 16), (Desolate, 4), (Graveyard, 2)]
    } else if border {
        vec![(Settled, 22), (Frontier, 22), (Rubble, 12), (Desolate, 20), (Graveyard, 24)]
    } else {
        vec![(Settled, 40), (Frontier, 26), (Rubble, 16), (Desolate, 14), (Graveyard, 4)]
    };
    if dead_end {
        for (kind, w) in &mut weights {
            if matches!(kind, Frontier | Desolate) {
                *w *= 2;
            }
        }
    }
    weights.choose_weighted(rng, |&(_, w)| w).unwrap().0
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::space::system::PlaceKind;

    #[test]
    fn galaxies_are_whole() {
        for universe in 0..12 {
            let g = generate(universe);
            let n = g.sites.len();
            assert!(n >= SYSTEMS - 5, "universe {universe}: only {n} systems");
            // Every system can be reached from every other.
            for to in 0..n {
                assert!(g.route(g.home, to, |_| true).is_some(), "universe {universe}: {to}");
            }
            // Lanes go both ways, and no star sits on top of another.
            for (i, s) in g.sites.iter().enumerate() {
                assert!(!s.lanes.is_empty());
                for &j in &s.lanes {
                    assert!(g.sites[j].lanes.contains(&i));
                }
                for j in i + 1..n {
                    assert!(g.distance(i, j) >= SPACING);
                }
            }
            let names: BTreeSet<&str> = g.sites.iter().map(|s| s.name.as_str()).collect();
            assert_eq!(names.len(), n, "universe {universe}: names repeat");
        }
    }

    #[test]
    fn each_people_holds_one_patch_round_its_seat() {
        for universe in 0..12 {
            let g = generate(universe);
            for c in Culture::ALL {
                let seat = g.seat(c);
                assert_eq!(g.sites[seat].culture, c);
                assert_eq!(g.sites[seat].kind, SystemKind::Seat);
                // Every system they hold is reachable without leaving
                // their space.
                for (i, s) in g.sites.iter().enumerate().filter(|(_, s)| s.culture == c) {
                    let inside = g.route(seat, i, |j| g.sites[j].culture == c);
                    assert!(inside.is_some(), "universe {universe}: {} cut off", s.name);
                }
                let held = g.sites.iter().filter(|s| s.culture == c).count();
                assert!(held >= 6, "universe {universe}: {} hold only {held}", c.name());
            }
        }
    }

    #[test]
    fn the_original_system_is_its_peoples_seat() {
        for universe in [0, 7, 1312] {
            let g = generate(universe);
            let old = crate::space::home_system(universe);
            let s = g.system(g.home);
            assert_eq!(s.name, old.name);
            assert_eq!(s.places.len(), old.places.len());
            assert_eq!(g.seat(old.culture), g.home);
            assert_eq!(g.sites[g.home].name, old.name);
        }
    }

    #[test]
    fn systems_are_what_the_map_says() {
        let g = generate(3);
        for (i, site) in g.sites.iter().enumerate() {
            let s = g.system(i);
            assert_eq!(
                (s.name.as_str(), s.culture, s.kind),
                (site.name.as_str(), site.culture, site.kind)
            );
            assert_eq!(s.star.name, site.star.name);
            assert_eq!(s.sells_fuel(), site.kind.sells_fuel(), "{}: {:?}", s.name, s.kind);
            assert!(matches!(
                s.places[s.edge_place()].kind,
                PlaceKind::Planet(_) | PlaceKind::Belt
            ));
        }
    }

    #[test]
    fn there_is_variety() {
        let mut seen = BTreeSet::new();
        for universe in 0..4 {
            for s in generate(universe).sites {
                seen.insert(format!("{:?}", s.kind));
            }
        }
        assert_eq!(seen.len(), SystemKind::ALL.len(), "{seen:?}");
    }

    #[test]
    fn routes_take_the_fewest_jumps_through_what_you_allow() {
        let g = generate(5);
        let far = (0..g.sites.len())
            .max_by(|&a, &b| g.distance(g.home, a).total_cmp(&g.distance(g.home, b)));
        let far = far.unwrap();
        let route = g.route(g.home, far, |_| true).unwrap();
        assert!(route.len() >= 3, "the far side is several jumps away");
        assert_eq!(*route.last().unwrap(), far);
        for pair in
            std::iter::once(g.home).chain(route.iter().copied()).collect::<Vec<_>>().windows(2)
        {
            assert!(g.sites[pair[0]].lanes.contains(&pair[1]), "jumps follow lanes");
        }
        assert_eq!(g.route(g.home, g.home, |_| true), Some(vec![]));
        assert_eq!(g.route(g.home, far, |s| s == g.home), None, "blocked");
        let mut visited = BTreeSet::new();
        visited.insert(g.home);
        let charted = g.charted(&visited);
        assert_eq!(charted.iter().filter(|&&c| c).count(), 1 + g.sites[g.home].lanes.len());
    }

    #[test]
    fn same_universe_same_galaxy() {
        let a = generate(42);
        let b = generate(42);
        let key = |g: &Galaxy| {
            g.sites.iter().map(|s| (s.name.clone(), s.lanes.clone(), s.kind)).collect::<Vec<_>>()
        };
        assert_eq!(key(&a), key(&b));
    }
}