Пролог

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

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

Позже я добавил 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-канал, где рассказываю, что делаю, делюсь прикольными проектами и кодом.