EN 
Українська🎮 Пошук шляху NPC у грі — A* пошук наживо
Спостерігайте, як справжній алгоритм пошуку A* розширює вузли симульованої ігрової карти наживо за справжньою вартістю f=g+h, знаходячи доведено найкоротші шляхи NPC навколо перешкод швидше за звичайний алгоритм Дейкстри.
Про симуляцію «A* пошук наживо»
Ігрові рушії постійно ставлять одне й те саме питання: який найкоротший прохідний маршрут від NPC до його цілі через карту, повну стін, місцевості та інших перешкод? Пошук A* (Харт, Нільссон і Рафаель, 1968) — це робоча відповідь: пошук найкращого-першого в графі, який підтримує справжню чергу з пріоритетом, впорядковану за f(n) = g(n) + h(n), де g(n) — це реальна накопичена вартість від старту, а h(n) — допустима евристична оцінка відстані, що залишилася. Ця симуляція виконує справжній алгоритм — справжній відкритий набір, справжній закритий набір, справжні батьківські вказівники — на ігровій карті-сітці, яку ви можете редагувати, і водночас виконує звичайний алгоритм Дейкстри (A* з h(n) = 0) на ідентичній карті, тож ви можете спостерігати, вузол за вузлом, скільки саме роботи заощаджує евристика.
🔬 Що показано
Дві сітки поруч, що спільно використовують одну карту перешкод: ліва сітка виконує справжній A* з октильно-відстаневою евристикою, права сітка виконує Дейкстру з евристикою, примусово зведеною до нуля. Блакитні клітинки належать до відкритого набору (виявлені, у черзі, ще не розширені), бурштинові клітинки — до закритого набору (розширені, завершені), а шлях акцентного кольору — це найкоротший маршрут, відновлений через батьківські вказівники, щойно вузол цілі витягується. Живі лічильники підсумовують реальну кількість вузлів, які кожна черга з пріоритетом справді витягнула.
🎮 Як користуватися
Оберіть режим — Стіна, Старт або Ціль — потім клацніть будь-яку клітинку на будь-якій сітці, щоб редагувати спільну карту; обидва пошуки миттєво перезапускаються. Використовуйте «Випадковий лабіринт», щоб згенерувати нову схему перешкод, «Очистити стіни», щоб почати з відкритого поля, і повзунок швидкості розширення, щоб уповільнити показ для навчання або пришвидшити, щоб одразу побачити фінальний шлях. «Повтор» перезапускає покрокову анімацію без повторного обчислення пошуку.
💡 А чи знали ви?
Оскільки алгоритм Дейкстри математично ідентичний A* з h(n)=0, обидві панелі виконують точно той самий шлях коду зі зміненим одним числом — саме тому це чесне, порівнюване зіставлення, а не дві непов'язані реалізації. На відкритих картах A* часто розширює менше половини вузлів, ніж Дейкстра; на картах, де стіна змушує обидва алгоритми йти довгим обхідним шляхом, розрив зменшується, бо жоден не може скоротити геометрію, яку евристика не бачить наскрізь.
Часті питання
Що таке пошук A* і чим він відрізняється від алгоритму Дейкстри?
Обидва — це пошуки найкращого-першого в графі, які на кожному кроці витягують вузол з найменшою вартістю з черги з пріоритетом (відкритого набору). Алгоритм Дейкстри впорядковує цю чергу виключно за g(n), реальною накопиченою вартістю від початкового вузла, тож він досліджує назовні в усіх напрямках однаково, як брижі на ставку. A* впорядковує ту саму чергу за f(n) = g(n) + h(n), додаючи допустиму евристичну оцінку h(n) відстані, що залишилася до цілі. Цей додатковий член зміщує розширення в бік цілі, тож A* зазвичай закриває набагато менше вузлів, ніж Дейкстра, при цьому гарантовано повертаючи той самий найкоротший шлях, оскільки виконання Дейкстри математично ідентичне виконанню A* з h(n) = 0 для кожного вузла — саме так ця симуляція реалізує порівняння на одній спільній карті.
Що робить евристику допустимою і чому це гарантує, що A* знаходить найкоротший шлях?
Евристика h(n) є допустимою, якщо вона ніколи не переоцінює справжню решту вартості від вузла n до цілі — вона може недооцінювати або бути точно правильною, але ніколи не бути надто оптимістичною в неправильному напрямку. На сітці, де діагональні кроки коштують √2, а ортогональні — 1, пряма (октильна) відстань до цілі завжди менша або дорівнює справжній решті вартості шляху навколо перешкод, тож вона допустима. З допустимою евристикою A* гарантовано ніколи не завершує вузол із неоптимальним g-значенням: будь-який шлях, який він повідомляє як найкоротший, дійсно є найкоротшим, тому симуляція може стверджувати, що A* і Дейкстра завжди дають однакову вартість шляху, а не лише схожу.
Що таке октильна відстань і навіщо її використовують на картах-сітках, що дозволяють діагональний рух?
Октильна відстань — це евристика для 8-напрямкових сіток: маючи |dx| і |dy| клітинок горизонтального й вертикального розділення, найкоротший можливий шлях (ігноруючи перешкоди) рухається по діагоналі min(|dx|,|dy|) разів вартістю √2 кожен, потім покриває решту |dx|−|dy| клітинок ортогонально вартістю 1 кожна. Формула (|dx|+|dy|) + (√2−2)·min(|dx|,|dy|) обчислює точно це. Звичайна евклідова чи манхеттенська відстань або переоцінювала б (порушуючи допустимість на сітці з діагональним рухом), або недооцінювала б надто грубо, тож октильна відстань — це точний, допустимий вибір, який ця симуляція використовує для h(n) алгоритму A*.
Чому A* зазвичай розширює менше вузлів, ніж Дейкстра?
Дейкстра не має уявлення про те, де ціль, тож її фронт розширення росте як приблизно кругова хвиля, центрована на старті, торкаючись кожного вузла в межах заданого радіуса вартості, перш ніж досягти цілі. Впорядкування f = g + h алгоритму A* тримає вузли, що вказують у бік цілі, ближче до початку черги з пріоритетом, тож його фронт витягується в подовжену, спрямовану до цілі форму й пропускає великі регіони з дальнього боку карти, які Дейкстрі все одно довелося б відвідати. Живі лічильники в цій симуляції підсумовують реальну кількість вузлів, які кожен алгоритм справді витягнув і закрив зі своєї власної черги з пріоритетом на ідентичній карті перешкод, тож розрив, який ви бачите, є справжньою, виміряною різницею, а не припущеною — а на картах, де пряму лінію до цілі блокує велика перешкода, розрив може зменшитися або навіть зникнути, що симуляція чесно покаже.
Яка різниця між відкритим набором і закритим набором?
Відкритий набір — це фронт: вузли, які були виявлені (досягнуті від якогось сусіда) і поміщені в чергу з пріоритетом, але ще не розширені. Закритий набір — це вузли, які вже витягнуті з черги, і всі їхні сусіди були розглянуті — їхня найкоротша g-вартість від старту завершена і більше не зміниться. У візуалізації блакитні клітинки належать до відкритого набору (кандидати, що все ще розглядаються), а бурштинові клітинки — до закритого набору (повністю оброблені); щойно ціль витягується із закритого набору, алгоритм зупиняється й відновлює шлях, проходячи батьківські вказівники назад від цілі до старту.
Чи може A* коли-небудь не знайти найкоротший шлях або взагалі не знайти шлях?
A* гарантовано знаходить найкоротший шлях, якщо він існує, а його евристика допустима — октильно-відстанева евристика цієї симуляції задовольняє цю умову на кожній карті, яку ви будуєте. Чого A* не може зробити, це знайти шлях, якого не існує: якщо ви повністю відгородите ціль стінами, і A*, і Дейкстра вичерпають свої відкриті набори й повідомлять про відсутність шляху, що панель статистики покаже явно, а не мовчки показуватиме застарілий маршрут.
Черга з пріоритетом на основі бінарної купи розширює вузли у справжньому порядку найкращого-першого за f(n)=g(n)+h(n) на лівій сітці та f(n)=g(n) на правій; обидві відновлюють найкоротший шлях через справжні батьківські вказівники, щойно ціль витягується із закритого набору.
3D · рушій Three.js / WebGL · ціль 60 FPS · працює повністю на клієнті, без встановлення