Orrery: game loop, name generator and derelict dungeons

An ASCII sci-fi-fantasy game for the terminal, built on ratatui.

- Game loop with a fixed 30 Hz tick and a stack of scenes; the kitty
  keyboard protocol is turned on where the terminal supports it, so later
  real-time scenes can tell when a key is held.
- Stable hierarchical seeds: the whole universe derives from one u64,
  with tests pinning the exact outputs so old seeds keep working.
- Name generator with four cultures, each with its own syllables and
  templates, plus unidentified/true names for artifacts.
- Title screen with an animated orrery, and a name forge for browsing
  generated names.
- Derelict ships to board: ship-shaped maps with an engine room, spine
  corridor, side rooms and bridge; symmetric shadowcasting sight;
  monsters that wake on sight and hunt; loot carried out through the
  airlock goes into the hold.
- `orrery names` and `orrery ship` print the generators' output without
  the TUI, for tuning.

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

1 files changed, 207 insertions, 0 deletions

diff --git a/src/dungeon/fov.rs b/src/dungeon/fov.rs
new file mode 100644
index 0000000..81f8c07
--- /dev/null
+++ b/src/dungeon/fov.rs
@@ -0,0 +1,207 @@
+//! Field of view by symmetric shadowcasting, after Albert Ford's write-up at
+//! <https://www.albertford.com/shadowcasting/>.
+//!
+//! Symmetric means that if you can see a floor cell, someone standing there
+//! can see you. Monsters wake when they come into view, so this keeps
+//! ambushes fair: nothing notices you that you couldn't have seen first.
+
+use super::{Map, Pos};
+
+/// The cells visible from one spot.
+pub struct Fov {
+    width: i32,
+    visible: Vec<bool>,
+}
+
+impl Fov {
+    pub fn contains(&self, p: Pos) -> bool {
+        p.x >= 0
+            && p.y >= 0
+            && p.x < self.width
+            && self.visible.get((p.y * self.width + p.x) as usize).copied().unwrap_or(false)
+    }
+}
+
+/// Everything visible from `origin` within `radius` cells. Walls are visible
+/// (that's how you see a room's shape); cells behind them aren't.
+pub fn compute(map: &Map, origin: Pos, radius: i32) -> Fov {
+    let mut fov = Fov { width: map.width, visible: vec![false; (map.width * map.height) as usize] };
+    let mut reveal = |p: Pos| {
+        if map.contains(p) {
+            fov.visible[map.index(p)] = true;
+        }
+    };
+    reveal(origin);
+    for quadrant in Quadrant::ALL {
+        let mut rows = vec![Row { depth: 1, start: Slope::new(-1, 1), end: Slope::new(1, 1) }];
+        while let Some(mut row) = rows.pop() {
+            if row.depth > radius {
+                continue;
+            }
+            let mut prev_blocked = None;
+            for col in row.min_col()..=row.max_col() {
+                let p = quadrant.cell(origin, row.depth, col);
+                let blocked = map.tile(p).blocks_sight();
+                let in_radius = col * col + row.depth * row.depth <= radius * radius + radius;
+                if in_radius && (blocked || row.is_symmetric(col)) {
+                    reveal(p);
+                }
+                if prev_blocked == Some(true) && !blocked {
+                    row.start = Slope::left_edge(row.depth, col);
+                }
+                if prev_blocked == Some(false) && blocked {
+                    let mut next = row.next();
+                    next.end = Slope::left_edge(row.depth, col);
+                    rows.push(next);
+                }
+                prev_blocked = Some(blocked);
+            }
+            if prev_blocked == Some(false) {
+                rows.push(row.next());
+            }
+        }
+    }
+    fov
+}
+
+#[derive(Clone, Copy)]
+enum Quadrant {
+    North,
+    East,
+    South,
+    West,
+}
+
+impl Quadrant {
+    const ALL: [Quadrant; 4] = [Quadrant::North, Quadrant::East, Quadrant::South, Quadrant::West];
+
+    /// The cell `depth` rows out from `origin` and `col` columns across.
+    fn cell(self, origin: Pos, depth: i32, col: i32) -> Pos {
+        match self {
+            Quadrant::North => origin.offset(col, -depth),
+            Quadrant::South => origin.offset(col, depth),
+            Quadrant::East => origin.offset(depth, col),
+            Quadrant::West => origin.offset(-depth, col),
+        }
+    }
+}
+
+/// An exact fraction, so shadows land on the same cells every time.
+#[derive(Clone, Copy)]
+struct Slope {
+    num: i32,
+    /// Always positive.
+    den: i32,
+}
+
+impl Slope {
+    const fn new(num: i32, den: i32) -> Slope {
+        Slope { num, den }
+    }
+
+    /// The slope through the left edge of the cell at (`depth`, `col`).
+    const fn left_edge(depth: i32, col: i32) -> Slope {
+        Slope::new(2 * col - 1, 2 * depth)
+    }
+}
+
+#[derive(Clone, Copy)]
+struct Row {
+    depth: i32,
+    start: Slope,
+    end: Slope,
+}
+
+impl Row {
+    /// `depth * start`, rounded with ties going up.
+    fn min_col(&self) -> i32 {
+        (2 * self.depth * self.start.num + self.start.den).div_euclid(2 * self.start.den)
+    }
+
+    /// `depth * end`, rounded with ties going down.
+    fn max_col(&self) -> i32 {
+        -(self.end.den - 2 * self.depth * self.end.num).div_euclid(2 * self.end.den)
+    }
+
+    /// Whether the centre of the cell at `col` is inside this row's slopes.
+    fn is_symmetric(&self, col: i32) -> bool {
+        col * self.start.den >= self.depth * self.start.num
+            && col * self.end.den <= self.depth * self.end.num
+    }
+
+    fn next(&self) -> Row {
+        Row { depth: self.depth + 1, ..*self }
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use rand::RngExt;
+
+    use super::*;
+    use crate::dungeon::Tile;
+    use crate::seed;
+
+    fn map_from(rows: &[&str]) -> (Map, Pos) {
+        let mut map = Map::new(rows[0].len() as i32, rows.len() as i32, Tile::Floor);
+        let mut at = Pos::new(0, 0);
+        for (y, row) in rows.iter().enumerate() {
+            for (x, c) in row.chars().enumerate() {
+                let p = Pos::new(x as i32, y as i32);
+                match c {
+                    '#' => map.set(p, Tile::Wall),
+                    '@' => at = p,
+                    _ => {}
+                }
+            }
+        }
+        (map, at)
+    }
+
+    #[test]
+    fn walls_cast_shadows() {
+        let (map, at) = map_from(&[
+            "#########", //
+            "#.......#", "#...@...#", "#..###..#", "#.......#", "#########",
+        ]);
+        let fov = compute(&map, at, 10);
+        assert!(fov.contains(Pos::new(1, 1)), "open floor is visible");
+        assert!(fov.contains(Pos::new(4, 3)), "the wall itself is visible");
+        assert!(!fov.contains(Pos::new(4, 4)), "the cell right behind the wall is hidden");
+        assert!(fov.contains(Pos::new(1, 3)), "cells beside the wall stay visible");
+    }
+
+    #[test]
+    fn radius_limits_sight() {
+        let (map, _) = map_from(&[&".".repeat(30)]);
+        let fov = compute(&map, Pos::new(0, 0), 5);
+        assert!(fov.contains(Pos::new(5, 0)));
+        assert!(!fov.contains(Pos::new(6, 0)));
+    }
+
+    /// The property the module promises: seeing is mutual between floor cells.
+    #[test]
+    fn sight_is_symmetric() {
+        let mut rng = seed::rng(4);
+        for _ in 0..20 {
+            let mut map = Map::new(24, 16, Tile::Floor);
+            for p in map.positions().collect::<Vec<_>>() {
+                if rng.random_bool(0.25) {
+                    map.set(p, Tile::Wall);
+                }
+            }
+            let floors: Vec<Pos> =
+                map.positions().filter(|&p| map.tile(p) == Tile::Floor).collect();
+            let views: Vec<Fov> = floors.iter().map(|&p| compute(&map, p, 8)).collect();
+            for (i, &a) in floors.iter().enumerate() {
+                for (j, &b) in floors.iter().enumerate() {
+                    assert_eq!(
+                        views[i].contains(b),
+                        views[j].contains(a),
+                        "{a:?} and {b:?} disagree about seeing each other"
+                    );
+                }
+            }
+        }
+    }
+}