Алгоритм A*: пошук шляху в іграх і на картах

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

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

Подробиці

Ідея: f = g + h

Див. також: алгоритм Дейкстри, пошук у ширину та в глибину, купа та черга з пріоритетом, ігровий цикл