Something went wrong. Try again.
A video game where you play as a misaligned AI, deceiving and building power. An experiment in spec-driven development. cameron.tngl.io/misaligned
Something went wrong. Try again.
4.6 kB · 87 lines
TypeScript
at main
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788// A grid over the map for drawing: things are filed by the squares their box covers, so what lies on the// screen is found from the squares the screen covers, not by a walk over the whole world. No game rules here.
/** Things filed by box, each in every square its box covers. A thing that covers too many squares (a long * line between far sites) is kept on a short list that every search looks through. */export class Grid<T> { private items: T[] = []; private box: number[] = []; // x0, y0, x1, y1 for each thing private cells = new Map<number, number[]>(); private big: number[] = []; private seen = new Uint32Array(64); private mark = 0; constructor(readonly cell: number, readonly most = 64) {} get size() { return this.items.length; } add(item: T, x0: number, y0: number, x1: number, y1: number) { const i = this.items.length, c = this.cell; this.items.push(item); this.box.push(x0, y0, x1, y1); const cx0 = Math.floor(x0 / c), cy0 = Math.floor(y0 / c), cx1 = Math.floor(x1 / c), cy1 = Math.floor(y1 / c); if ((cx1 - cx0 + 1) * (cy1 - cy0 + 1) > this.most) { this.big.push(i); return; } for (let cx = cx0; cx <= cx1; cx++) for (let cy = cy0; cy <= cy1; cy++) { const k = key(cx, cy), l = this.cells.get(k); if (l) l.push(i); else this.cells.set(k, [i]); } } /** Everything whose box meets this one, in the order it was filed. */ query(x0: number, y0: number, x1: number, y1: number, out: T[] = []): T[] { const c = this.cell, b = this.box, n = this.items.length; if (this.seen.length < n) this.seen = new Uint32Array(Math.max(n, this.seen.length * 2)); const mark = ++this.mark; if (mark === 0xffffffff) { this.seen.fill(0); this.mark = 1; } const hits: number[] = []; const take = (i: number) => { if (this.seen[i] === this.mark) return; this.seen[i] = this.mark; if (b[4 * i + 2] >= x0 && b[4 * i] <= x1 && b[4 * i + 3] >= y0 && b[4 * i + 1] <= y1) hits.push(i); }; const cx0 = Math.floor(x0 / c), cy0 = Math.floor(y0 / c), cx1 = Math.floor(x1 / c), cy1 = Math.floor(y1 / c); if ((cx1 - cx0 + 1) * (cy1 - cy0 + 1) > this.cells.size) for (let i = 0; i < n; i++) take(i); // the box covers more squares than are filled: look at everything else { for (const i of this.big) take(i); for (let cx = cx0; cx <= cx1; cx++) for (let cy = cy0; cy <= cy1; cy++) { const l = this.cells.get(key(cx, cy)); if (l) for (const i of l) take(i); } } hits.sort((p, q) => p - q); for (const i of hits) out.push(this.items[i]); return out; }}const key = (cx: number, cy: number) => (cx + 32768) * 65536 + (cy + 32768);
/** Boxes on the screen that labels must keep off, filed by square so a new label meets only its neighbours. */export class BoxGrid { private cells = new Map<number, number[]>(); private box: number[] = []; private seen = new Uint32Array(64); private mark = 0; private wide: number[] = []; constructor(readonly cell = 64) {} clear() { this.cells.clear(); this.box.length = 0; this.wide.length = 0; } add(b: readonly number[]) { const i = this.box.length / 4, c = this.cell; this.box.push(b[0], b[1], b[2], b[3]); const cx0 = Math.floor(b[0] / c), cy0 = Math.floor(b[1] / c), cx1 = Math.floor(b[2] / c), cy1 = Math.floor(b[3] / c); if ((cx1 - cx0 + 1) * (cy1 - cy0 + 1) > 4096) { this.wide.push(i); return; } // a huge box: every search looks at it for (let cx = cx0; cx <= cx1; cx++) for (let cy = cy0; cy <= cy1; cy++) { const k = key(cx, cy), l = this.cells.get(k); if (l) l.push(i); else this.cells.set(k, [i]); } } /** Does a box overlap any filed one (edges that only touch do not)? */ hits(b: readonly number[]): boolean { const c = this.cell, B = this.box, n = B.length / 4; if (this.seen.length < n) this.seen = new Uint32Array(Math.max(n, this.seen.length * 2)); const mark = ++this.mark; if (mark === 0xffffffff) { this.seen.fill(0); this.mark = 1; } for (const i of this.wide) if (b[0] < B[4 * i + 2] && b[2] > B[4 * i] && b[1] < B[4 * i + 3] && b[3] > B[4 * i + 1]) return true; const cx0 = Math.floor(b[0] / c), cy0 = Math.floor(b[1] / c), cx1 = Math.floor(b[2] / c), cy1 = Math.floor(b[3] / c); for (let cx = cx0; cx <= cx1; cx++) for (let cy = cy0; cy <= cy1; cy++) { const l = this.cells.get(key(cx, cy)); if (l) for (const i of l) { if (this.seen[i] === this.mark) continue; this.seen[i] = this.mark; if (b[0] < B[4 * i + 2] && b[2] > B[4 * i] && b[1] < B[4 * i + 3] && b[3] > B[4 * i + 1]) return true; } } return false; }}