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.
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.
Odpowiedzi:
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.
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 A
i 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) }
A
ma koszt 0
, wszystkie inne węzły są ustawione na nieskończoność (w typowej implementacji byłoby to coś podobnego int.MAX_VALUE
lub 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). A
moż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 D
jest droższa niż obecny koszt D
, dlatego można ją odrzucić. E
zostaną 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 C
można odrzucić, ponieważ ścieżka nie jest krótsza niż istniejący koszt. Znaleźliśmy krótszą ścieżkę E
, więc koszt E
i 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
. E
ma 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, 10
a 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 F
węzeł o najniższych kosztach, gotowe. Nasza ścieżka może być zbudowana przez prześledzenie poprzednich najkrótszych węzłów.
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_from
jest 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.
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: