From d36c54d996f3c14ae811312dbbe621e12a39edde Mon Sep 17 00:00:00 2001 From: skylar Date: Tue, 10 Nov 2026 06:50:08 -0800 Subject: 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 --- src/dungeon/crawl.rs | 416 +++++++++++++++++++++++++++++++++++++++++++++++ src/dungeon/fov.rs | 207 +++++++++++++++++++++++ src/dungeon/mod.rs | 156 ++++++++++++++++++ src/dungeon/ship.rs | 452 +++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 1231 insertions(+) create mode 100644 src/dungeon/crawl.rs create mode 100644 src/dungeon/fov.rs create mode 100644 src/dungeon/mod.rs create mode 100644 src/dungeon/ship.rs (limited to 'src/dungeon') diff --git a/src/dungeon/crawl.rs b/src/dungeon/crawl.rs new file mode 100644 index 0000000..c5196b9 --- /dev/null +++ b/src/dungeon/crawl.rs @@ -0,0 +1,416 @@ +//! The rules of a crawl: moving, fighting, picking things up, and what the +//! derelict's inhabitants do each turn. Nothing here draws; the scene turns +//! keys into `Action`s and draws whatever state results. + +use rand::RngExt; + +use super::fov::{self, Fov}; +use super::ship; +use super::{Map, Pos, Tile}; +use crate::names::Artifact; +use crate::seed::{self, Rng}; + +/// How far your lamp reaches, in cells. +pub const SIGHT_RADIUS: i32 = 8; +const PLAYER_HP: i32 = 20; +/// Your cutting torch. +const PLAYER_DAMAGE: (i32, i32) = (2, 5); +const PLAYER_HIT: f64 = 0.8; +const MONSTER_HIT: f64 = 0.7; +const MEDPATCH_HEAL: i32 = 8; +const LOG_LENGTH: usize = 50; + +pub struct MonsterKind { + pub name: &'static str, + pub glyph: char, + pub rgb: (u8, u8, u8), + pub hp: i32, + pub damage: (i32, i32), + /// As in "the rust-mite bites you". + pub verb: &'static str, + /// How common it is, relative to the others. + pub weight: u32, + /// At most one aboard any ship. + pub unique: bool, +} + +#[rustfmt::skip] +pub const MONSTERS: &[MonsterKind] = &[ + MonsterKind { name: "rust-mite", glyph: 'm', rgb: (196, 112, 60), hp: 3, damage: (1, 2), verb: "bites", weight: 5, unique: false }, + MonsterKind { name: "maintenance drone", glyph: 'd', rgb: (150, 175, 200), hp: 6, damage: (1, 3), verb: "zaps", weight: 3, unique: false }, + MonsterKind { name: "hollow crewman", glyph: 'h', rgb: (160, 200, 150), hp: 9, damage: (2, 4), verb: "claws at", weight: 2, unique: false }, + MonsterKind { name: "choir-wraith", glyph: 'W', rgb: (200, 150, 255), hp: 14, damage: (3, 6), verb: "sings into", weight: 1, unique: true }, +]; + +pub struct Monster { + pub kind: &'static MonsterKind, + pub pos: Pos, + pub hp: i32, + /// Dormant until it comes into view; then it hunts you. + pub awake: bool, +} + +pub enum Item { + Artifact(Artifact), + Salvage { name: &'static str, value: u32 }, + Medpatch, +} + +pub struct Loot { + pub pos: Pos, + pub item: Item, +} + +#[derive(Clone, Copy, Debug, PartialEq, Eq)] +pub enum Outcome { + /// Back through the airlock, with everything carried. + Escaped, + Died { + killer: &'static str, + }, +} + +#[derive(Clone, Copy, Debug)] +pub enum Action { + Move(i32, i32), + Wait, + UseMedpatch, +} + +pub struct Crawl { + /// "the Vexant". + pub name: String, + /// "Cant hauler". + pub description: String, + pub map: Map, + pub player: Pos, + pub hp: i32, + pub max_hp: i32, + pub monsters: Vec, + pub loot: Vec, + /// What you're carrying. It's only yours once you're back through the airlock. + pub artifacts: Vec, + pub scrip: u32, + pub medpatches: u32, + pub fov: Fov, + /// Cells you've seen at some point, drawn from memory when out of sight. + seen: Vec, + /// Messages, oldest first. + pub log: Vec, + pub turns: u32, + pub outcome: Option, + /// Dice for fights. Separate from the ship's seed, so the same ship and + /// the same moves always play out the same way. + rng: Rng, +} + +impl Crawl { + pub fn new(seed: u64) -> Crawl { + let ship = ship::generate(seed::derive(seed, "ship", 0)); + let cells = (ship.map.width * ship.map.height) as usize; + let mut crawl = Crawl { + fov: fov::compute(&ship.map, ship.start, SIGHT_RADIUS), + name: ship.name, + description: ship.description, + map: ship.map, + player: ship.start, + hp: PLAYER_HP, + max_hp: PLAYER_HP, + monsters: ship.monsters, + loot: ship.loot, + artifacts: Vec::new(), + scrip: 0, + medpatches: 0, + seen: vec![false; cells], + log: Vec::new(), + turns: 0, + outcome: None, + rng: seed::rng(seed::derive(seed, "dice", 0)), + }; + crawl.say(format!("You board {}, a derelict {}.", crawl.name, crawl.description)); + crawl.look(); + crawl + } + + pub fn seen(&self, p: Pos) -> bool { + self.map.contains(p) && self.seen[self.map.index(p)] + } + + pub fn monster_at(&self, p: Pos) -> Option<&Monster> { + self.monsters.iter().find(|m| m.pos == p) + } + + pub fn loot_at(&self, p: Pos) -> Option<&Loot> { + self.loot.iter().find(|l| l.pos == p) + } + + /// The name of where you're standing. + pub fn location(&self) -> &'static str { + self.map.room_at(self.player).map_or("a dark passage", |r| r.name) + } + + /// Takes your turn, then everything else's. Does nothing once the crawl + /// is over, or if the action wouldn't take any time (walking into a wall). + pub fn act(&mut self, action: Action) { + if self.outcome.is_some() { + return; + } + let took_time = match action { + Action::Wait => true, + Action::Move(dx, dy) => self.step(dx, dy), + Action::UseMedpatch => self.use_medpatch(), + }; + if !took_time || self.outcome.is_some() { + return; + } + self.turns += 1; + self.monsters_act(); + self.look(); + } + + fn say(&mut self, message: String) { + self.log.push(message); + if self.log.len() > LOG_LENGTH { + self.log.remove(0); + } + } + + /// Recomputes what you can see, remembers it, and wakes anything that's + /// now in view (and so, by symmetry, can see you). + fn look(&mut self) { + self.fov = fov::compute(&self.map, self.player, SIGHT_RADIUS); + for p in self.map.positions() { + if self.fov.contains(p) { + let i = self.map.index(p); + self.seen[i] = true; + } + } + let mut woken = Vec::new(); + for m in &mut self.monsters { + if !m.awake && self.fov.contains(m.pos) { + m.awake = true; + woken.push(m.kind.name); + } + } + for name in woken { + self.say(format!("A {name} stirs and turns toward you.")); + } + } + + fn step(&mut self, dx: i32, dy: i32) -> bool { + let target = self.player.offset(dx, dy); + if let Some(i) = self.monsters.iter().position(|m| m.pos == target) { + self.attack(i); + return true; + } + match self.map.tile(target) { + Tile::Door { open: false } => { + self.map.set(target, Tile::Door { open: true }); + self.say("The door grinds open.".into()); + true + } + Tile::Airlock => { + self.outcome = Some(Outcome::Escaped); + self.say("You cycle the airlock and cast off.".into()); + true + } + tile if tile.walkable() => { + self.player = target; + self.pick_up(); + true + } + _ => false, + } + } + + fn pick_up(&mut self) { + while let Some(i) = self.loot.iter().position(|l| l.pos == self.player) { + match self.loot.remove(i).item { + Item::Artifact(artifact) => { + self.say(format!("You find {}.", artifact.unidentified)); + self.artifacts.push(artifact); + } + Item::Salvage { name, value } => { + self.scrip += value; + self.say(format!("You salvage {name} ({value} ¤).")); + } + Item::Medpatch => { + self.medpatches += 1; + self.say("You pocket a medpatch.".into()); + } + } + } + } + + fn use_medpatch(&mut self) -> bool { + if self.medpatches == 0 { + self.say("You have no medpatches.".into()); + return false; + } + if self.hp == self.max_hp { + self.say("You're not hurt.".into()); + return false; + } + self.medpatches -= 1; + let healed = MEDPATCH_HEAL.min(self.max_hp - self.hp); + self.hp += healed; + self.say(format!("The medpatch stings, then numbs (+{healed}).")); + true + } + + fn attack(&mut self, i: usize) { + let name = self.monsters[i].kind.name; + self.monsters[i].awake = true; + if !self.rng.random_bool(PLAYER_HIT) { + self.say(format!("Your torch misses the {name}.")); + return; + } + let damage = self.rng.random_range(PLAYER_DAMAGE.0..=PLAYER_DAMAGE.1); + self.monsters[i].hp -= damage; + if self.monsters[i].hp <= 0 { + self.monsters.remove(i); + self.say(format!("You burn the {name} down to slag.")); + } else { + self.say(format!("You burn the {name} ({damage}).")); + } + } + + /// Each awake monster attacks if it's next to you, or else takes one + /// step along the shortest path toward you, opening doors on the way. + fn monsters_act(&mut self) { + let dist = self.map.distances_from(self.player); + for i in 0..self.monsters.len() { + if self.outcome.is_some() { + return; + } + let monster = &self.monsters[i]; + if !monster.awake { + continue; + } + if monster.pos.steps_to(self.player) == 1 { + self.monster_attacks(i); + continue; + } + let here = dist[self.map.index(monster.pos)].unwrap_or(u32::MAX); + let next = monster + .pos + .neighbours() + .filter(|&n| self.map.contains(n) && self.monster_at(n).is_none()) + .filter_map(|n| dist[self.map.index(n)].map(|d| (d, n))) + .filter(|&(d, _)| d < here) + .min_by_key(|&(d, n)| (d, n.y, n.x)); + if let Some((_, n)) = next { + if self.map.tile(n) == (Tile::Door { open: false }) { + self.map.set(n, Tile::Door { open: true }); + } else { + self.monsters[i].pos = n; + } + } + } + } + + fn monster_attacks(&mut self, i: usize) { + let kind = self.monsters[i].kind; + if !self.rng.random_bool(MONSTER_HIT) { + self.say(format!("The {} misses you.", kind.name)); + return; + } + let damage = self.rng.random_range(kind.damage.0..=kind.damage.1); + self.hp = (self.hp - damage).max(0); + self.say(format!("The {} {} you ({damage}).", kind.name, kind.verb)); + if self.hp == 0 { + self.outcome = Some(Outcome::Died { killer: kind.name }); + self.say(format!("You die aboard {}.", self.name)); + } + } +} + +#[cfg(test)] +mod tests { + use super::*; + + /// A bot that wanders at random, for shaking out panics and broken rules. + fn wander(crawl: &mut Crawl, rng: &mut Rng, turns: usize) { + const ACTIONS: [Action; 10] = [ + Action::Move(-1, -1), + Action::Move(0, -1), + Action::Move(1, -1), + Action::Move(-1, 0), + Action::Move(1, 0), + Action::Move(-1, 1), + Action::Move(0, 1), + Action::Move(1, 1), + Action::Wait, + Action::UseMedpatch, + ]; + for _ in 0..turns { + crawl.act(ACTIONS[rng.random_range(..ACTIONS.len())]); + } + } + + #[test] + fn random_play_keeps_the_rules() { + for seed in 0..40 { + let mut crawl = Crawl::new(seed); + wander(&mut crawl, &mut seed::rng(seed), 600); + assert!(crawl.hp >= 0 && crawl.hp <= crawl.max_hp); + assert!(crawl.map.tile(crawl.player).walkable(), "seed {seed}: player in a wall"); + for m in &crawl.monsters { + assert!(crawl.map.tile(m.pos).walkable(), "seed {seed}: {} in a wall", m.kind.name); + assert_ne!(m.pos, crawl.player); + } + if crawl.outcome.is_none() { + assert!(crawl.fov.contains(crawl.player)); + } + } + } + + #[test] + fn same_seed_same_moves_same_story() { + let play = || { + let mut crawl = Crawl::new(7); + wander(&mut crawl, &mut seed::rng(70), 300); + crawl.log + }; + assert_eq!(play(), play()); + } + + #[test] + fn the_airlock_takes_you_home() { + let mut crawl = Crawl::new(3); + let airlock = crawl.player.neighbours().find(|&n| crawl.map.tile(n) == Tile::Airlock); + let airlock = airlock.expect("the start is beside the airlock"); + let (dx, dy) = (airlock.x - crawl.player.x, airlock.y - crawl.player.y); + crawl.act(Action::Move(dx, dy)); + assert_eq!(crawl.outcome, Some(Outcome::Escaped)); + } + + #[test] + fn fighting_kills_things() { + let mut crawl = Crawl::new(5); + let next_to_player = crawl.player.neighbours().find(|&n| crawl.map.tile(n).walkable()); + let pos = next_to_player.unwrap(); + crawl.monsters = vec![Monster { kind: &MONSTERS[0], pos, hp: 3, awake: true }]; + let (dx, dy) = (pos.x - crawl.player.x, pos.y - crawl.player.y); + for _ in 0..50 { + crawl.act(Action::Move(dx, dy)); + if crawl.monsters.is_empty() { + break; + } + } + assert!(crawl.monsters.is_empty(), "a rust-mite survived 50 swings"); + assert!(crawl.log.iter().any(|m| m.contains("slag"))); + } + + #[test] + fn walking_into_walls_takes_no_time() { + let mut crawl = Crawl::new(11); + let wall = crawl + .player + .neighbours() + .find(|&n| matches!(crawl.map.tile(n), Tile::Wall | Tile::Hull)); + let wall = wall.unwrap(); + crawl.act(Action::Move(wall.x - crawl.player.x, wall.y - crawl.player.y)); + assert_eq!(crawl.turns, 0); + } +} 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 +//! . +//! +//! 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, +} + +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::>() { + if rng.random_bool(0.25) { + map.set(p, Tile::Wall); + } + } + let floors: Vec = + map.positions().filter(|&p| map.tile(p) == Tile::Floor).collect(); + let views: Vec = 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" + ); + } + } + } + } +} diff --git a/src/dungeon/mod.rs b/src/dungeon/mod.rs new file mode 100644 index 0000000..d3227a5 --- /dev/null +++ b/src/dungeon/mod.rs @@ -0,0 +1,156 @@ +//! Turn-based dungeons: the map, field of view, derelict-ship generation, +//! and the rules of a crawl. Drawing lives in `scenes::derelict`. + +pub mod crawl; +pub mod fov; +pub mod ship; + +#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] +pub struct Pos { + pub x: i32, + pub y: i32, +} + +impl Pos { + pub const fn new(x: i32, y: i32) -> Pos { + Pos { x, y } + } + + pub const fn offset(self, dx: i32, dy: i32) -> Pos { + Pos::new(self.x + dx, self.y + dy) + } + + /// Steps from here to `other` when diagonal moves are allowed. + pub fn steps_to(self, other: Pos) -> i32 { + (self.x - other.x).abs().max((self.y - other.y).abs()) + } + + /// The eight cells around this one. + pub fn neighbours(self) -> impl Iterator { + const DIRS: [(i32, i32); 8] = + [(-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)]; + DIRS.into_iter().map(move |(dx, dy)| self.offset(dx, dy)) + } +} + +#[derive(Clone, Copy, Debug, PartialEq, Eq)] +pub enum Tile { + /// Outside the ship. + Void, + /// The outer skin of the ship. + Hull, + /// An inside wall. + Wall, + Floor, + /// Floor strewn with wreckage. Walkable; it just looks different. + Debris, + Door { + open: bool, + }, + /// The way out: the airlock your own ship is docked to. + Airlock, +} + +impl Tile { + /// Whether you can step onto it. Closed doors open when bumped instead, + /// and stepping into the airlock leaves the ship. + pub fn walkable(self) -> bool { + matches!(self, Tile::Floor | Tile::Debris | Tile::Door { open: true }) + } + + pub fn blocks_sight(self) -> bool { + matches!( + self, + Tile::Void | Tile::Hull | Tile::Wall | Tile::Door { open: false } | Tile::Airlock + ) + } +} + +/// A named area of the map, shown to the player while they stand in it. +pub struct Room { + pub name: &'static str, +} + +pub struct Map { + pub width: i32, + pub height: i32, + tiles: Vec, + room_of: Vec>, + pub rooms: Vec, +} + +impl Map { + pub fn new(width: i32, height: i32, fill: Tile) -> Map { + let cells = (width * height) as usize; + Map { + width, + height, + tiles: vec![fill; cells], + room_of: vec![None; cells], + rooms: Vec::new(), + } + } + + pub fn contains(&self, p: Pos) -> bool { + p.x >= 0 && p.y >= 0 && p.x < self.width && p.y < self.height + } + + /// Index into a per-cell `Vec` laid out like the map. Panics off the map. + pub fn index(&self, p: Pos) -> usize { + assert!(self.contains(p), "{p:?} is off the map"); + (p.y * self.width + p.x) as usize + } + + /// The tile at `p`; everything off the map is `Void`. + pub fn tile(&self, p: Pos) -> Tile { + if self.contains(p) { self.tiles[self.index(p)] } else { Tile::Void } + } + + pub fn set(&mut self, p: Pos, tile: Tile) { + let i = self.index(p); + self.tiles[i] = tile; + } + + pub fn room_at(&self, p: Pos) -> Option<&Room> { + if !self.contains(p) { + return None; + } + self.room_of[self.index(p)].map(|r| &self.rooms[usize::from(r)]) + } + + pub fn add_room(&mut self, name: &'static str) -> u16 { + self.rooms.push(Room { name }); + (self.rooms.len() - 1) as u16 + } + + pub fn set_room(&mut self, p: Pos, room: Option) { + let i = self.index(p); + self.room_of[i] = room; + } + + pub fn positions(&self) -> impl Iterator + use<> { + let (w, h) = (self.width, self.height); + (0..h).flat_map(move |y| (0..w).map(move |x| Pos::new(x, y))) + } + + /// Steps from `from` to every cell reachable through walkable tiles and + /// closed doors, moving diagonally too; `None` where unreachable. + pub fn distances_from(&self, from: Pos) -> Vec> { + let mut dist = vec![None; self.tiles.len()]; + let mut queue = std::collections::VecDeque::from([from]); + dist[self.index(from)] = Some(0); + while let Some(p) = queue.pop_front() { + let d = dist[self.index(p)].unwrap(); + for n in p.neighbours() { + let tile = self.tile(n); + if (tile.walkable() || tile == (Tile::Door { open: false })) + && dist[self.index(n)].is_none() + { + dist[self.index(n)] = Some(d + 1); + queue.push_back(n); + } + } + } + dist + } +} diff --git a/src/dungeon/ship.rs b/src/dungeon/ship.rs new file mode 100644 index 0000000..dc9b0b8 --- /dev/null +++ b/src/dungeon/ship.rs @@ -0,0 +1,452 @@ +//! Derelict ships. +//! +//! A derelict is a hull silhouette, mirrored top to bottom, lying along the +//! x axis with its engines at the left and its nose at the right. A spine +//! corridor runs down the middle from the engine room to the bridge, and the +//! space either side of it is cut into sections, each holding a room above +//! the spine and one below: +//! +//! ```text +//! ########## +//! #####.....#..####### +//! #...#.....#..+.....##### +//! #...###+#######+######..### +//! #.............................## +//! #...###+######+#######..### +//! #...#......#.......##### +//! ############ ###### +//! engine room middle bridge +//! ``` +//! +//! Every room has a door onto the spine (or onto the room between it and the +//! spine), so the whole ship is connected; a few extra doors between +//! neighbouring rooms make loops to run around. + +use rand::RngExt; +use rand::seq::IndexedRandom; + +use super::crawl::{Item, Loot, MONSTERS, Monster}; +use super::{Map, Pos, Tile}; +use crate::names::{self, Culture}; +use crate::seed::{self, Rng}; + +pub struct Derelict { + /// "the Vexant". + pub name: String, + /// "Cant hauler". + pub description: String, + pub map: Map, + /// Where the player comes aboard, just inside the airlock. + pub start: Pos, + pub monsters: Vec, + pub loot: Vec, +} + +struct RoomKind { + name: &'static str, + /// How often it turns up, relative to the other middle rooms. + weight: u32, + /// Chance of an artifact. + artifact: f64, + /// How many pieces of salvage: anywhere from .0 to .1. + salvage: (u32, u32), + /// Chance of a medpatch. + medpatch: f64, +} + +const ENGINE_ROOM: RoomKind = + RoomKind { name: "the engine room", weight: 0, artifact: 0.05, salvage: (2, 3), medpatch: 0.1 }; +const BRIDGE: RoomKind = + RoomKind { name: "the bridge", weight: 0, artifact: 0.6, salvage: (0, 2), medpatch: 0.1 }; + +#[rustfmt::skip] +const ROOMS: &[RoomKind] = &[ + RoomKind { name: "a cargo hold", weight: 4, artifact: 0.05, salvage: (2, 4), medpatch: 0.05 }, + RoomKind { name: "the crew berths", weight: 3, artifact: 0.1, salvage: (0, 1), medpatch: 0.25 }, + RoomKind { name: "the galley", weight: 2, artifact: 0.02, salvage: (0, 2), medpatch: 0.1 }, + RoomKind { name: "the med-bay", weight: 1, artifact: 0.05, salvage: (0, 1), medpatch: 1.0 }, + RoomKind { name: "a machine shop", weight: 2, artifact: 0.05, salvage: (1, 3), medpatch: 0.0 }, + RoomKind { name: "the armoury", weight: 1, artifact: 0.15, salvage: (1, 2), medpatch: 0.3 }, + RoomKind { name: "a cryo-vault", weight: 1, artifact: 0.3, salvage: (0, 1), medpatch: 0.2 }, + RoomKind { name: "the chapel", weight: 1, artifact: 0.5, salvage: (0, 1), medpatch: 0.0 }, + RoomKind { name: "the reliquary", weight: 1, artifact: 0.9, salvage: (0, 0), medpatch: 0.0 }, + RoomKind { name: "the archive", weight: 1, artifact: 0.4, salvage: (0, 1), medpatch: 0.0 }, + RoomKind { name: "the navigator's cell", weight: 1, artifact: 0.5, salvage: (0, 1), medpatch: 0.0 }, + RoomKind { name: "an observation blister", weight: 1, artifact: 0.1, salvage: (0, 1), medpatch: 0.0 }, +]; + +/// Salvage and its base value; each find varies by ±30%. +const SALVAGE: &[(&str, u32)] = &[ + ("a coil of superconductor", 30), + ("a cracked reactor baffle", 45), + ("a crate of ration bricks", 10), + ("an intact navigation core", 90), + ("a spool of wiring", 15), + ("a stack of hull plates", 25), + ("a sealed canister of coolant", 20), + ("a working servo", 35), + ("a box of votive candles", 8), + ("a cantor's data-slate", 40), + ("a half-charged fuel cell", 50), +]; + +/// A room as generated, before its contents are placed. +struct Plan { + kind: &'static RoomKind, + cells: Vec, +} + +pub fn generate(seed: u64) -> Derelict { + let mut rng = seed::rng(seed); + let culture = Culture::ALL[rng.random_range(..Culture::ALL.len())]; + let name = format!("the {}", culture.word(&mut rng)); + let length: i32 = rng.random_range(44..=88); + let max_half: i32 = rng.random_range(5..=9); + let class = match length { + ..56 => "cutter", + 56..72 => "hauler", + _ if rng.random_bool(0.5) => "pilgrim-barge", + _ => "reliquary-ship", + }; + let description = format!("{} {class}", culture.adjective()); + + let hull = Hull::new(&mut rng, length, max_half); + let mut map = hull.map(); + let plans = carve_rooms(&mut map, &hull, &mut rng); + let start = place_airlock(&mut map, &hull, &mut rng); + + for p in map.positions().collect::>() { + if map.tile(p) == Tile::Floor && p != start && rng.random_bool(0.06) { + map.set(p, Tile::Debris); + } + } + + // Everything is connected by construction, but if a hull's odd shape + // ever cuts a room in two, wall off the part that can't be reached + // rather than strand loot or monsters there. + let dist = map.distances_from(start); + let reachable = |map: &Map, p: Pos| dist[map.index(p)].is_some(); + for p in map.positions().collect::>() { + let open = matches!(map.tile(p), Tile::Floor | Tile::Debris | Tile::Door { .. }); + if open && !reachable(&map, p) { + map.set(p, Tile::Wall); + map.set_room(p, None); + } + } + let free = |map: &Map, p: Pos| { + p != start && matches!(map.tile(p), Tile::Floor | Tile::Debris) && reachable(map, p) + }; + + let mut loot = Vec::new(); + for plan in &plans { + let cells: Vec = plan.cells.iter().copied().filter(|&p| free(&map, p)).collect(); + if cells.is_empty() { + continue; + } + let kind = plan.kind; + if rng.random_bool(kind.artifact) { + let pos = *cells.choose(&mut rng).unwrap(); + loot.push(Loot { pos, item: Item::Artifact(names::artifact(&mut rng)) }); + } + for _ in 0..rng.random_range(kind.salvage.0..=kind.salvage.1) { + let pos = *cells.choose(&mut rng).unwrap(); + let &(name, base) = SALVAGE.choose(&mut rng).unwrap(); + let value = (f64::from(base) * rng.random_range(0.7..1.3)).round() as u32; + loot.push(Loot { pos, item: Item::Salvage { name, value } }); + } + let medpatches = if kind.medpatch >= 1.0 { + rng.random_range(1..=2) + } else { + u32::from(rng.random_bool(kind.medpatch)) + }; + for _ in 0..medpatches { + loot.push(Loot { pos: *cells.choose(&mut rng).unwrap(), item: Item::Medpatch }); + } + } + // Every derelict is worth boarding: if no room rolled an artifact, put + // one as far from the airlock as the ship goes. + if !loot.iter().any(|l| matches!(l.item, Item::Artifact(_))) { + let farthest = map + .positions() + .filter(|&p| free(&map, p)) + .max_by_key(|&p| (dist[map.index(p)], p.x, p.y)) + .expect("a derelict always has floor"); + loot.push(Loot { pos: farthest, item: Item::Artifact(names::artifact(&mut rng)) }); + } + + let lairs: Vec = map + .positions() + .filter(|&p| free(&map, p) && dist[map.index(p)].is_some_and(|d| d >= 7)) + .collect(); + let mut monsters: Vec = Vec::new(); + for _ in 0..(length / 11 + rng.random_range(0..=2)) { + let Some(&pos) = lairs.choose(&mut rng) else { break }; + if monsters.iter().any(|m| m.pos == pos) { + continue; + } + let kind = MONSTERS.choose_weighted(&mut rng, |k| k.weight).unwrap(); + if kind.unique && monsters.iter().any(|m| m.kind.name == kind.name) { + continue; + } + monsters.push(Monster { kind, pos, hp: kind.hp, awake: false }); + } + + Derelict { name, description, map, start, monsters, loot } +} + +struct Hull { + /// Half-height of the hull at each x along the ship, stern first. + half: Vec, + /// How many columns of `half` are engine block, and how many nose. + engine: i32, + nose: i32, + max_half: i32, +} + +impl Hull { + fn new(rng: &mut Rng, length: i32, max_half: i32) -> Hull { + let engine = rng.random_range(4..=7); + let nose = (f64::from(length) * rng.random_range(0.2..0.32)) as i32; + let body = length - engine - nose; + + // A broad engine block, then a body of two to four blocky sections, + // each at least 4 high so the rooms either side of the spine fit. + let mut half = vec![rng.random_range(max_half - 2..=max_half); engine as usize]; + let sections = rng.random_range(2..=4); + for s in 0..sections { + let width = body * (s + 1) / sections - body * s / sections; + let h = rng.random_range(4.max(max_half * 3 / 5)..=max_half); + half.extend(std::iter::repeat_n(h, width as usize)); + } + // A nose tapering to a point; the exponent sets how blunt it is. + let last = f64::from(*half.last().unwrap()); + let bluntness = rng.random_range(1.0..2.5); + for i in 0..nose { + let t = f64::from(i + 1) / f64::from(nose); + half.push(((last * (1.0 - t.powf(bluntness))).round() as i32).max(1)); + } + Hull { half, engine, nose, max_half } + } + + fn length(&self) -> i32 { + self.half.len() as i32 + } + + /// The row the spine runs along. + fn spine(&self) -> i32 { + self.max_half + 1 + } + + /// Map x runs from 0 to length + 1, so there's a column of space at each end. + fn inside(&self, p: Pos) -> bool { + (1..=self.length()).contains(&p.x) + && (p.y - self.spine()).abs() <= self.half[(p.x - 1) as usize] + } + + /// Cells inside the hull become `Wall` (rooms are carved out of it + /// later); the edge of the inside becomes `Hull`. + fn map(&self) -> Map { + let mut map = Map::new(self.length() + 2, 2 * self.max_half + 3, Tile::Void); + for p in map.positions() { + if self.inside(p) { + let edge = p.neighbours().any(|n| !self.inside(n)); + map.set(p, if edge { Tile::Hull } else { Tile::Wall }); + } + } + map + } +} + +fn carve(map: &mut Map, p: Pos, room: u16) { + if map.tile(p) == Tile::Wall { + map.set(p, Tile::Floor); + map.set_room(p, Some(room)); + } +} + +fn door(map: &mut Map, p: Pos, rng: &mut Rng) { + // A quarter of doors were left open, or jammed that way. + map.set(p, Tile::Door { open: rng.random_bool(0.25) }); +} + +fn carve_rooms(map: &mut Map, hull: &Hull, rng: &mut Rng) -> Vec { + let (length, cy) = (hull.length(), hull.spine()); + let mut plans = Vec::new(); + + // The engine room and bridge span the ship's full height, so the spine + // runs straight into them. Carve them first so the spine's cells there + // belong to them (carving only turns walls into floor). + let engine_end = hull.engine; + let bridge_start = length - hull.nose + 1; + for (kind, xs) in [(&ENGINE_ROOM, 2..=engine_end), (&BRIDGE, bridge_start..=length - 1)] { + let room = map.add_room(kind.name); + let cells: Vec = + map.positions().filter(|p| xs.contains(&p.x) && map.tile(*p) == Tile::Wall).collect(); + for &p in &cells { + carve(map, p, room); + } + plans.push(Plan { kind, cells }); + } + let spine = map.add_room("the spine corridor"); + for x in 2..length { + carve(map, Pos::new(x, cy), spine); + } + + // Cut the middle into sections 3-8 wide, with a wall column between each. + let (lo, hi) = (engine_end + 2, bridge_start - 2); + let mut sections = Vec::new(); + let mut x = lo; + while x <= hi { + let mut end = (x + rng.random_range(2..=7)).min(hi); + if hi - end < 4 { + end = hi; + } + sections.push((x, end)); + x = end + 2; + } + + for &(sa, sb) in §ions { + for side in [-1, 1] { + // `depth` counts rows out from the spine; row 1 is the wall + // between spine and rooms. + let at = |x: i32, depth: i32| Pos::new(x, cy + side * depth); + let cells: Vec<(Pos, i32)> = (sa..=sb) + .flat_map(|x| (2..=hull.max_half).map(move |d| (at(x, d), d))) + .filter(|&(p, _)| map.tile(p) == Tile::Wall) + .collect(); + let door_xs: Vec = + (sa..=sb).filter(|&x| map.tile(at(x, 2)) == Tile::Wall).collect(); + if cells.len() < 4 || door_xs.is_empty() { + continue; + } + + // Deep enough sections sometimes hold two rooms, one behind the + // other, with a wall and a door between them. + let deepest = cells.iter().map(|&(_, d)| d).max().unwrap(); + let mut split = None; + if deepest >= 6 && rng.random_bool(0.5) { + let s = rng.random_range(4..=deepest - 2); + let between: Vec = (sa..=sb) + .filter(|&x| { + map.tile(at(x, s - 1)) == Tile::Wall && map.tile(at(x, s + 1)) == Tile::Wall + }) + .collect(); + if let Some(&x) = between.choose(rng) { + split = Some((s, x)); + } + } + + let rooms: Vec> = match split { + None => vec![cells.iter().map(|&(p, _)| p).collect()], + Some((s, _)) => vec![ + cells.iter().filter(|&&(_, d)| d < s).map(|&(p, _)| p).collect(), + cells.iter().filter(|&&(_, d)| d > s).map(|&(p, _)| p).collect(), + ], + }; + for room_cells in rooms { + let kind = ROOMS.choose_weighted(rng, |k| k.weight).unwrap(); + let room = map.add_room(kind.name); + for &p in &room_cells { + carve(map, p, room); + } + plans.push(Plan { kind, cells: room_cells }); + } + if let Some((s, x)) = split { + door(map, at(x, s), rng); + } + door(map, at(*door_xs.choose(rng).unwrap(), 1), rng); + } + } + + // Now and then, a door through the wall column between neighbouring + // rooms, so there's more than one way around. + let walls = std::iter::once(engine_end + 1).chain(sections.iter().map(|&(_, sb)| sb + 1)); + for x in walls.collect::>() { + for side in [-1, 1] { + let spots: Vec = (2..=hull.max_half) + .map(|d| Pos::new(x, cy + side * d)) + .filter(|&p| { + map.tile(p) == Tile::Wall + && map.tile(p.offset(-1, 0)) == Tile::Floor + && map.tile(p.offset(1, 0)) == Tile::Floor + }) + .collect(); + if !spots.is_empty() && rng.random_bool(0.3) { + door(map, *spots.choose(rng).unwrap(), rng); + } + } + } + plans +} + +/// Puts the airlock on a flat stretch of outer hull beside a middle room and +/// returns the cell just inside it. Falls back to the stern, where the spine +/// always meets the hull. +fn place_airlock(map: &mut Map, hull: &Hull, rng: &mut Rng) -> Pos { + let cy = hull.spine(); + let middle = hull.engine + 2..=hull.length() - hull.nose - 1; + let spots: Vec<(Pos, Pos)> = map + .positions() + .filter_map(|p| { + let side = (p.y - cy).signum(); + let inward = p.offset(0, -side); + let flat = + map.tile(p.offset(-1, 0)) == Tile::Hull && map.tile(p.offset(1, 0)) == Tile::Hull; + (side != 0 + && middle.contains(&p.x) + && map.tile(p) == Tile::Hull + && map.tile(p.offset(0, side)) == Tile::Void + && map.tile(inward) == Tile::Floor + && flat) + .then_some((p, inward)) + }) + .collect(); + let (airlock, start) = spots.choose(rng).copied().unwrap_or((Pos::new(1, cy), Pos::new(2, cy))); + map.set(airlock, Tile::Airlock); + start +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn derelicts_are_sound() { + for seed in 0..300 { + let d = generate(seed); + let map = &d.map; + assert!(map.width <= 90 && map.height <= 21, "seed {seed}: too big"); + assert_eq!(map.tile(d.start), Tile::Floor, "seed {seed}: start isn't floor"); + assert!( + d.start.neighbours().any(|n| map.tile(n) == Tile::Airlock), + "seed {seed}: no airlock beside the start" + ); + + let dist = map.distances_from(d.start); + for p in map.positions() { + if map.tile(p).walkable() || matches!(map.tile(p), Tile::Door { .. }) { + assert!(dist[map.index(p)].is_some(), "seed {seed}: {p:?} is unreachable"); + } + } + for m in &d.monsters { + assert!(map.tile(m.pos).walkable(), "seed {seed}: monster in a wall"); + assert!(dist[map.index(m.pos)] >= Some(7), "seed {seed}: monster too near start"); + } + for l in &d.loot { + assert!(map.tile(l.pos).walkable(), "seed {seed}: loot in a wall"); + assert_ne!(l.pos, d.start); + } + assert!(d.loot.iter().any(|l| matches!(l.item, Item::Artifact(_)))); + assert!(map.rooms.len() >= 4, "seed {seed}: only {} rooms", map.rooms.len()); + assert!(d.monsters.iter().filter(|m| m.kind.unique).count() <= 1); + } + } + + #[test] + fn same_seed_same_ship() { + let (a, b) = (generate(99), generate(99)); + assert_eq!(a.name, b.name); + assert_eq!(a.start, b.start); + assert!(a.map.positions().all(|p| a.map.tile(p) == b.map.tile(p))); + } +} -- cgit v1.2.3