import { CHUNK_SIZE } from "../../../shared/protocol/constants.js"; import { tileToChunk, tileToLocal } from "../world/coordinates.js"; class MinHeap { constructor () { this.items = []; } push (node) { this.items.push(node); this.#siftUp(this.items.length - 1); } pop () { if (this.items.length === 0) { return null; } const root = this.items[0]; const last = this.items.pop(); if (this.items.length > 0) { this.items[0] = last; this.#siftDown(0); } return root; } get size () { return this.items.length; } #siftUp (index) { while (index > 0) { const parent = (index - 1) >> 1; if (this.items[parent].f <= this.items[index].f) { break; } [this.items[parent], this.items[index]] = [this.items[index], this.items[parent]]; index = parent; } } #siftDown (index) { const length = this.items.length; while (true) { let smallest = index; const left = index * 2 + 1; const right = left + 1; if (left < length && this.items[left].f < this.items[smallest].f) { smallest = left; } if (right < length && this.items[right].f < this.items[smallest].f) { smallest = right; } if (smallest === index) { break; } [this.items[smallest], this.items[index]] = [this.items[index], this.items[smallest]]; index = smallest; } } } const CARDINALS = Object.freeze([ Object.freeze({ x: 1, y: 0 }), Object.freeze({ x: -1, y: 0 }), Object.freeze({ x: 0, y: 1 }), Object.freeze({ x: 0, y: -1 }) ]); /** Tiny f-cost nudge so equal-length paths prefer the preferred axis. */ const AXIS_TIE_BIAS = 0.001; /** * Prefer the axis with more remaining Manhattan distance to the goal. * When |dx| === |dy|, use `axisTiePreferVertical` (players vertical, mobs horizontal) * so opposing pathfinders still diverge on square diagonals. */ export function preferVerticalAxis (fromX, fromY, goalX, goalY, axisTiePreferVertical = false) { const dx = Math.abs(goalX - fromX); const dy = Math.abs(goalY - fromY); if (dy > dx) { return true; } if (dx > dy) { return false; } return !!axisTiePreferVertical; } /** * Neighbour order: most distance-to-goal reduction first, then the longer remaining * axis (or axis-tie preference when equal). */ export function orderedCardinals (fromX, fromY, goalX, goalY, axisTiePreferVertical = false) { const preferVertical = preferVerticalAxis(fromX, fromY, goalX, goalY, axisTiePreferVertical); const currentDist = Math.abs(goalX - fromX) + Math.abs(goalY - fromY); return CARDINALS .map((dir) => { const nx = fromX + dir.x; const ny = fromY + dir.y; const nextDist = Math.abs(goalX - nx) + Math.abs(goalY - ny); return { dir, reduction: currentDist - nextDist, vertical: dir.y !== 0 }; }) .sort((a, b) => { if (b.reduction !== a.reduction) { return b.reduction - a.reduction; } if (a.vertical !== b.vertical) { if (preferVertical) { return a.vertical ? -1 : 1; } return a.vertical ? 1 : -1; } return 0; }) .map((entry) => entry.dir); } /** * @param {object} [options] * @param {boolean} [options.preferVertical] axis-tie break only: players vertical, mobs horizontal * @param {(x: number, y: number) => number} [options.stepCost] movement cost into a tile (default 1) * @param {number} [options.minStepCost] lowest possible stepCost (default 1). Required for * admissible heuristics when some tiles cost less than 1 (e.g. path preference). */ export function findPath (startX, startY, goalX, goalY, isWalkable, minX, minY, maxX, maxY, options = {}) { const axisTiePreferVertical = !!options.preferVertical; const stepCost = typeof options.stepCost === "function" ? options.stepCost : null; const minStepCost = Math.max(0.001, Number(options.minStepCost) || 1); if (!isWalkable(goalX, goalY) || !isWalkable(startX, startY)) { return []; } if (startX === goalX && startY === goalY) { return []; } const width = maxX - minX + 1; const height = maxY - minY + 1; if (width <= 0 || height <= 0) { return []; } function index (x, y) { return (y - minY) * width + (x - minX); } const heuristic = (x, y) => (Math.abs(goalX - x) + Math.abs(goalY - y)) * minStepCost; const inBounds = (x, y) => x >= minX && y >= minY && x <= maxX && y <= maxY; const cameFrom = new Int32Array(width * height).fill(-1); const gScore = new Float64Array(width * height).fill(Infinity); const closed = new Uint8Array(width * height); const startIndex = index(startX, startY); gScore[startIndex] = 0; const open = new MinHeap(); open.push({ x: startX, y: startY, f: heuristic(startX, startY) }); while (open.size > 0) { const current = open.pop(); if (!inBounds(current.x, current.y)) { continue; } const currentIndex = index(current.x, current.y); if (closed[currentIndex]) { continue; } closed[currentIndex] = 1; if (current.x === goalX && current.y === goalY) { return reconstruct(cameFrom, current.x, current.y, minX, minY, width); } const preferVertical = preferVerticalAxis( current.x, current.y, goalX, goalY, axisTiePreferVertical ); for (const dir of orderedCardinals(current.x, current.y, goalX, goalY, axisTiePreferVertical)) { const nx = current.x + dir.x; const ny = current.y + dir.y; if (!inBounds(nx, ny) || !isWalkable(nx, ny)) { continue; } const neighborIndex = index(nx, ny); if (closed[neighborIndex]) { continue; } const cost = stepCost ? Math.max(minStepCost, Number(stepCost(nx, ny)) || 1) : 1; const tentative = gScore[currentIndex] + cost; if (tentative >= gScore[neighborIndex]) { continue; } cameFrom[neighborIndex] = currentIndex; gScore[neighborIndex] = tentative; const h = heuristic(nx, ny); const stepIsVertical = dir.y !== 0; const preferredStep = preferVertical ? stepIsVertical : !stepIsVertical; const bias = preferredStep ? 0 : AXIS_TIE_BIAS * minStepCost; open.push({ x: nx, y: ny, f: tentative + h + bias }); } } return []; } function reconstruct (cameFrom, x, y, minX, minY, width) { const path = []; let cx = x; let cy = y; while (true) { path.push({ x: cx, y: cy }); const idx = (cy - minY) * width + (cx - minX); const prev = cameFrom[idx]; if (prev < 0) { break; } cx = minX + (prev % width); cy = minY + Math.floor(prev / width); } path.reverse(); if (path.length > 0) { path.shift(); } return path; } export function chunkBoundsAround (tileX, tileY, chunkRadius) { const chunkX = tileToChunk(tileX); const chunkY = tileToChunk(tileY); const minChunkX = chunkX - chunkRadius; const minChunkY = chunkY - chunkRadius; const maxChunkX = chunkX + chunkRadius; const maxChunkY = chunkY + chunkRadius; return { minX: minChunkX * CHUNK_SIZE, minY: minChunkY * CHUNK_SIZE, maxX: (maxChunkX + 1) * CHUNK_SIZE - 1, maxY: (maxChunkY + 1) * CHUNK_SIZE - 1 }; } export { tileToLocal };