Jak mogę przyspieszyć A *, gdy cel jest nieprzejezdny?

Tworzę prostą grę 2D opartą na kafelkach, która wykorzystuje algorytm wyszukiwania ścieżki A * („gwiazda”). Wszystko działa poprawnie, ale mam problem z wydajnością wyszukiwania. Mówiąc najprościej, kiedy klikam nieprzejezdną płytkę, algorytm najwyraźniej przechodzi przez całą mapę, aby znaleźć drogę do nieprzejezdnej płytki - nawet jeśli stoję obok niej.

Jak mogę to obejść? Wydaje mi się, że mógłbym ograniczyć wyszukiwanie ścieżki do obszaru ekranu, ale może brakuje mi tutaj czegoś oczywistego?

Kilka pomysłów na unikanie wyszukiwań, które prowadzą do nieudanych ścieżek:

ID wyspy

Jednym z najtańszych sposobów na szybsze zakończenie wyszukiwania A * jest brak wyszukiwania. Jeśli obszary są naprawdę nieprzejezdne dla wszystkich agentów, zalej każdy obszar unikalnym identyfikatorem wyspy przy obciążeniu (lub w rurociągu). Podczas wyszukiwania ścieżki sprawdź, czy identyfikator wyspy początku ścieżki jest zgodny z identyfikatorem wyspy miejsca docelowego. Jeśli się nie zgadzają, wyszukiwanie nie ma sensu - dwa punkty znajdują się na odrębnych, niepołączonych wyspach. Pomaga to tylko wtedy, gdy dla wszystkich agentów istnieją naprawdę nieprzejezdne węzły.

Ogranicz górną granicę

Ograniczam górną granicę maksymalnej liczby węzłów, które można przeszukiwać. Pomaga to w nieprzerwanym wyszukiwaniu, ale oznacza to, że niektóre bardzo długie wyszukiwania, które są bardzo długie, mogą zostać utracone. Liczba ta musi zostać dostrojona i tak naprawdę nie rozwiązuje problemu, ale zmniejsza koszty związane z długimi poszukiwaniami.

Jeśli odkrywasz, że trwa to zbyt długo , przydatne są następujące techniki:

Zrób to asynchronicznie i ogranicz iteracje

Pozwól, aby wyszukiwanie przebiegało w osobnym wątku lub nieco w każdej ramce, aby gra nie utknęła w miejscu, czekając na wyszukiwanie. Wyświetlaj animację postaci drapiącą się po głowie lub tupiącą stopą, lub cokolwiek odpowiedniego, czekając na zakończenie poszukiwań. Aby to zrobić skutecznie, zachowałbym Stan wyszukiwania jako osobny obiekt i pozwoliłbym na istnienie wielu stanów. Gdy żądana jest ścieżka, weź wolny obiekt stanu i dodaj go do kolejki aktywnych obiektów stanu. W aktualizacji odnajdywania ścieżek ściągnij aktywny element z przodu kolejki i uruchamiaj A *, aż A. zakończy się lub B. zostanie przekroczony pewien limit iteracji. Po zakończeniu ponownie umieść obiekt stanu na liście obiektów stanu swobodnego. Jeśli się nie zakończyło, umieść je na końcu „aktywnych wyszukiwań” i przejdź do następnego.

Wybierz odpowiednie struktury danych

Upewnij się, że używasz odpowiednich struktur danych. Oto jak działa mój StateObject. Wszystkie moje węzły są wstępnie przypisane do skończonej liczby - powiedzmy 1024 lub 2048 - ze względu na wydajność. Używam puli węzłów, która przyspiesza przydzielanie węzłów, a także pozwala mi przechowywać indeksy zamiast wskaźników w moich strukturach danych, które są u16s (lub u8, jeśli mam 255 węzłów max, co robię w niektórych grach). Do wyszukiwania ścieżek używam kolejki priorytetowej dla otwartej listy, przechowując wskaźniki do obiektów Node. Jest zaimplementowany jako plik binarny, a wartości zmiennoprzecinkowe sortuję jako liczby całkowite, ponieważ są one zawsze dodatnie, a moja platforma ma wolne wartości zmiennoprzecinkowe w porównaniu. Używam hashtable dla mojej zamkniętej mapy, aby śledzić odwiedzone węzły. Przechowuje identyfikatory NodeID, a nie Nodes, aby zaoszczędzić na rozmiarach pamięci podręcznej.

Buforuj co możesz

Kiedy po raz pierwszy odwiedzasz węzeł i obliczasz odległość do miejsca docelowego, buforuj go w węźle przechowywanym w obiekcie stanu. Jeśli ponownie wrócisz do węzła, użyj wyniku z pamięci podręcznej zamiast ponownie go obliczać. W moim przypadku pomaga to nie robić pierwiastka kwadratowego na ponownie odwiedzonych węzłach. Może się okazać, że istnieją inne wartości, które można wstępnie obliczyć i buforować.

Inne obszary, które możesz zbadać: użyj dwukierunkowego wyszukiwania ścieżek, aby wyszukiwać z dowolnego końca. Nie zrobiłem tego, ale jak zauważyli inni, może to pomóc, ale nie jest to obojętne. Inną rzeczą na mojej liście do wypróbowania jest hierarchiczne wyszukiwanie ścieżek lub wyszukiwanie ścieżek klastrowych. Jest ciekawy opis w dokumentacji HavokAI Tutaj opisując ich koncepcji klastrów, która jest inna niż HPA * wdrożenia opisanych tutaj .

Powodzenia i daj nam znać, co znajdziesz.

AStar to kompletny algorytm planowania, co oznacza, że ​​jeśli istnieje ścieżka do węzła, AStar z pewnością ją znajdzie. W związku z tym musi sprawdzić każdą ścieżkę z węzła początkowego, zanim będzie mógł stwierdzić, że węzeł docelowy jest nieosiągalny. Jest to bardzo niepożądane, gdy masz zbyt wiele węzłów.

Sposoby złagodzenia tego:

• Jeśli wiesz z góry, że węzeł jest nieosiągalny (np. Nie ma sąsiadów lub jest oznaczony UnPassable), wróć No Pathbez wywoływania AStar.

• Ogranicz liczbę węzłów AStar będzie się rozszerzał przed zakończeniem. Sprawdź otwarty zestaw. Jeśli kiedykolwiek stanie się za duży, zakończ i wróć No Path. Ogranicza to jednak kompletność AStar; więc może planować tylko ścieżki o maksymalnej długości.

• Ogranicz czas potrzebny AStarowi na znalezienie ścieżki. Jeśli skończy się czas, wyjdź i wróć No Path. Ogranicza to kompletność jak poprzednia strategia, ale skaluje się wraz z prędkością komputera. Pamiętaj, że w przypadku wielu gier jest to niepożądane, ponieważ gracze z szybszymi lub wolniejszymi komputerami będą inaczej odczuwać grę.

4. Uruchom podwójne wyszukiwanie A * z węzła docelowego również w odwrotnej kolejności w tym samym czasie w tej samej pętli i przerwij oba wyszukiwania, gdy tylko zostanie znalezione nierozwiązywalne

Jeśli cel ma tylko 6 pól dostępnych wokół niego, a źródło ma 1002 płytki dostępne, wyszukiwanie zatrzyma się na 6 (podwójnych) iteracjach.

Gdy tylko jedno wyszukiwanie znajdzie odwiedzone węzły drugiego, możesz również ograniczyć zakres wyszukiwania do odwiedzanych węzłów drugiego i zakończyć szybciej.

Zakładając, że problemem jest to, że miejsce docelowe jest nieosiągalne. I że siatka nawigacji nie jest dynamiczna. Najłatwiejszym sposobem na to jest posiadanie znacznie rzadszego wykresu nawigacyjnego (na tyle rzadkiego, że pełne przejście jest stosunkowo szybkie) i użycie szczegółowego wykresu tylko wtedy, gdy możliwe jest ścieżki.

Użyj wielu algorytmów o różnych właściwościach

A * ma pewne dobre cechy. W szczególności zawsze znajduje najkrótszą ścieżkę, jeśli taka istnieje. Niestety, znalazłeś również złe cechy. W takim przypadku musi wyczerpująco wyszukać wszystkie możliwe ścieżki przed przyznaniem, że nie istnieje żadne rozwiązanie.

„Wada” odkryta w A * polega na tym, że nie jest świadoma topologii. Możesz mieć świat 2D, ale nie wie o tym. Z tego co wie, w odległym zakątku twojego świata znajdują się schody, które prowadzą go pod świat do miejsca przeznaczenia.

Rozważ utworzenie drugiego algorytmu uwzględniającego topologię. W pierwszym przejściu możesz wypełnić świat „węzłami” co 10 lub 100 spacji, a następnie zachować wykres połączeń między tymi węzłami. Ten algorytm szuka ścieżki, znajdując dostępne węzły w pobliżu początku i końca, a następnie próbując znaleźć ścieżkę między nimi na wykresie, jeśli taki istnieje.

Jednym łatwym sposobem na to byłoby przypisanie każdego kafelka do węzła. Trywialne jest pokazanie, że do każdego kafelka wystarczy przypisać tylko jeden węzeł (nigdy nie można uzyskać dostępu do dwóch węzłów, które nie są połączone na wykresie). Następnie krawędzie wykresu są zdefiniowane tak, aby były gdziekolwiek dwie płytki z różnymi węzłami sąsiadują.

Ten wykres ma wadę: nie znajduje optymalnej ścieżki. To tylko znajdzie się ścieżka. Jednak teraz pokazało ci, że A * może znaleźć optymalną ścieżkę.

Zapewnia również heurystykę, aby poprawić niedoszacowania potrzebne do uruchomienia funkcji A *, ponieważ teraz wiesz więcej o swoim krajobrazie. Jest mniej prawdopodobne, że będziesz musiał w pełni zbadać ślepy zaułek, zanim dowiesz się, że musisz cofnąć się, aby iść naprzód.

Kilka dodatkowych pomysłów oprócz powyższych odpowiedzi:

6. Wyniki wyszukiwania A * w pamięci podręcznej. Zapisz dane ścieżki z komórki A do komórki B i użyj ponownie, jeśli to możliwe. Jest to bardziej odpowiednie w przypadku map statycznych i będziesz musiał wykonać więcej pracy z mapami dynamicznymi.

7. Cache the neighbours of each cell. A* implementation need to expand each node and add its neighbours to the open set to search. If this neighbours is calculated each time rather than cached then it could dramatically slow down the search. And if you havnt already done so, use a priority queue for A*.

If your map is static you can just have each separate section have there own code and check this first before running A*. This can be done upon map creation or even coded in the map.

Impassable tiles should have a flag and when moving to a tile like that you could opt not to run A* or pick a tile next to it that is reachable.

If you have dynamic maps that change frequently you are pretty much out of luck. You have to way your decision making your algorithm stop before completion or do checks on sections get closed off frequently.

How can I make A* more quickly conclude that a node is impassable?

Profile your Node.IsPassable() function, figure out the slowest parts, speed them up.

When deciding whether a node is passable, put the most likely situations at the top, so that most of the time the function returns right away without bothering to check the more obscure possibilities.

But this is for making it faster to check a single node. You can profile to see how much time is spent on querying nodes, but sounds like your problem is that too many nodes are being checked.

when I click an impassable tile, the algorithm apparently goes through the entire map to find a route to the impassable tile

If the destination tile itself is impassable, the algorithm shouldn't check any tiles at all. Before even starting to do pathfinding, it should query the destination tile to check if it's possible, and if not, return a no path result.

If you mean that the destination itself is passable, but is encircled by impassable tiles, such that there is no path, then it is normal for A* to check the whole map. How else would it know there's no path?

If the latter is the case, you can speed it up by doing a bidirectional search - that way the search starting from the destination can quickly find that there is no path and stop the search. See this example, surround the destination with walls and compare bidirectional vs. single direction.

Do the path-finding backwards.

If only your map doesn't have big continuous areas of unreachable tiles then this will work. Rather than searching the entire reachable map, the path-finding will only search the enclosed unreachable area.

If the areas that the player are connected (no teleports etc.) and the unreachable areas are generally not very well connected, you can simply do the A* starting from the node you want to reach. That way you can still find any possible route to the destination and A* will stop searching quickly for unreachable areas.

when I click an impassable tile, the algorithm apparently goes through the entire map to find a route to the impassable tile — even if I'm standing next to it.

Other answers are great, but I have to point at the obvious - You should not run the pathfinding to an impassable tile at all.

This should be an early exit from the algo:

if not IsPassable(A) or not IsPasable(B) then
    return('NoWayExists');

To check for the longest distance in a graph between two nodes:

(assuming all edges have the same weight)

1. Run BFS from any vertex v.
2. Use the results to select a vertex furthest away from v, we'll call it d.
3. Run BFS from u.
4. Find the vertex furthest away from u,we'll call it w.
5. The distance between u and w is the longest distance in the graph.

Proof:

                D1                            D2
(v)---------------------------r_1-----------------------------(u)
                               |
                            R  | (note it might be that r1=r2)
                D3             |              D4
(x)---------------------------r_2-----------------------------(y)

• Lets say the distance between y and x is greater!
• Then according to this D2 + R < D3
• Then D2 < R + D3
• Then the distance between v and x is greater than that of v and u?
• Then u wouldn't have been picked in the first phase.

Credit to prof. Shlomi Rubinstein

If you are using weighted edges, you can accomplish the same thing in polynomial time by running Dijkstra instead of BFS to find the furthest vertex.

Please note I'm assuming it's a connected graph. I am also assuming it's undirected.

A* is not really useful for a simple 2d tile based game because if I understand correctly, assuming the creatures move in 4 directions, BFS will achieve the same results. Even if creatures can move in 8 directions, lazy BFS that prefers nodes closer to the target will still achieve the same results. A* is a modification Dijkstra which is far more computationally expensive then using BFS.

BFS = O(|V|) supposedly O(|V| + |E|) but not really in the case of a top down map. A* = O(|V|log|V|)

Jeśli dysponujemy mapą zawierającą tylko 32 x 32 kafelki, BFS będzie kosztować maksymalnie 1024, a prawdziwy A * może kosztować aż 10 000. Jest to różnica między 0,5 sekundy a 5 sekund, prawdopodobnie więcej, jeśli weźmiesz pod uwagę pamięć podręczną. Upewnij się więc, że Twój A * zachowuje się jak leniwy BFS, który woli płytki zbliżone do pożądanego celu.

Znak * jest przydatny w przypadku map nawigacyjnych, w których koszt krawędzi jest ważny w procesie podejmowania decyzji. W prostych grach opartych na kafelkach koszt krawędzi nie jest prawdopodobnie ważnym czynnikiem. Jeśli tak się stanie, (różne kafelki kosztują inaczej), możesz uruchomić zmodyfikowaną wersję BFS, która opóźnia i penalizuje ścieżki przechodzące przez kafelki, które spowalniają postać.

Więc tak BFS> A * w wielu przypadkach, jeśli chodzi o płytki.