PL 
Українська🎮 Wyszukiwacz ścieżek NPC w grze — algorytm A* na żywo
Obserwuj, jak prawdziwy algorytm przeszukiwania A* na żywo rozwija węzły symulowanej mapy gry według rzeczywistego kosztu f=g+h, znajdując dowiedzione najkrótsze ścieżki NPC wokół przeszkód szybciej niż zwykły Dijkstra.
O symulacji Wyszukiwacza ścieżek A* na żywo
Silniki gier wciąż zadają to samo pytanie: jaka jest najkrótsza możliwa do przejścia trasa od NPC do jego celu na mapie pełnej ścian, terenu i innych przeszkód? Przeszukiwanie A* (Hart, Nilsson i Raphael, 1968) to standardowa odpowiedź — przeszukiwanie grafu typu best-first, które utrzymuje prawdziwą kolejkę priorytetową uporządkowaną według f(n) = g(n) + h(n), gdzie g(n) to rzeczywisty skumulowany koszt od startu, a h(n) to dopuszczalne heurystyczne oszacowanie pozostałego dystansu. Ta symulacja uruchamia rzeczywisty algorytm — prawdziwy zbiór otwarty, prawdziwy zbiór zamknięty, prawdziwe wskaźniki rodziców — na siatkowej mapie gry, którą możesz edytować, i jednocześnie uruchamia zwykły algorytm Dijkstry (A* z h(n) = 0) na identycznej mapie, dzięki czemu możesz obserwować węzeł po węźle, ile pracy oszczędza heurystyka.
🔬 Co pokazuje
Dwie siatki obok siebie dzielące jedną mapę przeszkód: lewa siatka uruchamia prawdziwy A* z heurystyką odległości oktylowej, prawa siatka uruchamia Dijkstrę z heurystyką wymuszoną na zero. Cyjanowe komórki znajdują się w zbiorze otwartym (odkryte, w kolejce, jeszcze nie rozwinięte), bursztynowe komórki są w zbiorze zamkniętym (rozwinięte, sfinalizowane), a ścieżka w kolorze akcentu to najkrótsza trasa odtworzona przez wskaźniki rodziców po zdjęciu węzła celu. Liczniki na żywo sumują rzeczywistą liczbę węzłów faktycznie zdjętych przez każdą kolejkę priorytetową.
🎮 Jak korzystać
Wybierz tryb — Ściana, Start lub Cel — a następnie kliknij dowolną komórkę na dowolnej siatce, aby edytować wspólną mapę; oba przeszukiwania uruchamiają się ponownie natychmiast. Użyj Losowego labiryntu, aby wygenerować nowy układ przeszkód, Wyczyść ściany, aby zacząć od otwartego pola, oraz suwaka prędkości ekspansji, aby spowolnić odsłanianie na potrzeby nauczania lub przyspieszyć je, aby od razu zobaczyć ostateczną ścieżkę. Powtórz uruchamia animację węzeł po węźle ponownie bez przeliczania przeszukiwania.
💡 Czy wiesz, że?
Ponieważ algorytm Dijkstry jest matematycznie identyczny z A* przy h(n)=0, oba panele uruchamiają dokładnie tę samą ścieżkę kodu ze zmienioną jedną liczbą — dlatego jest to uczciwe porównanie jabłek z jabłkami, a nie dwie niepowiązane implementacje. Na otwartych mapach A* często rozwija mniej niż połowę węzłów, które rozwija Dijkstra; na mapach, gdzie ściana zmusza oba algorytmy do długiego objazdu, różnica maleje, ponieważ żaden z nich nie może skrócić geometrii, przez którą heurystyka nie widzi.
Najczęściej zadawane pytania
Czym jest przeszukiwanie A* i czym różni się od algorytmu Dijkstry?
Oba są przeszukiwaniami grafu typu best-first, które na każdym kroku pobierają węzeł o najniższym koszcie z kolejki priorytetowej (zbioru otwartego). Algorytm Dijkstry porządkuje tę kolejkę wyłącznie według g(n), czyli rzeczywistego skumulowanego kosztu od węzła startowego, więc eksploruje na zewnątrz równomiernie we wszystkich kierunkach, niczym fale na stawie. A* porządkuje tę samą kolejkę według f(n) = g(n) + h(n), dodając dopuszczalne heurystyczne oszacowanie h(n) pozostałego dystansu do celu. Ten dodatkowy człon kieruje ekspansję w stronę celu, dzięki czemu A* zazwyczaj zamyka znacznie mniej węzłów niż Dijkstra, wciąż gwarantując zwrócenie tej samej najkrótszej ścieżki kosztowej, ponieważ przebieg Dijkstry jest matematycznie identyczny z przebiegiem A* przy h(n) = 0 dla każdego węzła — dokładnie tak ta symulacja implementuje porównanie na jednej wspólnej mapie.
Co sprawia, że heurystyka jest dopuszczalna i dlaczego to gwarantuje, że A* znajduje najkrótszą ścieżkę?
Heurystyka h(n) jest dopuszczalna, jeśli nigdy nie przeszacowuje prawdziwego pozostałego kosztu od węzła n do celu — może go nieszacować lub trafiać dokładnie, ale nigdy nie być zbyt optymistyczna w złym kierunku. Na siatce, gdzie ruch po przekątnej kosztuje √2, a ruch prostopadły 1, odległość liniowa (oktylowa) do celu jest zawsze mniejsza lub równa rzeczywistemu pozostałemu kosztowi ścieżki wokół przeszkód, więc jest dopuszczalna. Przy dopuszczalnej heurystyce A* ma gwarancję, że nigdy nie sfinalizuje węzła z nieoptymalną wartością g: każda ścieżka zgłoszona jako najkrótsza rzeczywiście taka jest, dlatego symulacja może twierdzić, że A* i Dijkstra zawsze osiągają ten sam koszt ścieżki, a nie tylko podobny.
Czym jest odległość oktylowa i dlaczego stosuje się ją na mapach siatkowych dopuszczających ruch po przekątnej?
Odległość oktylowa to heurystyka dla siatek 8-kierunkowych: mając |dx| i |dy| komórek separacji poziomej i pionowej, najkrótsza możliwa ścieżka (pomijając przeszkody) porusza się po przekątnej min(|dx|,|dy|) razy kosztem √2 każdy, a następnie pokonuje pozostałe |dx|−|dy| komórek prostopadle kosztem 1 każdy. Wzór (|dx|+|dy|) + (√2−2)·min(|dx|,|dy|) oblicza dokładnie to. Zwykła odległość euklidesowa lub Manhattan albo przeszacowałaby (łamiąc dopuszczalność na siatce z ruchem po przekątnej), albo niedoszacowywałaby zbyt luźno, więc odległość oktylowa jest ścisłym, dopuszczalnym wyborem, jakiego ta symulacja używa dla h(n) algorytmu A*.
Dlaczego A* zwykle rozwija mniej węzłów niż Dijkstra?
Dijkstra nie ma pojęcia, gdzie znajduje się cel, więc jego front ekspansji rośnie jako mniej więcej okrągła fala wyśrodkowana na starcie, dotykając każdego węzła w danym promieniu kosztu, zanim dotrze do celu. Uporządkowanie A* według f = g + h utrzymuje węzły skierowane w stronę celu bliżej czoła kolejki priorytetowej, więc jego front rozciąga się w wydłużony, ukierunkowany na cel kształt i pomija duże obszary po drugiej stronie mapy, które Dijkstra nadal musiałby odwiedzić. Liczniki na żywo w tej symulacji sumują rzeczywistą liczbę węzłów, które każdy algorytm faktycznie zdjął i zamknął z własnej kolejki priorytetowej na identycznej mapie przeszkód, więc obserwowana różnica jest prawdziwa i zmierzona, a nie zakładana — a na mapach, gdzie linia prosta do celu jest zablokowana przez dużą przeszkodę, różnica może się zmniejszyć lub nawet zniknąć, co symulacja pokaże uczciwie.
Jaka jest różnica między zbiorem otwartym a zbiorem zamkniętym?
Zbiór otwarty to front: węzły, które zostały odkryte (osiągnięte od jakiegoś sąsiada) i umieszczone w kolejce priorytetowej, ale jeszcze nie rozwinięte. Zbiór zamknięty to węzły, które zostały już zdjęte z kolejki i miały zbadanych wszystkich sąsiadów — ich najkrótszy koszt g od startu jest sfinalizowany i już się nie zmieni. W wizualizacji cyjanowe komórki znajdują się w zbiorze otwartym (kandydaci wciąż rozważani), a bursztynowe komórki w zbiorze zamkniętym (w pełni przetworzone); gdy cel zostaje zdjęty ze zbioru zamkniętego, algorytm zatrzymuje się i odtwarza ścieżkę, przechodząc wstecz przez wskaźniki rodziców od celu do startu.
Czy A* może kiedykolwiek nie znaleźć najkrótszej ścieżki albo w ogóle nie znaleźć ścieżki?
A* ma gwarancję znalezienia najkrótszej ścieżki, jeśli tylko istnieje ona i jego heurystyka jest dopuszczalna — heurystyka odległości oktylowej tej symulacji spełnia ten warunek na każdej zbudowanej przez ciebie mapie. Czego A* nie potrafi, to znaleźć ścieżki, która nie istnieje: jeśli całkowicie odgrodzisz cel ścianami, zarówno A*, jak i Dijkstra wyczerpią swoje zbiory otwarte i zgłoszą brak ścieżki, co panel statystyk pokaże jawnie, zamiast po cichu wyświetlać nieaktualną trasę.
Kolejka priorytetowa oparta na kopcu binarnym rozwija węzły w prawdziwym porządku best-first według f(n)=g(n)+h(n) na lewej siatce i f(n)=g(n) na prawej; obie odtwarzają najkrótszą ścieżkę przez prawdziwe wskaźniki rodziców po zdjęciu celu ze zbioru zamkniętego.
3D · silnik Three.js / WebGL · cel 60 FPS · działa w pełni po stronie klienta, bez instalacji