Jak działa wyszukiwanie ścieżek A *?

Chciałbym zrozumieć na podstawowym poziomie, w jaki sposób działa wyszukiwanie ścieżek A *. Pomocne będą wszelkie implementacje kodu lub psuedo-code, a także wizualizacje.

Zrzeczenie się

Istnieje mnóstwo przykładów kodu i objaśnień A *, które można znaleźć w Internecie. To pytanie otrzymało również wiele świetnych odpowiedzi z wieloma przydatnymi linkami. W mojej odpowiedzi postaram się podać ilustrowany przykład algorytmu, który może być łatwiejszy do zrozumienia niż kod lub opisy.

Algorytm Dijkstry

Aby zrozumieć A *, sugeruję najpierw przyjrzeć się algorytmowi Dijkstry . Pozwól, że poprowadzę cię przez kroki, które algorytm Dijkstry wykona dla wyszukiwania.

Nasz węzeł początkowy jest Ai chcemy znaleźć najkrótszą ścieżkę do F. Każda krawędź wykresu ma związany z tym koszt ruchu (oznaczony jako czarne cyfry obok krawędzi). Naszym celem jest ocena minimalnego kosztu podróży dla każdego wierzchołka (lub węzła) wykresu, dopóki nie osiągniemy naszego węzła celu.

To jest nasz punkt wyjścia. Mamy do sprawdzenia węzły listy, obecnie jest to:

{ A(0) }

Ama koszt 0, wszystkie inne węzły są ustawione na nieskończoność (w typowej implementacji byłoby to coś podobnego int.MAX_VALUElub podobnego).

Bierzemy węzeł o najniższym koszcie z naszej listy węzłów (ponieważ nasza lista zawiera tylko A, to jest nasz kandydat) i odwiedzamy wszystkich jego sąsiadów. Ustalamy koszt każdego sąsiada:

Cost_of_Edge + Cost_of_previous_Node

i śledzić poprzedni węzeł (pokazany jako mała różowa litera poniżej węzła). Amoże być teraz oznaczony jako rozwiązany (czerwony), abyśmy go więcej nie odwiedzali. Nasza lista kandydatów wygląda teraz następująco:

{ B(2), D(3), C(4) }

Ponownie bierzemy węzeł o najniższym koszcie z naszej listy ( B) i oceniamy jego sąsiadów. Ścieżka do Djest droższa niż obecny koszt D, dlatego można ją odrzucić. Ezostaną dodane do naszej listy kandydatów, która teraz wygląda następująco:

{ D(3), C(4), E(4) }

Następny węzeł do sprawdzenia jest teraz D. Połączenie z Cmożna odrzucić, ponieważ ścieżka nie jest krótsza niż istniejący koszt. Znaleźliśmy krótszą ścieżkę E, więc koszt Ei poprzedni węzeł zostaną zaktualizowane. Nasza lista wygląda teraz tak:

{ E(3), C(4) }

Tak jak poprzednio, badamy węzeł o najniższym koszcie z naszej listy, który jest teraz E. Ema tylko jednego nierozwiązanego sąsiada, który jest również węzłem docelowym. Koszt dotarcia do węzła docelowego jest ustawiony na, 10a jego poprzedni węzeł na E. Nasza lista kandydatów wygląda teraz następująco:

{ C(4), F(10) }

Następnie badamy C. Możemy zaktualizować koszt i poprzedni węzeł dla F. Ponieważ nasza lista ma teraz Fwęzeł o najniższych kosztach, gotowe. Nasza ścieżka może być zbudowana przez prześledzenie poprzednich najkrótszych węzłów.

Algorytm *

Zastanawiasz się więc, dlaczego wyjaśniłem ci Dijkstrę zamiast algorytmu A * ? Cóż, jedyną różnicą jest sposób ważenia (lub sortowania) kandydatów. Z Dijkstra to:

Cost_of_Edge + Cost_of_previous_Node

Z A * to:

Cost_of_Edge + Cost_of_previous_Node + Estimated_Cost_to_reach_Target_from(Node)

Gdzie Estimated_Cost_to_reach_Target_fromjest powszechnie nazywany funkcją heurystyczną . Jest to funkcja, która spróbuje oszacować koszt dotarcia do węzła docelowego. Dobra funkcja heurystyczna umożliwi osiągnięcie mniejszej liczby węzłów w celu znalezienia celu. Podczas gdy algorytm Dijkstry rozszerzyłby się na wszystkie strony, A * będzie (dzięki heurystyce) szukać w kierunku celu.

Strona Amita o heurystyce ma dobry przegląd popularnych heurystyk.

Znalezienie ścieżki * jest najlepszym rodzajem wyszukiwania, które wykorzystuje dodatkową heurystykę.

Pierwszą rzeczą, którą musisz zrobić, to podzielić obszar wyszukiwania. Dla tego wyjaśnienia mapa jest kwadratową siatką kafelków, ponieważ większość gier 2D wykorzystuje siatkę kafelków i dlatego jest łatwa do wizualizacji. Pamiętaj jednak, że obszar wyszukiwania można podzielić w dowolny sposób: być może siatkę heksadecymalną, a nawet dowolne kształty, takie jak Ryzyko. Różne pozycje mapy są nazywane „węzłami”, a ten algorytm będzie działał za każdym razem, gdy masz do przejścia kilka węzłów i zdefiniowane połączenia między węzłami.

W każdym razie, zaczynając od danego kafelka początkowego:

• 8 płytek wokół płytki początkowej jest „punktowanych” na podstawie a) kosztu przejścia z aktualnej płytki do następnej płytki (zazwyczaj 1 dla ruchów poziomych lub pionowych, sqrt (2) dla ruchu po przekątnej).

• Każdej płytce przypisuje się dodatkowy wynik „heurystyczny” - przybliżoną względną wartość przejścia do każdej płytki. Stosuje się różne heurystyki, najprostszą jest odległość w linii prostej między środkami danej płytki i płytki końcowej.

• Bieżąca płytka jest następnie „zamykana”, a agent przesuwa się do sąsiadującej otwartej płytki, ma najniższy wynik ruchu i najniższy wynik heurystyczny.

• Ten proces powtarza się, dopóki nie zostanie osiągnięty węzeł celu lub nie ma już otwartych węzłów (co oznacza, że ​​agent jest zablokowany).

Aby zapoznać się ze schematami ilustrującymi te kroki, zapoznaj się z tym poradnikiem dla dobrego początkującego .

Istnieje kilka ulepszeń, które można wprowadzić, głównie w poprawie heurystyki:

• Biorąc pod uwagę różnice terenu, nierówności, stromość itp.

• Czasami przydaje się również „przesuwanie” po siatce, aby zablokować obszary mapy, które nie są wydajnymi ścieżkami: na przykład kształt litery U skierowany w stronę agenta. Bez testu wymiatania agent najpierw wszedłby w U, odwrócił się, a następnie opuścił i okrążył krawędź U. „Prawdziwy” inteligentny agent zauważyłby pułapkę w kształcie litery U i po prostu jej uniknął. Zamiatanie może pomóc w symulacji tego.

Nie jest najlepszy, ale to implementacja A * w C ++ kilka lat temu.

Prawdopodobnie lepiej, że wskażę ci zasoby niż próbę wyjaśnienia całego algorytmu. Ponadto, czytając artykuł na wiki, zagraj w wersję demonstracyjną i sprawdź, czy możesz sobie wyobrazić, jak to działa. Zostaw komentarz, jeśli masz konkretne pytanie.

1. A * na Wikipedii
2. Demonstracja * Java

Pomocny może być artykuł ActiveTut na temat wyszukiwania ścieżek . Omówiono zarówno algorytm A *, jak i algorytm Dijkstry oraz różnice między nimi. Jest skierowany do programistów Flash, ale powinien zapewnić dobry wgląd w teorię, nawet jeśli nie używasz Flasha.

Jedną z rzeczy, które należy wizualizować podczas pracy z A * i algorytmem Dijkstry, jest to, że A * jest kierowane; stara się znaleźć najkrótszą ścieżkę do określonego punktu, „zgadując”, w którą stronę patrzeć. Algorytm Dijkstry znajduje najkrótszą ścieżkę do / każdego / punktu.

Tak więc jako pierwsze stwierdzenie, A * jest algorytmem eksploracji grafów. Zwykle w grach jako wykres używamy kafelków lub innej geometrii świata, ale możesz użyć A * do innych celów. Dwa algorytmy ur dla przejścia przez wykres to wyszukiwanie w pierwszej kolejności w głębokości i wyszukiwanie w pierwszej kolejności. W DFS zawsze w pełni eksplorujesz swoją obecną gałąź, zanim spojrzysz na rodzeństwo bieżącego węzła, aw BFS zawsze patrzysz najpierw na rodzeństwo, a potem na dzieci. A * próbuje znaleźć środek między nimi, w którym eksplorujesz gałąź (czyli bardziej jak DFS), gdy zbliżasz się do pożądanego celu, ale czasami zatrzymaj się i spróbuj rodzeństwa, jeśli może mieć lepsze wyniki w swojej gałęzi. Rzeczywista matematyka polega na tym, że przechowujesz listę możliwych węzłów do zbadania, gdzie każdy ma „dobroć” wynik wskazujący, jak blisko (w pewnym sensie abstrakcyjnym) jest cel, przy czym niższe wyniki są lepsze (0 oznacza, że ​​cel został znaleziony). Wybierz, którego użyć następnie, znajdując minimum wyniku plus liczbę węzłów z dala od katalogu głównego (co jest zwykle bieżącą konfiguracją lub bieżącą pozycją w wyszukiwaniu ścieżek). Za każdym razem, gdy eksplorujesz węzeł, dodajesz wszystkie jego dzieci do tej listy, a następnie wybierasz nowy najlepszy.

Na poziomie abstrakcyjnym A * działa w następujący sposób:

• Traktujesz świat jako dyskretną liczbę połączonych węzłów, np. siatka lub wykres.
• Aby znaleźć ścieżkę przez ten świat, musisz znaleźć listę sąsiednich „węzłów” w tej przestrzeni, prowadzącą od początku do celu.
• Naiwne podejście byłoby następujące: oblicz każdą możliwą permutację węzłów, które zaczynają się od węzła początkowego i kończą na węźle końcowym, i wybierz najtańszą. To oczywiście zabrałoby wieczność na wszystkich, z wyjątkiem najmniejszych przestrzeni.
• Dlatego alternatywne podejścia próbują wykorzystać pewną wiedzę o świecie, aby odgadnąć, które permutacje są warte rozważenia w pierwszej kolejności i wiedzieć, czy dane rozwiązanie można pokonać. To oszacowanie nazywa się heurystycznym.
• A * wymaga heurystyki, która jest dopuszczalna . Oznacza to, że nigdy nie przecenia.
  • Dobrą heurystyką dla problemów z wyszukiwaniem ścieżek jest odległość euklidesowa, ponieważ wiemy, że najkrótsza trasa między 2 punktami to linia prosta. To nigdy nie przecenia odległości w rzeczywistych symulacjach.
• * Rozpoczyna się od węzła początkowego i próbuje kolejnych permutacji tego węzła plus każdego sąsiada, i sąsiadów jego sąsiada itp., Używając heurystyki, aby zdecydować, która permutacja ma spróbować później.
• Na każdym kroku A * patrzy na najbardziej obiecującą ścieżkę do tej pory i wybiera następny sąsiedni węzeł, który wydaje się być „najlepszy”, w oparciu o przebytą do tej pory odległość i szacunki heurystyczne dotyczące tego, jak daleko pozostanie do pokonania węzeł.
• Ponieważ heurystyka nigdy nie przecenia, a odległość do tej pory znana jest z dokładności, zawsze wybierze najbardziej optymistyczny następny krok.
  • Jeśli ten kolejny krok osiągnie cel, wiesz, że znalazł najkrótszą trasę od ostatniej pozycji, ponieważ było to najbardziej optymistyczne przypuszczenie, które z pozostałych poprawnych pozostały.
  • Jeśli nie osiągnął celu, pozostawiono go do zbadania później. Algorytm wybiera teraz następną najbardziej obiecującą możliwość, więc powyższa logika nadal obowiązuje.