path: root/src/dungeon/ship.rs

//! 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)));
    }
}