Spaces:
Running
Running
Download core.js from thelamapi/Next-Passage: direct link, hf CLI and curl.
- Browser
- Download file 10.8 kB
-
https://huggingface.co/spaces/thelamapi/Next-Passage/resolve/main/core.js
- Command line
-
hf download hf://spaces/thelamapi/Next-Passage/core.js
-
curl -L -o core.js https://huggingface.co/spaces/thelamapi/Next-Passage/resolve/main/core.js
10.8 kB
| /* 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 }; | |
| }); | |