Алгоритм пошуку шляху A* —
від теорії до JavaScript

1. Задача про найкоротший шлях

Задано граф G = (V, E), де кожне ребро (u, v) має невід'ємну вартість w(u,v); потрібно знайти шлях мінімальної вартості від початкового вузла s до цільового вузла g.

Для ігрових сіток граф неявний: клітинки — це вузли, ортогональні/діагональні сусіди — ребра з вартістю 1 (або √2 для діагоналей). Перешкоди — це просто відсутні ребра. Той самий код A* працює на явних графах (дорожні мережі, схеми метро), якщо надати список сусідів замість пошуку на сітці.

2. Алгоритм A*

A* присвоює кожному вузлу n оцінку пріоритету:

Алгоритм підтримує два набори:

• Відкритий набір (черга з пріоритетами) — виявлені вузли, ще не повністю оцінені, упорядковані за f.
• Закритий набір — вузли, що вже оцінені; нам ніколи не доведеться повертатися до них (за допустимої h).

На кожному кроці A* витягує з відкритого набору вузол з найменшим f, розгортає його сусідів, і для кожного сусіда обчислює кандидатне g = g(поточний) + w(поточний, сусід). Якщо це краще за будь-який раніше відомий шлях до цього сусіда, оновлює його та додає до черги.

Наочний хід на сітці 5×5

S = старт (0,0), G = ціль (4,4), стіни сірі. Числа в клітинках показують f-оцінку. Синій = закритий (вже розгорнутий), зелений = відкритий (у черзі), помаранчевий = фінальний шлях.

3. Евристичні функції

Евристика h(n) є допустимою, якщо h(n) ≤ h*(n) для всіх n, де h*(n) — справжня оптимальна вартість від n до цілі. Допустимість гарантує, що A* знайде оптимальний шлях. Узгоджена (монотонна) евристика також задовольняє h(n) ≤ w(n,n') + h(n') для кожного ребра — це означає, що значення f ніколи не спадає вздовж шляху, спрощуючи логіку закритого набору.

4. Реалізація на JavaScript

Наведена нижче реалізація працює на плоскому масиві-сітці, де grid[y * width + x] дорівнює true для прохідних клітинок. Вона повертає оптимальний шлях як масив об'єктів {x, y} або null, якщо шляху немає.

// MinHeap — проста двійкова купа з ключем за .f
class MinHeap {
  constructor() { this.data = []; }
  push(node) {
    this.data.push(node);
    this._bubbleUp(this.data.length - 1);
  }
  pop() {
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length) { this.data[0] = last; this._siftDown(0); }
    return top;
  }
  get size() { return this.data.length; }
  _bubbleUp(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.data[p].f <= this.data[i].f) break;
      [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
      i = p;
    }
  }
  _siftDown(i) {
    const n = this.data.length;
    while (true) {
      let min = i, l = 2*i+1, r = 2*i+2;
      if (l < n && this.data[l].f < this.data[min].f) min = l;
      if (r < n && this.data[r].f < this.data[min].f) min = r;
      if (min === i) break;
      [this.data[min], this.data[i]] = [this.data[i], this.data[min]];
      i = min;
    }
  }
}

// Евристика октильної відстані (8 напрямків, діагональ = √2)
function octile(ax, ay, bx, by) {
  const dx = Math.abs(ax - bx), dy = Math.abs(ay - by);
  return Math.max(dx, dy) + (Math.SQRT2 - 1) * Math.min(dx, dy);
}

/**
 * @param {boolean[]} grid  - плоский масив, true = прохідна
 * @param {number}    width - ширина сітки
 * @param {{x,y}}     start - старт
 * @param {{x,y}}     goal  - ціль
 * @param {boolean}   [diag=true] - дозволити діагональний рух
 * @returns {{x,y}[]|null}
 */
function aStar(grid, width, start, goal, diag = true) {
  const height = grid.length / width;
  const key = (x, y) => y * width + x;

  const gScore = new Float32Array(grid.length).fill(Infinity);
  const cameFrom = new Int32Array(grid.length).fill(-1);
  const closed  = new Uint8Array(grid.length);

  const heap = new MinHeap();
  const sk = key(start.x, start.y);
  gScore[sk] = 0;
  heap.push({ x: start.x, y: start.y, f: octile(start.x, start.y, goal.x, goal.y) });

  const dirs = diag
    ? [[-1,-1],[0,-1],[1,-1],[-1,0],[1,0],[-1,1],[0,1],[1,1]]
    : [[0,-1],[-1,0],[1,0],[0,1]];

  while (heap.size) {
    const cur = heap.pop();
    if (cur.x === goal.x && cur.y === goal.y) return reconstruct(cameFrom, width, key(cur.x, cur.y));
    const ck = key(cur.x, cur.y);
    if (closed[ck]) continue;
    closed[ck] = 1;
    for (const [dx, dy] of dirs) {
      const nx = cur.x + dx, ny = cur.y + dy;
      if (nx < 0 || ny < 0 || nx >= width || ny >= height) continue;
      const nk = key(nx, ny);
      if (!grid[nk] || closed[nk]) continue;
      const moveCost = (dx !== 0 && dy !== 0) ? Math.SQRT2 : 1;
      const tentG = gScore[ck] + moveCost;
      if (tentG < gScore[nk]) {
        gScore[nk] = tentG;
        cameFrom[nk] = ck;
        heap.push({ x: nx, y: ny, f: tentG + octile(nx, ny, goal.x, goal.y) });
      }
    }
  }
  return null; // шляху немає
}

function reconstruct(cameFrom, width, goalKey) {
  const path = [];
  let k = goalKey;
  while (k !== -1) {
    path.push({ x: k % width, y: Math.floor(k / width) });
    k = cameFrom[k];
  }
  return path.reverse();
}

5. Черга з пріоритетами та розв'язання нічиїх

Ефективність A* повністю залежить від черги з пріоритетами. Двійкова мінімальна купа дає O(log N) для додавання й витягування. Для дуже великих сіток купа Фібоначчі дає амортизовану O(1) для зменшення ключа, але на практиці рідко виправдовує складність реалізації.

Розв'язання нічиїх критично важливе для продуктивності. Коли багато вузлів мають однакову f-оцінку, A* досліджує їх у довільному порядку. Додавання невеликого розв'язувача нічиїх на основі векторного добутку (надавати перевагу вузлам, чий поточний напрямок збігається з вектором старт→ціль) зменшує кількість досліджених вузлів на 30–50% на відкритій місцевості:

// Трохи зсуваємо f у бік прямолінійного коридору
function hTieBreak(nx, ny, gx, gy, sx, sy) {
  const dx1 = nx - gx, dy1 = ny - gy;
  const dx2 = sx - gx, dy2 = sy - gy;
  const cross = Math.abs(dx1*dy2 - dx2*dy1);
  return octile(nx, ny, gx, gy) + cross * 0.001;
}

6. Дейкстра, BFS і зважений A*

A* — це узагальнення. Задаючи h різні значення, відновлюємо добре відомі алгоритми:

В ігровому ШІ ієрархічний пошук шляху A* (HPA*) будує дворівневу ієрархію: абстрактний граф на рівні кластерів + шляхи всередині кластерів. Дальні запити виконуються на малому абстрактному графі; точні шляхи обчислюються лише поблизу агента. Саме так RTS-ігри керують сотнями юнітів на картах 512×512 в реальному часі.

Jump Point Search (JPS) використовує симетрію рівномірно зваженої сітки: він пропускає надлишкові симетричні шляхи й стрибає до «цікавих» вузлів, зменшуючи кількість досліджених вузлів у 10–40 разів порівняно зі звичайним A* на відкритих сітках без попередньої обробки.

7. Складність і практичні нотатки

• Часова складність: O(b^d) у найгіршому випадку, де b = коефіцієнт розгалуження, d = глибина. З досконалою евристикою (h = h*) розгортаються лише вузли на оптимальному шляху.
• Просторова складність: O(b^d) — відкритий набір може містити експоненційно багато вузлів. Варіанти з обмеженою пам'яттю (SMA*, RBFS) обмежують це ціною повторного розгортання.
• Допустимість проти узгодженості: узгодженість (монотонність) передбачає допустимість і означає, що кожен вузол розгортається щонайбільше один раз. Завжди надавайте перевагу узгодженим евристикам.
• Динамічні графи: D* Lite (динамічний A*) ефективно переплановує, коли змінюються ваги ребер (наприклад, нові перешкоди, виявлені сенсором робота). Він поширює зміни назад від цілі, а не переплановує з нуля.
• Попередньо обчислені таблиці: бази даних шаблонів (PDB) попередньо обчислюють h для підзадач, даючи тісніші нижні межі. Широко використовуються в розв'язанні головоломок (15-пазл, кубик Рубіка).

Пов'язаний вміст