| 1 | import { CHUNK_SIZE } from "../../../shared/protocol/constants.js"; |
| 2 | import { tileToChunk, tileToLocal } from "../world/coordinates.js"; |
| 3 | |
| 4 | class MinHeap |
| 5 | { |
| 6 | constructor () |
| 7 | { |
| 8 | this.items = []; |
| 9 | } |
| 10 | |
| 11 | push (node) |
| 12 | { |
| 13 | this.items.push(node); |
| 14 | this.#siftUp(this.items.length - 1); |
| 15 | } |
| 16 | |
| 17 | pop () |
| 18 | { |
| 19 | if (this.items.length === 0) |
| 20 | { return null; } |
| 21 | |
| 22 | const root = this.items[0]; |
| 23 | const last = this.items.pop(); |
| 24 | if (this.items.length > 0) |
| 25 | { |
| 26 | this.items[0] = last; |
| 27 | this.#siftDown(0); |
| 28 | } |
| 29 | return root; |
| 30 | } |
| 31 | |
| 32 | get size () |
| 33 | { |
| 34 | return this.items.length; |
| 35 | } |
| 36 | |
| 37 | #siftUp (index) |
| 38 | { |
| 39 | while (index > 0) |
| 40 | { |
| 41 | const parent = (index - 1) >> 1; |
| 42 | if (this.items[parent].f <= this.items[index].f) |
| 43 | { break; } |
| 44 | [this.items[parent], this.items[index]] = [this.items[index], this.items[parent]]; |
| 45 | index = parent; |
| 46 | } |
| 47 | } |
| 48 | |
| 49 | #siftDown (index) |
| 50 | { |
| 51 | const length = this.items.length; |
| 52 | while (true) |
| 53 | { |
| 54 | let smallest = index; |
| 55 | const left = index * 2 + 1; |
| 56 | const right = left + 1; |
| 57 | if (left < length && this.items[left].f < this.items[smallest].f) |
| 58 | { smallest = left; } |
| 59 | if (right < length && this.items[right].f < this.items[smallest].f) |
| 60 | { smallest = right; } |
| 61 | if (smallest === index) |
| 62 | { break; } |
| 63 | [this.items[smallest], this.items[index]] = [this.items[index], this.items[smallest]]; |
| 64 | index = smallest; |
| 65 | } |
| 66 | } |
| 67 | } |
| 68 | |
| 69 | const CARDINALS = Object.freeze([ |
| 70 | Object.freeze({ x: 1, y: 0 }), |
| 71 | Object.freeze({ x: -1, y: 0 }), |
| 72 | Object.freeze({ x: 0, y: 1 }), |
| 73 | Object.freeze({ x: 0, y: -1 }) |
| 74 | ]); |
| 75 | |
| 76 | /** Tiny f-cost nudge so equal-length paths prefer the preferred axis. */ |
| 77 | const AXIS_TIE_BIAS = 0.001; |
| 78 | |
| 79 | /** |
| 80 | * Prefer the axis with more remaining Manhattan distance to the goal. |
| 81 | * When |dx| === |dy|, use `axisTiePreferVertical` (players vertical, mobs horizontal) |
| 82 | * so opposing pathfinders still diverge on square diagonals. |
| 83 | */ |
| 84 | export function preferVerticalAxis (fromX, fromY, goalX, goalY, axisTiePreferVertical = false) |
| 85 | { |
| 86 | const dx = Math.abs(goalX - fromX); |
| 87 | const dy = Math.abs(goalY - fromY); |
| 88 | if (dy > dx) |
| 89 | { return true; } |
| 90 | if (dx > dy) |
| 91 | { return false; } |
| 92 | return !!axisTiePreferVertical; |
| 93 | } |
| 94 | |
| 95 | /** |
| 96 | * Neighbour order: most distance-to-goal reduction first, then the longer remaining |
| 97 | * axis (or axis-tie preference when equal). |
| 98 | */ |
| 99 | export function orderedCardinals (fromX, fromY, goalX, goalY, axisTiePreferVertical = false) |
| 100 | { |
| 101 | const preferVertical = preferVerticalAxis(fromX, fromY, goalX, goalY, axisTiePreferVertical); |
| 102 | const currentDist = Math.abs(goalX - fromX) + Math.abs(goalY - fromY); |
| 103 | return CARDINALS |
| 104 | .map((dir) => |
| 105 | { |
| 106 | const nx = fromX + dir.x; |
| 107 | const ny = fromY + dir.y; |
| 108 | const nextDist = Math.abs(goalX - nx) + Math.abs(goalY - ny); |
| 109 | return { |
| 110 | dir, |
| 111 | reduction: currentDist - nextDist, |
| 112 | vertical: dir.y !== 0 |
| 113 | }; |
| 114 | }) |
| 115 | .sort((a, b) => |
| 116 | { |
| 117 | if (b.reduction !== a.reduction) |
| 118 | { return b.reduction - a.reduction; } |
| 119 | if (a.vertical !== b.vertical) |
| 120 | { |
| 121 | if (preferVertical) |
| 122 | { return a.vertical ? -1 : 1; } |
| 123 | return a.vertical ? 1 : -1; |
| 124 | } |
| 125 | return 0; |
| 126 | }) |
| 127 | .map((entry) => entry.dir); |
| 128 | } |
| 129 | |
| 130 | /** |
| 131 | * @param {object} [options] |
| 132 | * @param {boolean} [options.preferVertical] axis-tie break only: players vertical, mobs horizontal |
| 133 | * @param {(x: number, y: number) => number} [options.stepCost] movement cost into a tile (default 1) |
| 134 | * @param {number} [options.minStepCost] lowest possible stepCost (default 1). Required for |
| 135 | * admissible heuristics when some tiles cost less than 1 (e.g. path preference). |
| 136 | */ |
| 137 | export function findPath (startX, startY, goalX, goalY, isWalkable, minX, minY, maxX, maxY, options = {}) |
| 138 | { |
| 139 | const axisTiePreferVertical = !!options.preferVertical; |
| 140 | const stepCost = typeof options.stepCost === "function" ? options.stepCost : null; |
| 141 | const minStepCost = Math.max(0.001, Number(options.minStepCost) || 1); |
| 142 | if (!isWalkable(goalX, goalY) || !isWalkable(startX, startY)) |
| 143 | { return []; } |
| 144 | |
| 145 | if (startX === goalX && startY === goalY) |
| 146 | { return []; } |
| 147 | |
| 148 | const width = maxX - minX + 1; |
| 149 | const height = maxY - minY + 1; |
| 150 | if (width <= 0 || height <= 0) |
| 151 | { return []; } |
| 152 | |
| 153 | function index (x, y) |
| 154 | { |
| 155 | return (y - minY) * width + (x - minX); |
| 156 | } |
| 157 | |
| 158 | const heuristic = (x, y) => (Math.abs(goalX - x) + Math.abs(goalY - y)) * minStepCost; |
| 159 | |
| 160 | const inBounds = (x, y) => x >= minX && y >= minY && x <= maxX && y <= maxY; |
| 161 | const cameFrom = new Int32Array(width * height).fill(-1); |
| 162 | const gScore = new Float64Array(width * height).fill(Infinity); |
| 163 | const closed = new Uint8Array(width * height); |
| 164 | const startIndex = index(startX, startY); |
| 165 | gScore[startIndex] = 0; |
| 166 | |
| 167 | const open = new MinHeap(); |
| 168 | open.push({ x: startX, y: startY, f: heuristic(startX, startY) }); |
| 169 | |
| 170 | while (open.size > 0) |
| 171 | { |
| 172 | const current = open.pop(); |
| 173 | if (!inBounds(current.x, current.y)) |
| 174 | { continue; } |
| 175 | |
| 176 | const currentIndex = index(current.x, current.y); |
| 177 | if (closed[currentIndex]) |
| 178 | { continue; } |
| 179 | closed[currentIndex] = 1; |
| 180 | |
| 181 | if (current.x === goalX && current.y === goalY) |
| 182 | { return reconstruct(cameFrom, current.x, current.y, minX, minY, width); } |
| 183 | |
| 184 | const preferVertical = preferVerticalAxis( |
| 185 | current.x, |
| 186 | current.y, |
| 187 | goalX, |
| 188 | goalY, |
| 189 | axisTiePreferVertical |
| 190 | ); |
| 191 | for (const dir of orderedCardinals(current.x, current.y, goalX, goalY, axisTiePreferVertical)) |
| 192 | { |
| 193 | const nx = current.x + dir.x; |
| 194 | const ny = current.y + dir.y; |
| 195 | if (!inBounds(nx, ny) || !isWalkable(nx, ny)) |
| 196 | { continue; } |
| 197 | |
| 198 | const neighborIndex = index(nx, ny); |
| 199 | if (closed[neighborIndex]) |
| 200 | { continue; } |
| 201 | |
| 202 | const cost = stepCost ? Math.max(minStepCost, Number(stepCost(nx, ny)) || 1) : 1; |
| 203 | const tentative = gScore[currentIndex] + cost; |
| 204 | if (tentative >= gScore[neighborIndex]) |
| 205 | { continue; } |
| 206 | |
| 207 | cameFrom[neighborIndex] = currentIndex; |
| 208 | gScore[neighborIndex] = tentative; |
| 209 | const h = heuristic(nx, ny); |
| 210 | const stepIsVertical = dir.y !== 0; |
| 211 | const preferredStep = preferVertical ? stepIsVertical : !stepIsVertical; |
| 212 | const bias = preferredStep ? 0 : AXIS_TIE_BIAS * minStepCost; |
| 213 | open.push({ x: nx, y: ny, f: tentative + h + bias }); |
| 214 | } |
| 215 | } |
| 216 | |
| 217 | return []; |
| 218 | } |
| 219 | |
| 220 | function reconstruct (cameFrom, x, y, minX, minY, width) |
| 221 | { |
| 222 | const path = []; |
| 223 | let cx = x; |
| 224 | let cy = y; |
| 225 | while (true) |
| 226 | { |
| 227 | path.push({ x: cx, y: cy }); |
| 228 | const idx = (cy - minY) * width + (cx - minX); |
| 229 | const prev = cameFrom[idx]; |
| 230 | if (prev < 0) |
| 231 | { break; } |
| 232 | cx = minX + (prev % width); |
| 233 | cy = minY + Math.floor(prev / width); |
| 234 | } |
| 235 | path.reverse(); |
| 236 | if (path.length > 0) |
| 237 | { path.shift(); } |
| 238 | return path; |
| 239 | } |
| 240 | |
| 241 | export function chunkBoundsAround (tileX, tileY, chunkRadius) |
| 242 | { |
| 243 | const chunkX = tileToChunk(tileX); |
| 244 | const chunkY = tileToChunk(tileY); |
| 245 | const minChunkX = chunkX - chunkRadius; |
| 246 | const minChunkY = chunkY - chunkRadius; |
| 247 | const maxChunkX = chunkX + chunkRadius; |
| 248 | const maxChunkY = chunkY + chunkRadius; |
| 249 | return { |
| 250 | minX: minChunkX * CHUNK_SIZE, |
| 251 | minY: minChunkY * CHUNK_SIZE, |
| 252 | maxX: (maxChunkX + 1) * CHUNK_SIZE - 1, |
| 253 | maxY: (maxChunkY + 1) * CHUNK_SIZE - 1 |
| 254 | }; |
| 255 | } |
| 256 | |
| 257 | export { tileToLocal }; |