diff --git a/docs/engine/maps.md b/docs/engine/maps.md index 0049b4b..6235e67 100644 --- a/docs/engine/maps.md +++ b/docs/engine/maps.md @@ -169,6 +169,10 @@ const path = findPathToNeighbor(map, from, npcTile); // к краю тайла NPC ``` +Внутри A* — мин-куча открытых узлов по f (tie-break по порядку вставки — +обход детерминирован), `findPathToNeighbor` — один прогон со всеми 8 соседями +как целями (эвристика — минимум манхэттена по целям), а не до 8 полных поисков. + ## Коллизии (круг поверх сетки) Движковые коллизии — чистая математика в `map/collision.ts`, без Pixi: diff --git a/packages/engine/src/map/__tests__/pathfinding.test.ts b/packages/engine/src/map/__tests__/pathfinding.test.ts index eb101ce..de1e75d 100644 --- a/packages/engine/src/map/__tests__/pathfinding.test.ts +++ b/packages/engine/src/map/__tests__/pathfinding.test.ts @@ -88,4 +88,19 @@ ]); expect(findPathToNeighbor(grid, { x: 0, y: 4 }, { x: 2, y: 2 })).toBeNull(); }); + + it('выбирает ближайшего из 8 соседей за один прогон', () => { + // Цель в углу сетки, старт по диагонали: из трёх соседей цели + // ближайший к старту — (4,4), путь к нему кратчайший возможный. + const grid = makeGrid(6, 6); + const path = findPathToNeighbor(grid, { x: 0, y: 0 }, { x: 5, y: 5 }); + expect(path).not.toBeNull(); + expect(path!.at(-1)).toEqual({ x: 4, y: 4 }); + expect(path!.length).toBe(8); // манхэттен (0,0)->(4,4), без крюка + }); + + it('старт уже сосед цели — пустой путь', () => { + const grid = makeGrid(10, 10); + expect(findPathToNeighbor(grid, { x: 3, y: 5 }, { x: 4, y: 5 })).toEqual([]); + }); }); diff --git a/packages/engine/src/map/pathfinding.ts b/packages/engine/src/map/pathfinding.ts index 7089f59..0040506 100644 --- a/packages/engine/src/map/pathfinding.ts +++ b/packages/engine/src/map/pathfinding.ts @@ -16,62 +16,102 @@ g: number; f: number; parent: Node | null; + /** Порядок вставки: при равном f выбираем ранее вставленный (детерминизм обхода). */ + seq: number; } -function heuristic(a: { x: number; y: number }, b: { x: number; y: number }): number { +interface Vec2 { + x: number; + y: number; +} + +/** Соседство 4/8 (диагонали без среза углов проверяются отдельно). */ +const DIRS4: readonly Vec2[] = [ + { x: 1, y: 0 }, + { x: -1, y: 0 }, + { x: 0, y: 1 }, + { x: 0, y: -1 } +]; +const DIRS8: readonly Vec2[] = [...DIRS4, { x: 1, y: 1 }, { x: 1, y: -1 }, { x: -1, y: 1 }, { x: -1, y: -1 }]; + +function manhattan(a: Vec2, b: Vec2): number { return Math.abs(a.x - b.x) + Math.abs(a.y - b.y); } -/** - * Возвращает путь (без стартового тайла, включая конечный) или null, если пути нет. - * Включение диагоналей добавляет шаги (±1, ±1), но только если оба ортогональных - * соседа проходимы (без среза углов). - */ -export function findPath( - grid: Grid, - start: { x: number; y: number }, - goal: { x: number; y: number }, - allowDiagonal = false -): { x: number; y: number }[] | null { - if (!grid.isWalkable(goal.x, goal.y)) return null; - if (start.x === goal.x && start.y === goal.y) return []; +/** a важнее b в куче: меньшее f, при равном — более ранней вставки. */ +function before(a: Node, b: Node): boolean { + return a.f < b.f || (a.f === b.f && a.seq < b.seq); +} +/** Мин-куча открытых узлов по f — вместо линейного скана (O(log n) на операцию). */ +class OpenHeap { + private nodes: Node[] = []; + + get size(): number { + return this.nodes.length; + } + + push(n: Node): void { + const a = this.nodes; + a.push(n); + let i = a.length - 1; + while (i > 0) { + const p = (i - 1) >> 1; + if (!before(a[i]!, a[p]!)) break; + a[i] = a[p]!; + a[p] = n; + i = p; + } + } + + pop(): Node | null { + const a = this.nodes; + const top = a[0] ?? null; + const last = a.pop()!; + if (a.length > 0) { + a[0] = last; + let i = 0; + for (;;) { + const l = 2 * i + 1; + const r = l + 1; + let m = i; + if (l < a.length && before(a[l]!, a[m]!)) m = l; + if (r < a.length && before(a[r]!, a[m]!)) m = r; + if (m === i) break; + const t = a[i]!; + a[i] = a[m]!; + a[m] = t; + i = m; + } + } + return top; + } +} + +/** + * Общий каркас A*: цель и эвристика — параметры (многоцелевой прогон + * findPathToNeighbor переиспользует тот же цикл). Возвращает конечный узел + * (путь — по цепочке parent) или null. + */ +function astar( + grid: Grid, + start: Vec2, + dirs: readonly Vec2[], + isGoal: (x: number, y: number) => boolean, + h: (x: number, y: number) => number +): Node | null { const key = (x: number, y: number) => y * grid.width + x; - const open: Node[] = []; + const open = new OpenHeap(); const best = new Map(); - const startNode: Node = { x: start.x, y: start.y, g: 0, f: heuristic(start, goal), parent: null }; - open.push(startNode); + let seq = 0; + open.push({ x: start.x, y: start.y, g: 0, f: h(start.x, start.y), parent: null, seq: seq++ }); best.set(key(start.x, start.y), 0); - const dirs4 = [ - { x: 1, y: 0 }, - { x: -1, y: 0 }, - { x: 0, y: 1 }, - { x: 0, y: -1 } - ]; + while (open.size > 0) { + const cur = open.pop()!; + if (isGoal(cur.x, cur.y)) return cur; - while (open.length > 0) { - // Извлекаем узел с минимальным f (карты маленькие, линейного поиска достаточно). - let idx = 0; - for (let i = 1; i < open.length; i++) { - if (open[i].f < open[idx].f) idx = i; - } - const cur = open.splice(idx, 1)[0]; - - if (cur.x === goal.x && cur.y === goal.y) { - const path: { x: number; y: number }[] = []; - for (let n: Node | null = cur; n !== null; n = n.parent) { - path.unshift({ x: n.x, y: n.y }); - } - path.shift(); // убираем стартовый тайл - return path; - } - - const neighbors = allowDiagonal - ? [...dirs4, { x: 1, y: 1 }, { x: 1, y: -1 }, { x: -1, y: 1 }, { x: -1, y: -1 }] - : dirs4; - - for (const d of neighbors) { + for (const d of dirs) { const nx = cur.x + d.x; const ny = cur.y + d.y; if (nx < 0 || ny < 0 || nx >= grid.width || ny >= grid.height) continue; @@ -85,33 +125,85 @@ const k = key(nx, ny); if (best.has(k) && best.get(k)! <= g) continue; best.set(k, g); - open.push({ x: nx, y: ny, g, f: g + heuristic({ x: nx, y: ny }, goal), parent: cur }); + open.push({ x: nx, y: ny, g, f: g + h(nx, ny), parent: cur, seq: seq++ }); } } return null; } + +/** Путь из цепочки parent (без стартового тайла, включая конечный). */ +function tracePath(node: Node): { x: number; y: number }[] { + const path: { x: number; y: number }[] = []; + for (let n: Node | null = node; n !== null; n = n.parent) { + path.unshift({ x: n.x, y: n.y }); + } + path.shift(); // убираем стартовый тайл + return path; +} + +/** + * Возвращает путь (без стартового тайла, включая конечный) или null, если пути нет. + * Включение диагоналей добавляет шаги (±1, ±1), но только если оба ортогональных + * соседа проходимы (без среза углов). + */ +export function findPath( + grid: Grid, + start: Vec2, + goal: Vec2, + allowDiagonal = false +): { x: number; y: number }[] | null { + if (!grid.isWalkable(goal.x, goal.y)) return null; + if (start.x === goal.x && start.y === goal.y) return []; + + const node = astar( + grid, + start, + allowDiagonal ? DIRS8 : DIRS4, + (x, y) => x === goal.x && y === goal.y, + (x, y) => manhattan({ x, y }, goal) + ); + return node ? tracePath(node) : null; +} + /** * Путь к ближайшей проходимой клетке, соседней с goal (8-соседство). * Идём к краю цели: goal может быть непроходим (тайл NPC/объекта) или занят — - * стоять на нём не нужно. Пути нет — null. + * стоять на нём не нужно. Один прогон A* со всеми 8 соседями как целями + * (эвристика — минимум манхэттена по целям); пути нет — null. */ export function findPathToNeighbor( grid: Grid, - start: { x: number; y: number }, - goal: { x: number; y: number } + start: Vec2, + goal: Vec2 ): { x: number; y: number }[] | null { - let best: { x: number; y: number }[] | null = null; + const goals: Vec2[] = []; for (let dy = -1; dy <= 1; dy++) { for (let dx = -1; dx <= 1; dx++) { if (dx === 0 && dy === 0) continue; const tx = goal.x + dx; const ty = goal.y + dy; if (tx < 0 || ty < 0 || tx >= grid.width || ty >= grid.height) continue; - if (!grid.isWalkable(tx, ty)) continue; - const p = findPath(grid, start, { x: tx, y: ty }); - if (p && (best === null || p.length < best.length)) best = p; + if (grid.isWalkable(tx, ty)) goals.push({ x: tx, y: ty }); } } - return best; -} + if (goals.length === 0) return null; + if (goals.some((g) => g.x === start.x && g.y === start.y)) return []; + + const goalKeys = new Set(goals.map((g) => g.y * grid.width + g.x)); + const node = astar( + grid, + start, + DIRS4, + (x, y) => goalKeys.has(y * grid.width + x), + (x, y) => { + let min = Infinity; + for (const g of goals) { + const d = Math.abs(x - g.x) + Math.abs(y - g.y); + if (d < min) min = d; + } + return min; + } + ); + return node ? tracePath(node) : null; +} \ No newline at end of file