Orrery 0.1.0: the galaxy, flight, cities, inventory and saves

Grows the derelict crawler into the whole game, and gets it ready to
publish.

- A galaxy of star systems joined by lanes, split between four peoples'
  territories, with a star map and a system map. Systems are modelled
  with Kepler orbits, moons inside their Hill spheres, belts past the
  frost line and stations at Lagrange points.
- Flight around one place at a time: arcade flight with a throttle
  fallback where held keys can't be detected, mining rocks for ore,
  landing, docking at stations, and boarding wrecks that come and go by
  the calendar.
- Your ship to walk about, and capital cities to land at: generated
  plans with walls, quarters and streets, building interiors, shops,
  taverns, scholars and armourers.
- Fighting with a weapon and a gun ready, six damage types and how each
  monster takes them, and armour that guards, wears and can be mended.
- Everything you own has a weight: a vim-keyed inventory, a pack and the
  ship's lockers, and trade in ore, salvage, arms and fuel.
- Characters with a people and a ship of their own, saved as versioned
  JSON on every scene change and on quit, with a character sheet, a
  saves list and a pause menu wherever you are.
- `orrery weapons`, `armour`, `galaxy`, `system` and `town` print the
  generators' output without the TUI.
- Release: README install steps for macOS and Linux, a Makefile whose
  install also works with macOS's install, an MIT licence, and Cargo
  metadata with rust-version 1.88.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>

1 files changed, 573 insertions, 0 deletions

diff --git a/src/space/galaxy.rs b/src/space/galaxy.rs
new file mode 100644
index 0000000..bb06667
--- /dev/null
+++ b/src/space/galaxy.rs
@@ -0,0 +1,573 @@
+//! 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));
+    }
+}