How would you design Google Maps?

// Maps: slippy-map tile math, Dijkstra vs A* on a road grid, and a reroute after a traffic jam.
let seed = 2024;
function rand() { seed = (seed * 48271) % 2147483647; return seed / 2147483647; }

function tile(lat, lon, z) {
  const n = 2 ** z, r = lat * Math.PI / 180;
  return [Math.floor((lon + 180) / 360 * n), Math.floor((1 - Math.log(Math.tan(r) + 1 / Math.cos(r)) / Math.PI) / 2 * n)];
}
for (const z of [0, 10, 15]) { const [x, y] = tile(51.5074, -0.1278, z); console.log("London at zoom " + z + " -> tile " + z + "/" + x + "/" + y); }
let total = 0;
for (let z = 0; z <= 18; z++) { total += 4 ** z; if (z === 10 || z === 14 || z === 18) console.log("tiles at zoom " + z + ": " + 4 ** z + ", cumulative 0.." + z + ": " + total); }

// Road grid: SIZE x SIZE intersections, each road segment takes 20..60 seconds to drive.
const SIZE = 40, MIN_EDGE = 20;
const cost = new Map(); // "a-b" with a < b -> seconds
function key(a, b) { return a < b ? a + "-" + b : b + "-" + a; }
for (let r = 0; r < SIZE; r++) for (let c = 0; c < SIZE; c++) {
  const id = r * SIZE + c;
  if (c + 1 < SIZE) cost.set(key(id, id + 1), 20 + Math.floor(rand() * 41));
  if (r + 1 < SIZE) cost.set(key(id, id + SIZE), 20 + Math.floor(rand() * 41));
}
function nbrs(id) {
  const r = Math.floor(id / SIZE), c = id % SIZE, out = [];
  if (r > 0) out.push(id - SIZE); if (c > 0) out.push(id - 1); if (c + 1 < SIZE) out.push(id + 1); if (r + 1 < SIZE) out.push(id + SIZE);
  return out;
}
function less(a, b) { return a[0] < b[0] || (a[0] === b[0] && a[1] < b[1]); }
function heapPush(h, e) { h.push(e); let i = h.length - 1; while (i > 0) { const p = (i - 1) >> 1; if (!less(h[i], h[p])) break; [h[i], h[p]] = [h[p], h[i]]; i = p; } }
function heapPop(h) {
  const top = h[0], last = h.pop();
  if (h.length) { h[0] = last; let i = 0; for (;;) { const l = 2 * i + 1, r = l + 1; let m = i; if (l < h.length && less(h[l], h[m])) m = l; if (r < h.length && less(h[r], h[m])) m = r; if (m === i) break; [h[i], h[m]] = [h[m], h[i]]; i = m; } }
  return top;
}
function route(src, dst, useHeuristic) {
  const h = (id) => useHeuristic ? MIN_EDGE * (Math.abs(Math.floor(id / SIZE) - Math.floor(dst / SIZE)) + Math.abs(id % SIZE - dst % SIZE)) : 0;
  const dist = new Array(SIZE * SIZE).fill(Infinity), prev = new Array(SIZE * SIZE).fill(-1), done = new Array(SIZE * SIZE).fill(false);
  const heap = []; dist[src] = 0; heapPush(heap, [h(src), src]); let settled = 0;
  while (heap.length) {
    const [, u] = heapPop(heap);
    if (done[u]) continue;
    done[u] = true; settled++;
    if (u === dst) break;
    for (const v of nbrs(u)) {
      const g = dist[u] + cost.get(key(u, v));
      if (g < dist[v]) { dist[v] = g; prev[v] = u; heapPush(heap, [g + h(v), v]); }
    }
  }
  const path = []; for (let v = dst; v !== -1; v = prev[v]) path.unshift(v);
  return { eta: dist[dst], settled, path };
}
function pathCost(path) { let s = 0; for (let i = 1; i < path.length; i++) s += cost.get(key(path[i - 1], path[i])); return s; }
function fmt(sec) { return Math.floor(sec / 60) + " min " + (sec % 60) + " s"; }

const src = 5 * SIZE + 5, dst = 20 * SIZE + 30;
console.log("graph: " + SIZE * SIZE + " intersections, " + cost.size + " road segments; route (5,5) -> (20,30)");
const d = route(src, dst, false), a = route(src, dst, true);
console.log("Dijkstra: eta " + fmt(d.eta) + ", " + d.path.length + " intersections on path, settled " + d.settled + " nodes");
console.log("A*:       eta " + fmt(a.eta) + ", " + a.path.length + " intersections on path, settled " + a.settled + " nodes");

// Live traffic: the 6 segments in the middle of the chosen route become 5x slower.
const mid = Math.floor(a.path.length / 2);
for (let i = mid - 3; i < mid + 3; i++) cost.set(key(a.path[i], a.path[i + 1]), cost.get(key(a.path[i], a.path[i + 1])) * 5);
console.log("jam on 6 segments: old route now takes " + fmt(pathCost(a.path)));
const re = route(src, dst, true);
let shared = 0; for (const v of re.path) if (a.path.includes(v)) shared++;
console.log("reroute with A*: eta " + fmt(re.eta) + ", shares " + shared + " of " + re.path.length + " intersections with the old route, settled " + re.settled + " nodes");