Створення візуалізатора пошуку шляху

Сітка — це плоский Uint8Array для ефективного використання кешу. Кожна комірка: 0 = відкрита, 1 = стіна, 2 = старт, 3 = фініш, 4 = відвідана, 5 = шлях:

const COLS = 40, ROWS = 30;
const CELL = 20; // пікселів на комірку
const canvas = document.getElementById('grid');
const ctx = canvas.getContext('2d');
canvas.width  = COLS * CELL;
canvas.height = ROWS * CELL;

const grid = new Uint8Array(COLS * ROWS); // плоский масив

const idx = (c, r) => r * COLS + c;

const COLORS = {
  0: '#1a1a2e', // відкрита
  1: '#334155', // стіна
  2: '#22c55e', // старт
  3: '#ef4444', // фініш
  4: '#1e40af', // відвідана
  5: '#facc15', // шлях
};

function render() {
  for (let r = 0; r < ROWS; r++) {
    for (let c = 0; c < COLS; c++) {
      ctx.fillStyle = COLORS[grid[idx(c, r)]];
      ctx.fillRect(c * CELL + 1, r * CELL + 1, CELL - 2, CELL - 2);
    }
  }
}

І Дейкстрі, і A* потрібно ефективно діставати вузол з мінімальною вартістю. Бінарна мінімальна купа дає push/pop за O(log N):

class MinHeap {
  constructor() { this.data = []; }
  push(item) {
    this.data.push(item);
    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._sinkDown(0); }
    return top;
  }
  get size() { return this.data.length; }
  _bubbleUp(i) {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.data[parent].f <= this.data[i].f) break;
      [this.data[parent], this.data[i]] = [this.data[i], this.data[parent]];
      i = parent;
    }
  }
  _sinkDown(i) {
    const n = this.data.length;
    while (true) {
      let smallest = i;
      const l = 2*i+1, r = 2*i+2;
      if (l < n && this.data[l].f < this.data[smallest].f) smallest = l;
      if (r < n && this.data[r].f < this.data[smallest].f) smallest = r;
      if (smallest === i) break;
      [this.data[smallest], this.data[i]] = [this.data[i], this.data[smallest]];
      i = smallest;
    }
  }
}

Дейкстра гарантує найкоротший шлях на сітках з однаковою вартістю переходів. Він досліджує одночасно в усіх напрямках, наче вода, що розтікається назовні:

function dijkstra(startC, startR, endC, endR) {
  const dist = new Float32Array(COLS * ROWS).fill(Infinity);
  const prev = new Int32Array(COLS * ROWS).fill(-1);
  const heap = new MinHeap();

  const start = idx(startC, startR);
  dist[start] = 0;
  heap.push({ f: 0, i: start });

  const steps = []; // для анімації

  while (heap.size) {
    const { i } = heap.pop();
    if (i === idx(endC, endR)) break;

    const c = i % COLS, r = Math.floor(i / COLS);
    steps.push({ type: 'visit', i });

    // Сусіди в 4 напрямках
    for (const [dc, dr] of [[1,0],[-1,0],[0,1],[0,-1]]) {
      const nc = c + dc, nr = r + dr;
      if (nc < 0 || nc >= COLS || nr < 0 || nr >= ROWS) continue;
      const ni = idx(nc, nr);
      if (grid[ni] === 1) continue; // стіна
      const newDist = dist[i] + 1;
      if (newDist < dist[ni]) {
        dist[ni] = newDist;
        prev[ni] = i;
        heap.push({ f: newDist, i: ni });
      }
    }
  }

  // Відновлюємо шлях
  const path = [];
  let cur = idx(endC, endR);
  while (cur !== -1) { path.push(cur); cur = prev[cur]; }
  return { steps, path: path.reverse() };
}

A* додає евристику, що скеровує розширення до цілі. На сітці без діагоналей манхеттенська відстань є допустимою (ніколи не завищує) та ефективною:

// Евристика манхеттенської відстані
function heuristic(c, r, endC, endR) {
  return Math.abs(c - endC) + Math.abs(r - endR);
}

function aStar(startC, startR, endC, endR) {
  const g = new Float32Array(COLS * ROWS).fill(Infinity);
  const prev = new Int32Array(COLS * ROWS).fill(-1);
  const heap = new MinHeap();
  const steps = [];

  const start = idx(startC, startR);
  g[start] = 0;
  heap.push({ f: heuristic(startC, startR, endC, endR), i: start });

  while (heap.size) {
    const { i } = heap.pop();
    if (i === idx(endC, endR)) break;

    const c = i % COLS, r = Math.floor(i / COLS);
    steps.push({ type: 'visit', i });

    for (const [dc, dr] of [[1,0],[-1,0],[0,1],[0,-1]]) {
      const nc = c + dc, nr = r + dr;
      if (nc < 0 || nc >= COLS || nr < 0 || nr >= ROWS) continue;
      const ni = idx(nc, nr);
      if (grid[ni] === 1) continue; // стіна
      const ng = g[i] + 1;
      if (ng < g[ni]) {
        g[ni] = ng;
        prev[ni] = i;
        const h = heuristic(nc, nr, endC, endR);
        heap.push({ f: ng + h, i: ni });
      }
    }
  }

  const path = [];
  let cur = idx(endC, endR);
  while (cur !== -1) { path.push(cur); cur = prev[cur]; }
  return { steps, path: path.reverse() };
}

function animate(steps, path, speed = 15) {
  let stepIndex = 0;

  function frame() {
    // Обробляємо `speed` кроків за кадр
    for (let s = 0; s < speed && stepIndex < steps.length; s++, stepIndex++) {
      const { i } = steps[stepIndex];
      if (grid[i] !== 2 && grid[i] !== 3) grid[i] = 4; // позначаємо як відвідану
    }

    render();

    if (stepIndex < steps.length) {
      requestAnimationFrame(frame);
    } else {
      // Малюємо шлях після завершення
      for (const i of path) {
        if (grid[i] !== 2 && grid[i] !== 3) grid[i] = 5;
      }
      render();
    }
  }
  requestAnimationFrame(frame);
}

let painting = false;
let paintType = 1; // 1 = стіна, 0 = стерти

canvas.addEventListener('mousedown', e => {
  painting = true;
  paintType = e.button === 2 ? 0 : 1; // правий клік стирає
  paint(e);
});
canvas.addEventListener('mousemove', e => { if (painting) paint(e); });
canvas.addEventListener('mouseup',   () => painting = false);
canvas.addEventListener('contextmenu', e => e.preventDefault());

function paint(e) {
  const rect = canvas.getBoundingClientRect();
  const c = Math.floor((e.clientX - rect.left) / CELL);
  const r = Math.floor((e.clientY - rect.top)  / CELL);
  if (c < 0 || c >= COLS || r < 0 || r >= ROWS) return;
  const i = idx(c, r);
  if (grid[i] === 2 || grid[i] === 3) return; // не перезаписуємо старт/фініш
  grid[i] = paintType;
  render();
}

Щоб запустити обидва й порівняти кількість відвіданих вузлів, запустіть кожен на копії сітки:

function runAndCompare() {
  const startC = 1, startR = 1, endC = COLS-2, endR = ROWS-2;

  const resD = dijkstra(startC, startR, endC, endR);
  const resA = aStar(startC, startR, endC, endR);

  console.log(`Дейкстра відвідано: ${resD.steps.length}, шлях: ${resD.path.length}`);
  console.log(`A* відвідано:       ${resA.steps.length}, шлях: ${resA.path.length}`);

  // На відкритій сітці A* зазвичай відвідує на 60-80% менше вузлів, ніж Дейкстра
}