${champion ? "\u265B " : ""}${name}
${window.TarinaiUIHelpers.htmlEscape(gen)} / ${window.TarinaiUIHelpers.htmlEscape(status)}${champion ? " / \u738B\u8005" : ""}
${statLine}
${deathLine}
${tagLine}
`;
}
/*
* Family archive rendering is intentionally a top-down tree diagram.
* Do not replace this section with list/cards/readable grids: the archive must remain a \u5bb6\u7cfb\u56f3.
* The layout below may reorder siblings/parents inside the same generation only to reduce crossings.
*/
function lineageParentIds(n, idSet, family = world.family || {}) {
return lineageMutualParentIds(n, family, idSet).slice(0, 2);
}
function lineageParentKey(n, idSet) {
const parents = lineageParentIds(n, idSet);
if (!parents.length) return `root:${n?.id || Math.random()}`;
return parents.slice().sort().join("+");
}
function lineageMedian(values) {
if (!values.length) return Number.POSITIVE_INFINITY;
const sorted = values.slice().sort((a, b) => a - b);
const mid = Math.floor(sorted.length / 2);
return sorted.length % 2 ? sorted[mid] : (sorted[mid - 1] + sorted[mid]) / 2;
}
function lineageRankMap(rows) {
const rank = new Map();
rows.forEach((row, rowIndex) => {
row.forEach((n, i) => rank.set(n.id, rowIndex * 10000 + i));
});
return rank;
}
function lineageChildIds(n, idSet, family = world.family || {}) {
return lineageMutualChildIds(n, family, idSet);
}
function lineageOrderChildGroups(row, idSet, rank) {
const groups = new Map();
for (const n of row) {
const key = lineageParentKey(n, idSet);
if (!groups.has(key)) groups.set(key, []);
groups.get(key).push(n);
}
const records = Array.from(groups.entries()).map(([key, items]) => {
const parents = key.startsWith("root:") ? [] : key.split("+").filter(Boolean);
const parentRanks = parents.map(id => rank.get(id)).filter(v => Number.isFinite(v));
const score = parentRanks.length ? lineageMedian(parentRanks) : Number.POSITIVE_INFINITY;
items.sort(lineageNodeSort);
return {
key,
items,
score,
fallback: Math.min(...items.map(n => n.birthTime || 0)),
generation: Math.min(...items.map(n => n.generation || 1)),
};
});
records.sort((a, b) => a.score - b.score || a.generation - b.generation || a.fallback - b.fallback || String(a.key).localeCompare(String(b.key)));
return records.flatMap(r => r.items);
}
function lineageOrderParentsByChildren(row, idSet, childRank) {
if (!row.length || !childRank?.size) return row;
const records = row.map((n, index) => {
const childRanks = lineageChildIds(n, idSet).map(id => childRank.get(id)).filter(v => Number.isFinite(v));
return {
node: n,
score: childRanks.length ? lineageMedian(childRanks) : Number.POSITIVE_INFINITY,
original: index,
};
});
records.sort((a, b) => a.score - b.score || a.original - b.original || lineageNodeSort(a.node, b.node));
return records.map(r => r.node);
}
function lineagePartnerEdgesByGeneration(nodes, idToNode, idSet) {
const byGeneration = new Map();
const seen = new Set();
for (const child of nodes) {
const parents = lineageParentIds(child, idSet);
if (parents.length < 2) continue;
const a = idToNode.get(parents[0]);
const b = idToNode.get(parents[1]);
if (!a || !b) continue;
const generation = Math.min(a.generation || 1, b.generation || 1);
const key = parents.slice().sort().join("+");
if (seen.has(key)) continue;
seen.add(key);
if (!byGeneration.has(generation)) byGeneration.set(generation, []);
byGeneration.get(generation).push(parents.slice());
}
return byGeneration;
}
function lineageOrderPartnerComponent(ids, adjacency, rank, idToNode) {
if (ids.length <= 2) {
return ids.slice().sort((a, b) => (rank.get(a) ?? 0) - (rank.get(b) ?? 0) || lineageNodeSort(idToNode.get(a), idToNode.get(b)));
}
const degree = id => (adjacency.get(id) || new Set()).size;
const start = ids.slice().sort((a, b) => degree(b) - degree(a) || (rank.get(a) ?? 0) - (rank.get(b) ?? 0))[0];
const neighbors = Array.from(adjacency.get(start) || []).filter(id => ids.includes(id));
const left = [];
const right = [];
neighbors.sort((a, b) => (rank.get(a) ?? 0) - (rank.get(b) ?? 0) || lineageNodeSort(idToNode.get(a), idToNode.get(b)));
neighbors.forEach((id, i) => (i % 2 ? left : right).push(id));
const placed = new Set([start, ...neighbors]);
const rest = ids.filter(id => !placed.has(id)).sort((a, b) => (rank.get(a) ?? 0) - (rank.get(b) ?? 0) || lineageNodeSort(idToNode.get(a), idToNode.get(b)));
return [...left.reverse(), start, ...right, ...rest];
}
function lineageOrderPartnerClusters(row, partnerEdges, rank, idToNode) {
if (!partnerEdges?.length) return row;
const rowIds = new Set(row.map(n => n.id));
const adjacency = new Map();
for (const [a, b] of partnerEdges) {
if (!rowIds.has(a) || !rowIds.has(b)) continue;
if (!adjacency.has(a)) adjacency.set(a, new Set());
if (!adjacency.has(b)) adjacency.set(b, new Set());
adjacency.get(a).add(b);
adjacency.get(b).add(a);
}
if (!adjacency.size) return row;
const clusteredIds = new Set(adjacency.keys());
const seen = new Set();
const records = [];
for (const n of row) {
if (!clusteredIds.has(n.id)) {
records.push({ ids: [n.id], score: rank.get(n.id) ?? Number.POSITIVE_INFINITY, fallback: idToNode.get(n.id)?.birthTime || 0 });
continue;
}
if (seen.has(n.id)) continue;
const stack = [n.id];
const ids = [];
seen.add(n.id);
while (stack.length) {
const id = stack.pop();
ids.push(id);
for (const next of adjacency.get(id) || []) {
if (seen.has(next)) continue;
seen.add(next);
stack.push(next);
}
}
const orderedIds = lineageOrderPartnerComponent(ids, adjacency, rank, idToNode);
records.push({
ids: orderedIds,
score: lineageMedian(orderedIds.map(id => rank.get(id)).filter(v => Number.isFinite(v))),
fallback: Math.min(...orderedIds.map(id => idToNode.get(id)?.birthTime || 0)),
});
}
records.sort((a, b) => a.score - b.score || a.fallback - b.fallback || String(a.ids[0]).localeCompare(String(b.ids[0])));
return records.flatMap(c => c.ids.map(id => idToNode.get(id)).filter(Boolean));
}
function lineageAdjacentCrossCost(parentRow, childRow, idSet) {
if (!parentRow?.length || !childRow?.length) return 0;
const parentPos = new Map(parentRow.map((n, i) => [n.id, i]));
const edges = [];
for (let childIndex = 0; childIndex < childRow.length; childIndex++) {
const child = childRow[childIndex];
const parents = lineageParentIds(child, idSet).filter(id => parentPos.has(id));
if (!parents.length) continue;
const from = lineageMedian(parents.map(id => parentPos.get(id)));
edges.push({ from, to: childIndex, weight: parents.length >= 2 ? 1.4 : 1 });
}
let cost = 0;
for (let i = 0; i < edges.length; i++) {
for (let j = i + 1; j < edges.length; j++) {
const a = edges[i];
const b = edges[j];
const cross = (a.from - b.from) * (a.to - b.to) < 0;
if (cross) cost += a.weight * b.weight * 4.5;
}
}
return cost;
}
function lineageRowCost(row, rowIndex, rows, idSet) {
const pos = new Map(row.map((n, i) => [n.id, i]));
let cost = 0;
for (const n of row) {
const i = pos.get(n.id);
const parents = lineageParentIds(n, idSet);
if (parents.length && rowIndex > 0) {
const parentRow = rows[rowIndex - 1] || [];
const parentPos = parents.map(id => parentRow.findIndex(x => x.id === id)).filter(v => v >= 0);
if (parentPos.length) cost += Math.abs(i - lineageMedian(parentPos)) * (parents.length >= 2 ? 1.5 : 1.2);
}
const childRow = rows[rowIndex + 1] || [];
const childPos = childRow.filter(x => lineageParentIds(x, idSet).includes(n.id)).map(x => childRow.findIndex(y => y.id === x.id));
if (childPos.length) cost += Math.abs(i - lineageMedian(childPos)) * 1.0;
const siblingPos = row.filter(x => x.id !== n.id && lineageParentKey(x, idSet) === lineageParentKey(n, idSet)).map(x => pos.get(x.id));
if (siblingPos.length) cost += Math.abs(i - lineageMedian(siblingPos)) * 0.22;
}
const seenPairs = new Set();
for (const child of rows[rowIndex + 1] || []) {
const parents = lineageParentIds(child, idSet).filter(id => pos.has(id));
if (parents.length < 2) continue;
const key = parents.slice().sort().join("+");
if (seenPairs.has(key)) continue;
seenPairs.add(key);
const pair = parents.slice().sort((a, b) => pos.get(a) - pos.get(b));
const span = pos.get(pair[1]) - pos.get(pair[0]);
cost += span * span * 3.4;
if (span > 1) cost += 12;
}
return cost;
}
function lineageTotalCost(rows, idSet) {
let cost = 0;
for (let i = 0; i < rows.length; i++) {
cost += lineageRowCost(rows[i], i, rows, idSet);
if (i < rows.length - 1) cost += lineageAdjacentCrossCost(rows[i], rows[i + 1], idSet);
}
return cost;
}
function lineageMoveItem(row, fromIndex, toIndex) {
if (fromIndex === toIndex) return row.slice();
const next = row.slice();
const [item] = next.splice(fromIndex, 1);
next.splice(toIndex, 0, item);
return next;
}
function lineageOptimizeRows(rows, idSet) {
const totalNodes = rows.reduce((sum, row) => sum + row.length, 0);
const maxRow = Math.max(0, ...rows.map(row => row.length));
// The old exhaustive optimizer was cubic-to-quartic in practice and froze on
// large archives. Keep it only for small families; large trees use the
// barycentric ordering above, which is stable and linear-ish.
if (totalNodes > 90 || maxRow > 16) return rows.map(row => row.slice());
let bestRows = rows.map(row => row.slice());
let bestCost = lineageTotalCost(bestRows, idSet);
const passes = totalNodes > 54 || maxRow > 10 ? 3 : 6;
for (let pass = 0; pass < passes; pass++) {
let changed = false;
for (let rowIndex = 0; rowIndex < bestRows.length; rowIndex++) {
const row = bestRows[rowIndex];
if (!row || row.length < 2) continue;
for (let from = 0; from < row.length; from++) {
const span = row.length > 10 ? 3 : row.length;
const minTo = Math.max(0, from - span);
const maxTo = Math.min(row.length - 1, from + span);
for (let to = minTo; to <= maxTo; to++) {
if (from === to) continue;
const moved = lineageMoveItem(bestRows[rowIndex], from, to);
const candidate = bestRows.slice();
candidate[rowIndex] = moved;
const cost = lineageTotalCost(candidate, idSet);
if (cost + 0.001 < bestCost) {
bestRows = candidate;
bestCost = cost;
changed = true;
}
}
}
}
if (!changed) break;
}
return bestRows;
}
function lineageRowsForLayout(nodes, generations, idToNode, idSet) {
const byGeneration = new Map(generations.map(g => [g, []]));
for (const n of nodes) byGeneration.get(n.generation || 1).push(n);
let rows = generations.map(g => (byGeneration.get(g) || []).slice().sort(lineageNodeSort));
const partnerEdges = lineagePartnerEdgesByGeneration(nodes, idToNode, idSet);
const totalNodes = nodes.length;
const maxRow = Math.max(0, ...rows.map(row => row.length));
const veryLarge = totalNodes > 220 || maxRow > 44;
const passes = veryLarge ? 1 : (totalNodes > 180 || maxRow > 32 ? 2 : (totalNodes > 90 || maxRow > 18 ? 3 : 6));
for (let pass = 0; pass < passes; pass++) {
let rank = lineageRankMap(rows);
rows = rows.map(row => lineageOrderChildGroups(row, idSet, rank));
rank = lineageRankMap(rows);
for (let i = rows.length - 2; i >= 0; i--) {
const childRank = new Map(rows[i + 1].map((n, index) => [n.id, index]));
rows[i] = lineageOrderParentsByChildren(rows[i], idSet, childRank);
}
if (!veryLarge) {
rank = lineageRankMap(rows);
rows = rows.map((row, i) => lineageOrderPartnerClusters(row, partnerEdges.get(generations[i]), rank, idToNode));
if (totalNodes <= 90 && maxRow <= 16) rows = lineageOptimizeRows(rows, idSet);
}
}
return rows;
}
function lineageBuildRowGroups(row, idSet) {
const groups = [];
let i = 0;
while (i < row.length) {
const key = lineageParentKey(row[i], idSet);
const items = [row[i]];
i += 1;
while (i < row.length && lineageParentKey(row[i], idSet) === key) {
items.push(row[i]);
i += 1;
}
groups.push({ key, items });
}
return groups;
}
function lineageLayoutRows(rows, idSet) {
const NODE_W = 150;
const NODE_H = 112;
const SIBLING_GAP = 24;
const GROUP_GAP = 42;
const PARTNER_GROUP_GAP = 18;
const ROW_GAP = 74;
const LEFT_PAD = 82;
const TOP_PAD = 44;
const RIGHT_PAD = 48;
const BOTTOM_PAD = 30;
const rowGroups = rows.map(row => lineageBuildRowGroups(row, idSet).map(group => ({
...group,
groupW: group.items.length * NODE_W + Math.max(0, group.items.length - 1) * SIBLING_GAP,
})));
const pairedKeysByRow = rows.map((row) => {
const set = new Set();
const rowIds = new Set(row.map(n => n.id));
for (const futureRow of rows) {
for (const child of futureRow) {
const parents = lineageParentIds(child, rowIds);
if (parents.length >= 2) set.add(parents.slice().sort().join("+"));
}
}
return set;
});
let positions = new Map();
let width = 420;
const placePass = (existingPositions) => {
const nextPositions = new Map();
let nextWidth = 420;
const rowLayouts = [];
rows.forEach((row, rowIndex) => {
const groups = rowGroups[rowIndex] || [];
const desiredLefts = [];
const y = TOP_PAD + rowIndex * (NODE_H + ROW_GAP);
const nextRow = rows[rowIndex + 1] || [];
for (let gIndex = 0; gIndex < groups.length; gIndex++) {
const group = groups[gIndex];
const first = group.items[0];
const parentCenters = lineageParentIds(first, idSet)
.map(id => existingPositions.get(id) || nextPositions.get(id))
.filter(Boolean)
.map(p => p.x + NODE_W / 2);
const groupIds = new Set(group.items.map(n => n.id));
const childCenters = nextRow
.filter(child => lineageParentIds(child, idSet).some(id => groupIds.has(id)))
.map(child => existingPositions.get(child.id))
.filter(Boolean)
.map(p => p.x + NODE_W / 2);
const desiredCenterValues = [];
if (parentCenters.length) desiredCenterValues.push(...parentCenters, ...parentCenters);
if (childCenters.length) desiredCenterValues.push(...childCenters);
const fallbackCenter = LEFT_PAD + group.groupW / 2 + gIndex * (group.groupW + GROUP_GAP);
const desiredCenter = Number.isFinite(lineageMedian(desiredCenterValues)) ? lineageMedian(desiredCenterValues) : fallbackCenter;
desiredLefts[gIndex] = desiredCenter - group.groupW / 2;
}
const lefts = [];
const SOFT_EXTRA_GAP = 54;
for (let gIndex = 0; gIndex < groups.length; gIndex++) {
const prevGroup = groups[gIndex - 1];
const pairGap = prevGroup && prevGroup.items.length === 1 && groups[gIndex].items.length === 1
&& pairedKeysByRow[rowIndex].has([prevGroup.items[0].id, groups[gIndex].items[0].id].sort().join("+"));
const gap = pairGap ? PARTNER_GROUP_GAP : GROUP_GAP;
const minLeft = gIndex === 0 ? LEFT_PAD : lefts[gIndex - 1] + groups[gIndex - 1].groupW + gap;
const desired = Number.isFinite(desiredLefts[gIndex]) ? desiredLefts[gIndex] : minLeft;
lefts[gIndex] = Math.max(minLeft, Math.min(desired, minLeft + SOFT_EXTRA_GAP));
}
for (let gIndex = groups.length - 2; gIndex >= 0; gIndex--) {
const nextGroup = groups[gIndex + 1];
const pairGap = nextGroup && groups[gIndex].items.length === 1 && nextGroup.items.length === 1
&& pairedKeysByRow[rowIndex].has([groups[gIndex].items[0].id, nextGroup.items[0].id].sort().join("+"));
const gap = pairGap ? PARTNER_GROUP_GAP : GROUP_GAP;
const maxLeft = lefts[gIndex + 1] - groups[gIndex].groupW - gap;
lefts[gIndex] = Math.min(lefts[gIndex], maxLeft);
if (gIndex === 0) lefts[gIndex] = Math.max(lefts[gIndex], LEFT_PAD);
}
const contentW = groups.length ? (lefts[lefts.length - 1] + groups[groups.length - 1].groupW - LEFT_PAD) : 0;
nextWidth = Math.max(nextWidth, LEFT_PAD + contentW + RIGHT_PAD);
groups.forEach((group, gIndex) => {
const left = lefts[gIndex];
group.items.forEach((n, i) => {
const x = left + i * (NODE_W + SIBLING_GAP);
nextPositions.set(n.id, { x, y, rowIndex, node: n });
});
});
rowLayouts.push({ rowIndex, groups, lefts, contentW, y });
});
return { positions: nextPositions, width: nextWidth, rowLayouts };
};
for (let pass = 0; pass < 5; pass++) {
const result = placePass(positions);
positions = result.positions;
width = result.width;
}
// Re-run once more and center the entire family as one block to avoid left-heavy layouts
// without breaking parent/child alignment between rows.
const finalResult = placePass(positions);
positions = new Map(finalResult.positions);
let minX = Number.POSITIVE_INFINITY;
let maxX = 0;
for (const pos of positions.values()) {
minX = Math.min(minX, pos.x);
maxX = Math.max(maxX, pos.x + NODE_W);
}
const contentW = Number.isFinite(minX) ? Math.max(0, maxX - minX) : 0;
width = Math.max(finalResult.width, LEFT_PAD + contentW + RIGHT_PAD);
if (Number.isFinite(minX)) {
const targetLeft = LEFT_PAD + Math.max(0, (width - LEFT_PAD - RIGHT_PAD - contentW) / 2);
const shift = targetLeft - minX;
if (shift) {
for (const [id, prev] of positions.entries()) positions.set(id, { ...prev, x: prev.x + shift });
}
}
const groupBounds = (group) => {
const xs = group.items.map(n => positions.get(n.id)?.x).filter(Number.isFinite);
if (!xs.length) return null;
return { left: Math.min(...xs), right: Math.max(...xs) + NODE_W, width: group.groupW };
};
const groupGap = (leftGroup, rightGroup, rowIndex) => {
const pairGap = leftGroup && rightGroup && leftGroup.items.length === 1 && rightGroup.items.length === 1
&& pairedKeysByRow[rowIndex].has([leftGroup.items[0].id, rightGroup.items[0].id].sort().join("+"));
return pairGap ? PARTNER_GROUP_GAP : GROUP_GAP;
};
const shiftGroup = (group, dx) => {
if (!dx) return;
for (const n of group.items) {
const prev = positions.get(n.id);
if (prev) positions.set(n.id, { ...prev, x: prev.x + dx });
}
};
for (let pass = 0; pass < 3; pass++) {
for (let rowIndex = 1; rowIndex < rowGroups.length; rowIndex++) {
const groups = rowGroups[rowIndex] || [];
for (let gIndex = 0; gIndex < groups.length; gIndex++) {
const group = groups[gIndex];
const first = group.items[0];
const parentIds = lineageParentIds(first, idSet);
if (!parentIds.length) continue;
const parentPositions = parentIds.map(id => positions.get(id)).filter(Boolean);
if (!parentPositions.length) continue;
const parentCenter = parentPositions.reduce((sum, p) => sum + p.x + NODE_W / 2, 0) / parentPositions.length;
const bounds = groupBounds(group);
if (!bounds) continue;
const idealLeft = parentCenter - bounds.width / 2;
let minShift = LEFT_PAD - bounds.left;
let maxShift = Number.POSITIVE_INFINITY;
const prevGroup = groups[gIndex - 1];
if (prevGroup) {
const pb = groupBounds(prevGroup);
if (pb) minShift = Math.max(minShift, pb.right + groupGap(prevGroup, group, rowIndex) - bounds.left);
}
const nextGroup = groups[gIndex + 1];
if (nextGroup) {
const nb = groupBounds(nextGroup);
if (nb) maxShift = nb.left - groupGap(group, nextGroup, rowIndex) - bounds.right;
}
const desiredShift = idealLeft - bounds.left;
const shift = clamp(desiredShift, minShift, maxShift);
if (Math.abs(shift) > 0.2) shiftGroup(group, shift);
}
}
}
width = Math.max(width, ...Array.from(positions.values()).map(p => p.x + NODE_W + RIGHT_PAD));
// Fallback placement for any node that somehow missed layout.
rows.forEach((row, rowIndex) => {
const y = TOP_PAD + rowIndex * (NODE_H + ROW_GAP);
let fallbackX = LEFT_PAD;
for (const n of row) {
if (positions.has(n.id)) {
fallbackX = Math.max(fallbackX, positions.get(n.id).x + NODE_W + GROUP_GAP);
continue;
}
positions.set(n.id, { x: fallbackX, y, rowIndex, node: n });
fallbackX += NODE_W + GROUP_GAP;
width = Math.max(width, fallbackX + RIGHT_PAD);
}
});
const height = TOP_PAD + Math.max(0, rows.length - 1) * (NODE_H + ROW_GAP) + NODE_H + BOTTOM_PAD;
return { positions, width, height, nodeW: NODE_W, nodeH: NODE_H, topPad: TOP_PAD, rowGap: ROW_GAP };
}