🗺️ Wyszukiwanie ścieżki — A*, Dijkstra, BFS

Traktuje siatkę jako graf i animuje, jak wybrany algorytm przeszukuje przestrzeń od komórki startowej do komórki końcowej, kolorując zbiór otwarty, odwiedzone (zamknięte) komórki i ostateczną najkrótszą ścieżkę. Liczniki na żywo pokazują liczbę odwiedzonych komórek i długość wynikowej ścieżki, dzięki czemu można porównać efektywność z optymalnością.

A* utrzymuje kolejkę priorytetową uporządkowaną według f(n) = g(n) + h(n). Wartość g to liczba kroków od startu, a h szacuje pozostałą odległość do celu. W każdym kroku rozwija komórkę o najniższym f, co kieruje przeszukiwanie w stronę celu, jednocześnie gwarantując najkrótszą ścieżkę, gdy heurystyka nigdy nie przeszacowuje.

Oba używają tego samego wzoru f = g + h, ale innej heurystyki. Odległość Manhattan sumuje różnice poziome i pionowe (|dr| + |dc|), co dokładnie pasuje do siatki z ruchem w 4 kierunkach. Odległość euklidesowa wykorzystuje przeciwprostokątną linię prostą, która bardziej niedoszacowuje na siatce bez ruchu po przekątnej, więc może eksplorować nieco więcej komórek.

Dijkstra to A* z h ustawionym na zero, więc przeszukuje wyłącznie na podstawie skumulowanego kosztu i rozszerza się równomiernie we wszystkich kierunkach. Greedy Best-First używa f = h, pędząc w stronę celu wyłącznie na podstawie oszacowania, co jest szybkie, ale ściany mogą zwieść go na dłuższą trasę. BFS używa zwykłej kolejki FIFO zamiast kolejki priorytetowej.

A* (z dopuszczalną heurystyką), Dijkstra i BFS zawsze zwracają gwarantowaną najkrótszą ścieżkę na tej jednorodnej siatce kosztów, ponieważ każdy krok kosztuje jeden. Greedy Best-First nie gwarantuje optymalności; często szybko znajduje trasę, ale może obrać dłuższy objazd wokół przeszkód, ponieważ ignoruje już poniesiony koszt.

Etykiety Ściana, Start, Koniec i Gumka określają, co robi kliknięcie lub przeciąganie po siatce. Ściana blokuje komórki, Start i Koniec przenoszą zielony i czerwony punkt końcowy, a Gumka usuwa ściany. Suwak prędkości wybiera, ile kroków przeszukiwania wykonuje się na klatkę animacji, od jednego kroku do stu, pozwalając oglądać powoli lub rozwiązać natychmiast.

Niebieskie półprzezroczyste komórki to zbiór otwarty wciąż oczekujący na eksplorację, ciemnoniebieskie komórki to zbiór zamknięty już odwiedzony, a żółty oznacza zrekonstruowaną najkrótszą ścieżkę. Porównanie rozmiaru obszaru zamkniętego między algorytmami pokazuje ich efektywność: A* zwykle odwiedza znacznie mniej komórek niż Dijkstra, aby osiągnąć ten sam cel.

Przycisk Generuj labirynt wypełnia siatkę ścianami, a następnie uruchamia rekurencyjny algorytm cofania. Zaczynając od komórki w rogu, wykuwa przejścia po dwie komórki naraz w losowo przetasowanej kolejności, burząc ścianę między połączonymi komórkami. Wynikiem jest idealny labirynt z dokładnie jedną ścieżką między dowolnymi dwiema otwartymi komórkami.

Tak. Za każdym razem, gdy komórka jest osiągana po raz pierwszy, algorytm zapisuje, z jakiego sąsiada przyszedł, w mapie poprzedników. Gdy komórka końcowa zostaje zdjęta z kolejki, trasa jest odtwarzana przez podążanie tymi powiązaniami wstecz od celu do startu, a następnie odwracana, aby dać ścieżkę w przód podświetloną na żółto.

A* i Dijkstra stanowią podstawę planerów tras GPS i map, ruchu postaci niesterowanych w grach wideo oraz nawigacji robotów magazynowych i dostawczych. Te same idee przeszukiwania grafów rozciągają się na trasowanie sieci, rozwiązywanie łamigłówek i logistykę. A* został po raz pierwszy opracowany w 1968 roku w Stanford Research Institute dla robota Shakey.