Next-Passage / core.js
Lamapi's picture
Publish Next-Passage space
8e11959 verified
Raw History Blame Contribute Delete
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 };
});