1// The viewer is a tilemap with levels of detail. The field is cut into map2// tiles of TILE_PX screen pixels at a discrete raster zoom (pixels per3// cell); each map tile is rasterised once and cached; an event dirties4// only the map tiles whose cells it touches; a frame composes cached map5// tiles at the continuous view scale. Pure logic here (keys, ranges, dirty6// tracking); the raster itself lives in the island.78export const TILE_PX = 256;910/** Raster zooms, in pixels per cell. A view scale s is drawn from the11 * smallest zoom >= s (never upscaled), so the composed image stays sharp. */12export const ZOOMS = [0.25, 0.5, 1, 2, 4, 8, 16, 32, 64] as const;13export type Zoom = (typeof ZOOMS)[number];1415/** Revisions over which a newly known cell's lift fades (the ripple). */16export const RECENCY_REVS = 8;1718/** Level of detail, by raster zoom: territory, shapes, values, lines. */19export type Level = 0 | 1 | 2 | 3;2021export function zoomFor(scale: number): Zoom {22 for (const z of ZOOMS) if (z >= scale) return z;23 return ZOOMS[ZOOMS.length - 1];24}2526/**27 * L0 under 3 px per cell (territory only), L1 from 3 (shapes), L2 from 1228 * (values as discs), L3 from 30 (lines), by the continuous view scale. A29 * cached map tile is keyed by raster zoom and level, so a raster is drawn30 * at exactly one level.31 */32export function levelFor(scale: number): Level {33 if (scale < 3) return 0;34 if (scale < 12) return 1;35 if (scale < 30) return 2;36 return 3;37}3839/** Cells covered by one map tile at a zoom (fractional under 1 px/cell). */40export function cellsPerTile(zoom: number): number {41 return TILE_PX / zoom;42}4344/** Geometry key of a map tile: what the change log tracks. */45export function tileKey(zoom: number, tx: number, ty: number): string {46 return `${zoom}:${tx}:${ty}`;47}4849/** Cache key: the geometry key plus the level the raster was drawn at. */50export function cacheKey(key: string, level: Level): string {51 return `${key}|L${level}`;52}5354export type View = { scale: number; ox: number; oy: number };5556export type MapTile = {57 zoom: Zoom;58 level: Level;59 tx: number;60 ty: number;61 key: string; // geometry key (zoom:tx:ty)62 cacheKey: string; // key plus level63};6465/**66 * Map tiles intersecting a viewport of W x H screen pixels, at the zoom67 * the view scale rasterises from. Row-major; never outside the field.68 */69export function tilesForView(70 G: number,71 view: View,72 W: number,73 H: number,74): MapTile[] {75 const zoom = zoomFor(view.scale);76 const level = levelFor(view.scale);77 const cpt = cellsPerTile(zoom);78 const n = Math.ceil(G / cpt);79 const px = cpt * view.scale; // screen pixels per map tile80 const tx0 = Math.max(0, Math.floor(-view.ox / px));81 const ty0 = Math.max(0, Math.floor(-view.oy / px));82 const tx1 = Math.min(n - 1, Math.floor((W - view.ox) / px));83 const ty1 = Math.min(n - 1, Math.floor((H - view.oy) / px));84 const out: MapTile[] = [];85 for (let ty = ty0; ty <= ty1; ty++) {86 for (let tx = tx0; tx <= tx1; tx++) {87 const key = tileKey(zoom, tx, ty);88 out.push({ zoom, level, tx, ty, key, cacheKey: cacheKey(key, level) });89 }90 }91 return out;92}9394/** Map-tile keys (at every zoom) that contain any of the cells. */95export function keysForCells(96 G: number,97 cells: Iterable<number>,98 zooms: readonly number[] = ZOOMS,99): Set<string> {100 const out = new Set<string>();101 for (const zoom of zooms) {102 const cpt = cellsPerTile(zoom);103 for (const id of cells) {104 const x = id % G, y = Math.floor(id / G);105 out.add(tileKey(zoom, Math.floor(x / cpt), Math.floor(y / cpt)));106 }107 }108 return out;109}110111/**112 * Which map tiles each revision changed, so a cached raster drawn at one113 * revision is known to be valid (or not) at another: it is valid when no114 * change lies in (min(a, b) - RECENCY_REVS, max(a, b)] — the recency115 * window is included because a cell's lift fades over those revisions.116 */117export class ChangeLog {118 private changes = new Map<string, number[]>();119120 add(rev: number, keys: Iterable<string>) {121 for (const k of keys) {122 let list = this.changes.get(k);123 if (!list) {124 list = [];125 this.changes.set(k, list);126 }127 if (list.length === 0 || list[list.length - 1] < rev) list.push(rev);128 }129 }130131 /** True when a raster drawn at `drawn` still shows revision `want`. */132 valid(key: string, drawn: number, want: number): boolean {133 if (drawn === want) return true;134 const list = this.changes.get(key);135 if (!list) return true;136 const lo = Math.min(drawn, want) - RECENCY_REVS;137 const hi = Math.max(drawn, want);138 // first index with rev > lo139 let i = 0, j = list.length;140 while (i < j) {141 const m = (i + j) >> 1;142 if (list[m] > lo) j = m;143 else i = m + 1;144 }145 return !(i < list.length && list[i] <= hi);146 }147148 /** Revisions that touched a key (for tests and the timeline). */149 revisions(key: string): number[] {150 return this.changes.get(key) ?? [];151 }152153 size(): number {154 return this.changes.size;155 }156}157158/** A cache of rasters keyed by map tile, each stamped with the revision it159 * was drawn at. The image type is generic so the logic is testable. */160export class TileCache<T> {161 private entries = new Map<string, { img: T; rev: number }>();162 constructor(readonly limit = 1024) {}163164 /** `key` is the cache key; `geomKey` what the change log is keyed by. */165 get(166 key: string,167 geomKey: string,168 want: number,169 log: ChangeLog,170 ): T | undefined {171 const e = this.entries.get(key);172 if (!e) return undefined;173 if (!log.valid(geomKey, e.rev, want)) return undefined;174 // refresh insertion order (LRU)175 this.entries.delete(key);176 this.entries.set(key, e);177 return e.img;178 }179180 set(key: string, img: T, rev: number) {181 this.entries.delete(key);182 this.entries.set(key, { img, rev });183 while (this.entries.size > this.limit) {184 const oldest = this.entries.keys().next().value as string;185 this.entries.delete(oldest);186 }187 }188189 clear() {190 this.entries.clear();191 }192193 size(): number {194 return this.entries.size;195 }196}197198/** Screen rectangle of a map tile at the view's continuous scale. */199export function tileScreenRect(200 t: MapTile,201 view: View,202): { x: number; y: number; size: number } {203 const px = cellsPerTile(t.zoom) * view.scale;204 return { x: view.ox + t.tx * px, y: view.oy + t.ty * px, size: px };205}206207/** Cell range (inclusive x0..x1, y0..y1) a map tile covers, clipped to G. */208export function tileCellRange(209 t: MapTile,210 G: number,211): { x0: number; y0: number; x1: number; y1: number; cpt: number } {212 const cpt = cellsPerTile(t.zoom);213 const x0 = Math.floor(t.tx * cpt), y0 = Math.floor(t.ty * cpt);214 const x1 = Math.min(G - 1, Math.ceil((t.tx + 1) * cpt) - 1);215 const y1 = Math.min(G - 1, Math.ceil((t.ty + 1) * cpt) - 1);216 return { x0, y0, x1, y1, cpt };217}218219// ---------------------------------------------------------------- field extent220221/** Bounding box (inclusive cells) of a set of tiles; null when empty. */222export type Box = { x0: number; y0: number; x1: number; y1: number };223224export function boxOf(225 tiles: readonly { x0: number; y0: number; w: number; h: number }[],226): Box | null {227 let x0 = Infinity, y0 = Infinity, x1 = -Infinity, y1 = -Infinity;228 for (const t of tiles) {229 // a placeholder (the fogged live view: a tile known only by id) has230 // no shape and frames nothing231 if (t.w <= 0 || t.h <= 0) continue;232 if (t.x0 < x0) x0 = t.x0;233 if (t.y0 < y0) y0 = t.y0;234 if (t.x0 + t.w - 1 > x1) x1 = t.x0 + t.w - 1;235 if (t.y0 + t.h - 1 > y1) y1 = t.y0 + t.h - 1;236 }237 if (x0 === Infinity) return null;238 return { x0, y0, x1, y1 };239}240241/** A view that frames a box (the generated tiles, not the field) in a242 * W x H viewport with a margin. */243export function fitBox(box: Box, W: number, H: number, margin = 0.94): View {244 const bw = box.x1 - box.x0 + 1, bh = box.y1 - box.y0 + 1;245 const scale = Math.min((W * margin) / bw, (H * margin) / bh);246 return {247 scale,248 ox: (W - bw * scale) / 2 - box.x0 * scale,249 oy: (H - bh * scale) / 2 - box.y0 * scale,250 };251}252253/**254 * Which map tiles hold any tile at all, per raster zoom. On a G=1000255 * field with a cluster at the centre most map tiles are empty space; they256 * are neither rasterised nor iterated. Built once per geometry.257 */258export class Occupancy {259 private bits = new Map<number, { n: number; set: Uint8Array }>();260261 constructor(262 G: number,263 tiles: readonly { x0: number; y0: number; w: number; h: number }[],264 zooms: readonly number[] = ZOOMS,265 ) {266 for (const zoom of zooms) {267 const cpt = cellsPerTile(zoom);268 const n = Math.ceil(G / cpt);269 const set = new Uint8Array(n * n);270 for (const t of tiles) {271 const tx0 = Math.floor(t.x0 / cpt), ty0 = Math.floor(t.y0 / cpt);272 const tx1 = Math.floor((t.x0 + t.w - 1) / cpt);273 const ty1 = Math.floor((t.y0 + t.h - 1) / cpt);274 for (let ty = ty0; ty <= ty1; ty++) {275 for (let tx = tx0; tx <= tx1; tx++) set[ty * n + tx] = 1;276 }277 }278 this.bits.set(zoom, { n, set });279 }280 }281282 has(zoom: number, tx: number, ty: number): boolean {283 const b = this.bits.get(zoom);284 if (!b) return true;285 if (tx < 0 || ty < 0 || tx >= b.n || ty >= b.n) return false;286 return b.set[ty * b.n + tx] === 1;287 }288289 /** Occupied map tiles at a zoom (for tests and the perf counter). */290 count(zoom: number): number {291 const b = this.bits.get(zoom);292 if (!b) return 0;293 let c = 0;294 for (const v of b.set) c += v;295 return c;296 }297}298299/** tilesForView restricted to map tiles that hold any tile. */300export function occupiedTilesForView(301 G: number,302 view: View,303 W: number,304 H: number,305 occ: Occupancy | null,306): MapTile[] {307 const all = tilesForView(G, view, W, H);308 if (!occ) return all;309 return all.filter((t) => occ.has(t.zoom, t.tx, t.ty));310}311312/** Cells covered by tiles given only their shapes (a `grow` event lists313 * the new tiles before any geometry has them). */314export function cellsOfTiles(315 G: number,316 tiles: readonly {317 x0: number;318 y0: number;319 w: number;320 h: number;321 rects: readonly (readonly [number, number, number, number])[];322 }[],323): number[] {324 const out: number[] = [];325 for (const t of tiles) {326 const seen = new Set<number>();327 for (const [lx, ly, rw, rh] of t.rects) {328 for (let y = ly; y < ly + rh; y++) {329 for (let x = lx; x < lx + rw; x++) {330 const id = (t.y0 + y) * G + t.x0 + x;331 if (!seen.has(id)) {332 seen.add(id);333 out.push(id);334 }335 }336 }337 }338 }339 return out;340}341342/**343 * Cells an event touched, for dirtying map tiles. `geo` is the fullest344 * geometry known (a reveal of a tile that only exists after a grow still345 * resolves); a `grow` event's cells come from its own tile list.346 */347export function cellsOfEvent(348 ev: { kind: string; [k: string]: unknown },349 geo: { G: number; cellsOf: number[][] } | null,350): number[] {351 if (ev.kind === "grow") {352 const tiles = ev.tiles as Parameters<typeof cellsOfTiles>[1] | undefined;353 return tiles && geo ? cellsOfTiles(geo.G, tiles) : [];354 }355 if (!geo || ev.kind !== "batch") return [];356 const op = ev.op as string;357 if (op === "reveal") return geo.cellsOf[ev.tile as number] ?? [];358 if (op === "commit") {359 const out = (ev.accepted as { id: number }[]).map((c) => c.id);360 for (const t of ev.solved as number[]) out.push(...(geo.cellsOf[t] ?? []));361 return out;362 }363 return (ev.cells as number[]) ?? [];364}