| 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 caller's axis. */ |
| 77 | const AXIS_TIE_BIAS = 0.001; |
| 78 | |
| 79 | /** |
| 80 | * Neighbour order: most distance-to-goal reduction first, then preferred axis |
| 81 | * (horizontal for mobs, vertical for players) so opposing pathfinders diverge. |
| 82 | */ |
| 83 | export function orderedCardinals (fromX, fromY, goalX, goalY, preferVertical = false) |
| 84 | { |
| 85 | const currentDist = Math.abs(goalX - fromX) + Math.abs(goalY - fromY); |
| 86 | return CARDINALS |
| 87 | .map((dir) => |
| 88 | { |
| 89 | const nx = fromX + dir.x; |
| 90 | const ny = fromY + dir.y; |
| 91 | const nextDist = Math.abs(goalX - nx) + Math.abs(goalY - ny); |
| 92 | return { |
| 93 | dir, |
| 94 | reduction: currentDist - nextDist, |
| 95 | vertical: dir.y !== 0 |
| 96 | }; |
| 97 | }) |
| 98 | .sort((a, b) => |
| 99 | { |
| 100 | if (b.reduction !== a.reduction) |
| 101 | { return b.reduction - a.reduction; } |
| 102 | if (a.vertical !== b.vertical) |
| 103 | { |
| 104 | if (preferVertical) |
| 105 | { return a.vertical ? -1 : 1; } |
| 106 | return a.vertical ? 1 : -1; |
| 107 | } |
| 108 | return 0; |
| 109 | }) |
| 110 | .map((entry) => entry.dir); |
| 111 | } |
| 112 | |
| 113 | /** |
| 114 | * @param {object} [options] |
| 115 | * @param {boolean} [options.preferVertical] players prefer vertical; mobs (default) prefer horizontal |
| 116 | */ |
| 117 | export function findPath (startX, startY, goalX, goalY, isWalkable, minX, minY, maxX, maxY, options = {}) |
| 118 | { |
| 119 | const preferVertical = !!options.preferVertical; |
| 120 | if (!isWalkable(goalX, goalY) || !isWalkable(startX, startY)) |
| 121 | { return []; } |
| 122 | |
| 123 | if (startX === goalX && startY === goalY) |
| 124 | { return []; } |
| 125 | |
| 126 | const width = maxX - minX + 1; |
| 127 | const height = maxY - minY + 1; |
| 128 | if (width <= 0 || height <= 0) |
| 129 | { return []; } |
| 130 | |
| 131 | function index (x, y) |
| 132 | { |
| 133 | return (y - minY) * width + (x - minX); |
| 134 | } |
| 135 | |
| 136 | const inBounds = (x, y) => x >= minX && y >= minY && x <= maxX && y <= maxY; |
| 137 | const cameFrom = new Int32Array(width * height).fill(-1); |
| 138 | const gScore = new Float64Array(width * height).fill(Infinity); |
| 139 | const closed = new Uint8Array(width * height); |
| 140 | const startIndex = index(startX, startY); |
| 141 | gScore[startIndex] = 0; |
| 142 | |
| 143 | const open = new MinHeap(); |
| 144 | open.push({ x: startX, y: startY, f: Math.abs(goalX - startX) + Math.abs(goalY - startY) }); |
| 145 | |
| 146 | while (open.size > 0) |
| 147 | { |
| 148 | const current = open.pop(); |
| 149 | if (!inBounds(current.x, current.y)) |
| 150 | { continue; } |
| 151 | |
| 152 | const currentIndex = index(current.x, current.y); |
| 153 | if (closed[currentIndex]) |
| 154 | { continue; } |
| 155 | closed[currentIndex] = 1; |
| 156 | |
| 157 | if (current.x === goalX && current.y === goalY) |
| 158 | { return reconstruct(cameFrom, current.x, current.y, minX, minY, width); } |
| 159 | |
| 160 | for (const dir of orderedCardinals(current.x, current.y, goalX, goalY, preferVertical)) |
| 161 | { |
| 162 | const nx = current.x + dir.x; |
| 163 | const ny = current.y + dir.y; |
| 164 | if (!inBounds(nx, ny) || !isWalkable(nx, ny)) |
| 165 | { continue; } |
| 166 | |
| 167 | const neighborIndex = index(nx, ny); |
| 168 | if (closed[neighborIndex]) |
| 169 | { continue; } |
| 170 | |
| 171 | const tentative = gScore[currentIndex] + 1; |
| 172 | if (tentative >= gScore[neighborIndex]) |
| 173 | { continue; } |
| 174 | |
| 175 | cameFrom[neighborIndex] = currentIndex; |
| 176 | gScore[neighborIndex] = tentative; |
| 177 | const h = Math.abs(goalX - nx) + Math.abs(goalY - ny); |
| 178 | const stepIsVertical = dir.y !== 0; |
| 179 | const preferredStep = preferVertical ? stepIsVertical : !stepIsVertical; |
| 180 | const bias = preferredStep ? 0 : AXIS_TIE_BIAS; |
| 181 | open.push({ x: nx, y: ny, f: tentative + h + bias }); |
| 182 | } |
| 183 | } |
| 184 | |
| 185 | return []; |
| 186 | } |
| 187 | |
| 188 | function reconstruct (cameFrom, x, y, minX, minY, width) |
| 189 | { |
| 190 | const path = []; |
| 191 | let cx = x; |
| 192 | let cy = y; |
| 193 | while (true) |
| 194 | { |
| 195 | path.push({ x: cx, y: cy }); |
| 196 | const idx = (cy - minY) * width + (cx - minX); |
| 197 | const prev = cameFrom[idx]; |
| 198 | if (prev < 0) |
| 199 | { break; } |
| 200 | cx = minX + (prev % width); |
| 201 | cy = minY + Math.floor(prev / width); |
| 202 | } |
| 203 | path.reverse(); |
| 204 | if (path.length > 0) |
| 205 | { path.shift(); } |
| 206 | return path; |
| 207 | } |
| 208 | |
| 209 | export function chunkBoundsAround (tileX, tileY, chunkRadius) |
| 210 | { |
| 211 | const chunkX = tileToChunk(tileX); |
| 212 | const chunkY = tileToChunk(tileY); |
| 213 | const minChunkX = chunkX - chunkRadius; |
| 214 | const minChunkY = chunkY - chunkRadius; |
| 215 | const maxChunkX = chunkX + chunkRadius; |
| 216 | const maxChunkY = chunkY + chunkRadius; |
| 217 | return { |
| 218 | minX: minChunkX * CHUNK_SIZE, |
| 219 | minY: minChunkY * CHUNK_SIZE, |
| 220 | maxX: (maxChunkX + 1) * CHUNK_SIZE - 1, |
| 221 | maxY: (maxChunkY + 1) * CHUNK_SIZE - 1 |
| 222 | }; |
| 223 | } |
| 224 | |
| 225 | export { tileToLocal }; |