Поиск пути A* на тайловой сетке: от поиска в ширину до рабочего кода на JavaScript

Коротко

A* находит кратчайший путь на тайловой карте, оценивая каждую клетку как f = g + h: g — сколько уже пройдено, h — оценка остатка до цели. Если h никогда не завышает расстояние (Манхэттен для 4 направлений, Чебышёв для 8), путь получается кратчайшим, а клеток просматривается заметно меньше, чем у поиска в ширину. Ниже — объяснение через поиск в ширину и Дейкстру, рабочий код на JavaScript и пять практических ловушек: стоимость клеток, ничьи, отсутствие пути, бюджет кадра и много врагов сразу.

Содержание

1. Откуда взялся A*
2. Поиск в ширину, Дейкстра, жадный поиск и A*
3. Эвристика для 4 и 8 направлений
4. Код A* для тайловой сетки
5. Стоимость клеток: трава, вода, лес
6. Ничьи и зигзаги
7. Когда пути нет
8. Бюджет кадра и много врагов
9. Чек-лист: враг, который обходит стены
10. Когда вам это не подойдёт

Откуда взялся A*

A* описали Питер Харт, Нильс Нильссон и Бертрам Рафаэль из Стэнфордского исследовательского института в 1968 году, в статье «A Formal Basis for the Heuristic Determination of Minimum Cost Paths» (IEEE Transactions on Systems Science and Cybernetics, том 4, выпуск 2, с. 100–107). Алгоритм создавался для планирования пути робота Shakey (Wikipedia, проверено: ноябрь 2026). С тех пор это стандартный выбор для поиска пути от одной точки к одной цели на сетке или графе.

Поиск в ширину, Дейкстра, жадный поиск и A*

A* проще всего понять как четвёртый шаг после трёх более простых алгоритмов. Эту последовательность использует Амит Патель в статье Introduction to A* на Red Blob Games (проверено: ноябрь 2026).

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

Эвристика для 4 и 8 направлений

Эвристика — это оценка оставшегося расстояния, и на сетке она выбирается по разрешённым направлениям движения. По Wikipedia (проверено: ноябрь 2026) для сетки с 4 направлениями подходит манхэттенское расстояние, для 8 направлений — расстояние Чебышёва:

dx = |x1 − x2|,  dy = |y1 − y2|

Манхэттен (4 направления):  h = dx + dy
Чебышёв   (8 направлений):  h = max(dx, dy)

Правило выбора: эвристика не должна завышать реальную стоимость. Тогда, как пишет Red Blob Games, A* находит кратчайший путь. Если диагональный шаг стоит 1,414 (примерно √2), а не 1, расстояние Чебышёва остаётся заниженным и путь всё ещё кратчайший, просто клеток просматривается больше. Если же для 8 направлений по ошибке взять Манхэттен, он завысит диагональный путь, и A* может вернуть не самый короткий маршрут.

Код A* для тайловой сетки

Ниже A* для карты, где grid[y][x] равно 0 для прохода и 1 для стены, 4 направления. Клетка кодируется одним числом y * W + x, поэтому вместо словарей используются обычные массивы — так советует и Red Blob Games для целочисленных идентификаторов.

function findPath(grid, sx, sy, tx, ty) {
  const H = grid.length, W = grid[0].length;
  const start = sy * W + sx, goal = ty * W + tx;
  const cost = new Float64Array(W * H).fill(Infinity);   // g
  const from = new Int32Array(W * H).fill(-1);           // cameFrom
  const open = new MinHeap();                            // очередь по f
  cost[start] = 0;
  open.push(start, 0);

  while (open.size > 0) {
    const cur = open.pop();
    if (cur === goal) break;                             // ранний выход
    const cx = cur % W, cy = (cur - cx) / W;
    for (const [dx, dy] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
      const nx = cx + dx, ny = cy + dy;
      if (nx < 0 || ny < 0 || nx >= W || ny >= H || grid[ny][nx] === 1) continue;
      const next = ny * W + nx;
      const g = cost[cur] + 1;                           // стоимость шага
      if (g < cost[next]) {
        cost[next] = g;
        from[next] = cur;
        const h = Math.abs(nx - tx) + Math.abs(ny - ty); // Манхэттен
        open.push(next, g + h);
      }
    }
  }
  if (from[goal] === -1 && goal !== start) return null;  // пути нет
  const path = [];
  for (let c = goal; c !== -1; c = from[c]) path.push([c % W, Math.floor(c / W)]);
  return path.reverse();
}

Очередь с приоритетом — обычная двоичная куча:

class MinHeap {
  constructor() { this.items = []; this.prio = []; }
  get size() { return this.items.length; }
  push(item, p) {
    this.items.push(item); this.prio.push(p);
    let i = this.items.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.prio[parent] <= this.prio[i]) break;
      this.swap(i, parent); i = parent;
    }
  }
  pop() {
    const top = this.items[0], last = this.items.length - 1;
    this.swap(0, last); this.items.pop(); this.prio.pop();
    let i = 0;
    for (;;) {
      const l = 2 * i + 1, r = l + 1;
      let m = i;
      if (l < this.items.length && this.prio[l] < this.prio[m]) m = l;
      if (r < this.items.length && this.prio[r] < this.prio[m]) m = r;
      if (m === i) break;
      this.swap(i, m); i = m;
    }
    return top;
  }
  swap(a, b) {
    [this.items[a], this.items[b]] = [this.items[b], this.items[a]];
    [this.prio[a], this.prio[b]] = [this.prio[b], this.prio[a]];
  }
}

В код намеренно не добавлена проверка «клетка уже в очереди»: Red Blob Games отмечает, что дубликаты в очереди допустимы, и без такой проверки код заметно проще. Устаревшая запись просто достаётся позже и ничего не улучшает.

Стоимость клеток: трава, вода, лес

Стоимость клетки — это то, что превращает «кратчайший» путь в «удобный». В коде выше она равна 1; достаточно заменить её на значение из таблицы типов тайлов. Red Blob Games приводит пример, где проход по воде в 10 раз дороже, чем по траве, и вспоминает Civilization, где равнина стоит 1 очко движения, а лес и холмы — 5.

стоимость шага = стоимость тайла, в который входим

трава 1, дорога 0,5, лес 3, вода 10, стена — непроходимо

Если самая дешёвая клетка стоит меньше 1 (дорога 0,5), эвристику нужно умножить на минимальную стоимость, иначе она завысит расстояние и путь перестанет быть кратчайшим.

Ничьи и зигзаги

Ничьи возникают, когда у многих клеток одинаковое f, и именно они дают путь-«лесенку» на открытом поле. Red Blob Games в Implementation of A* (проверено: ноябрь 2026) предлагает два приёма:

• Добавка к стоимости. Небольшое число, например 0,001, добавленное к стоимости шага в определённых случаях, заставляет алгоритм последовательно предпочитать один из равных путей.
• Штраф за диагональ. Для 8 направлений добавка 0,001 к стоимости диагонального шага делает выбор между равными путями предсказуемым и убирает лишние диагональные «ступеньки».

Добавка должна быть меньше разницы между реальными стоимостями, иначе она начнёт менять выбор маршрута, а не только разбивать ничьи.

Когда пути нет

Когда цель недостижима, A* просматривает все клетки, до которых может дойти, и только потом сдаётся. Red Blob Games отмечает этот случай отдельно и советует заранее разметить связные области карты. Это делается одной заливкой при загрузке уровня:

function labelRegions(grid) {
  const H = grid.length, W = grid[0].length;
  const region = new Int32Array(W * H).fill(-1);
  let id = 0;
  for (let i = 0; i < W * H; i++) {
    if (region[i] !== -1 || grid[Math.floor(i / W)][i % W] === 1) continue;
    const stack = [i]; region[i] = id;
    while (stack.length) {
      const c = stack.pop(), x = c % W, y = (c - x) / W;
      for (const [nx, ny] of [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]) {
        if (nx < 0 || ny < 0 || nx >= W || ny >= H || grid[ny][nx] === 1) continue;
        const n = ny * W + nx;
        if (region[n] === -1) { region[n] = id; stack.push(n); }
      }
    }
    id++;
  }
  return region;   // если region[старт] !== region[цель], поиск можно не запускать
}

Разметку нужно пересчитывать при изменении карты (разрушенная стена, открытая дверь).

Бюджет кадра и много врагов

Поиск пути не нужно запускать каждый кадр. Red Blob Games сообщает, что в его проектах на JavaScript поиск в ширину обрабатывает больше миллиона узлов в секунду; A* с кучей на узел дороже, поэтому реальные цифры нужно мерить на своей карте.

карта 64 × 36 = 2 304 клетки
кадр при 60 кадрах/с ≈ 16,7 мс

правила:
- пересчитывать путь, когда цель сменила клетку, а не каждый кадр;
- не чаще, например, 4 раз в секунду на одного врага;
- раскладывать запросы разных врагов по разным кадрам;
- измерять время поиска через performance.now() и выводить максимум за секунду.

Если к одной цели (герою) идут десятки врагов, выгоднее один раз запустить поиск в ширину или Дейкстру от героя и получить для каждой клетки направление к нему: стоимость одна, а пользуются результатом все враги сразу.

Чек-лист: враг, который обходит стены

Задача: враг на тайловой карте 64×36 идёт к герою в обход стен. Проверяемый результат — враг не застревает в углах, путь не петляет на открытом поле, а самый долгий поиск за минуту игры укладывается в выбранный бюджет (например, 2 мс).

1. Выберите направления: 4 или 8 — и соответствующую эвристику.
2. Задайте стоимость тайлов таблицей; проверьте, что эвристика умножена на минимальную стоимость.
3. Разметьте связные области при загрузке уровня и при изменении карты.
4. Пересчитывайте путь при смене клетки героя, не чаще заданной частоты.
5. Ведите врага по клеткам пути от центра к центру; при достижении центра берите следующую.
6. Добавьте разбиение ничьих, если путь выглядит «лесенкой».
7. Нарисуйте отладочный слой: просмотренные клетки, путь, значения f — ошибки эвристики видны сразу.
8. Замерьте время самого медленного поиска.

Когда вам это не подойдёт

A* на тайловой сетке — правильный инструмент для персонажей, которые ходят по клеткам сверху или сбоку без прыжков. Случаи, когда нужно другое:

• Платформер с прыжками. Сетка не знает о гравитации; для врагов-прыгунов граф строят из платформ и возможных прыжков между ними.
• Свободное движение по большим открытым картам. Сетка становится огромной; используют навигационные сетки или графы ключевых точек.
• Десятки врагов к одной цели. Одна карта направлений от цели дешевле десятков запусков A*.
• Враг должен выглядеть умным, а не оптимальным. Кратчайший путь — не всегда интересное поведение; иногда достаточно патрулирования и преследования по прямой.

Мы разрабатываем J2DRU — браузерный 2D игровой движок; он в разработке и публично пока не открыт, заявку можно оставить на странице раннего доступа (подача заявки не гарантирует приглашение).

Источники (проверено: ноябрь 2026): Wikipedia — A* search algorithm (авторы, 1968, Shakey, эвристики для сеток, Дейкстра как частный случай); Amit Patel, Red Blob Games — Introduction to the A* Algorithm (поиск в ширину, Дейкстра, жадный поиск, A*, стоимость движения); Red Blob Games — Implementation of A* (дубликаты в очереди, случай «пути нет», ничьи, массивы для целочисленных идентификаторов, скорость поиска в ширину на JavaScript). Код и расчёты бюджета — наш пример.

Читайте также:

• Тайловые сетки и устройство 2D-миров
• Патрулирование врагов и читаемые опасности
• Движение по сетке против свободного движения в 2D-игре