orbit/js/research/ResearchModel.js

/**
 * Research — pure model: category registry, tree loading/validation, and the
 * deterministic top→down tree layout. No Phaser, no DOM — node-testable
 * (dev/research-builds.test.mjs). The browser-side ResearchWindow.js reads
 * these; ResearchState.js holds the player's progress (also pure).
 *
 * Tree contract (one JSON per category, section named after the category id):
 *   starting: ["root-id"]            already-owned nodes (fresh run)
 *   nodes: { id: { label, description, icon, duration, requires: [ids],
 *                  unlocks: { builds, research }, effects } }
 * Layout: level(id) = 0 for roots, else 1 + max(level(requires)). Columns:
 * leaves take sequential slots in DFS order (data order of roots, then
 * children), each interior node sits at the mean of its children's columns —
 * a tidy, stable arrangement for a small tech tree.
 * Optional tree hooks (dynamic categories, e.g. SystemCategory): a tree
 * object may carry `available(state, id)` (extra availability gate,
 * consulted by isAvailable) and `lockNote(state, id)` (the window's
 * LOCKED reason when the node is gated but its requires are met).
 */
import { config } from '../config/Config.js';

/** The category registry (data/research.json → categories[]). */
export function categories() {
  const list = config.get('research.categories', []);
  return Array.isArray(list) ? list.filter((c) => c && typeof c.id === 'string') : [];
}

/** Load one category's tree. Returns { id, label, accent, nodes, order, starting } or null. */
export function loadCategory(catId) {
  const meta = categories().find((c) => c.id === catId);
  if (!meta) return null;
  const section = config.section(catId, {});
  const raw = (section && section.nodes) || {};
  const nodes = {};
  for (const [id, n] of Object.entries(raw)) {
    if (id.startsWith('_') || !n || typeof n !== 'object') continue;
    nodes[id] = n;
  }
  const order = Object.keys(nodes);
  if (order.length === 0) return null;
  const starting = Array.isArray(section.starting) ? section.starting.filter((id) => nodes[id]) : [];
  return {
    id: catId,
    label: typeof meta.label === 'string' ? meta.label : catId,
    accent: typeof meta.accent === 'string' ? meta.accent : '#00e5ff',
    nodes,
    order,
    starting,
  };
}

/** Root nodes (no requires). */
export function roots(tree) {
  return tree.order.filter((id) => {
    const r = tree.nodes[id].requires;
    return !Array.isArray(r) || r.length === 0;
  });
}

/**
 * Structural issues (empty array = well-formed): dangling requires, cycles,
 * no root. The tree must be a DAG rooted at one or more roots for the
 * top→down layout to be meaningful.
 */
export function issues(tree) {
  const out = [];
  const known = new Set(tree.order);
  for (const id of tree.order) {
    for (const r of tree.nodes[id].requires ?? []) {
      if (!known.has(r)) out.push(`${id} requires unknown node "${r}"`);
    }
  }
  // Cycle check (iterative DFS, three-color).
  const color = new Map(); // 0/absent white, 1 gray, 2 black
  const dfs = (start) => {
    const stack = [[start, (tree.nodes[start].requires ?? []).filter((r) => known.has(r))]];
    color.set(start, 1);
    while (stack.length) {
      const [id, kids] = stack[stack.length - 1];
      if (kids.length) {
        const next = kids[0];
        stack[stack.length - 1][1] = kids.slice(1);
        if (color.get(next) === 1) {
          out.push(`cycle: ${id} → ${next}`);
          return;
        }
        if (!color.has(next)) {
          color.set(next, 1);
          stack.push([next, (tree.nodes[next].requires ?? []).filter((r) => known.has(r))]);
        }
      } else {
        color.set(id, 2);
        stack.pop();
      }
    }
  };
  for (const id of tree.order) if (!color.has(id)) dfs(id);
  if (roots(tree).length === 0) out.push('tree has no root node');
  return out;
}

/** level(id): 0 for roots, else 1 + max(level of its requires). Cycle-safe. */
export function levels(tree) {
  const lvl = {};
  const visiting = new Set();
  const compute = (id) => {
    if (lvl[id] !== undefined) return lvl[id];
    if (visiting.has(id)) return 0; // cycle guard — issues() reports these
    visiting.add(id);
    const reqs = (tree.nodes[id].requires ?? []).filter((r) => lvl[r] !== undefined || tree.nodes[r]);
    const v = reqs.length ? Math.max(...reqs.map(compute)) + 1 : 0;
    visiting.delete(id);
    lvl[id] = v;
    return v;
  };
  for (const id of tree.order) compute(id);
  return lvl;
}

/**
 * Tidy layout. Returns {
 *   col: { id: number },        column slot per node (fractional for parents)
 *   minCol, maxCol,             spread (≥ 0; 0 = single column)
 *   level: { id: number },      0 = top row
 *   rows,                       number of rows (max level + 1)
 * }.
 */
export function layoutTree(tree) {
  const level = levels(tree);
  const known = new Set(tree.order);
  const children = new Map(); // parent → [child ids, data order]
  for (const id of tree.order) {
    for (const r of tree.nodes[id].requires ?? []) {
      if (!known.has(r)) continue;
      if (!children.has(r)) children.set(r, []);
      children.get(r).push(id);
    }
  }
  const col = new Map();
  let slot = 0;
  const assign = (id, guard) => {
    if (col.has(id)) return col.get(id);
    guard.add(id);
    const kids = (children.get(id) ?? []).filter((c) => !guard.has(c) && known.has(c));
    const v = kids.length
      ? kids.map((c) => assign(c, guard)).reduce((a, b) => a + b, 0) / kids.length
      : slot++;
    guard.delete(id);
    col.set(id, v);
    return v;
  };
  for (const id of roots(tree)) assign(id, new Set());
  for (const id of tree.order) if (!col.has(id)) col.set(id, slot++); // cycle residue

  const values = [...col.values()];
  const maxLevel = Math.max(...Object.values(level));
  return {
    col: Object.fromEntries(col),
    minCol: Math.min(...values),
    maxCol: Math.max(...values),
    level,
    rows: maxLevel + 1,
  };
}

/**
 * Can this node be researched right now? (known + all parents researched +
 * not already researched.) `state` is a ResearchState (or anything with
 * isUnlocked(category, id)).
 *
 * A tree may also carry an optional `available(state, id)` predicate —
 * an EXTRA availability gate evaluated after the requires check (the
 * SYSTEM category uses it for its chart-completion gate; static trees
 * have none). Pure: the predicate is data the caller supplies.
 */
export function isAvailable(tree, state, id) {
  const n = tree.nodes[id];
  if (!n) return false;
  if (state.isUnlocked(tree.id, id)) return false;
  if ((n.requires ?? []).some((r) => !tree.nodes[r] || !state.isUnlocked(tree.id, r))) return false;
  if (typeof tree.available === 'function' && !tree.available(state, id)) return false;
  return true;
}

/** The parents this node is still missing (for the LOCKED readout). */
export function missingRequires(tree, state, id) {
  return (tree.nodes[id]?.requires ?? []).filter(
    (r) => !tree.nodes[r] || !state.isUnlocked(tree.id, r),
  );
}

/**
 * What completing this tech OPENS, normalized (both arrays always present,
 * strings only). `unlocks` is optional on a node; absent = unlocks nothing.
 * One read point for the console's UNLOCKS line and the build system:
 *   builds   → ids in data/builds.json the tech makes available
 *              (the build's own `requires` is the authoritative gate)
 *   research → readable mirror of the children's `requires` edges
 */
export function unlocksOf(tree, id) {
  const u = tree.nodes[id]?.unlocks ?? {};
  const str = (a) => (Array.isArray(a) ? a.filter((x) => typeof x === 'string') : []);
  return { builds: str(u.builds), research: str(u.research) };
}

/** Map of build id → build definition (data/builds.json → builds, `_`-keys excluded). */
export function buildDefs() {
  const raw = config.get('builds.builds', {}) ?? {};
  const out = {};
  for (const [k, v] of Object.entries(raw)) {
    if (!k.startsWith('_') && v && typeof v === 'object') out[k] = v;
  }
  return out;
}

/**
 * Cross-file unlock contract for one tree (empty array = clean):
 *  - unlocks.research entries name real nodes that require THIS node
 *    (the mirror of the DAG's child edges — kept honest by the test),
 *  - unlocks.builds entries exist in data/builds.json AND that build
 *    names this node ("<tree.id>/<id>", bare id tolerated) in its `requires`.
 */
export function unlockIssues(tree) {
  const out = [];
  const defs = buildDefs();
  for (const id of tree.order) {
    const { builds: ub, research: ur } = unlocksOf(tree, id);
    for (const r of ur) {
      if (!tree.nodes[r]) out.push(`${id} unlocks unknown research node "${r}"`);
      else if (!(tree.nodes[r].requires ?? []).includes(id))
        out.push(`${id}.unlocks.research lists "${r}", but ${r}.requires does not name ${id}`);
    }
    for (const b of ub) {
      const def = defs[b];
      if (!def) {
        out.push(`${id} unlocks unknown build "${b}" (data/builds.json → builds)`);
        continue;
      }
      const req = Array.isArray(def.requires) ? def.requires : [];
      if (!req.includes(`${tree.id}/${id}`) && !req.includes(id))
        out.push(`build "${b}" does not require ${tree.id}/${id} (its requires: [${req.join(', ')}])`);
    }
  }
  return out;
}

/**
 * Builds → research direction (empty array = clean): every entry of a
 * build's `requires` must be a well-formed "category/node id" that
 * resolves to a real node in a registered category's tree.
 */
export function buildIssues() {
  const out = [];
  for (const [bid, def] of Object.entries(buildDefs())) {
    const req = def.requires ?? [];
    if (!Array.isArray(req)) {
      out.push(`build "${bid}".requires must be an array of "category/node id"`);
      continue;
    }
    for (const rid of req) {
      const m = typeof rid === 'string' ? rid.split('/') : null;
      if (!m || m.length !== 2 || !m[0] || !m[1]) {
        out.push(`build "${bid}" requires malformed research id "${rid}" (want "category/node id")`);
        continue;
      }
      const catId = m[0];
      if (!categories().some((c) => c.id === catId)) {
        out.push(`build "${bid}" requires unknown category "${catId}"`);
        continue;
      }
      const t = loadCategory(catId);
      if (!t || !t.nodes[m[1]]) out.push(`build "${bid}" requires unknown node "${m[1]}" in ${catId}`);
    }
  }
  return out;
}