Как я делал автопуть для игры на Phaser (TypeScript)

Пролог

Всем привет! Сразу хочу сказать, что это не гайд, и я не рассказываю, как нужно кодить — просто хочу поделиться тем, что у меня получилось, и что я использовал в процессе разработки.

Я не эксперт, и всё, о чём я пишу — это то, что сам прочитал и попробовал на практике. Моей основной задачей было сгенерировать сеточную карту и заставить персонажа искать кратчайший путь до точки, на которую я нажал, и двигаться к ней.

Позже я добавил NPC с простым AI: они могут преследовать игрока, если тот находится рядом. В этой статье речь пойдёт только о построении пути.

Для решения такой задачи мне понадобился алгоритм, как и для всех задач где есть работа с поиском чего либо. В моём случает мне не нужно было диагональное перемещение поэтому я использовал алгоритм A*.

A* — это один из алгоритмов поиска пути, особенно хорошо работает на сетках с препятствиями. Он находит путь быстро и при этом остаётся довольно точным.

Вкратце разберёмся, как работает алгоритм A*.

A* сочетает в себе:

• поиск по стоимости (g) — сколько уже пройдено;

• эвристику (h) — оценка, сколько ещё осталось;

• и общее значение (f = g + h) — приоритет выбора.

В моём случае карта представляла собой двумерный массив Tile[][], где каждая клетка могла находиться в одном из нескольких состояний:

• walkable — проходимая клетка (если я не поставил туда объект);

• occupant — занятая клетка (если в ней находится NPC или игрок);

• reservedBy — временно зарезервированная клетка, чтобы избежать конфликтов между путями NPC и игрока.

Реализация на TypeScript для тех кому сразу нуден код

interface PathNode {     x: number;     y: number;     g: number;     f: number;     cameFrom?: PathNode; }  export class Pathfinder {     private grid: Tile[][];      constructor(grid: Tile[][], private readonly ignoreReservedBy?: unknown) {         this.grid = grid;     }      public findPath(start: { x: number; y: number }, goal: { x: number; y: number }): { x: number; y: number }[] {         if (!this.isWalkable(goal.x, goal.y)) return [];          const key = (x: number, y: number) => `${x},${y}`;         const h = (a: { x: number; y: number }, b: { x: number; y: number }) =>             Math.abs(a.x - b.x) + Math.abs(a.y - b.y);          const openSet: PathNode[] = [];         const openMap = new Map<string, PathNode>();         const closedSet = new Set<string>();          const startNode: PathNode = { ...start, g: 0, f: h(start, goal) };         openSet.push(startNode);         openMap.set(key(start.x, start.y), startNode);          while (openSet.length > 0) {             let currentIndex = 0;             for (let i = 1; i < openSet.length; i++) {                 if (openSet[i].f < openSet[currentIndex].f) {                     currentIndex = i;                 }             }              const current = openSet.splice(currentIndex, 1)[0];             openMap.delete(key(current.x, current.y));й              closedSet.add(key(current.x, current.y));              if (current.x === goal.x && current.y === goal.y) {                 const path: { x: number; y: number }[] = [];                 let node: PathNode | undefined = current;                 while (node) {                     path.push({ x: node.x, y: node.y });                     node = node.cameFrom;                 }                 return path.reverse();             }              const directions = [                 { x: 1, y: 0 }, { x: -1, y: 0 },                 { x: 0, y: 1 }, { x: 0, y: -1 },             ];              for (const offset of directions) {                 const nx = current.x + offset.x;                 const ny = current.y + offset.y;                 const neighborKey = key(nx, ny);                  if (!this.isWalkable(nx, ny) || closedSet.has(neighborKey)) continue;                  const tentativeG = current.g + 1;                 const existing = openMap.get(neighborKey);                  if (!existing || tentativeG < existing.g) {                     const node: PathNode = {                         x: nx,                         y: ny,                         g: tentativeG,                         f: tentativeG + h({ x: nx, y: ny }, goal),                         cameFrom: current,                     };                      if (!existing) {                         openSet.push(node);                         openMap.set(neighborKey, node);                     } else {                         Object.assign(existing, node);                     }                 }             }         }          return [];     }      private isWalkable(x: number, y: number): boolean {         const tile = this.grid[y]?.[x];         if (!tile || !tile.walkable) return false;         if (tile.occupant) return false;         if (tile.reservedBy && tile.reservedBy !== this.ignoreReservedBy) return false;         return true;     } } 

А теперь для тех кому интересно как это работает:

Перед началом поиска я проверяю: можно ли в принципе встать в клетку? Если нет — то просто выхожу.

• key нужен для адресации узлов в Map и Set

• h — манхэттенская эвристика: |х1 — х2| + |у1 — у2| (манхэттенская , потому что город выстроен квадратами и вы не можете ходить диагоналями).

х1 и y1 это начальная точка

x2 и y2 это точка куда нудно добраться

Это модуль числа — то есть расстояние до нуля, всегда положительное.

Далее я завёл три переменные:

• openSet[] — список узлов, ожидающих обработки;

• openMap — Map для быстрого поиска узлов по координатам;

• closedSet — Set с уже обработанными узлами.

Я инициализирую стартовую точку и добавляю её в openSet.

В главном цикле While я ищу узел с наименьшим f и удаляю его из очереди, заношу в закрытое множество.

let currentIndex = 0; for (let i = 1; i < openSet.length; i++) {     if (openSet[i].f < openSet[currentIndex].f) {         currentIndex = i;     } }  const current = openSet.splice(currentIndex, 1)[0]; openMap.delete(key(current.x, current.y)); closedSet.add(key(current.x, current.y));

Если текущая точка — это цель, строю путь, двигаясь по cameFrom, и разворачиваю его. cameFrom — это ссылка на предыдущую клетку, откуда пришёл текущий узел. Поэтому путь получается в обратном порядке: от цели к старту. Метод .reverse() нужен, чтобы вернуть путь в прямом направлении — от старта к цели.

if (current.x === goal.x && current.y === goal.y) {     const path: { x: number; y: number }[] = [];     let node: PathNode | undefined = current;     while (node) {         path.push({ x: node.x, y: node.y });         node = node.cameFrom;     }     return path.reverse(); }

Далее я прохожу по соседним клеткам (только вверх, вниз, влево и вправо). Пропускаю закрытые (closedSet) и непроходимые (!isWalkable) клетки.

const tentativeG = current.g + 1; const existing = openMap.get(neighborKey);  if (!existing || tentativeG < existing.g) {     const node: PathNode = {         x: nx,         y: ny,         g: tentativeG,         f: tentativeG + h({ x: nx, y: ny }, goal),         cameFrom: current,     };      if (!existing) {         openSet.push(node);         openMap.set(neighborKey, node);     } else {         Object.assign(existing, node);     } }

Если найден более короткий путь к соседу — обновляю его данные и добавляю в openSet.

Если очередь опустела, а цель не достигнута — выходим.

Если мы нашли лучший путь к соседу — обновляем или добавляем его в список обработки.

В целом это всё по матчасти. Дальше будет пиар.

Я завёл Telegram-канал, где рассказываю, что делаю, делюсь прикольными проектами и кодом.