summaryrefslogtreecommitdiff
path: root/src/dungeon
diff options
context:
space:
mode:
Diffstat (limited to 'src/dungeon')
-rw-r--r--src/dungeon/crawl.rs416
-rw-r--r--src/dungeon/fov.rs207
-rw-r--r--src/dungeon/mod.rs156
-rw-r--r--src/dungeon/ship.rs452
4 files changed, 1231 insertions, 0 deletions
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<Monster>,
+ pub loot: Vec<Loot>,
+ /// What you're carrying. It's only yours once you're back through the airlock.
+ pub artifacts: Vec<Artifact>,
+ 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<bool>,
+ /// Messages, oldest first.
+ pub log: Vec<String>,
+ pub turns: u32,
+ pub outcome: Option<Outcome>,
+ /// 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
+//! <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"
+ );
+ }
+ }
+ }
+ }
+}
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<Item = Pos> {
+ 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<Tile>,
+ room_of: Vec<Option<u16>>,
+ pub rooms: Vec<Room>,
+}
+
+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<u16>) {
+ let i = self.index(p);
+ self.room_of[i] = room;
+ }
+
+ pub fn positions(&self) -> impl Iterator<Item = Pos> + 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<Option<u32>> {
+ 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<Monster>,
+ pub loot: Vec<Loot>,
+}
+
+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<Pos>,
+}
+
+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::<Vec<_>>() {
+ 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::<Vec<_>>() {
+ 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<Pos> = 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<Pos> = map
+ .positions()
+ .filter(|&p| free(&map, p) && dist[map.index(p)].is_some_and(|d| d >= 7))
+ .collect();
+ let mut monsters: Vec<Monster> = 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<i32>,
+ /// 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<Plan> {
+ 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<Pos> =
+ 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 &sections {
+ 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<i32> =
+ (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<i32> = (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<Vec<Pos>> = 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::<Vec<_>>() {
+ for side in [-1, 1] {
+ let spots: Vec<Pos> = (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)));
+ }
+}
generated by cgit v1.2.3 (git 2.46.0) at 2026-11-12 01:19:44 +0000