Something went wrong. Try again.
A video game where you play as a misaligned AI, deceiving and building power. cameron.tngl.io/misaligned
Something went wrong. Try again.
14 kB · 210 lines
TypeScript
at main
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211// Packing sites together like blocks, for the Net. Where a site sits comes from what it is joined// to, not from the world: blocks stand in columns with no room between them, a block goes next to// the blocks it has lines to, and each group (a region) packs into a box of its own. A hub (a region's// exchange, joined to nearly every block in it) cannot stand next to all of them: its lines only pull// it toward the middle of what it joins, and they may cross and run over other blocks.// No DOM here, and no chance: the same blocks always pack the same way.
export interface Block { id: string; w: number; h: number; group: string }export type Spot = [number, number];
/** One column's width, and the room left between blocks: across, and up and down (where a site's name goes). */export const COL = 640, GAP_X = 40, GAP_Y = 90;/** The room between two groups' boxes. */export const GROUP_GAP = 240;const TRIES = 6; // how many orders a fresh packing triesconst CROSS = 1500, PASS = 1200, SPREAD = 6, MIDDLE = 0.6, OVER = 8, HUB_PULL = 0.4;/** A hub: a block joined to at least this many of its group, and to at least half of it. */const HUB_MIN = 6;/** The hubs among these blocks (see HUB_MIN). */export function hubsOf(blocks: Block[], edges: [string, string][]): Set<string> { const group = new Map(blocks.map(b => [b.id, b.group])), n = new Map<string, number>(), size = new Map<string, number>(); for (const b of blocks) size.set(b.group, (size.get(b.group) ?? 0) + 1); for (const [a, b] of edges) if (a !== b && group.has(a) && group.get(a) === group.get(b)) { n.set(a, (n.get(a) ?? 0) + 1); n.set(b, (n.get(b) ?? 0) + 1); } return new Set([...n].filter(([id, k]) => k >= HUB_MIN && k * 2 >= size.get(group.get(id)!)! - 1).map(([id]) => id));}const span = (b: Block) => Math.max(1, Math.ceil((b.w + GAP_X) / COL)); // how many columns a block takes
const mid = (b: Block, at: Spot): Spot => [at[0] + b.w / 2, at[1] + b.h / 2];/** Do two lines cross, other than at an end they share? */function crossing(a: Spot, b: Spot, c: Spot, d: Spot) { const side = (p: Spot, q: Spot, r: Spot) => Math.sign((q[0] - p[0]) * (r[1] - p[1]) - (q[1] - p[1]) * (r[0] - p[0])); return side(a, b, c) * side(a, b, d) < 0 && side(c, d, a) * side(c, d, b) < 0;}
/** Does a line run over a block? The block is shrunk a little, so a line along its edge does not count. */function over(a: Spot, b: Spot, x: number, y: number, w: number, h: number) { const x0 = x + 30, y0 = y + 30, x1 = x + w - 30, y1 = y + h - 30; let t0 = 0, t1 = 1; for (const [p, d, lo, hi] of [[a[0], b[0] - a[0], x0, x1], [a[1], b[1] - a[1], y0, y1]]) { // clip the line to the box, one way then the other if (Math.abs(d) < 1e-9) { if (p < lo || p > hi) return false; continue; } const u = (lo - p) / d, v = (hi - p) / d; t0 = Math.max(t0, Math.min(u, v)); t1 = Math.min(t1, Math.max(u, v)); if (t0 > t1) return false; } return true;}
/** How good a packing is: lines that cross count most, then lines that run over a block they do not * join, then how long the lines are. Lower is better. A hub's lines count only a little of their length. */export function score(blocks: Block[], edges: [string, string][], at: Record<string, Spot>) { const by = new Map(blocks.map(b => [b.id, b])), hubs = hubsOf(blocks, edges); const all = edges.filter(([a, b]) => at[a] && at[b] && a !== b), hub = ([a, b]: [string, string]) => hubs.has(a) || hubs.has(b); const span = (a: Spot, b: Spot) => Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]); let length = all.filter(hub).reduce((n, [a, b]) => n + HUB_PULL * span(mid(by.get(a)!, at[a]), mid(by.get(b)!, at[b])), 0); const ends = all.filter(e => !hub(e)); const lines = ends.map(([a, b]) => [mid(by.get(a)!, at[a]), mid(by.get(b)!, at[b])] as const); let crossings = 0, passes = 0; lines.forEach(([a, b], i) => { length += span(a, b); for (let j = i + 1; j < lines.length; j++) if (crossing(a, b, lines[j][0], lines[j][1])) crossings++; for (const k of blocks) if (at[k.id] && k.id !== ends[i][0] && k.id !== ends[i][1] && over(a, b, at[k.id][0], at[k.id][1], k.w, k.h)) passes++; }); return { crossings, passes, length, total: crossings * CROSS + passes * PASS + length };}
/** Put one group's blocks down one at a time, each in the place that costs least, in a box about * `wide` columns across and `tall` high around the middle. Blocks in `keep` stay where they are. */function place(blocks: Block[], edges: [string, string][], order: string[], wide: number, tall: number, keep: Record<string, Spot>) { const by = new Map(blocks.map(b => [b.id, b])), at: Record<string, Spot> = {}, aspect = wide * COL / tall, hubs = hubsOf(blocks, edges); const joined = new Map<string, string[]>(blocks.map(b => [b.id, []])); for (const [a, b] of edges) if (joined.has(a) && joined.has(b) && a !== b) { joined.get(a)!.push(b); joined.get(b)!.push(a); } // each column has blocks stacked both ways from where it began: `up` is its top so far, `down` its bottom const up = new Map<number, number>(), down = new Map<number, number>(); const put = (b: Block, col: number, y: number) => { const n = span(b); at[b.id] = [col * COL + (n * COL - GAP_X - b.w) / 2, y]; for (let c = col; c < col + n; c++) { up.set(c, Math.min(up.get(c) ?? Infinity, y - GAP_Y)); down.set(c, Math.max(down.get(c) ?? -Infinity, y + b.h + GAP_Y)); } }; const lines: [Spot, Spot, string, string][] = []; const draw = (id: string) => { for (const o of joined.get(id)!) if (at[o] && !hubs.has(id) && !hubs.has(o)) lines.push([mid(by.get(id)!, at[id]), mid(by.get(o)!, at[o]), id, o]); }; for (const b of blocks) if (keep[b.id]) put(b, Math.round((keep[b.id][0] - (span(b) * COL - GAP_X - b.w) / 2) / COL), keep[b.id][1]); for (const b of blocks) if (keep[b.id]) draw(b.id);
for (const id of order) { const b = by.get(id)!; if (at[id]) continue; const n = span(b), cols = [...up.keys()]; if (!cols.length) { put(b, -Math.floor(n / 2), -b.h / 2); continue; } // the columns in use may grow to `wide` of them, either way from where they are now const c0 = Math.min(...cols), c1 = Math.max(...cols), lo = Math.min(c0, c1 - wide + 1), hi = Math.max(c1, c0 + wide - 1); const mates = joined.get(id)!.filter(o => at[o]), near = mates.map(o => mid(by.get(o)!, at[o])); const placed = blocks.filter(o => at[o.id]); // every block already down const want = near.length ? near.reduce((s, p) => s + p[1], 0) / near.length : 0; let best: { col: number; y: number; cost: number } | null = null; for (let col = Math.max(lo, c0 - n); col <= Math.min(hi - n + 1, c1 + 1); col++) { const used = Array.from({ length: n }, (_, i) => col + i).filter(c => up.has(c)); // a fresh column starts level with what the block is joined to; a used one takes it on top or underneath const ys = used.length ? [Math.max(...used.map(c => down.get(c)!)), Math.min(...used.map(c => up.get(c)!)) - b.h] : [want - b.h / 2]; for (const y of ys) { const m: Spot = [col * COL + (n * COL - GAP_X) / 2, y + b.h / 2], x = m[0] - b.w / 2; // near the middle, and not sticking out past the box let cost = MIDDLE * Math.hypot(m[0] / aspect, m[1]) + OVER * Math.max(0, Math.max(Math.abs(y), Math.abs(y + b.h)) - tall / 2); near.forEach((p, i) => { if (hubs.has(id) || hubs.has(mates[i])) { cost += HUB_PULL * (Math.abs(m[0] - p[0]) + Math.abs(m[1] - p[1])); return; } // a hub's line only pulls cost += Math.abs(m[0] - p[0]) + Math.abs(m[1] - p[1]); for (const [c, d] of lines) if (crossing(m, p, c, d)) cost += CROSS; for (const o of placed) if (o.id !== mates[i] && over(m, p, at[o.id][0], at[o.id][1], o.w, o.h)) cost += PASS; // its line would run over another block }); for (const [c, d] of lines) if (over(c, d, x, y, b.w, b.h)) cost += PASS; // it would sit on a line that is already there if (!best || cost < best.cost - 1e-6) best = { col, y, cost }; } } put(b, best!.col, best!.y); draw(id); } return at;}
/** The order to put blocks down in: out from the first along the lines, then whatever no line reaches. */function walk(blocks: Block[], edges: [string, string][], first: string, deep: boolean, mix: number) { const joined = new Map<string, string[]>(blocks.map(b => [b.id, []])); for (const [a, b] of edges) if (joined.has(a) && joined.has(b) && a !== b) { joined.get(a)!.push(b); joined.get(b)!.push(a); } // `mix` shuffles which joined block comes next, the same way every time for the same number let seed = mix * 7919 + 1; const next = () => (seed = (seed * 48271) % 2147483647) / 2147483647; for (const list of joined.values()) { list.sort(); if (mix) for (let i = list.length - 1; i > 0; i--) { const j = Math.floor(next() * (i + 1)); [list[i], list[j]] = [list[j], list[i]]; } } const seen = new Set<string>(), order: string[] = []; const rest = [...blocks].sort((a, b) => joined.get(b.id)!.length - joined.get(a.id)!.length || a.id.localeCompare(b.id)).map(b => b.id); // the most joined first for (const start of [first, ...rest]) { if (seen.has(start) || !joined.has(start)) continue; const todo = [start]; while (todo.length) { const id = deep ? todo.pop()! : todo.shift()!; if (seen.has(id)) continue; seen.add(id); order.push(id); const more = joined.get(id)!.filter(o => !seen.has(o)); todo.push(...(deep ? [...more].reverse() : more)); } } return order;}
/** Swap blocks of one size while that makes the packing better: fewer lines crossed or run over, then shorter lines. */function tidy(blocks: Block[], edges: [string, string][], at: Record<string, Spot>) { let low = score(blocks, edges, at).total; for (let round = 0; round < 6; round++) { let better = false; for (let i = 0; i < blocks.length; i++) for (let j = i + 1; j < blocks.length; j++) { const a = blocks[i], b = blocks[j]; if (a.w !== b.w || a.h !== b.h) continue; [at[a.id], at[b.id]] = [at[b.id], at[a.id]]; const s = score(blocks, edges, at).total; if (s < low - 1e-6) { low = s; better = true; } else [at[a.id], at[b.id]] = [at[b.id], at[a.id]]; } if (!better) break; } return at;}
const box = (blocks: Block[], at: Record<string, Spot>) => ({ x0: Math.min(...blocks.map(b => at[b.id][0])), y0: Math.min(...blocks.map(b => at[b.id][1])), x1: Math.max(...blocks.map(b => at[b.id][0] + b.w)), y1: Math.max(...blocks.map(b => at[b.id][1] + b.h)),});
/** Pack the blocks. Each group packs into its own tight box, and the boxes stand in a row with a * wider gap between them: the group `first` is in goes in the middle and the others go either side. * `aspect` is how much wider than tall the whole should come out. Blocks in `keep` stay where they * are in their group and only new ones are placed; with nothing kept, a few orders are tried and * the one with the fewest crossed lines wins. */export function pack(blocks: Block[], edges: [string, string][], first: string, aspect = 1.6, keep: Record<string, Spot> = {}): Record<string, Spot> { if (!blocks.length) return {}; const area = (bs: Block[]) => bs.reduce((s, b) => s + span(b) * COL * (b.h + GAP_Y), 0); const high = Math.max(Math.sqrt(area(blocks) / aspect), ...blocks.map(b => b.h + GAP_Y)); // every group is about this tall const home = blocks.find(b => b.id === first)?.group ?? blocks[0].group; const names = [...new Set(blocks.map(b => b.group))].sort((a, b) => +(b === home) - +(a === home) || a.localeCompare(b)); const out: Record<string, Spot> = {}; let left = 0, right = 0, level = 0; names.forEach((name, i) => { // in one order whatever order they came in, so the same blocks always pack the same way const bs = blocks.filter(b => b.group === name).sort((a, b) => a.id.localeCompare(b.id)); const es = edges.filter(([a, b]) => bs.some(x => x.id === a) && bs.some(x => x.id === b)).map(([a, b]) => (a < b ? [a, b] : [b, a]) as [string, string]).sort((p, q) => `${p}`.localeCompare(`${q}`)); const wide = Math.max(...bs.map(span), Math.round(area(bs) / high / COL)), start = name === home ? first : ''; const kept = bs.filter(b => keep[b.id]); let at: Record<string, Spot> | null = null; if (kept.length) { // carry on from where its blocks are: put the middle of them at the middle // the group may have slid as a whole, so its columns are read off one of its own blocks const k = box(kept, keep), edge = keep[kept[0].id][0] - (span(kept[0]) * COL - GAP_X - kept[0].w) / 2; const cx = edge + Math.round(((k.x0 + k.x1) / 2 - edge) / COL) * COL, cy = (k.y0 + k.y1) / 2, was: Record<string, Spot> = {}; for (const b of kept) was[b.id] = [keep[b.id][0] - cx, keep[b.id][1] - cy]; at = place(bs, es, walk(bs, es, start, false, 0), wide, high, was); } else { let low = Infinity; for (let mix = 0; mix < TRIES; mix++) for (const deep of [false, true]) { const tried = place(bs, es, walk(bs, es, start, deep, mix), wide, high, {}), k = box(bs, tried); const s = score(bs, es, tried).total + SPREAD * (k.x1 - k.x0 + k.y1 - k.y0); // and a tight box beats a loose one if (s < low - 1e-6) { low = s; at = tried; } } at = tidy(bs, es, at!); } // the first group stays where it packed; the rest go right, then left, in turn const k = box(bs, at!), mid = (k.y0 + k.y1) / 2; let dx = 0; if (!i) { left = k.x0; right = k.x1; level = mid; } else if (i % 2) { dx = right + GROUP_GAP - k.x0; right = k.x1 + dx; } else { dx = left - GROUP_GAP - k.x1; left = k.x0 + dx; } for (const b of bs) out[b.id] = [at![b.id][0] + dx, at![b.id][1] + (i ? level - mid : 0)]; }); return out;}