orbit/js/galaxy/Galaxy.js

543 lines
23 KiB
JavaScript
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

import { config } from '../config/Config.js';
import { Rng } from '../utils/Rng.js';
import { NameGenerator } from '../utils/NameGenerator.js';
import { buildJumpNetwork } from './JumpNetwork.js';
import { assignPlanetFrames } from './PlanetFrames.js';
import { assignStationFrames } from './StationFrames.js';
import { generateSystemContent, rollSystemComposition, settlementDensity } from './SystemGenerator.js';
const TAU = Math.PI * 2;
const clamp = (v, lo, hi) => Math.min(hi, Math.max(lo, v));
/**
* The Galaxy — an immense, procedurally generated collection of star
* systems, fully determined by its seed.
*
* Two-level generation (the "grand scale" design):
*
* 1. GALAXY ROSTER — generated once, up front, when New Game is pressed:
* `systemCount` lightweight records ({ id, name, type, x, y, d, zone }).
* This is cheap: the 90-system default is a few ms and a few hundred KB.
* It fixes the shape of the galaxy, where every system sits, and
* what KIND each one is — for the entire galaxy, from the seed alone.
*
* 2. SYSTEM CONTENTS — planets, moons, belts, hazards… generated LAZILY,
* the first time the player arrives (`ensureContent(id)`), then
* cached. Because each system's draw stream is derived from
* (seed, 'system', id), a lazy generation is identical to an eager
* one — so this is a pure performance choice, never a correctness one.
* `generateAll()` exists for exactly that, if it's ever "just as easy".
*
* The SHAPE (data/galaxy.json):
* - a seeded WIDE (2:1) field of stars (layout.field.width × height,
* center at the world origin) placed by Bridson Poisson-disk
* sampling — an even, organic field: every pair of systems stays at
* least minSpacing·√(width·height/N) apart, no clumps, no voids, not
* a grid. The 2:1 aspect matches the map plate (js/ui/MapWindow.js at
* the 1280×720 design size), so the fully-zoomed-out galaxy fills
* the plate instead of letterboxing;
* - the player's HOME system sits in the star nearest the configured
* corner (startingSystem: policy "corner", corner NE/NW/SE/SW,
* screen orientation — SE = lower right); "center" / "random" still
* work; the HOME→FAR diagonal is the galaxy's progression axis:
* each record carries `d` (0 at the home corner, 1 at the opposite
* corner) and its `zone` (near/middle/far, distribution.zones);
* - types mix PER ZONE (distribution.zoneMix × the type's global
* distribution.weight — the old per-type radiusBand is gone: type
* flavor is regional now), and free-space settlement density thins
* home→far (settlements.gradient, keyed on `d`).
*
* Determinism contract:
* same seed ⇒ same roster (positions, types, names), same contents,
* in any order of generation. Dev/test tools rely on this.
*
* Extension points for later world rules (see docs/PROJECT_NOTES.md):
* - FACTIONS: assign each system a faction id (or null = wild space)
* at roster time — the record is the seam (reputation's `owner`
* resolution and the galaxy plate's `faction: null` are reserved).
* - COMBAT / TRADE: read difficulty and price levels off `record.d`
* and `record.zone` (the middle zone is where the zone borders cross
* — the planned contested space + transit trade hubs).
* - more layout knobs in data/galaxy.json `layout.field`.
*/
export class Galaxy {
constructor(seed, params, typeDefs) {
this.seed = seed;
this.params = params;
this.typeDefs = typeDefs;
this.records = [];
this.byId = new Map();
this.contentCache = new Map();
this.currentSystemId = null;
// The STARTING system — the player's home port. Set once at roster
// build and never moves: `currentSystemId` tracks where the player IS
// NOW (jumps + saves move it), but the home world always belongs to
// the starting system (SystemGenerator's isHome rule, GameScene's
// home/star split). Without this split, lazily generated content for
// a newly arrived system would compute isHome = true (currentSystemId
// had already moved there) and deal it a home world of its own.
this.homeSystemId = null;
this.planetFrames = new Map(); // id → [frame, ...] — the frame-diversity pass
this.homeWorldFrame = null; // the starting system's home world frame
this.stationFrames = new Map(); // id → frame — the station-variant spread pass
this.name = NameGenerator.galaxy(Rng.derive(seed, 'galaxy', 'name'));
}
/**
* Build a galaxy from a seed (trimmed; ' abc ' and 'abc' are the same
* galaxy). `overrides` shallow-merges over data/galaxy.json — used by
* dev tools (e.g. a 300-system galaxy for brute-force tests).
*/
static create(seed, overrides = {}) {
if (seed === undefined || seed === null || String(seed).trim().length === 0) {
throw new Error('Galaxy.create() needs a non-empty seed');
}
const params = { ...config.section('galaxy', {}), ...overrides };
const typeDefs = config.get('systems.types', {});
if (Object.keys(typeDefs).length === 0) {
throw new Error('No system types found — is data/systems.json listed in data/manifest.json?');
}
const count = Math.floor(params.systemCount ?? 200);
if (!(count >= 1)) {
throw new Error(`galaxy.systemCount must be a whole number >= 1 (got ${params.systemCount})`);
}
const galaxy = new Galaxy(String(seed).trim(), params, typeDefs);
galaxy._generate(count);
return galaxy;
}
// ------------------------------------------------------------------
// Roster generation (level 1)
// ------------------------------------------------------------------
_generate(count) {
const L = this.params.layout ?? {};
const F = L.field ?? {};
const W = Math.max(4, Math.floor(Number(F.width) || 32000));
const H = Math.max(4, Math.floor(Number(F.height) || 16000));
this.fieldW = W; // the field's extent (world px, center at origin)
this.fieldH = H;
const halfW = W / 2;
const halfH = H / 2;
const minSpacing = clamp(Number(F.minSpacing) || 0.8, 0.4, 1.2);
// The HOME CORNER (data/galaxy.json → startingSystem.corner; screen
// orientation — y down, so SE = lower right). Two things key off it:
// the starting-system policy (home = the star NEAREST this corner),
// and the difficulty diagonal (d = 0 here, d = 1 at the opposite
// corner — the galaxy's progression axis, whatever policy picks the
// starting system).
const start = this.params.startingSystem ?? {};
const corner = this._cornerPoint(start.corner ?? 'SE', { halfW, halfH });
const opp = { x: -corner.x, y: -corner.y };
const diag2 = (corner.x - opp.x) ** 2 + (corner.y - opp.y) ** 2; // W² + H²
const dOf = (x, y) => clamp(
((corner.x - x) * (corner.x - opp.x) + (corner.y - y) * (corner.y - opp.y)) / diag2,
0, 1,
);
// ZONES — slices of the home→far diagonal (distribution.zones), and
// the PER-ZONE type mix (distribution.zoneMix × each type's global
// distribution.weight). Regional flavor replaces the old per-type
// radiusBand: which KINDS of stars favor which region of the galaxy.
const zones = this._zones();
const zoneOf = (d) => (zones.find((z) => d >= z.d[0] && d < z.d[1]) ?? zones[zones.length - 1]).name;
const mix = this.params.distribution?.zoneMix ?? {};
const typeIds = Object.keys(this.typeDefs);
const weightsFor = (zone) => {
const m = mix[zone] ?? {};
const w = {};
for (const id of typeIds) {
const mul = m[id] === undefined ? 1 : Math.max(0, Number(m[id]) || 0);
w[id] = Math.max(0, this.typeDefs[id].distribution?.weight ?? 1) * mul;
}
return w;
};
const g = Rng.derive(this.seed, 'layout');
// EVEN PLACEMENT — a Bridson Poisson-disk (blue-noise) field: every
// pair of systems stays at least dmin apart (no clumps, no voids)
// while the field stays organic (not a grid). dmin is a fraction of
// the mean inter-star spacing √(width·height/N)
// (layout.field.minSpacing).
// Even spacing is what keeps the jump network's hop counts
// proportional to map distance — the property the trade economy
// leans on ("a hop is a hop").
const dmin = minSpacing * Math.sqrt((W * H) / Math.max(1, count));
const points = this._poissonDisk(count, { halfW, halfH }, dmin);
const records = this.records;
for (let i = 1; i <= count; i++) {
const id = `S${String(i).padStart(6, '0')}`;
const p = points[i - 1] ?? { x: g.range(-halfW, halfW), y: g.range(-halfH, halfH) };
const d = dOf(p.x, p.y);
const zone = zoneOf(d);
const type = g.weighted(weightsFor(zone), typeIds[0]);
// Name comes from a per-record fork so roster generation order can
// never leak into it. d (0 = home corner, 1 = far corner) and zone
// stay on the record: the settlement generator uses d (home→far
// density), and factions/trade/combat will read difficulty off both.
const name = NameGenerator.star(Rng.derive(this.seed, 'name', id));
const rec = { id, name, type, x: p.x, y: p.y, d, zone };
records.push(rec);
this.byId.set(id, rec);
}
// Starting system (the player's home port).
const policy = start.policy ?? 'corner';
const closestTo = (px, py) =>
records
.slice()
.sort((a, b) => (a.x - px) ** 2 + (a.y - py) ** 2 - ((b.x - px) ** 2 + (b.y - py) ** 2))[0]?.id ?? records[0]?.id;
this.currentSystemId =
policy === 'random'
? `S${String(g.int(1, count)).padStart(6, '0')}`
: policy === 'center'
? closestTo(0, 0)
: closestTo(corner.x, corner.y); // 'corner' (default)
// Frozen copy of the starting system — `currentSystemId` will track
// the player from here on (jumps, saves); the home rules must not.
this.homeSystemId = this.currentSystemId;
// Spatial hash for fast neighbor queries (jump ranges, proximity rules,
// the eventual star map).
const area = W * H;
this.cellSize = Math.max(8, Math.sqrt(area / count) * 1.4);
this.grid = new Map();
for (const rec of records) {
const key = `${Math.floor(rec.x / this.cellSize)},${Math.floor(rec.y / this.cellSize)}`;
let cell = this.grid.get(key);
if (!cell) {
cell = [];
this.grid.set(key, cell);
}
cell.push(rec);
}
// The BARREN set — the gate-only dead ends (objectCount → 0). The
// SAME roll the content generator uses (dedicated per-system forks —
// rollSystemComposition), so the network and the content always agree:
// JumpNetwork keeps every barren system a LEAF of the tree (one gate —
// in and out the same way), the maze's dead ends.
const typeDefs = this.typeDefs ?? {};
const barren = new Set();
for (const record of records) {
if (record.id === this.currentSystemId) continue; // home is exempt
const type = typeDefs[record.type] ?? {};
const density = settlementDensity({ params: this.params }, record);
const composition = rollSystemComposition(
this.seed, record, false, type.attributes?.settlements ?? {}, density, type.attributes ?? {},
);
if (composition.classes.length === 0) barren.add(record.id);
}
// The JUMP NETWORK (data/gates.json): which star each system's jump
// gates reach. A PURE SPANNING TREE of the nearest-star graph (no
// shortcuts — data/gates.json → shortcuts:false) — the galaxy reads as
// a MAZE: exactly one route between any two systems, no closed loops.
// Tree edges run BOTH ways, so from any system the player can reach
// any other and every jump has a RETURN gate (no trapped sets). Each
// system holds 1maxGates gates (its tree degree); a BARREN system is
// a dead-end LEAF — exactly one gate (in and out the same way).
// Deterministic: same roster ⇒ same network.
const pool = Math.max(1, Math.min(count - 1, (config.get('gates.neighborPool', 8) | 0)));
this.jumpNetwork = buildJumpNetwork({
records,
knn: (id) => this.neighborsOf(id, pool),
minGates: Math.max(0, config.get('gates.minGates', 1) | 0),
maxGates: Math.max(1, config.get('gates.maxGates', 3) | 0),
shortcuts: config.get('gates.shortcuts', true) === true,
barren,
rootId: this.currentSystemId,
});
// Defensive repairs that had to fire (0 on a healthy kNN graph).
this.jumpNetworkRepaired = this.jumpNetwork.repaired;
if (this.jumpNetworkRepaired > 0) {
console.warn(`[orbit] jump network: ${this.jumpNetworkRepaired} system(s) needed a repair attach`);
}
// FRAME DIVERSITY (js/galaxy/PlanetFrames.js): the galaxy-wide
// (class, frame) assignment — each planet's sheet frame avoids what
// the NEAREST stars already wear for that class, so the same face is
// spread across the galaxy instead of clustering in one region. Fixed
// roster order ⇒ visit-order independent; read back by the content
// generator (planet.frame / content.homeFrame) — the lazy === eager
// contract is preserved.
const pool8 = Math.max(1, Math.floor(this.params.neighbors ?? 8));
const { frames, homeFrame } = assignPlanetFrames({
seed: this.seed,
records,
homeId: this.currentSystemId,
params: this.params,
neighborsOf: (id) => this.neighborsOf(id, pool8),
});
this.planetFrames = frames; // Map id → [frame, ...] (ordinal order)
this.homeWorldFrame = homeFrame;
// STATION VARIANT SPREAD (js/galaxy/StationFrames.js): each system's
// deep-space station wears one of the spacestations.png variants
// (data/stations.json → variants) — the frame avoids what the
// NEAREST stars already wear, so the same station type is spread
// across the galaxy instead of clustering in one region. Fixed
// roster order ⇒ visit-order independent; read back by the content
// generator (settlement.stationFrame) — lazy === eager preserved.
const { frames: stationFrames } = assignStationFrames({
seed: this.seed,
records,
homeId: this.currentSystemId,
params: this.params,
neighborsOf: (id) => this.neighborsOf(id, pool8),
});
this.stationFrames = stationFrames; // Map id → frame (station-bearing systems)
}
/**
* The home→far zones (data/galaxy.json → distribution.zones),
* validated and sorted by `d`. A single fallback zone when the config
* is missing/malformed — the galaxy still generates.
*/
_zones() {
const raw = this.params.distribution?.zones;
const out = (Array.isArray(raw) ? raw : [])
.filter(
(z) =>
z &&
typeof z.name === 'string' &&
Array.isArray(z.d) &&
z.d.length === 2 &&
Number.isFinite(z.d[0]) &&
Number.isFinite(z.d[1]) &&
z.d[1] > z.d[0],
)
.map((z) => ({ name: z.name, d: [clamp(z.d[0], 0, 1), clamp(z.d[1], 0, 1)] }))
.sort((a, b) => a.d[0] - b.d[0]);
return out.length ? out : [{ name: 'all', d: [0, 1] }];
}
/** A corner of the field (screen orientation — y DOWN). */
_cornerPoint(name, { halfW, halfH }) {
const CORNERS = { NE: [1, -1], NW: [-1, -1], SE: [1, 1], SW: [-1, 1] };
const key = String(name ?? 'SE').toUpperCase();
const [sx, sy] = CORNERS[key] ?? CORNERS.SE;
return { x: sx * halfW, y: sy * halfH };
}
/**
* Even star placement: exactly `n` points in the field
* [halfW, halfW] × [halfH, halfH], every pair at least `d0` apart
* (Bridson / Poisson disk). If the field can't hold `n` points at
* `d0` (dense config), retry a few times with a relaxed spacing; as a
* last resort pad with random points — a working galaxy beats a
* perfect one. Deterministic: each attempt draws from its own seeded
* fork (seed, 'layout', 'poisson', attempt).
*/
_poissonDisk(n, { halfW, halfH }, d0) {
if (n <= 0) return [];
let d = Math.max(1, d0);
let pts = null;
for (let attempt = 0; attempt < 8; attempt++) {
const rng = Rng.derive(this.seed, 'layout', 'poisson', attempt);
pts = this._bridson(n, { halfW, halfH }, d, rng);
if (pts.length >= n) break;
d *= 0.88; // not enough room — loosen the spacing and retry
}
const rng = Rng.derive(this.seed, 'layout', 'poisson', 'pad');
while (pts.length < n) {
pts.push({ x: rng.range(-halfW, halfW), y: rng.range(-halfH, halfH) });
}
return pts.slice(0, n);
}
/**
* Bridson's algorithm: grow a Poisson-disk of points in the field,
* stopping once `n` points are placed (or the frontier is exhausted).
* Pure — deterministic for a given (n, halfW, halfH, d, rng stream).
*/
_bridson(n, { halfW, halfH }, d, rng) {
if (n <= 0) return [];
const cell = d / Math.SQRT2;
const grid = new Map(); // "cx,cy" → [point, …]
const pts = [];
const active = []; // indices into pts (Bridson's active list)
const inside = (p) =>
p.x >= -halfW && p.x <= halfW && p.y >= -halfH && p.y <= halfH;
const keyOf = (p) =>
`${Math.floor((p.x + halfW) / cell)},${Math.floor((p.y + halfH) / cell)}`;
const free = (p) => {
const cx = Math.floor((p.x + halfW) / cell);
const cy = Math.floor((p.y + halfH) / cell);
for (let ax = -2; ax <= 2; ax++) {
for (let ay = -2; ay <= 2; ay++) {
const bucket = grid.get(`${cx + ax},${cy + ay}`);
if (!bucket) continue;
for (const q of bucket) {
const dx = q.x - p.x;
const dy = q.y - p.y;
if (dx * dx + dy * dy < d * d) return false;
}
}
}
return true;
};
const place = (p) => {
pts.push(p);
active.push(pts.length - 1);
const k = keyOf(p);
const bucket = grid.get(k);
if (bucket) bucket.push(p);
else grid.set(k, [p]);
};
// Seed the frontier with one random interior point.
place({ x: rng.range(-halfW, halfW), y: rng.range(-halfH, halfH) });
while (active.length > 0 && pts.length < n) {
const i = rng.int(0, active.length - 1);
const p = pts[active[i]];
let placed = false;
for (let t = 0; t < 30 && !placed; t++) {
// Sample a candidate in the annulus [d, 2d) around p.
const r = d * (1 + rng.next());
const a = rng.next() * TAU;
const q = { x: p.x + r * Math.cos(a), y: p.y + r * Math.sin(a) };
if (!inside(q) || !free(q)) continue;
place(q);
placed = true;
}
if (!placed) active.splice(i, 1); // p can never yield a neighbor
}
return pts;
}
// ------------------------------------------------------------------
// Queries
// ------------------------------------------------------------------
/**
* The k nearest systems to a world-space point (k=1 by default).
* Ring-expands the spatial hash; exact as long as k systems exist.
*/
nearest(x, y, k = 1) {
const c = this.cellSize;
const cx = Math.floor(x / c);
const cy = Math.floor(y / c);
const best = [];
const consider = (rec) => {
const d2 = (rec.x - x) ** 2 + (rec.y - y) ** 2;
best.push({ d2, record: rec });
best.sort((a, b) => a.d2 - b.d2);
if (best.length > k) best.length = k;
};
const maxRing = Math.min(1024, Math.ceil(Math.hypot(this.fieldW ?? 32000, this.fieldH ?? 16000) / c) + 1);
for (let ring = 0; ring <= maxRing; ring++) {
for (let dx = -ring; dx <= ring; dx++) {
for (let dy = -ring; dy <= ring; dy++) {
if (Math.max(Math.abs(dx), Math.abs(dy)) !== ring) continue;
const cell = this.grid.get(`${cx + dx},${cy + dy}`);
if (cell) for (const rec of cell) consider(rec);
}
}
// Everything left unscanned is at least ring·c away; if the kth
// best is already closer, the answer is final.
if (best.length >= k) {
const bound = ring * c;
if (best[k - 1].d2 <= bound * bound) break;
}
}
return best.slice(0, k).map((e) => e.record);
}
/** The k nearest OTHER systems to a system (jump-range candidate list). */
neighborsOf(id, k = null) {
const rec = this.byId.get(id);
if (!rec) throw new Error(`Unknown system "${id}"`);
const need = k ?? Math.floor(this.params.neighbors ?? 8);
const out = [];
for (const cand of this.nearest(rec.x, rec.y, need + 1)) {
if (cand.id !== id) out.push(cand);
if (out.length >= need) break;
}
return out;
}
/**
* The other systems this system's jump gates jump to — the star
* RECORDS ({ id, name, x, y }), ordered with the "road home" (parent)
* edge first, then the local shortcuts. minGatesmaxGates entries for
* n > 1 (data/gates.json); empty for a one-system galaxy.
*/
jumpGatesFor(id) {
const rec = this.byId.get(id);
if (!rec) throw new Error(`Unknown system "${id}"`);
return (this.jumpNetwork.gates.get(id) ?? []).map((tid) => this.byId.get(tid)).filter(Boolean);
}
/** @returns {object} the player's current (starting) system record */
currentSystem() {
return this.byId.get(this.currentSystemId) ?? this.records[0];
}
/** True when the system is the player's STARTING one — the only system
* whose central body is the home world (a star, in every other). Stable
* across jumps, unlike a `currentSystemId` comparison. */
isHomeSystem(id) {
return id === this.homeSystemId;
}
// ------------------------------------------------------------------
// Contents (level 2, lazy)
// ------------------------------------------------------------------
/**
* Generate (once) and return a system's full contents. Safe to call from
* "the player arrived here" — the result is identical to what an
* up-front generateAll() would have produced.
*/
ensureContent(id) {
const cached = this.contentCache.get(id);
if (cached) return cached;
const record = this.byId.get(id);
if (!record) throw new Error(`Unknown system "${id}"`);
const content = generateSystemContent(this, record);
this.contentCache.set(id, content);
return content;
}
/** Alias of ensureContent() — reads nicer at call sites. */
contentOf(id) {
return this.ensureContent(id);
}
/**
* Eager mode: generate every system now. Deterministically identical to
* lazy generation (per-system seeded streams) — use it if profiling ever
* shows "just do it all at once" is fine.
*/
generateAll() {
for (const rec of this.records) this.ensureContent(rec.id);
return this;
}
get generatedCount() {
return this.contentCache.size;
}
// ------------------------------------------------------------------
/** Debug/console summary. */
summary() {
const byType = {};
for (const r of this.records) byType[r.type] = (byType[r.type] ?? 0) + 1;
const byZone = {};
for (const r of this.records) byZone[r.zone] = (byZone[r.zone] ?? 0) + 1;
return {
name: this.name,
seed: this.seed,
systems: this.records.length,
byType,
byZone,
generated: this.generatedCount,
currentSystemId: this.currentSystemId,
};
}
}