1// The geohash cell system, in its two modes.2//3// SYNTHETIC. On a ground that is only a picture — a game map, a sphere's4// raster — geohash is recursive halving in world pixels: thirty-two children5// to a cell, addresses that refine by appending a character. It divides any6// ground at all, because it never asks what the picture is of. On a PLANE it7// halves the world square itself (`geohashExtent` below), so the grid covers8// the full map and stays put across lens switches; on a sphere it halves the9// declared surface, exactly as it always has.10//11// REAL. A plane that declares an earth Mercator window and says its body is12// earth (bend-or) is a picture OF somewhere, and its geohashes are the real13// ones: the classic WGS84 arithmetic — longitude first, five bits to a14// character, the same alphabet, run in degrees — with the cells put on the15// picture through the declared flattening. The window is city-sized, so the16// telescope's three layers start at the depth whose cells first fit the17// window (`baseDepth`) rather than at one character.18//19// The halving itself is arithmetic the vectors gate compares byte for byte,20// so nothing about how it is written here may move a float: the mask walk,21// the axis alternation and the order of the two divisions are the recorded22// behaviour, in both modes.2324import type { CellID, CellLabel, GroundedCellSystem, LocatedCell, Pole, Ring } from "./contract.ts";25import type { CellSystem } from "./contract.ts";26import type { Coordinate, Extent, Ground } from "./ground.ts";27import { surfaceExtent } from "./ground.ts";28import { palette } from "./tokens.ts";29import { mercatorMapping, mercatorWindow, worldSurface } from "../semconv/geometry.ts";30import type { GeoMapping, World } from "../semconv/geometry.ts";31import { KEY_GEOMETRY_BODY } from "../semconv/keys.ts";3233/**34 * The alphabet, in its canonical order — no `a`, `i`, `l` or `o`, so a hash35 * read aloud or typed from a screenshot cannot be misheard. It is the real36 * geohash alphabet in the real order, which is what lets the same characters37 * name real ground when the world is anchored to it.38 */39export const geohashAlphabet = "0123456789bcdefghjkmnpqrstuvwxyz";4041/**42 * The synthetic telescope's floor. Three characters is fifteen halvings — a43 * cell a few world pixels across on an 8192 square — which is depth enough44 * for a couple thousand pins and shallow enough that every level stays a45 * place. On an earth-anchored ground the floor is deeper and the ground's46 * own: ask {@link geohashDepth}.47 */48export const geohashMaxDepth = 3;4950/**51 * The telescope is three layers of precision on every ground: the base52 * depth's cells, their children, and theirs. Level counts layers — the root53 * is 0 whether its children are one character (synthetic) or four (bend-or).54 */55const geohashLayers = 3;5657/** The five bits of one character, most significant first. */58const masks = [16, 8, 4, 2, 1] as const;5960/**61 * The ground geohash divides, which since Part 1 of the plane ruling is NOT62 * always `surfaceExtent`: a game map's grid must cover the full map and stay63 * put across lens switches, and two lenses of one world may declare64 * different surfaces. So on a PLANE with no earth anchoring, geohash divides65 * the whole world square `[0, -size, size, 0]` whenever the volume declares66 * one, and only a ground with no volume at all falls back to the surface67 * ladder. Spheres keep the ladder — their surface is the body's own picture —68 * and every other consumer of `surfaceExtent` (S2, the ground questions)69 * keeps it too.70 */71export function geohashExtent(ground: Ground): Extent {72 if (worldSurface(ground.world) !== "plane") return surfaceExtent(ground);73 const size = ground.tileGridSize;74 if (size === null) return surfaceExtent(ground);75 return [0, -size, size, 0];76}7778// ---------------------------------------------------------------------------79// The synthetic halving80// ---------------------------------------------------------------------------8182/**83 * The recursive halving itself: alternate axes, five bits to a character.84 *85 * A character outside the alphabet is skipped without consuming a halving —86 * the axis does not alternate past it — which is what the field's own87 * normalization makes unreachable and what this keeps true anyway.88 */89function bbox(ground: Ground, hash: CellID): Extent {90 const extent: [number, number, number, number] = [...geohashExtent(ground)];91 let splitX = true;92 for (const character of hash) {93 const value = geohashAlphabet.indexOf(character);94 if (value < 0) continue;95 for (const mask of masks) {96 if (splitX) {97 const middle = (extent[0] + extent[2]) / 2;98 if (value & mask) extent[0] = middle;99 else extent[2] = middle;100 } else {101 const middle = (extent[1] + extent[3]) / 2;102 if (value & mask) extent[1] = middle;103 else extent[3] = middle;104 }105 splitX = !splitX;106 }107 }108 return extent;109}110111/**112 * The halving run backward: the same divisions, choosing at each one the side113 * the point is on. Computed when asked rather than stored, because a hash114 * stored beside a location could only ever be right for one ground.115 *116 * A point off the surface names nothing.117 */118function cellAt(ground: Ground, coordinate: Coordinate, depth: number): CellID {119 const extent: [number, number, number, number] = [...geohashExtent(ground)];120 const [x, y] = coordinate;121 if (x < extent[0] || x > extent[2] || y < extent[1] || y > extent[3]) return "";122 let splitX = true;123 let hash = "";124 for (let level = 0; level < depth; level++) {125 let value = 0;126 for (const mask of masks) {127 if (splitX) {128 const middle = (extent[0] + extent[2]) / 2;129 if (x >= middle) {130 value |= mask;131 extent[0] = middle;132 } else {133 extent[2] = middle;134 }135 } else {136 const middle = (extent[1] + extent[3]) / 2;137 if (y >= middle) {138 value |= mask;139 extent[1] = middle;140 } else {141 extent[3] = middle;142 }143 }144 splitX = !splitX;145 }146 // `value` is five bits, so the alphabet always has the character; the147 // fallback is what `noUncheckedIndexedAccess` costs and it never fires.148 hash += geohashAlphabet[value] ?? "";149 }150 return hash;151}152153/**154 * The ordinal of a hash's last character. The root — and any hash ending in a155 * character the alphabet does not carry — is ordinal 0.156 */157function ordinal(id: CellID): number {158 return Math.max(0, geohashAlphabet.indexOf(id.slice(-1)));159}160161/**162 * One remembered box. Callers sweep thousands of pins against one cell at a163 * time, so the last cell's extent is kept rather than re-halved per pin. It is164 * a cache over a pure function and nothing observes it: the key carries the165 * ground as well as the id, because a ground switch moves every box.166 */167let memo: { key: string; extent: Extent } | null = null;168169function cachedBox(ground: Ground, id: CellID): Extent {170 const key = `${geohashExtent(ground).join(",")}|${id}`;171 if (memo?.key !== key) memo = { key, extent: bbox(ground, id) };172 return memo.extent;173}174175// ---------------------------------------------------------------------------176// The real mode: classic WGS84 geohash through the declared window177// ---------------------------------------------------------------------------178179/** One degree rectangle: a geohash cell's own ground. */180interface DegreeBox {181 readonly west: number;182 readonly south: number;183 readonly east: number;184 readonly north: number;185}186187/** An earth-anchored ground, read once per world. */188interface RealGround {189 readonly mapping: GeoMapping;190 /** The declared window's ground, west/north/east/south degrees. */191 readonly window: DegreeBox;192 /** The smallest depth whose cells fit the window on either axis. */193 readonly baseDepth: number;194 /** The base-depth cells that intersect the window, in reading order. */195 roots?: CellID[];196}197198/**199 * Real mode's condition, whole: a PLANE (a sphere's geohash is the synthetic200 * one over its picture), an invertible Mercator window, and a world that says201 * the body pictured is earth — mars is a sphere and carries no earth body, so202 * nothing here so much as looks at it.203 */204const realGrounds = new WeakMap<World, RealGround | null>();205206function realGroundOf(ground: Ground): RealGround | null {207 const world = ground.world;208 const held = realGrounds.get(world);209 if (held !== undefined) return held;210 let fresh: RealGround | null = null;211 if (worldSurface(world) === "plane" && world.attrs[KEY_GEOMETRY_BODY] === "earth") {212 const mapping = mercatorMapping(world);213 const declared = mercatorWindow(world);214 if (mapping && declared) {215 const [west, north, east, south] = declared.deg;216 const window: DegreeBox = { west, south, east, north };217 fresh = { mapping, window, baseDepth: baseDepthOf(window) };218 }219 }220 realGrounds.set(world, fresh);221 return fresh;222}223224/**225 * A depth's cell spans, exact. Five bits alternate starting with longitude,226 * so `d` characters split longitude `ceil(5d/2)` times and latitude227 * `floor(5d/2)` — every span is 360° or 180° over a power of two, which a228 * double carries without rounding.229 */230function cellSpans(depth: number): { lng: number; lat: number } {231 const bits = 5 * depth;232 return {233 lng: 360 / 2 ** Math.ceil(bits / 2),234 lat: 180 / 2 ** Math.floor(bits / 2),235 };236}237238/**239 * The smallest depth ≥ 1 at which a cell's longitude span fits the window's240 * OR its latitude span does, capped at 9. Depth 1 is a hemisphere-sized cell241 * and depth 3 would swallow a city whole; for bend-or's window242 * (0.32909° × 0.23650°) this is 4, because the depth-4 latitude span243 * (0.17578125°) fits where the longitude span (0.3515625°) just misses.244 */245function baseDepthOf(window: DegreeBox): number {246 const lngSpan = window.east - window.west;247 const latSpan = window.north - window.south;248 for (let depth = 1; depth < 9; depth++) {249 const spans = cellSpans(depth);250 if (spans.lng <= lngSpan || spans.lat <= latSpan) return depth;251 }252 return 9;253}254255/** The classic mask walk, forward: a hash to its degree rectangle. */256function degreeBox(hash: CellID): DegreeBox {257 const lng: [number, number] = [-180, 180];258 const lat: [number, number] = [-90, 90];259 let splitLng = true;260 for (const character of hash) {261 const value = geohashAlphabet.indexOf(character);262 if (value < 0) continue;263 for (const mask of masks) {264 if (splitLng) {265 const middle = (lng[0] + lng[1]) / 2;266 if (value & mask) lng[0] = middle;267 else lng[1] = middle;268 } else {269 const middle = (lat[0] + lat[1]) / 2;270 if (value & mask) lat[0] = middle;271 else lat[1] = middle;272 }273 splitLng = !splitLng;274 }275 }276 return { west: lng[0], south: lat[0], east: lng[1], north: lat[1] };277}278279/** The classic mask walk, backward: true degrees to a hash. */280function encodeLatLng(lat: number, lng: number, depth: number): CellID {281 const lngRange: [number, number] = [-180, 180];282 const latRange: [number, number] = [-90, 90];283 let splitLng = true;284 let hash = "";285 for (let level = 0; level < depth; level++) {286 let value = 0;287 for (const mask of masks) {288 if (splitLng) {289 const middle = (lngRange[0] + lngRange[1]) / 2;290 if (lng >= middle) {291 value |= mask;292 lngRange[0] = middle;293 } else {294 lngRange[1] = middle;295 }296 } else {297 const middle = (latRange[0] + latRange[1]) / 2;298 if (lat >= middle) {299 value |= mask;300 latRange[0] = middle;301 } else {302 latRange[1] = middle;303 }304 }305 splitLng = !splitLng;306 }307 hash += geohashAlphabet[value] ?? "";308 }309 return hash;310}311312/**313 * The real address under a point, at any depth. A point outside the declared314 * window still HAS a real geohash — the ground is real earth and every point315 * of the picture's plane is somewhere on it — so nothing here refuses.316 */317function realCellAt(real: RealGround, coordinate: Coordinate, depth: number): CellID {318 const [lat, lng] = real.mapping.toLatLng(coordinate[0], -coordinate[1]);319 return encodeLatLng(lat, lng, depth);320}321322/**323 * A real cell's rectangle in world pixels, through the declared flattening.324 * Mercator keeps latitude lines horizontal, so the cell stays a world-pixel325 * rectangle and its four corners are two: the south-west and the north-east.326 * `toWorld` answers y-down pixels; the lane speaks y negative-down, and the327 * sign flips here, at the one call where the conventions meet.328 */329function realExtent(real: RealGround, box: DegreeBox): Extent {330 const [minimumX, bottom] = real.mapping.toWorld(box.south, box.west);331 const [maximumX, top] = real.mapping.toWorld(box.north, box.east);332 return [minimumX, -bottom, maximumX, -top];333}334335/**336 * Whether a cell's ground and the window share any real area. Strict on337 * every edge: a cell that only touches the window's boundary pictures none338 * of it, and enumerating it would draw a rectangle with nothing inside.339 */340function intersectsWindow(box: DegreeBox, window: DegreeBox): boolean {341 return box.west < window.east && box.east > window.west &&342 box.south < window.north && box.north > window.south;343}344345/**346 * The base-depth cells that intersect the window, in reading order: north to347 * south, west to east — a 2×3-ish handful for a city window. These are the348 * root's children and the whole of the root plan.349 */350function rootsOf(real: RealGround): CellID[] {351 if (real.roots) return real.roots;352 const spans = cellSpans(real.baseDepth);353 const window = real.window;354 const firstColumn = Math.floor((window.west + 180) / spans.lng);355 const lastColumn = Math.floor((window.east + 180) / spans.lng);356 const firstRow = Math.floor((window.south + 90) / spans.lat);357 const lastRow = Math.floor((window.north + 90) / spans.lat);358 const roots: CellID[] = [];359 for (let row = lastRow; row >= firstRow; row--) {360 for (let column = firstColumn; column <= lastColumn; column++) {361 const box: DegreeBox = {362 west: -180 + column * spans.lng,363 east: -180 + (column + 1) * spans.lng,364 south: -90 + row * spans.lat,365 north: -90 + (row + 1) * spans.lat,366 };367 if (!intersectsWindow(box, window)) continue;368 // The cell's centre is exactly inside it, so the walk back lands on it.369 roots.push(encodeLatLng(370 (box.south + box.north) / 2,371 (box.west + box.east) / 2,372 real.baseDepth,373 ));374 }375 }376 real.roots = roots;377 return roots;378}379380/** Geohash on real earth, bound to one anchored ground. */381function realGrounded(ground: Ground, real: RealGround): GroundedCellSystem {382 const base = real.baseDepth;383 // The PLAN only enumerates cells that intersect the window — the grid is384 // the window's even though the addresses are the planet's — and the plan385 // asks `children`, so the filter lives here. Order is the alphabet's, which386 // is the synthetic child order and the palette order.387 const children = (id: CellID): CellID[] => {388 if (id === "") return [...rootsOf(real)];389 return [...geohashAlphabet]390 .map((character) => id + character)391 .filter((child) => intersectsWindow(degreeBox(child), real.window));392 };393 // The sibling ordinal is the position among the WINDOW'S siblings, the way394 // S2's is a child position: with absent siblings filtered out, the last395 // character's own ordinal would leave holes in the palette walk.396 const childIndex = (id: CellID): number => {397 if (id === "") return 0;398 return Math.max(0, children(id.length <= base ? "" : id.slice(0, -1)).indexOf(id));399 };400 const box = (id: CellID): Extent => {401 if (id !== "") return realExtent(real, degreeBox(id));402 // The root is the whole of what the plan can show: the union of its own403 // children's rectangles, overhang and all.404 let union: [number, number, number, number] | null = null;405 for (const root of rootsOf(real)) {406 const extent = realExtent(real, degreeBox(root));407 union = union === null408 ? [...extent]409 : [410 Math.min(union[0], extent[0]),411 Math.min(union[1], extent[1]),412 Math.max(union[2], extent[2]),413 Math.max(union[3], extent[3]),414 ];415 }416 return union ?? surfaceExtent(ground);417 };418 return {419 // Level counts layers, not characters: the root's children are base-depth420 // cells, and the telescope is three layers on every ground.421 level(id: CellID): number {422 return id === "" ? 0 : id.length - base + 1;423 },424425 parent(id: CellID): CellID {426 return id.length <= base ? "" : id.slice(0, -1);427 },428429 children,430 childIndex,431432 contains(id: CellID, at: Coordinate): boolean {433 if (id === "") return true;434 const cell = degreeBox(id);435 const [lat, lng] = real.mapping.toLatLng(at[0], -at[1]);436 return lng >= cell.west && lng <= cell.east && lat >= cell.south && lat <= cell.north;437 },438439 descendTarget(id: CellID, at: Coordinate): CellID {440 return realCellAt(real, at, id === "" ? base : id.length + 1);441 },442443 bbox: box,444445 center(id: CellID): Coordinate {446 const extent = box(id);447 return [(extent[0] + extent[2]) / 2, (extent[1] + extent[3]) / 2];448 },449450 ring(id: CellID): Ring {451 const [minimumX, minimumY, maximumX, maximumY] = box(id);452 return [453 [minimumX, minimumY],454 [minimumX, maximumY],455 [maximumX, maximumY],456 [maximumX, minimumY],457 [minimumX, minimumY],458 ];459 },460461 // A city window pictures no pole, and a Mercator window cannot.462 poleContained(): Pole | null {463 return null;464 },465466 label(id: CellID): CellLabel {467 return { context: id.slice(0, -1), principal: id.slice(-1) };468 },469470 colorKey(id: CellID): number {471 return childIndex(id) % palette.length;472 },473474 normalizeInput(text: string): string {475 return [...text.toLocaleLowerCase()]476 .filter((character) => geohashAlphabet.includes(character))477 .slice(0, base + 2)478 .join("");479 },480481 // Whole or nothing: a real address is at least base-depth characters —482 // anything shorter names a cell the window's grid never shows, so it is a483 // draft the field holds while the session stays put. The root is a place.484 parseInput(text: string): CellID | null {485 if (text === "") return "";486 return text.length < base ? null : text;487 },488489 locate(at: Coordinate): LocatedCell | null {490 return { label: "Geohash", value: realCellAt(real, at, base + 2) };491 },492 };493}494495// ---------------------------------------------------------------------------496// The ground-aware contract497// ---------------------------------------------------------------------------498499/**500 * The depth the base layer starts at: 1 on a synthetic ground, the window's501 * own {@link baseDepthOf} on an earth-anchored one (4 for bend-or).502 */503export function geohashBaseDepth(ground: Ground): number {504 return realGroundOf(ground)?.baseDepth ?? 1;505}506507/**508 * The hash-length floor of this ground's telescope — the depth `locate`509 * answers at and the length the navigator's field accepts. Always the base510 * depth plus two: three layers of precision, wherever the layers start511 * (3 on a synthetic ground, 6 for bend-or).512 */513export function geohashDepth(ground: Ground): number {514 return geohashBaseDepth(ground) + 2;515}516517/**518 * The pin card's fixed-depth address, independent of where the grid stands.519 * The one caller that names a depth of its own.520 */521export function geohashCellAt(522 ground: Ground,523 coordinate: Coordinate,524 depth: number = geohashDepth(ground),525): CellID {526 const real = realGroundOf(ground);527 if (real) return realCellAt(real, coordinate, depth);528 return cellAt(ground, coordinate, depth);529}530531/** Geohash, bound to one synthetic ground. */532function grounded(ground: Ground): GroundedCellSystem {533 const real = realGroundOf(ground);534 if (real) return realGrounded(ground, real);535 return {536 level(id: CellID): number {537 return id.length;538 },539540 parent(id: CellID): CellID {541 return id.slice(0, -1);542 },543544 children(id: CellID): CellID[] {545 return [...geohashAlphabet].map((character) => id + character);546 },547548 childIndex(id: CellID): number {549 return ordinal(id);550 },551552 contains(id: CellID, at: Coordinate): boolean {553 const extent = cachedBox(ground, id);554 const [x, y] = at;555 return x >= extent[0] && x <= extent[2] && y >= extent[1] && y <= extent[3];556 },557558 descendTarget(id: CellID, at: Coordinate): CellID {559 return cellAt(ground, at, id.length + 1);560 },561562 bbox(id: CellID): Extent {563 return bbox(ground, id);564 },565566 center(id: CellID): Coordinate {567 const extent = bbox(ground, id);568 return [(extent[0] + extent[2]) / 2, (extent[1] + extent[3]) / 2];569 },570571 ring(id: CellID): Ring {572 const [minimumX, minimumY, maximumX, maximumY] = bbox(ground, id);573 return [574 [minimumX, minimumY],575 [minimumX, maximumY],576 [maximumX, maximumY],577 [maximumX, minimumY],578 [minimumX, minimumY],579 ];580 },581582 // A halved rectangle on a flat picture circles nothing.583 poleContained(): Pole | null {584 return null;585 },586587 label(id: CellID): CellLabel {588 return { context: id.slice(0, -1), principal: id.slice(-1) };589 },590591 colorKey(id: CellID): number {592 return ordinal(id) % palette.length;593 },594595 normalizeInput(text: string): string {596 return [...text.toLocaleLowerCase()]597 .filter((character) => geohashAlphabet.includes(character))598 .slice(0, geohashMaxDepth)599 .join("");600 },601602 // Every normalized spelling is a place — the empty string is the root —603 // so parsing never refuses.604 parseInput(text: string): CellID | null {605 return text;606 },607608 locate(at: Coordinate): LocatedCell | null {609 const value = cellAt(ground, at, geohashMaxDepth);610 return value ? { label: "Geohash", value } : null;611 },612 };613}614615export const geohashSystem: CellSystem = {616 slug: "geohash",617 name: "Geohash",618 short: "G",619620 // Geohash divides anything: it never asks what the picture is of.621 appliesTo(): boolean {622 return true;623 },624625 // Three layers of precision on every ground; only where they START moves.626 maxLevel(): number {627 return geohashLayers;628 },629630 // The field takes a whole address at the floor: three characters on a631 // synthetic ground, six on bend-or. internal/app/grid.go answers the same632 // ground-aware number, so the navigator's maxlength follows.633 inputLength(ground: Ground): number {634 return geohashDepth(ground);635 },636637 on: grounded,638};