/* Next Passage compute core: line-by-line port of passage_core.py. Cells are keyed as y*W+x. */ (function (root, factory) { if (typeof module === "object" && module.exports) module.exports = factory(); else root.Core = factory(); })(typeof self !== "undefined" ? self : this, function () { "use strict"; const W = 21, H = 15, MOVES = [[0, 0], [1, 0], [-1, 0], [0, 1], [0, -1]], DENSITY = { low: 3, medium: 6, high: 10 }; const ASSETS = ["model.json"]; const K = (x, y) => y * W + x; function less(a, b) { for (let i = 0; i < 3; i++) { if (a[i] < b[i]) return true; if (a[i] > b[i]) return false; } return false; } class Heap { constructor() { this.a = []; } push(it) { const a = this.a; a.push(it); let i = a.length - 1; while (i > 0) { const p = (i - 1) >> 1; if (!less(a[i], a[p])) break; [a[p], a[i]] = [a[i], a[p]]; i = p; } } pop() { const a = this.a, top = a[0], last = a.pop(); if (a.length) { a[0] = last; let i = 0; const n = a.length; for (;;) { const l = 2 * i + 1, r = l + 1; let m = i; if (l < n && less(a[l], a[m])) m = l; if (r < n && less(a[r], a[m])) m = r; if (m === i) break; [a[m], a[i]] = [a[i], a[m]]; i = m; } } return top; } get length() { return this.a.length; } } function makeWorld(seed, density, pStall) { density = density || "medium"; pStall = pStall == null ? 0.15 : pStall; const rng = NLRT.mulberry32((seed * 2654435761) % 4294967296); const walls = new Set(); for (let x = 0; x < W; x++) { walls.add(K(x, 0)); walls.add(K(x, H - 1)); } for (let y = 0; y < H; y++) { walls.add(K(0, y)); walls.add(K(W - 1, y)); } const doors = []; for (const wx of [5, 10, 15]) { const gapOpen = 1 + rng.randint(H - 2); let gapDoor = 1 + rng.randint(H - 2); while (Math.abs(gapDoor - gapOpen) < 3) gapDoor = 1 + rng.randint(H - 2); for (let y = 1; y < H - 1; y++) if (y !== gapOpen && y !== gapDoor) walls.add(K(wx, y)); const period = 8 + rng.randint(8); doors.push({ cell: [wx, gapDoor], period, phase: rng.randint(period), closed: Math.max(2, Math.floor(period / 2) - 1 + rng.randint(3)) }); } for (let i = 0; i < 6; i++) { const x = 2 + rng.randint(W - 4), y = 2 + rng.randint(H - 4); if (![4, 5, 6, 9, 10, 11, 14, 15, 16].includes(x)) walls.add(K(x, y)); } const start = [1, 1 + rng.randint(H - 2)], goal = [W - 2, 1 + rng.randint(H - 2)]; walls.delete(K(...start)); walls.delete(K(...goal)); const doorCells = new Set(doors.map(d => K(...d.cell))); const obstacles = [], used = new Set(); let tries = 0; while (obstacles.length < DENSITY[density] && tries < 400) { tries++; const horiz = rng.random() < 0.5, x = 1 + rng.randint(W - 2), y = 1 + rng.randint(H - 2), length = 4 + rng.randint(7); const cells = []; for (let k = 0; k < length; k++) { const c = horiz ? [x + k, y] : [x, y + k]; if (walls.has(K(...c)) || doorCells.has(K(...c)) || used.has(K(...c)) || c[0] >= W - 1 || c[1] >= H - 1 || (c[0] === start[0] && c[1] === start[1]) || (c[0] === goal[0] && c[1] === goal[1])) break; cells.push(c); } if (cells.length < 3) continue; const loop = cells.concat(cells.slice(1, -1).reverse()); cells.forEach(c => used.add(K(...c))); obstacles.push({ loop, offset: rng.randint(loop.length) }); } const wl = Array.from(walls).map(k => [k % W, Math.floor(k / W)]).sort((a, b) => a[0] - b[0] || a[1] - b[1]); return { seed, density, p_stall: pStall, walls: wl, doors, obstacles, start, goal }; } const doorClosed = (d, t) => ((t + d.phase) % d.period) < d.closed; const free = (walls, x, y) => x >= 0 && x < W && y >= 0 && y < H && !walls.has(K(x, y)); function bfs(walls, start, goal, blocked) { blocked = blocked || new Set(); const s = K(...start), g = K(...goal), prev = new Map([[s, -1]]), q = [s]; let qi = 0, expanded = 0; while (qi < q.length) { const c = q[qi++]; expanded++; if (c === g) { const path = []; let n = c; while (n !== -1) { path.push([n % W, Math.floor(n / W)]); n = prev.get(n); } return [path.reverse(), expanded]; } const cx = c % W, cy = Math.floor(c / W); for (let m = 1; m < 5; m++) { const nx = cx + MOVES[m][0], ny = cy + MOVES[m][1], n = K(nx, ny); if (!prev.has(n) && free(walls, nx, ny) && !blocked.has(n)) { prev.set(n, c); q.push(n); } } } return [null, expanded]; } function distanceMap(walls, goal) { const g = K(...goal), dist = new Map([[g, 0]]), q = [g]; let qi = 0; while (qi < q.length) { const c = q[qi++], cx = c % W, cy = Math.floor(c / W); for (let m = 1; m < 5; m++) { const nx = cx + MOVES[m][0], ny = cy + MOVES[m][1], n = K(nx, ny); if (!dist.has(n) && free(walls, nx, ny)) { dist.set(n, dist.get(c) + 1); q.push(n); } } } return dist; } function timedAstar(walls, doors, dist, start, t0, goal, obsIdx, loops, horizon, maxExpand) { horizon = horizon || 160; maxExpand = maxExpand || 60000; const g = K(...goal), doorAt = new Map(doors.map(d => [K(...d.cell), d])); const occupied = t => { const s = new Set(); loops.forEach((L, i) => { for (const tt of [t, t - 1]) if (tt >= t0) s.add(K(...L[(obsIdx[i] + tt - t0) % L.length])); }); return s; }; const occCache = new Map(), s = K(...start); if (!dist.has(s)) return [null, 0]; const heap = new Heap(); let seq = 0; heap.push([dist.get(s), 0, seq, start[0], start[1], t0]); const parent = new Map([[s + "," + t0, null]]); let expanded = 0; while (heap.length && expanded < maxExpand) { const [, , , x, y, t] = heap.pop(); const c = K(x, y); expanded++; if (c === g) { const path = []; let node = [c, t]; while (node !== null) { path.push([node[0] % W, Math.floor(node[0] / W)]); node = parent.get(node[0] + "," + node[1]); } return [path.reverse(), expanded]; } if (t - t0 >= horizon) continue; const nt = t + 1; if (!occCache.has(nt)) occCache.set(nt, occupied(nt)); const occ = occCache.get(nt); for (const [dx, dy] of MOVES) { const nx = x + dx, ny = y + dy, n = K(nx, ny); if (!free(walls, nx, ny) || occ.has(n) || !dist.has(n)) continue; const d = doorAt.get(n); if (d !== undefined && doorClosed(d, nt)) continue; const key = n + "," + nt; if (parent.has(key)) continue; parent.set(key, [c, t]); seq++; const gg = nt - t0; heap.push([gg + dist.get(n), -gg, seq, nx, ny, nt]); } } return [null, expanded]; } function runEpisode(world, planner, maxSteps) { const walls = new Set(world.walls.map(c => K(...c))), doors = world.doors; const doorAt = new Map(doors.map(d => [K(...d.cell), d])); const loops = world.obstacles.map(o => o.loop), idx = world.obstacles.map(o => o.offset % o.loop.length); const dist = distanceMap(walls, world.goal); let [staticPath, nodes] = bfs(walls, world.start, world.goal); maxSteps = maxSteps || 3 * staticPath.length + 60; const rng = NLRT.mulberry32((world.seed * 7 + 3) >>> 0); let pos = world.start.slice(), t = 0; const goalK = K(...world.goal); let plan = staticPath.slice(), planI = 0, replans = 0, collisions = 0, doorHits = 0, hardWaits = 0; let pred = idx.slice(); const trace = [{ t: 0, robot: pos.slice(), obs: loops.map((L, i) => L[idx[i]]) }], events = []; if (planner === "timed") { let n; [plan, n] = timedAstar(walls, doors, dist, pos, 0, world.goal, idx, loops); nodes += n; replans++; planI = 0; } let arrived = null; while (t < maxSteps) { if (K(...pos) === goalK) { arrived = t; break; } const obsNow = new Set(loops.map((L, i) => K(...L[idx[i]]))); let nxt = pos; if (planner === "static" || planner === "reactive") { if (plan !== null && planI + 1 < plan.length) { const cand = plan[planI + 1], d = doorAt.get(K(...cand)); const blocked = obsNow.has(K(...cand)) || (d !== undefined && doorClosed(d, t)); if (!blocked) { nxt = cand; planI++; } else if (planner === "reactive") { const block = new Set(obsNow); doors.forEach(dd => { if (doorClosed(dd, t)) block.add(K(...dd.cell)); }); block.delete(K(...pos)); const [newp, n] = bfs(walls, pos, world.goal, block); nodes += n; replans++; if (newp !== null && newp.length > 1) { plan = newp; planI = 1; nxt = newp[1]; } else hardWaits++; } else hardWaits++; } } else { const deviated = idx.some((v, i) => v !== pred[i]); const invalid = plan === null || planI + 1 >= plan.length; if (deviated || invalid) { let n; [plan, n] = timedAstar(walls, doors, dist, pos, t, world.goal, idx, loops); nodes += n; replans++; planI = 0; pred = idx.slice(); } if (plan !== null && planI + 1 < plan.length) { nxt = plan[planI + 1]; planI++; } else hardWaits++; } const old = loops.map((L, i) => K(...L[idx[i]])); for (let i = 0; i < loops.length; i++) { if (rng.random() >= world.p_stall) idx[i] = (idx[i] + 1) % loops[i].length; pred[i] = (pred[i] + 1) % loops[i].length; } t++; const nw = loops.map((L, i) => K(...L[idx[i]])), nk = K(...nxt), pk = K(...pos); const hit = nw.some((v, i) => v === nk || (old[i] === nk && v === pk)); pos = nxt.slice(); if (hit) { collisions++; events.push({ t, type: "collision", cell: pos.slice() }); } const d = doorAt.get(K(...pos)); if (d !== undefined && doorClosed(d, t)) { doorHits++; events.push({ t, type: "door_closed_on_robot", cell: pos.slice() }); } trace.push({ t, robot: pos.slice(), obs: loops.map((L, i) => L[idx[i]]) }); } if (arrived === null && K(...pos) === goalK) arrived = t; return { arrived: arrived !== null, arrival_time: arrived, collisions, door_hits: doorHits, replans, nodes_expanded: nodes, waits_blocked: hardWaits, static_length: staticPath.length - 1, max_steps: maxSteps, events, trace }; } function runCase(ctx, input) { const world = makeWorld(input.seed, input.density, input.p_stall); const r = runEpisode(world, input.planner); return { world_obstacles: world.obstacles.length, start: world.start, goal: world.goal, arrived: r.arrived, arrival_time: r.arrival_time === null ? -1 : r.arrival_time, collisions: r.collisions, door_hits: r.door_hits, replans: r.replans, nodes_expanded: r.nodes_expanded, final: r.trace[r.trace.length - 1].robot }; } return { ASSETS, init: a => ({ meta: a["model.json"].meta }), W, H, makeWorld, runEpisode, doorClosed, runCase }; });