BlueGit

timfa questward

Files

questward / shared / courier / doorwayGraph.js

doorwayGraph.js

doorwayGraph.js 10.2 KiB Download Raw
1/**
2 * Pure doorway-portal graph for courier cross-dimension routing.
3 * Edges are unidirectional (from doorway tile → configured target).
4 */
5
6import { OVERWORLD_ID, normalizeDimensionId } from "../world/dimensions.js";
7import { DEFAULT_WORLD_SETTINGS } from "../protocol/constants.js";
8
9/**
10 * @typedef {{
11 * fromDimensionId: string,
12 * fromTileX: number,
13 * fromTileY: number,
14 * toDimensionId: string,
15 * toTileX: number,
16 * toTileY: number
17 * }} DoorwayEdge
18 */
19
20/**
21 * @typedef {{
22 * kind: "fly" | "portal" | "abstract",
23 * fromDimensionId?: string,
24 * fromX?: number,
25 * fromY?: number,
26 * toDimensionId?: string,
27 * toX?: number,
28 * toY?: number,
29 * distance?: number
30 * }} CourierLeg
31 */
32
33/**
34 * Build a directed doorway graph from scanned doorway tiles.
35 * @param {Array<{
36 * tileX: number,
37 * tileY: number,
38 * dimensionId?: string,
39 * targetDimensionId?: string,
40 * targetTileX?: number,
41 * targetTileY?: number
42 * }>} doorways
43 */
44export function buildDoorwayGraph (doorways)
45{
46 const edges = [];
47 /** @type {Map<string, DoorwayEdge[]>} */
48 const byFromDim = new Map();
49 for (const doorway of doorways ?? [])
50 {
51 const targetRaw = doorway?.targetDimensionId;
52 if (targetRaw == null || String(targetRaw).trim() === "")
53 { continue; }
54 const targetTileX = Number(doorway.targetTileX);
55 const targetTileY = Number(doorway.targetTileY);
56 if (!Number.isFinite(targetTileX) || !Number.isFinite(targetTileY))
57 { continue; }
58 /** @type {DoorwayEdge} */
59 const edge = {
60 fromDimensionId: normalizeDimensionId(doorway.dimensionId ?? OVERWORLD_ID),
61 fromTileX: doorway.tileX | 0,
62 fromTileY: doorway.tileY | 0,
63 toDimensionId: normalizeDimensionId(targetRaw),
64 toTileX: targetTileX | 0,
65 toTileY: targetTileY | 0
66 };
67 edges.push(edge);
68 const list = byFromDim.get(edge.fromDimensionId);
69 if (list)
70 { list.push(edge); }
71 else
72 { byFromDim.set(edge.fromDimensionId, [edge]); }
73 }
74 return { edges, byFromDim };
75}
76
77/**
78 * BFS over dimensions via doorway edges. Returns the doorway edge sequence,
79 * or null if unreachable. Same-dimension yields [].
80 * @param {{ byFromDim: Map<string, DoorwayEdge[]> }} graph
81 * @param {string} fromDimensionId
82 * @param {string} toDimensionId
83 * @returns {DoorwayEdge[] | null}
84 */
85export function findDimensionPath (graph, fromDimensionId, toDimensionId)
86{
87 const fromDim = normalizeDimensionId(fromDimensionId);
88 const toDim = normalizeDimensionId(toDimensionId);
89 if (fromDim === toDim)
90 { return []; }
91 const byFromDim = graph?.byFromDim ?? new Map();
92 const queue = [fromDim];
93 const visited = new Set([fromDim]);
94 /** @type {Map<string, DoorwayEdge>} */
95 const cameVia = new Map();
96 let head = 0;
97 while (head < queue.length)
98 {
99 const current = queue[head++];
100 for (const edge of byFromDim.get(current) ?? [])
101 {
102 const next = edge.toDimensionId;
103 if (visited.has(next))
104 { continue; }
105 visited.add(next);
106 cameVia.set(next, edge);
107 if (next === toDim)
108 {
109 const path = [];
110 let dim = toDim;
111 while (dim !== fromDim)
112 {
113 const via = cameVia.get(dim);
114 if (!via)
115 { return null; }
116 path.push(via);
117 dim = via.fromDimensionId;
118 }
119 path.reverse();
120 return path;
121 }
122 queue.push(next);
123 }
124 }
125 return null;
126}
127
128function flyLeg (fromDimensionId, fromX, fromY, toDimensionId, toX, toY)
129{
130 return {
131 kind: "fly",
132 fromDimensionId: normalizeDimensionId(fromDimensionId),
133 fromX,
134 fromY,
135 toDimensionId: normalizeDimensionId(toDimensionId),
136 toX,
137 toY
138 };
139}
140
141function portalLeg (edge)
142{
143 return {
144 kind: "portal",
145 fromDimensionId: edge.fromDimensionId,
146 fromX: edge.fromTileX + 0.5,
147 fromY: edge.fromTileY + 0.5,
148 toDimensionId: edge.toDimensionId,
149 toX: edge.toTileX + 0.5,
150 toY: edge.toTileY + 0.5
151 };
152}
153
154/**
155 * Plan courier legs from origin to destination using the doorway graph.
156 * Same-dim → single fly. Cross-dim with path → fly/portal/fly….
157 * Cross-dim with no path → { mode: "fallback", legs: null } (caller builds fade legs).
158 */
159export function planPortalLegs ({
160 fromX,
161 fromY,
162 fromDimensionId = OVERWORLD_ID,
163 toX,
164 toY,
165 toDimensionId = OVERWORLD_ID,
166 graph
167})
168{
169 const fromDim = normalizeDimensionId(fromDimensionId);
170 const toDim = normalizeDimensionId(toDimensionId);
171 if (fromDim === toDim)
172 {
173 return {
174 mode: "direct",
175 legs: [flyLeg(fromDim, fromX, fromY, toDim, toX, toY)]
176 };
177 }
178 const doorPath = findDimensionPath(graph, fromDim, toDim);
179 if (!doorPath)
180 {
181 return { mode: "fallback", legs: null };
182 }
183 /** @type {CourierLeg[]} */
184 const legs = [];
185 let cx = fromX;
186 let cy = fromY;
187 let cd = fromDim;
188 for (const edge of doorPath)
189 {
190 const enterX = edge.fromTileX + 0.5;
191 const enterY = edge.fromTileY + 0.5;
192 legs.push(flyLeg(cd, cx, cy, cd, enterX, enterY));
193 legs.push(portalLeg(edge));
194 cx = edge.toTileX + 0.5;
195 cy = edge.toTileY + 0.5;
196 cd = edge.toDimensionId;
197 }
198 legs.push(flyLeg(cd, cx, cy, toDim, toX, toY));
199 return { mode: "portal", legs };
200}
201
202/**
203 * Walk from (x,y) along unit direction until `stop(tileX, tileY)` is true.
204 * Returns the first tile-center where stop is true, or the last sample if never.
205 */
206export function walkUntilStop ({
207 x,
208 y,
209 dirX,
210 dirY,
211 stop,
212 maxSteps = 96,
213 step = 1
214})
215{
216 let px = x;
217 let py = y;
218 const len = Math.hypot(dirX, dirY);
219 const ux = len > 1e-9 ? dirX / len : 1;
220 const uy = len > 1e-9 ? dirY / len : 0;
221 for (let i = 0; i < maxSteps; i++)
222 {
223 px += ux * step;
224 py += uy * step;
225 if (stop(Math.floor(px), Math.floor(py)))
226 { return { x: px, y: py, steps: i + 1 }; }
227 }
228 return { x: px, y: py, steps: maxSteps };
229}
230
231export function estimateAbstractDistance ({
232 fromX,
233 fromY,
234 toX,
235 toY,
236 fadeOutDist = 0,
237 fadeInDist = 0,
238 crossDimension = false
239})
240{
241 const direct = Math.hypot(toX - fromX, toY - fromY);
242 const budget = crossDimension ? Math.max(direct, 32) : direct;
243 return Math.max(0, budget - fadeOutDist - fadeInDist);
244}
245
246/**
247 * Build fade-out → abstract → fade-in legs when no doorway path exists.
248 * `isSimulating(tileX, tileY, dimensionId)` must not force-load regions.
249 */
250export function buildFallbackLegs ({
251 fromX,
252 fromY,
253 fromDimensionId = OVERWORLD_ID,
254 toX,
255 toY,
256 toDimensionId = OVERWORLD_ID,
257 isSimulating,
258 settings = DEFAULT_WORLD_SETTINGS
259})
260{
261 void settings;
262 const fromDim = normalizeDimensionId(fromDimensionId);
263 const toDim = normalizeDimensionId(toDimensionId);
264 const awayX = fromX - toX;
265 const awayY = fromY - toY;
266 const awayLen = Math.hypot(awayX, awayY);
267 const outDirX = awayLen > 1e-9 ? awayX / awayLen : 1;
268 const outDirY = awayLen > 1e-9 ? awayY / awayLen : 0;
269
270 /** @type {CourierLeg[]} */
271 const legs = [];
272 let fadeOutEndX = fromX;
273 let fadeOutEndY = fromY;
274 let fadeOutDist = 0;
275 if (typeof isSimulating === "function"
276 && isSimulating(Math.floor(fromX), Math.floor(fromY), fromDim))
277 {
278 const exit = walkUntilStop({
279 x: fromX,
280 y: fromY,
281 dirX: outDirX,
282 dirY: outDirY,
283 stop: (tx, ty) => !isSimulating(tx, ty, fromDim)
284 });
285 fadeOutEndX = exit.x;
286 fadeOutEndY = exit.y;
287 fadeOutDist = Math.hypot(fadeOutEndX - fromX, fadeOutEndY - fromY);
288 legs.push(flyLeg(fromDim, fromX, fromY, fromDim, fadeOutEndX, fadeOutEndY));
289 }
290
291 const approachX = toX - fromX;
292 const approachY = toY - fromY;
293 const approachLen = Math.hypot(approachX, approachY);
294 const backDirX = approachLen > 1e-9 ? -approachX / approachLen : -1;
295 const backDirY = approachLen > 1e-9 ? -approachY / approachLen : 0;
296
297 let fadeInStartX = toX;
298 let fadeInStartY = toY;
299 let fadeInDist = 0;
300 const destSimulating = typeof isSimulating === "function"
301 && isSimulating(Math.floor(toX), Math.floor(toY), toDim);
302 if (destSimulating)
303 {
304 const entry = walkUntilStop({
305 x: toX,
306 y: toY,
307 dirX: backDirX,
308 dirY: backDirY,
309 stop: (tx, ty) => !isSimulating(tx, ty, toDim)
310 });
311 fadeInStartX = entry.x;
312 fadeInStartY = entry.y;
313 fadeInDist = Math.hypot(toX - fadeInStartX, toY - fadeInStartY);
314 }
315
316 const abstractDistance = estimateAbstractDistance({
317 fromX,
318 fromY,
319 toX,
320 toY,
321 fadeOutDist,
322 fadeInDist,
323 crossDimension: fromDim !== toDim
324 });
325 legs.push({
326 kind: "abstract",
327 fromDimensionId: fromDim,
328 fromX: fadeOutEndX,
329 fromY: fadeOutEndY,
330 toDimensionId: toDim,
331 toX: fadeInStartX,
332 toY: fadeInStartY,
333 distance: abstractDistance
334 });
335 legs.push(flyLeg(toDim, fadeInStartX, fadeInStartY, toDim, toX, toY));
336 return { mode: "fallback", legs };
337}
338
339/**
340 * Advance an abstract (invisible) travel leg at cruise speed.
341 */
342export function advanceAbstractTravel ({
343 traveled,
344 distance,
345 dt,
346 settings = DEFAULT_WORLD_SETTINGS
347})
348{
349 const total = Math.max(0, distance ?? 0);
350 const cruise = Math.max(0.25, settings.pigeonCruiseTilesPerSec ?? 8);
351 if (!(total > 0))
352 {
353 return {
354 traveled: 0,
355 arrived: true,
356 speed: 0,
357 total: 0
358 };
359 }
360 const nextTraveled = Math.min(total, (traveled || 0) + cruise * Math.max(0, dt));
361 return {
362 traveled: nextTraveled,
363 arrived: nextTraveled >= total - 1e-6,
364 speed: cruise,
365 total
366 };
367}
368
369/**
370 * Pose along the current leg given traveled distance.
371 * Abstract legs have no visible pose (returns null).
372 */
373export function poseOnCourierLeg (leg, traveled = 0)
374{
375 if (!leg)
376 { return null; }
377 if (leg.kind === "abstract")
378 { return null; }
379 if (leg.kind === "portal")
380 {
381 return {
382 x: leg.toX,
383 y: leg.toY,
384 dimensionId: normalizeDimensionId(leg.toDimensionId ?? OVERWORLD_ID)
385 };
386 }
387 const fromX = leg.fromX;
388 const fromY = leg.fromY;
389 const toX = leg.toX;
390 const toY = leg.toY;
391 const total = Math.hypot(toX - fromX, toY - fromY);
392 const t = total < 1e-6 ? 1 : Math.min(1, Math.max(0, (traveled || 0) / total));
393 return {
394 x: fromX + (toX - fromX) * t,
395 y: fromY + (toY - fromY) * t,
396 dimensionId: normalizeDimensionId(leg.fromDimensionId ?? OVERWORLD_ID)
397 };
398}
399
400/**
401 * Normalize / migrate a transit's legs. Old rows without legs become a single fly.
402 */
403export function ensureCourierLegs (transit)
404{
405 if (Array.isArray(transit.legs) && transit.legs.length > 0)
406 {
407 transit.legIndex = Math.max(0, Math.min(transit.legIndex | 0, transit.legs.length - 1));
408 return transit;
409 }
410 const fromDim = normalizeDimensionId(transit.originDimensionId ?? OVERWORLD_ID);
411 const toDim = normalizeDimensionId(transit.destDimensionId ?? OVERWORLD_ID);
412 transit.legs = [flyLeg(
413 fromDim,
414 transit.originX,
415 transit.originY,
416 toDim,
417 transit.destX,
418 transit.destY
419 )];
420 transit.legIndex = 0;
421 transit.originDimensionId = fromDim;
422 transit.destDimensionId = toDim;
423 return transit;
424}