A* (A-Star)
Основа всієї сучасної навігації (Google Maps, NPC в іграх).
Секрет успіху (F = G + H):
- G (Cost): Скільки ми вже пройшли. Гарантує, що шлях реальний.
- H (Heuristic): "Інтуїція". Відстань до фінішу по прямій. Тягне алгоритм у правильному напрямку.
Якщо прибрати H (евристику), A* перетворюється на Dijkstra (гарантовано найкоротший, але перевіряє всі напрямки як кола на воді).
Старт
Фініш
Стіна
Шлях
Закриті
Відкриті