Exact source used by this build. SHA-256: 1f270373ae01e1d6ac3dabed16fe871941dd0aa9a235782a01e380e2c3b67f0f.
1 import type { Area, WorldState } from '../../types';
2 import type { RoutePoint } from './types';
3 const key = (x: number, y: number) => `${x},${y}`;
4 const inside = (x: number, y: number, warp: Area['warps'][number]) => x >= warp.x && x < warp.x + warp.width && y >= warp.y && y < warp.y + warp.height;
5 export function npcWalkable(area: Area, x: number, y: number): boolean {
6 const tx = Math.floor(x), ty = Math.floor(y);
7 return tx >= 0 && ty >= 0 && tx < area.width && ty < area.height && !area.collision[ty * area.width + tx] && !area.tiles[ty * area.width + tx]?.objectId;
8 }
9 /** Deterministic four-neighbour A*, retaining corners for collision-safe rendering. */
10 export function findNpcAreaPath(area: Area, from: { x: number; y: number }, to: { x: number; y: number }, allowedWarpId?: string): RoutePoint[] | null {
11 if (!npcWalkable(area, from.x, from.y) || !npcWalkable(area, to.x, to.y)) return null;
12 const sx = Math.floor(from.x), sy = Math.floor(from.y), tx = Math.floor(to.x), ty = Math.floor(to.y), start = key(sx, sy), goal = key(tx, ty);
13 const open: { x: number; y: number; g: number; f: number }[] = [{ x: sx, y: sy, g: 0, f: Math.abs(tx - sx) + Math.abs(ty - sy) }];
14 const scores = new Map([[start, 0]]), previous = new Map<string, string>();
15 const push = (node: typeof open[number]) => { open.push(node); let at = open.length - 1; while (at > 0) { const parent = Math.floor((at - 1) / 2); if (open[parent]!.f <= node.f) break; open[at] = open[parent]!; at = parent; } open[at] = node; };
16 const pop = () => { const first = open[0]!, last = open.pop()!; if (open.length) { let at = 0; open[0] = last; while (true) { let next = at, left = at * 2 + 1, right = left + 1; if (left < open.length && open[left]!.f < open[next]!.f) next = left; if (right < open.length && open[right]!.f < open[next]!.f) next = right; if (next === at) break; [open[at], open[next]] = [open[next]!, open[at]!]; at = next; } } return first; };
17 while (open.length) {
18 const current = pop(), currentKey = key(current.x, current.y);
19 if (current.g !== scores.get(currentKey)) continue;
20 if (currentKey === goal) {
21 const cells = [goal]; while (cells.at(-1) !== start) cells.push(previous.get(cells.at(-1)!)!);
22 const path = cells.reverse().slice(1).map((cell) => { const [x, y] = cell.split(',').map(Number); return { areaId: area.id, x: x! + .5, y: y! + .5 }; });
23 // Join at the source tile centre before taking grid edges, avoiding diagonal corner cuts.
24 if (path.length && (from.x !== sx + .5 || from.y !== sy + .5)) path.unshift({ areaId: area.id, x: sx + .5, y: sy + .5 });
25 if (!path.length || path.at(-1)!.x !== to.x || path.at(-1)!.y !== to.y) path.push({ areaId: area.id, ...to });
26 return path;
27 }
28 for (const [dx, dy] of [[0, -1], [-1, 0], [1, 0], [0, 1]] as const) {
29 const x = current.x + dx, y = current.y + dy;
30 if (!npcWalkable(area, x + .5, y + .5) || area.warps.some((warp) => warp.id !== allowedWarpId && inside(x + .5, y + .5, warp))) continue;
31 const id = key(x, y), g = current.g + 1;
32 if (g >= (scores.get(id) ?? Infinity)) continue;
33 scores.set(id, g); previous.set(id, currentKey); push({ x, y, g, f: g + Math.abs(x - tx) + Math.abs(y - ty) });
34 }
35 }
36 return null;
37 }
38 /** Search the unlocked warp graph, checking each edge against the collision grid. */
39 export function findNpcRoute(state: WorldState, from: RoutePoint, to: RoutePoint): RoutePoint[] | null {
40 const queue: { point: RoutePoint; path: RoutePoint[]; visited: string[] }[] = [{ point: from, path: [], visited: [from.areaId] }];
41 for (let cursor = 0; cursor < queue.length; cursor++) {
42 const current = queue[cursor]!, area = state.areas[current.point.areaId];
43 if (!area || area.locked) continue;
44 if (area.id === to.areaId) { const path = findNpcAreaPath(area, current.point, to); if (path) return [...current.path, ...path]; }
45 for (const warp of area.warps) {
46 const target = state.areas[warp.targetAreaId];
47 if (warp.locked || !target || target.locked || current.visited.includes(target.id) || !npcWalkable(target, warp.targetX, warp.targetY)) continue;
48 const candidates: { x: number; y: number }[] = [];
49 for (let y = Math.floor(warp.y); y < Math.ceil(warp.y + warp.height); y++) for (let x = Math.floor(warp.x); x < Math.ceil(warp.x + warp.width); x++) if (inside(x + .5, y + .5, warp) && npcWalkable(area, x + .5, y + .5)) candidates.push({ x: x + .5, y: y + .5 });
50 candidates.sort((a, b) => Math.abs(a.x - current.point.x) + Math.abs(a.y - current.point.y) - Math.abs(b.x - current.point.x) - Math.abs(b.y - current.point.y));
51 for (const candidate of candidates) {
52 const path = findNpcAreaPath(area, current.point, candidate, warp.id); if (!path) continue;
53 path[path.length - 1] = { ...path.at(-1)!, warpId: warp.id };
54 const point = { areaId: target.id, x: warp.targetX, y: warp.targetY };
55 queue.push({ point, path: [...current.path, ...path, point], visited: [...current.visited, target.id] }); break;
56 }
57 }
58 }
59 return null;
60 }
61