| 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 = [ |
| 70 | { x: 1, y: 0 }, |
| 71 | { x: -1, y: 0 }, |
| 72 | { x: 0, y: 1 }, |
| 73 | { x: 0, y: -1 } |
| 74 | ]; |
| 75 | |
| 76 | export function findPath (startX, startY, goalX, goalY, isWalkable, minX, minY, maxX, maxY) |
| 77 | { |
| 78 | if (!isWalkable(goalX, goalY) || !isWalkable(startX, startY)) |
| 79 | { return []; } |
| 80 | |
| 81 | if (startX === goalX && startY === goalY) |
| 82 | { return []; } |
| 83 | |
| 84 | const width = maxX - minX + 1; |
| 85 | const height = maxY - minY + 1; |
| 86 | if (width <= 0 || height <= 0) |
| 87 | { return []; } |
| 88 | |
| 89 | function index (x, y) |
| 90 | { |
| 91 | return (y - minY) * width + (x - minX); |
| 92 | } |
| 93 | |
| 94 | const inBounds = (x, y) => x >= minX && y >= minY && x <= maxX && y <= maxY; |
| 95 | const cameFrom = new Int32Array(width * height).fill(-1); |
| 96 | const gScore = new Float64Array(width * height).fill(Infinity); |
| 97 | const closed = new Uint8Array(width * height); |
| 98 | const startIndex = index(startX, startY); |
| 99 | gScore[startIndex] = 0; |
| 100 | |
| 101 | const open = new MinHeap(); |
| 102 | open.push({ x: startX, y: startY, f: Math.abs(goalX - startX) + Math.abs(goalY - startY) }); |
| 103 | |
| 104 | while (open.size > 0) |
| 105 | { |
| 106 | const current = open.pop(); |
| 107 | if (!inBounds(current.x, current.y)) |
| 108 | { continue; } |
| 109 | |
| 110 | const currentIndex = index(current.x, current.y); |
| 111 | if (closed[currentIndex]) |
| 112 | { continue; } |
| 113 | closed[currentIndex] = 1; |
| 114 | |
| 115 | if (current.x === goalX && current.y === goalY) |
| 116 | { return reconstruct(cameFrom, current.x, current.y, minX, minY, width); } |
| 117 | |
| 118 | for (const dir of CARDINALS) |
| 119 | { |
| 120 | const nx = current.x + dir.x; |
| 121 | const ny = current.y + dir.y; |
| 122 | if (!inBounds(nx, ny) || !isWalkable(nx, ny)) |
| 123 | { continue; } |
| 124 | |
| 125 | const neighborIndex = index(nx, ny); |
| 126 | if (closed[neighborIndex]) |
| 127 | { continue; } |
| 128 | |
| 129 | const tentative = gScore[currentIndex] + 1; |
| 130 | if (tentative >= gScore[neighborIndex]) |
| 131 | { continue; } |
| 132 | |
| 133 | cameFrom[neighborIndex] = currentIndex; |
| 134 | gScore[neighborIndex] = tentative; |
| 135 | const h = Math.abs(goalX - nx) + Math.abs(goalY - ny); |
| 136 | open.push({ x: nx, y: ny, f: tentative + h }); |
| 137 | } |
| 138 | } |
| 139 | |
| 140 | return []; |
| 141 | } |
| 142 | |
| 143 | function reconstruct (cameFrom, x, y, minX, minY, width) |
| 144 | { |
| 145 | const path = []; |
| 146 | let cx = x; |
| 147 | let cy = y; |
| 148 | while (true) |
| 149 | { |
| 150 | path.push({ x: cx, y: cy }); |
| 151 | const idx = (cy - minY) * width + (cx - minX); |
| 152 | const prev = cameFrom[idx]; |
| 153 | if (prev < 0) |
| 154 | { break; } |
| 155 | cx = minX + (prev % width); |
| 156 | cy = minY + Math.floor(prev / width); |
| 157 | } |
| 158 | path.reverse(); |
| 159 | if (path.length > 0) |
| 160 | { path.shift(); } |
| 161 | return path; |
| 162 | } |
| 163 | |
| 164 | export function chunkBoundsAround (tileX, tileY, chunkRadius) |
| 165 | { |
| 166 | const chunkX = tileToChunk(tileX); |
| 167 | const chunkY = tileToChunk(tileY); |
| 168 | const minChunkX = chunkX - chunkRadius; |
| 169 | const minChunkY = chunkY - chunkRadius; |
| 170 | const maxChunkX = chunkX + chunkRadius; |
| 171 | const maxChunkY = chunkY + chunkRadius; |
| 172 | return { |
| 173 | minX: minChunkX * CHUNK_SIZE, |
| 174 | minY: minChunkY * CHUNK_SIZE, |
| 175 | maxX: (maxChunkX + 1) * CHUNK_SIZE - 1, |
| 176 | maxY: (maxChunkY + 1) * CHUNK_SIZE - 1 |
| 177 | }; |
| 178 | } |
| 179 | |
| 180 | export { tileToLocal }; |