//! Laying out a capital.
//!
//! The wall is a rounded, slightly lumpy oval. A landing field lies outside
//! its west gate, and one to three more gates open on the other sides. A
//! road runs inside the wall all the way round, and avenues run from each
//! gate to the market square in the middle.
//!
//! The city is shared out into quarters around points scattered inside the
//! wall: a market around the square, a gate quarter by the landing field,
//! then a grand quarter, a holy one, homes, a poor quarter, works, gardens.
//! Then it's cut into blocks, from the outside in: each block is split in
//! two by a street until it's small enough for its quarter, so streets meet
//! at T-junctions and never quite line up, the way old cities grow. Poor
//! quarters end up with small blocks and alleys, grand ones with big blocks
//! and wide streets.
//!
//! A few blocks are kept whole: one for the palace, one for the temple,
//! parks and plazas. Every other block gets buildings packed along the
//! streets around it, doors facing out, with yards and courtyards left
//! behind them. Then each building is given a use to suit its quarter, and
//! the shops are chosen from buildings in the right places: the broker and
//! the shipyard by the gate you came in by, the tavern by the square.
//!
//! The world has a say too (`Lay`): how many parks there are, how big their
//! ponds, how thick the trees and what's scattered outside the walls. On
//! an ocean world the city stands on an island, its landing field out on a
//! spit of sand and its other roads running out to sea as causeways.

use rand::RngExt;
use rand::seq::{IndexedRandom, SliceRandom};

use super::words;
use super::*;
use crate::seed::Rng;

/// Columns west of the city wall, for the landing field and the road in.
const FIELD: i32 = 26;
/// The landing field's east edge.
const PAD_RIGHT: i32 = 19;
/// How far the wall's wobble can push it out, as a share of its radius.
const REACH: f64 = 1.08;

/// How a world bends a city's plan. Each is times what it'd be otherwise.
struct Lay {
    parks: f64,
    trees: f64,
    /// How big ponds are. None at all at 0.
    ponds: f64,
    /// The chance of something standing on any bit of ground outside the
    /// walls (not times anything).
    wild: f64,
    /// Whether the sea comes up round the walls.
    sea: bool,
}

fn lay(terrain: Terrain) -> Lay {
    let lay = |parks, trees, ponds, wild| Lay { parks, trees, ponds, wild, sea: false };
    match terrain {
        // Few parks, small cisterns, little shade.
        Terrain::Desert => lay(0.35, 0.5, 0.55, 0.04),
        Terrain::Ice => lay(0.6, 0.6, 1.0, 0.06),
        Terrain::Ocean => Lay { sea: true, ..lay(1.0, 1.0, 1.2, 0.05) },
        // Parks everywhere, trees crowding every yard.
        Terrain::Jungle => lay(3.0, 3.0, 1.0, 0.3),
        // Nothing pools on airless rock.
        Terrain::Barren | Terrain::Clouds => lay(0.6, 0.8, 0.0, 0.05),
        Terrain::Forge => lay(0.7, 0.7, 0.7, 0.06),
    }
}

fn lerp(a: f64, b: f64, t: f64) -> f64 {
    a + (b - a) * t
}

/// The line of the city wall: a superellipse, wobbled.
struct WallShape {
    cx: f64,
    cy: f64,
    rx: f64,
    ry: f64,
    /// 2 is an ellipse; the higher, the squarer.
    n: f64,
    /// Sine waves on the radius: (how many round the wall, how big, where).
    wobble: [(f64, f64, f64); 2],
}

impl WallShape {
    fn inside(&self, p: Pos) -> bool {
        let dx = (f64::from(p.x) + 0.5 - self.cx) / self.rx;
        let dy = (f64::from(p.y) + 0.5 - self.cy) / self.ry;
        let d = (dx.abs().powf(self.n) + dy.abs().powf(self.n)).powf(1.0 / self.n);
        let angle = dy.atan2(dx);
        let r =
            1.0 + self.wobble.iter().map(|&(k, amp, at)| amp * (k * angle + at).sin()).sum::<f64>();
        d <= r
    }
}

/// How big blocks get in a quarter before a street splits them: columns
/// and rows.
fn block_size(q: QuarterKind) -> (i32, i32) {
    match q {
        QuarterKind::Poor => (14, 6),
        QuarterKind::Homes => (20, 8),
        QuarterKind::Market => (18, 8),
        QuarterKind::Gate => (20, 8),
        QuarterKind::Grand => (30, 12),
        QuarterKind::Holy => (24, 10),
        QuarterKind::Works => (26, 10),
        QuarterKind::Gardens => (26, 11),
    }
}

/// How wide a street is, columns for one running north–south and rows for
/// one running east–west. A row is twice as tall as a column is wide, so
/// (2, 1) looks the same either way.
fn street_width(q: QuarterKind, depth: u32, rng: &mut Rng) -> (i32, i32) {
    use QuarterKind::*;
    match (q, depth) {
        (Poor, 0) => (2, 1),
        (Poor, _) => (1, 1),
        (_, 0) | (Grand | Market | Gate, 1) => (3, 2),
        (Homes, 3..) if rng.random_bool(0.3) => (1, 1),
        _ => (2, 1),
    }
}

/// The sizes of building a quarter packs along its streets.
struct Lots {
    /// For doors facing north or south: columns along the street, and rows
    /// deep.
    wide: (i32, i32),
    deep: (i32, i32),
    /// For doors facing east or west: rows along the street, and columns deep.
    tall: (i32, i32),
    long: (i32, i32),
    /// The chance of a gap after each building.
    gap: f64,
}

fn lots(q: QuarterKind) -> Lots {
    let lots = |wide, deep, tall, long, gap| Lots { wide, deep, tall, long, gap };
    match q {
        QuarterKind::Poor => lots((4, 6), (2, 3), (3, 3), (4, 6), 0.12),
        QuarterKind::Homes => lots((5, 8), (2, 4), (3, 4), (5, 8), 0.3),
        QuarterKind::Market => lots((6, 11), (3, 4), (3, 4), (6, 10), 0.15),
        QuarterKind::Gate => lots((6, 11), (3, 4), (3, 4), (6, 10), 0.25),
        QuarterKind::Grand => lots((8, 13), (3, 5), (3, 5), (8, 12), 0.45),
        QuarterKind::Holy => lots((5, 9), (3, 4), (3, 4), (5, 9), 0.35),
        QuarterKind::Works => lots((7, 13), (3, 5), (3, 5), (7, 12), 0.2),
        QuarterKind::Gardens => lots((5, 9), (2, 4), (3, 4), (5, 8), 0.6),
    }
}

/// What the buildings in a quarter tend to be, and how often.
fn uses(q: QuarterKind, culture: Culture) -> Vec<(Kind, f64)> {
    use Kind::*;
    let baths = if matches!(culture, Culture::Qaari | Culture::Houses) { 1.0 } else { 0.0 };
    match q {
        QuarterKind::Market => vec![
            (House, 3.0),
            (Workshop, 2.5),
            (Warehouse, 1.0),
            (Tenement, 1.0),
            (Shrine, 0.3),
            (Bathhouse, 0.6 * baths),
        ],
        QuarterKind::Gate => {
            vec![(Warehouse, 3.0), (House, 2.0), (Workshop, 1.5), (Tenement, 1.0), (Shrine, 0.2)]
        }
        QuarterKind::Homes => vec![
            (House, 8.0),
            (Tenement, 1.5),
            (Shrine, 0.5),
            (Workshop, 1.0),
            (Bathhouse, 0.4 * baths),
        ],
        QuarterKind::Poor => vec![(Tenement, 5.0), (House, 3.0), (Workshop, 1.0), (Shrine, 0.6)],
        QuarterKind::Grand => {
            vec![(Manor, 6.0), (House, 1.5), (Shrine, 0.5), (Bathhouse, 0.6 * baths)]
        }
        QuarterKind::Holy => vec![(Shrine, 2.5), (House, 3.0), (Tenement, 1.0), (Workshop, 1.0)],
        QuarterKind::Works => {
            vec![(Workshop, 6.0), (Warehouse, 4.0), (Tenement, 2.0), (House, 1.0)]
        }
        QuarterKind::Gardens => {
            vec![(House, 3.0), (Manor, 2.0), (Shrine, 1.0), (Bathhouse, 0.6 * baths)]
        }
    }
}

/// Whether a building this many columns and rows is big enough to be one
/// of these.
fn fits(kind: Kind, w: i32, h: i32) -> bool {
    let area = w * h;
    match kind {
        Kind::Manor => area >= 21,
        Kind::Warehouse | Kind::Bathhouse => area >= 18,
        Kind::Tenement => area >= 15,
        _ => true,
    }
}

/// How likely each kind of building is to have its door barred to you.
fn barred_chance(kind: Kind) -> f64 {
    match kind {
        Kind::House => 0.35,
        Kind::Manor => 0.5,
        Kind::Warehouse => 0.4,
        Kind::Tenement => 0.15,
        Kind::Workshop => 0.05,
        _ => 0.0,
    }
}

struct Planner<'a> {
    t: Town,
    rng: &'a mut Rng,
    lay: Lay,
    wall: WallShape,
    size: f64,
    main: i32,
    square: Rect,
    /// Quarter kinds and the points they're centred on.
    points: Vec<(QuarterKind, Pos)>,
    /// Blocks between streets, and whether each has been used for
    /// something already.
    blocks: Vec<(Rect, bool)>,
    /// Parks, which get more trees.
    parks: Vec<Rect>,
    /// Market stalls, each with its keeper's place in front.
    stalls: Vec<Pos>,
    /// The grounds of the palace and the temple, which streets go round.
    grounds: Vec<Rect>,
}

pub(super) fn build(
    name: String,
    culture: Culture,
    land: Land,
    seed: u64,
    size: f64,
    rng: &mut Rng,
) -> Town {
    let rx = lerp(60.0, 116.0, size) * rng.random_range(0.92..1.08);
    let ry = rx * rng.random_range(0.40..0.50);
    let width = FIELD + (2.0 * rx * REACH).ceil() as i32 + 6;
    let height = (2.0 * ry * REACH).ceil() as i32 + 10;
    let main = height / 2;
    let mut wobble = || {
        (
            f64::from(rng.random_range(3..=7)),
            rng.random_range(0.0..0.035),
            rng.random_range(0.0..6.3),
        )
    };
    let wobble = [wobble(), wobble()];
    let wall = WallShape {
        cx: f64::from(FIELD) + rx * REACH,
        cy: f64::from(main) + 0.5,
        rx,
        ry,
        n: rng.random_range(2.3..4.0),
        wobble,
    };
    let cells = (width * height) as usize;
    let t = Town {
        name,
        culture,
        land,
        seed,
        site: Site::new(width, height, Tile::Ground, Tile::CityWall, true),
        owner: vec![NO_OWNER; cells],
        quarter_of: vec![NO_QUARTER; cells],
        quarters: Vec::new(),
        buildings: Vec::new(),
        shops: Vec::new(),
        ship: Pos::new(7, main - 1),
        start: Pos::new(13, main),
        square: Pos::new(0, main),
        gates: Vec::new(),
    };
    let mut p = Planner {
        t,
        rng,
        lay: lay(land.terrain),
        wall,
        size,
        main,
        square: Rect::new(0, 0, 0, 0),
        points: Vec::new(),
        blocks: Vec::new(),
        parks: Vec::new(),
        stalls: Vec::new(),
        grounds: Vec::new(),
    };
    p.walls();
    p.field();
    let sides = p.gates();
    p.market_square();
    p.avenues(&sides);
    p.quarters();
    p.landmarks();
    let inside = p.inside_bounds();
    p.split(inside, 0);
    for b in 0..p.t.buildings.len() {
        let front = p.t.buildings[b].front();
        p.link(front);
    }
    p.parks_and_plazas();
    let blocks: Vec<Rect> = p.blocks.iter().filter(|(_, used)| !used).map(|&(r, _)| r).collect();
    for r in blocks {
        p.pack(r);
    }
    p.uses();
    p.shops();
    p.guardhouses();
    if p.lay.sea {
        p.sea();
    }
    p.dress();
    p.people();
    p.t
}

impl Planner<'_> {
    fn tile(&self, p: Pos) -> Tile {
        self.t.site.tile(p)
    }

    fn set(&mut self, p: Pos, tile: Tile) {
        if self.t.site.contains(p) {
            self.t.site.set(p, tile);
        }
    }

    /// Paves over open ground: streets go round what's already built, and
    /// round landmarks' grounds.
    fn carve(&mut self, r: Rect) {
        for p in r.cells() {
            if self.tile(p) == Tile::Garden && !self.reserved(p) {
                self.set(p, Tile::Street);
            }
        }
    }

    fn walls(&mut self) {
        let site = &self.t.site;
        let all: Vec<Pos> = site.positions().collect();
        for &p in &all {
            if self.wall.inside(p) {
                let edge = p.neighbours().any(|n| !self.wall.inside(n));
                self.set(p, if edge { Tile::CityWall } else { Tile::Garden });
            }
        }
        // A road inside the wall, all the way round.
        let ring: Vec<Pos> = all
            .into_iter()
            .filter(|&p| {
                self.tile(p) == Tile::Garden
                    && p.neighbours().any(|n| self.tile(n) == Tile::CityWall)
            })
            .collect();
        for p in ring {
            self.set(p, Tile::Street);
        }
    }

    /// The landing field, with your ship on it.
    fn field(&mut self) {
        let main = self.main;
        self.t.site.fill(Rect::new(3, main - 5, PAD_RIGHT, main + 5), Tile::Pad);
        let (sw, sh) = SHIP_SIZE;
        let ship = self.t.ship;
        self.t.site.fill(Rect::new(ship.x, ship.y, ship.x + sw - 1, ship.y + sh - 1), Tile::Ship);
    }

    /// Cuts a gate through the wall along each lane, paving the way to it
    /// from outside, and returns the cell just inside the middle lane.
    fn gate(&mut self, lanes: &[Pos], (dx, dy): (i32, i32)) -> Pos {
        let mut inner = Vec::new();
        for &start in lanes {
            let mut p = start;
            while self.t.site.contains(p) && self.tile(p) != Tile::CityWall {
                if self.tile(p) == Tile::Ground {
                    self.set(p, Tile::Street);
                }
                p = p.offset(dx, dy);
            }
            while self.tile(p) == Tile::CityWall && self.t.site.contains(p) {
                self.set(p, Tile::Gate);
                p = p.offset(dx, dy);
            }
            inner.push(p);
        }
        inner[lanes.len() / 2]
    }

    /// The west gate, and one to three others. Returns which side each
    /// gate is on, in the order of `Town::gates`.
    fn gates(&mut self) -> Vec<Side> {
        let main = self.main;
        let west: Vec<Pos> = (main - 1..=main + 1).map(|y| Pos::new(PAD_RIGHT + 1, y)).collect();
        let inner = self.gate(&west, (1, 0));
        self.t.gates.push(inner);
        let mut sides = vec![Side::North, Side::South, Side::East];
        sides.shuffle(self.rng);
        let extra = 1 + self.rng.random_range(0..=(self.size * 2.0).round() as usize);
        sides.truncate(extra);
        let (w, h) = (self.t.width(), self.t.height());
        for &side in &sides {
            let inner = match side {
                Side::North | Side::South => {
                    let x = (self.wall.cx + self.wall.rx * self.rng.random_range(-0.45..0.45))
                        .round() as i32;
                    let (y, dy) = if side == Side::North { (0, 1) } else { (h - 1, -1) };
                    let lanes: Vec<Pos> = (x - 2..=x + 1).map(|x| Pos::new(x, y)).collect();
                    self.gate(&lanes, (0, dy))
                }
                _ => {
                    let y = (self.wall.cy + self.wall.ry * self.rng.random_range(-0.35..0.35))
                        .round() as i32;
                    let lanes: Vec<Pos> = (y - 1..=y + 1).map(|y| Pos::new(w - 1, y)).collect();
                    self.gate(&lanes, (-1, 0))
                }
            };
            self.t.gates.push(inner);
        }
        let mut all = vec![Side::West];
        all.extend(sides);
        all
    }

    fn market_square(&mut self) {
        let size = self.size;
        let w = lerp(20.0, 36.0, size) as i32 + self.rng.random_range(0..5);
        let h = lerp(7.0, 12.0, size) as i32 + self.rng.random_range(0..2);
        let x = (self.wall.cx + self.wall.rx * self.rng.random_range(-0.12..0.12)).round() as i32;
        let top = self.main - h / 2 + self.rng.random_range(-1..=1);
        let r = Rect::new(x - w / 2, top, x - w / 2 + w - 1, top + h - 1);
        for p in r.cells() {
            if matches!(self.tile(p), Tile::Garden | Tile::Street) {
                self.set(p, Tile::Square);
            }
        }
        self.square = r;
        self.t.square = Pos::new(x, self.main);
        for dx in -1..=1 {
            self.set(Pos::new(x + dx, self.main), Tile::Centrepiece);
        }
    }

    /// Paves an L from `a` to `b`, `cols` wide where it runs north–south
    /// and `rows` tall where it runs east–west.
    fn road(&mut self, a: Pos, b: Pos, (cols, rows): (i32, i32), down_first: bool) {
        let vertical = |x: i32, y0: i32, y1: i32| {
            Rect::new(x - cols / 2, y0.min(y1), x - cols / 2 + cols - 1, y0.max(y1))
        };
        let across = |y: i32, x0: i32, x1: i32| {
            Rect::new(x0.min(x1), y - rows / 2, x0.max(x1), y - rows / 2 + rows - 1)
        };
        if down_first {
            self.carve(vertical(a.x, a.y, b.y));
            self.carve(across(b.y, a.x, b.x));
        } else {
            self.carve(across(a.y, a.x, b.x));
            self.carve(vertical(b.x, a.y, b.y));
        }
    }

    fn avenues(&mut self, sides: &[Side]) {
        let sq = self.square;
        for (i, &side) in sides.iter().enumerate() {
            let g = self.t.gates[i];
            match side {
                Side::West => self.road(g, Pos::new(sq.left + 1, self.main), (4, 3), false),
                Side::North | Side::South => {
                    let y = if side == Side::North { sq.top + 1 } else { sq.bottom - 1 };
                    let to = Pos::new(g.x.clamp(sq.left + 2, sq.right - 2), y);
                    self.road(g, to, (4, 3), true);
                }
                Side::East => {
                    let to = Pos::new(sq.right - 2, g.y.clamp(sq.top + 1, sq.bottom - 1));
                    self.road(g, to, (4, 3), false);
                }
            }
        }
    }

    fn inside_bounds(&self) -> Rect {
        let inside: Vec<Pos> =
            self.t.site.positions().filter(|&p| self.tile(p) != Tile::Ground).collect();
        let xs = inside.iter().filter(|p| p.x > PAD_RIGHT + 1).map(|p| p.x);
        let ys = inside.iter().map(|p| p.y);
        Rect::new(
            xs.clone().min().unwrap_or(0),
            ys.clone().min().unwrap_or(0),
            xs.max().unwrap_or(0),
            ys.max().unwrap_or(0),
        )
    }

    fn nearest_quarter(&self, p: Pos) -> usize {
        (0..self.points.len()).min_by_key(|&i| distance2(self.points[i].1, p)).unwrap_or(0)
    }

    fn quarter_kind(&self, p: Pos) -> QuarterKind {
        self.points[self.nearest_quarter(p)].0
    }

    fn quarters(&mut self) {
        use QuarterKind::*;
        let count = 4 + (self.size * 4.0).round() as usize;
        let gate = self.t.gates[0];
        self.points.push((Market, self.t.square));
        self.points.push((Gate, gate.offset((self.wall.rx * 0.3) as i32, 0)));
        let mut rest = vec![Homes, Works, Poor, Gardens];
        rest.shuffle(self.rng);
        let kinds = [Grand, Holy].into_iter().chain(rest).chain([Homes, Poor, Homes, Works]);
        let inside: Vec<Pos> =
            self.t.site.positions().filter(|&p| self.tile(p) == Tile::Garden).collect();
        for kind in kinds.take(count - 2) {
            // Of a dozen places, the one furthest from the others.
            let tries: Vec<Pos> =
                (0..12).filter_map(|_| inside.choose(self.rng).copied()).collect();
            let far = tries.into_iter().max_by_key(|&p| {
                self.points.iter().map(|&(_, q)| distance2(p, q)).min().unwrap_or(0)
            });
            if let Some(p) = far {
                self.points.push((kind, p));
            }
        }
        let mut sums = vec![(0i64, 0i64, 0i64); self.points.len()];
        for p in self.t.site.positions().collect::<Vec<_>>() {
            if self.tile(p) != Tile::Ground && p.x > PAD_RIGHT {
                let q = self.nearest_quarter(p);
                let i = self.t.site.index(p);
                self.t.quarter_of[i] = q as u8;
                sums[q] = (sums[q].0 + i64::from(p.x), sums[q].1 + i64::from(p.y), sums[q].2 + 1);
            }
        }
        let culture = self.t.culture;
        for (i, &(kind, at)) in self.points.iter().enumerate() {
            let (sx, sy, n) = sums[i];
            let centre = if n > 0 { Pos::new((sx / n) as i32, (sy / n) as i32) } else { at };
            let mut name = words::quarter_name(culture, kind, self.rng);
            for _ in 0..10 {
                if !self.t.quarters.iter().any(|q| q.name == name) {
                    break;
                }
                name = words::quarter_name(culture, kind, self.rng);
            }
            self.t.quarters.push(Quarter { kind, name, centre });
        }
    }

    /// Splits `r` with a street, and its halves, and theirs, until each is
    /// small enough to be a block in its quarter.
    fn split(&mut self, r: Rect, depth: u32) {
        let kind = self.quarter_kind(r.centre());
        let (max_w, max_h) = block_size(kind);
        let (w, h) = (r.width(), r.height());
        let (wide, tall) = (w > max_w, h > max_h);
        let nearly = w <= max_w * 3 / 2 && h <= max_h * 3 / 2;
        if !wide && !tall || w < 8 || h < 5 || depth > 2 && nearly && self.rng.random_bool(0.15) {
            self.blocks.push((r, false));
            return;
        }
        let upright = if wide && tall {
            f64::from(w) > 2.0 * f64::from(h) * self.rng.random_range(0.8..1.25)
        } else {
            wide
        };
        let (cols, rows) = street_width(kind, depth, self.rng);
        if upright {
            let lo = r.left + w * 3 / 10;
            let hi = (r.right - w * 3 / 10 - cols + 1).max(lo);
            let x = self.rng.random_range(lo..=hi);
            self.carve(Rect::new(x, r.top, x + cols - 1, r.bottom));
            self.split(Rect::new(r.left, r.top, x - 1, r.bottom), depth + 1);
            self.split(Rect::new(x + cols, r.top, r.right, r.bottom), depth + 1);
        } else {
            let lo = r.top + h * 3 / 10;
            let hi = (r.bottom - h * 3 / 10 - rows + 1).max(lo);
            let y = self.rng.random_range(lo..=hi);
            self.carve(Rect::new(r.left, y, r.right, y + rows - 1));
            self.split(Rect::new(r.left, r.top, r.right, y - 1), depth + 1);
            self.split(Rect::new(r.left, y + rows, r.right, r.bottom), depth + 1);
        }
    }

    /// Whether every cell of `r` is open ground: nothing built, no street
    /// through it, all inside the wall, and not set aside for a landmark.
    fn whole(&self, r: Rect) -> bool {
        r.cells().all(|p| self.tile(p) == Tile::Garden && !self.reserved(p))
    }

    /// Whether `p` is in the grounds of a landmark.
    fn reserved(&self, p: Pos) -> bool {
        self.grounds.iter().any(|r| r.contains(p))
    }

    fn add_building(&mut self, kind: Kind, foot: Rect, door: Pos, facing: Side) -> usize {
        let b = self.t.buildings.len();
        for p in foot.cells() {
            self.set(p, Tile::Roof);
            let i = self.t.site.index(p);
            self.t.owner[i] = b as u16;
        }
        self.set(door, Tile::Door { open: true });
        let name = String::new();
        self.t.buildings.push(Building {
            kind,
            left: foot.left,
            top: foot.top,
            right: foot.right,
            bottom: foot.bottom,
            door,
            facing,
            barred: false,
            shop: None,
            name,
        });
        b
    }

    /// Paves from `from` in direction `step` until it meets a street.
    fn pave_to_street(&mut self, from: Pos, (dx, dy): (i32, i32)) {
        let mut p = from;
        for _ in 0..12 {
            if self.tile(p) != Tile::Garden {
                return;
            }
            self.set(p, Tile::Square);
            p = p.offset(dx, dy);
        }
    }

    /// Sets aside grounds for a great building before the streets are cut,
    /// as near the middle of its quarter as they'll fit, with a street all
    /// round them and a paved way from the door to it. Shrinks the building
    /// if it won't fit anywhere.
    fn landmark(&mut self, kind: Kind, home: QuarterKind, (mut w, mut h): (i32, i32)) {
        let target =
            self.points.iter().find(|(k, _)| *k == home).map_or(self.t.square, |&(_, p)| p);
        let mut open: Vec<Pos> =
            self.t.site.positions().filter(|&p| self.tile(p) == Tile::Garden).collect();
        open.sort_by_key(|&p| distance2(p, target));
        let around = |r: Rect| Rect::new(r.left - 2, r.top - 1, r.right + 2, r.bottom + 1);
        loop {
            let (gw, gh) = (w + 6, h + 2);
            let at = |c: Pos| {
                let (left, top) = (c.x - gw / 2, c.y - gh / 2);
                Rect::new(left, top, left + gw - 1, top + gh - 1)
            };
            let found = open.iter().map(|&c| at(c)).find(|&grounds| {
                self.whole(grounds)
                    && around(grounds).cells().all(|p| {
                        grounds.contains(p)
                            || !self.reserved(p)
                                && matches!(
                                    self.tile(p),
                                    Tile::Garden | Tile::Street | Tile::Square
                                )
                    })
            });
            if let Some(grounds) = found {
                self.grounds.push(grounds);
                self.carve(around(grounds));
                let (left, top) = (grounds.left + 3, grounds.top + 1);
                let foot = Rect::new(left, top, left + w - 1, top + h - 1);
                // The door faces the square, or at least its side of the city.
                let facing = if grounds.centre().y < self.main { Side::South } else { Side::North };
                let x = foot.centre().x;
                let door = Pos::new(x, if facing == Side::South { foot.bottom } else { foot.top });
                let step = facing.step();
                for dx in -1..=1 {
                    self.pave_to_street(door.offset(dx + step.0, step.1), step);
                }
                let front = door.offset(0, step.1);
                for dx in [-3, 3] {
                    if self.tile(front.offset(dx, 0)) == Tile::Garden {
                        self.set(front.offset(dx, 0), Tile::Statue);
                    }
                }
                self.add_building(kind, foot, door, facing);
                return;
            }
            if w <= 8 {
                return;
            }
            w -= 2;
            h = (h - 1).max(3);
        }
    }

    fn landmarks(&mut self) {
        let size = self.size;
        let palace = (lerp(14.0, 22.0, size) as i32, lerp(5.0, 8.0, size) as i32);
        let temple = (lerp(10.0, 16.0, size) as i32, lerp(4.0, 6.0, size) as i32);
        self.landmark(Kind::Palace, QuarterKind::Grand, palace);
        self.landmark(Kind::Temple, QuarterKind::Holy, temple);
    }

    /// The paved cells you can walk to from `from` without leaving the
    /// streets.
    fn paved_from(&self, from: Pos) -> Vec<bool> {
        let site = &self.t.site;
        let paved =
            |p: Pos| site.contains(p) && self.tile(p).outdoors() && self.tile(p) != Tile::Garden;
        let mut seen = vec![false; (site.width * site.height) as usize];
        if !paved(from) {
            return seen;
        }
        let mut queue = std::collections::VecDeque::from([from]);
        seen[site.index(from)] = true;
        while let Some(p) = queue.pop_front() {
            for n in p.neighbours() {
                if paved(n) && !seen[site.index(n)] {
                    seen[site.index(n)] = true;
                    queue.push_back(n);
                }
            }
        }
        seen
    }

    /// Makes sure you can walk by street from the west gate to `to`, paving
    /// a road between the nearest two streets if not.
    fn link(&mut self, to: Pos) {
        let reached = self.paved_from(self.t.gates[0]);
        let site = &self.t.site;
        if reached[site.index(to)] {
            return;
        }
        let cut_off = self.paved_from(to);
        let ours: Vec<Pos> = site.positions().filter(|&p| reached[site.index(p)]).collect();
        let theirs = site.positions().filter(|&p| cut_off[site.index(p)]);
        let pair = theirs
            .flat_map(|a| ours.iter().map(move |&b| (a, b)))
            .min_by_key(|&(a, b)| distance2(a, b));
        if let Some((a, b)) = pair {
            let down_first = self.rng.random_bool(0.5);
            self.road(a, b, (2, 1), down_first);
        }
    }

    fn parks_and_plazas(&mut self) {
        for i in 0..self.blocks.len() {
            let (r, used) = self.blocks[i];
            if used || r.width() < 6 || r.height() < 3 || r.cells().any(|p| self.reserved(p)) {
                continue;
            }
            let q = self.quarter_kind(r.centre());
            let park = match q {
                QuarterKind::Gardens => 0.55,
                QuarterKind::Market | QuarterKind::Gate => 0.0,
                _ => 0.03,
            };
            let plaza = match q {
                QuarterKind::Gardens | QuarterKind::Grand => 0.0,
                _ if r.area() > 200 => 0.0,
                _ => 0.03,
            };
            if self.rng.random_bool((park * self.lay.parks).min(0.95)) {
                self.blocks[i].1 = true;
                self.park(r);
            } else if self.rng.random_bool(plaza) {
                self.blocks[i].1 = true;
                self.plaza(r);
            }
        }
    }

    /// Puts something in the middle of a park or plaza, if the middle is
    /// open ground inside the walls.
    fn centrepiece(&mut self, at: Pos, tile: Tile) {
        if matches!(self.tile(at), Tile::Garden | Tile::Street | Tile::Square) {
            self.set(at, tile);
        }
    }

    /// Paths crossing, a pond if there's room, and trees later.
    fn park(&mut self, r: Rect) {
        self.parks.push(r);
        let c = r.centre();
        let path = |p: &mut Planner, cell: Pos| {
            if p.tile(cell) == Tile::Garden {
                p.set(cell, Tile::Street);
            }
        };
        for x in r.left..=r.right {
            path(self, Pos::new(x, c.y));
        }
        for y in r.top..=r.bottom {
            path(self, Pos::new(c.x, y));
            path(self, Pos::new(c.x + 1, y));
        }
        let size = self.lay.ponds;
        if size > 0.0 && r.width() >= 14 && r.height() >= 6 {
            // In one corner, between the paths.
            let qx =
                if self.rng.random_bool(0.5) { (r.left + c.x) / 2 } else { (c.x + r.right) / 2 };
            let qy =
                if self.rng.random_bool(0.5) { (r.top + c.y) / 2 } else { (c.y + r.bottom) / 2 };
            let (ax, ay) = (f64::from(r.width()) / 7.0 * size, f64::from(r.height()) / 5.0 * size);
            for p in r.cells() {
                let dx = f64::from(p.x - qx) / ax.max(1.0);
                let dy = f64::from(p.y - qy) / ay.max(0.8);
                if dx * dx + dy * dy <= 1.0 && self.tile(p) == Tile::Garden {
                    self.set(p, Tile::Water);
                }
            }
        }
        let centre = if self.rng.random_bool(0.5) { Tile::Statue } else { Tile::Well };
        self.centrepiece(c, centre);
    }

    /// A little square with a well or a statue in the middle.
    fn plaza(&mut self, r: Rect) {
        for p in r.cells() {
            if self.tile(p) == Tile::Garden {
                self.set(p, Tile::Square);
            }
        }
        let wells = matches!(self.t.culture, Culture::Qaari | Culture::Drift);
        let centre = if wells != self.rng.random_bool(0.25) { Tile::Well } else { Tile::Statue };
        self.centrepiece(r.centre(), centre);
    }

    /// Packs buildings along the streets round a block, the long sides
    /// first, then the ends.
    fn pack(&mut self, r: Rect) {
        let lots = lots(self.quarter_kind(r.centre()));
        let mut long = [Side::North, Side::South];
        let mut ends = [Side::West, Side::East];
        long.shuffle(self.rng);
        ends.shuffle(self.rng);
        for side in long.into_iter().chain(ends) {
            self.pack_side(r, side, &lots);
        }
    }

    fn pack_side(&mut self, r: Rect, side: Side, lots: &Lots) {
        let upright = matches!(side, Side::North | Side::South);
        let (len, cap) = if upright {
            (r.width(), (r.height() + 1) / 2)
        } else {
            (r.height(), (r.width() + 1) / 2)
        };
        let (along, deep) = if upright { (lots.wide, lots.deep) } else { (lots.tall, lots.long) };
        let min_deep = if upright { 2 } else { 3 };
        let mut u = 0;
        while u < len {
            let want = self.rng.random_range(along.0..=along.1);
            let depth = self.rng.random_range(deep.0..=deep.1).min(cap);
            if depth < min_deep {
                return;
            }
            let mut placed = None;
            for n in (along.0.min(want)..=want).rev() {
                let foot = match side {
                    Side::North => {
                        Rect::new(r.left + u, r.top, r.left + u + n - 1, r.top + depth - 1)
                    }
                    Side::South => {
                        Rect::new(r.left + u, r.bottom - depth + 1, r.left + u + n - 1, r.bottom)
                    }
                    Side::West => {
                        Rect::new(r.left, r.top + u, r.left + depth - 1, r.top + u + n - 1)
                    }
                    Side::East => {
                        Rect::new(r.right - depth + 1, r.top + u, r.right, r.top + u + n - 1)
                    }
                };
                let inside = foot.right <= r.right && foot.bottom <= r.bottom;
                if inside
                    && self.whole(foot)
                    && let Some(door) = self.door_for(foot, side)
                {
                    self.add_building(Kind::House, foot, door, side);
                    placed = Some(n);
                    break;
                }
            }
            match placed {
                Some(n) => {
                    let gap = if self.rng.random_bool(lots.gap) {
                        if self.rng.random_bool(0.25) { 2 } else { 1 }
                    } else {
                        0
                    };
                    u += n + gap;
                }
                None => u += 1,
            }
        }
    }

    /// A door on the `side` edge of a footprint, away from the corners,
    /// that opens onto a street.
    fn door_for(&mut self, foot: Rect, side: Side) -> Option<Pos> {
        let (dx, dy) = side.step();
        let doors: Vec<Pos> = match side {
            Side::North | Side::South => {
                let y = if side == Side::North { foot.top } else { foot.bottom };
                (foot.left + 1..foot.right).map(|x| Pos::new(x, y)).collect()
            }
            Side::West | Side::East => {
                let x = if side == Side::West { foot.left } else { foot.right };
                (foot.top + 1..foot.bottom).map(|y| Pos::new(x, y)).collect()
            }
        };
        let good: Vec<Pos> =
            doors.into_iter().filter(|d| self.tile(d.offset(dx, dy)).paved()).collect();
        good.choose(self.rng).copied()
    }

    /// Decides what each ordinary building is, by its quarter and size, and
    /// names it.
    fn uses(&mut self) {
        let culture = self.t.culture;
        for b in 0..self.t.buildings.len() {
            let building = &self.t.buildings[b];
            let (w, h) = (building.width(), building.height());
            let mut kind = building.kind;
            if kind == Kind::House {
                let q = self.quarter_kind(building.centre());
                let options = uses(q, culture);
                kind = options
                    .choose_weighted(self.rng, |(_, weight)| *weight)
                    .map_or(Kind::House, |(k, _)| *k);
                if !fits(kind, w, h) {
                    kind = Kind::House;
                }
            }
            let barred = self.rng.random_bool(barred_chance(kind));
            let name = words::building_name(kind, culture, self.rng);
            let building = &mut self.t.buildings[b];
            building.kind = kind;
            building.barred = barred;
            building.name = name;
            let door = building.door;
            self.set(door, Tile::Door { open: !barred });
        }
    }

    fn make(&mut self, b: usize, kind: Kind) {
        let culture = self.t.culture;
        let name = words::building_name(kind, culture, self.rng);
        let building = &mut self.t.buildings[b];
        building.kind = kind;
        building.barred = false;
        building.name = name;
        let door = building.door;
        self.set(door, Tile::Door { open: true });
    }

    /// Picks one of the ordinary buildings nearest to `near`, and wide
    /// enough for a sign `sign` long.
    /// An ordinary building near `near` with room for the sign over its
    /// door, and not just down the street from another shop of the same
    /// kind.
    fn site_near(&mut self, near: Pos, kind: ShopKind) -> Option<usize> {
        let need = kind.sign().len() as i32 + 2;
        let rivals: Vec<Pos> = self
            .t
            .shops
            .iter()
            .filter(|s| s.kind == kind)
            .map(|s| self.t.buildings[s.building].door)
            .collect();
        let mut options: Vec<usize> = (0..self.t.buildings.len())
            .filter(|&b| {
                let building = &self.t.buildings[b];
                let ordinary = matches!(
                    building.kind,
                    Kind::House | Kind::Workshop | Kind::Warehouse | Kind::Tenement | Kind::Shrine
                );
                ordinary
                    && building.width() >= need
                    && building.height() >= 3
                    && rivals.iter().all(|&r| distance2(r, building.door) > 24 * 24)
            })
            .collect();
        options.sort_by_key(|&b| distance2(self.t.buildings[b].door, near));
        options.truncate(4);
        options.choose(self.rng).copied()
    }

    fn shops(&mut self) {
        let culture = self.t.culture;
        let anchor = |p: &Planner, kinds: &[QuarterKind]| {
            let quarters: Vec<&Quarter> =
                p.t.quarters.iter().filter(|q| kinds.contains(&q.kind)).collect();
            quarters.first().map(|q| q.centre)
        };
        let gate = self.t.gates[0].offset(8, 0);
        let square = self.t.square;
        let temple = self.t.buildings.iter().find(|b| b.kind == Kind::Temple).map(|b| b.front());
        let scholar = anchor(self, &[QuarterKind::Holy]).or(temple).unwrap_or(square);
        let homes = anchor(self, &[QuarterKind::Homes, QuarterKind::Market]).unwrap_or(square);
        let works = anchor(self, &[QuarterKind::Works, QuarterKind::Poor]).unwrap_or(gate);
        let mut wanted = vec![
            (ShopKind::Broker, gate),
            (ShopKind::Shipyard, gate),
            (ShopKind::Tavern, square),
            (ShopKind::Doctor, homes),
            (ShopKind::Scholar, scholar),
            (ShopKind::Armoury, works),
        ];
        let mut quiet: Vec<Pos> = self
            .t
            .quarters
            .iter()
            .filter(|q| {
                matches!(q.kind, QuarterKind::Poor | QuarterKind::Homes | QuarterKind::Works)
            })
            .map(|q| q.centre)
            .collect();
        // More taverns in bigger cities, each in a different quarter while
        // there are quarters to go round.
        quiet.shuffle(self.rng);
        let extra = (self.size * 3.0).round() as usize;
        wanted.extend(quiet.iter().cycle().take(extra).map(|&at| (ShopKind::Tavern, at)));
        for (kind, near) in wanted {
            let Some(b) = self.site_near(near, kind) else { continue };
            let mut name = words::shop_name(kind, culture, self.rng);
            for _ in 0..10 {
                if !self.t.shops.iter().any(|s| s.name == name) {
                    break;
                }
                name = words::shop_name(kind, culture, self.rng);
            }
            let shop = self.t.shops.len();
            self.t.shops.push(Shop {
                kind,
                name: name.clone(),
                keeper: culture.person(self.rng),
                building: b,
            });
            self.make(b, Kind::Shop(kind));
            self.t.buildings[b].shop = Some(shop);
            self.t.buildings[b].name = name;
        }
    }

    /// Each gate has a guardhouse just inside it.
    fn guardhouses(&mut self) {
        for g in self.t.gates.clone() {
            let near = (0..self.t.buildings.len())
                .filter(|&b| {
                    let kind = self.t.buildings[b].kind;
                    !matches!(kind, Kind::Shop(_) | Kind::Palace | Kind::Temple | Kind::Guardhouse)
                })
                .min_by_key(|&b| distance2(self.t.buildings[b].door, g));
            if let Some(b) = near.filter(|&b| distance2(self.t.buildings[b].door, g) < 40 * 40) {
                self.make(b, Kind::Guardhouse);
            }
        }
    }

    /// Floods the ground outside the walls, but for a shore round them and
    /// the landing field, and the road between. The roads to the other
    /// gates run on out to sea.
    fn sea(&mut self) {
        let site = &self.t.site;
        let (main, cx) = (self.main, self.wall.cx);
        let shore = |p: Pos| {
            let t = site.tile(p);
            let west_road = t == Tile::Street && (p.y - main).abs() <= 1 && f64::from(p.x) < cx;
            !matches!(t, Tile::Ground | Tile::Street) || west_road
        };
        // How far each bit of ground is from the shore, a step at a time.
        let mut far = vec![i32::MAX; site.tiles.len()];
        let mut queue = std::collections::VecDeque::new();
        for p in site.positions() {
            if shore(p) {
                far[site.index(p)] = 0;
                queue.push_back(p);
            }
        }
        while let Some(p) = queue.pop_front() {
            let d = far[site.index(p)];
            for n in p.neighbours() {
                if site.contains(n) && site.tile(n) == Tile::Ground && far[site.index(n)] > d + 1 {
                    far[site.index(n)] = d + 1;
                    queue.push_back(n);
                }
            }
        }
        // A beach two or three wide, wider and narrower along the coast.
        let (a, b) = (self.rng.random_range(0.0..6.3), self.rng.random_range(0.0..6.3));
        let flood: Vec<Pos> = site
            .positions()
            .filter(|&p| {
                let (x, y) = (f64::from(p.x), f64::from(p.y));
                let beach = 2.2 + 1.3 * (x * 0.23 + a).sin() * (y * 0.41 + b).sin();
                site.tile(p) == Tile::Ground && f64::from(far[site.index(p)]) > beach
            })
            .collect();
        for p in flood {
            self.set(p, Tile::Sea);
        }
    }

    /// Trees, stalls and lamps.
    fn dress(&mut self) {
        let all: Vec<Pos> = self.t.site.positions().collect();
        let main = self.main;
        // The Cant and the Drift leave pipes and scrap about; everyone plants.
        let clutter = matches!(self.t.culture, Culture::Cant | Culture::Drift);
        for &p in &all {
            let tile = self.tile(p);
            let roadside =
                p.neighbours().any(|n| self.tile(n).paved() || self.tile(n) == Tile::Pad);
            if tile == Tile::Ground && !roadside && (p.y - main).abs() > 1 {
                if self.rng.random_bool(self.lay.wild) {
                    self.set(p, Tile::Wild);
                }
            } else if tile == Tile::Garden && !roadside {
                let park = self.parks.iter().any(|r| r.contains(p));
                let grounds = p.neighbours().any(|n| {
                    self.t.building_at(n).is_some_and(|b| {
                        matches!(self.t.buildings[b].kind, Kind::Palace | Kind::Temple)
                    })
                });
                let chance = if park {
                    0.16
                } else if grounds {
                    0.3
                } else {
                    0.07
                };
                if self.rng.random_bool((chance * self.lay.trees).min(0.6)) {
                    let planted = !clutter || park || grounds || self.rng.random_bool(0.4);
                    self.set(p, if planted { Tile::Tree } else { Tile::Decor });
                }
            }
        }
        // Stalls along the top and bottom of the square, facing in, keeping
        // clear of the streets that come into it.
        let sq = self.square;
        for (y, front) in [(sq.top + 1, 1), (sq.bottom - 1, -1)] {
            let edge = if front == 1 { sq.top - 1 } else { sq.bottom + 1 };
            let mut x = sq.left + 2;
            while x + 2 <= sq.right - 2 {
                let clear = (x - 1..=x + 3).all(|x| !self.tile(Pos::new(x, edge)).paved())
                    && (x..=x + 2).all(|x| self.tile(Pos::new(x, y)) == Tile::Square)
                    && (y - main).abs() > 1;
                if clear && self.rng.random_bool(0.7) {
                    for dx in 0..3 {
                        self.set(Pos::new(x + dx, y), Tile::Stall);
                    }
                    self.stalls.push(Pos::new(x + 1, y + front));
                    x += 6;
                } else {
                    x += 2;
                }
            }
        }
        for p in [
            Pos::new(sq.left, sq.top),
            Pos::new(sq.right, sq.top),
            Pos::new(sq.left, sq.bottom),
            Pos::new(sq.right, sq.bottom),
        ] {
            let doorstep = p.neighbours().any(|n| matches!(self.tile(n), Tile::Door { .. }));
            if self.tile(p) == Tile::Square && !doorstep {
                self.set(p, Tile::Lamp);
            }
        }
    }

    fn person(&mut self, pos: Pos, role: Role, stays: bool) {
        let culture = self.t.culture;
        let says = *words::lines(role, culture).choose(self.rng).unwrap_or(&"...");
        self.t.site.people.push(Person { pos, role, name: None, says, stays });
    }

    fn people(&mut self) {
        for at in self.stalls.clone() {
            if self.t.site.free(at) {
                self.person(at, Role::Stallholder, true);
            }
        }
        // Guards just inside each gate, against the wall.
        for g in self.t.gates.clone() {
            let mut spots: Vec<Pos> = Rect::new(g.x - 3, g.y - 3, g.x + 3, g.y + 3)
                .cells()
                .filter(|&p| {
                    self.tile(p).outdoors()
                        && self.tile(p) != Tile::Gate
                        && self.t.site.free(p)
                        && p.neighbours().any(|n| self.tile(n) == Tile::CityWall)
                        && p.neighbours().all(|n| self.tile(n) != Tile::Gate)
                })
                .collect();
            spots.shuffle(self.rng);
            for p in spots.into_iter().take(2) {
                self.person(p, Role::Guard, true);
            }
        }
        let streets: Vec<Pos> = self.t.site.positions().filter(|&p| self.tile(p).paved()).collect();
        let count = (streets.len() / 55).clamp(16, 180);
        let crowd = (self.square.area() / 30) as usize;
        let square: Vec<Pos> =
            streets.iter().copied().filter(|&p| self.tile(p) == Tile::Square).collect();
        let mut placed = 0;
        let mut tries = 0;
        while placed < count + crowd && tries < 20 * (count + crowd) {
            tries += 1;
            let pool = if placed < crowd { &square } else { &streets };
            let Some(&p) = pool.choose(self.rng) else { break };
            if !self.t.site.free(p) {
                continue;
            }
            let q = self.quarter_kind(p);
            let roll = self.rng.random_range(0.0..1.0);
            let role = match q {
                QuarterKind::Homes | QuarterKind::Poor if roll < 0.2 => Role::Child,
                QuarterKind::Works | QuarterKind::Gate if roll < 0.25 => Role::Porter,
                QuarterKind::Holy if roll < 0.3 => Role::Pilgrim,
                _ => Role::Passerby,
            };
            self.person(p, role, false);
            placed += 1;
        }
    }
}