Czy A * jest skuteczny, nawet gdy poruszają się przeszkody?


30

Właśnie zaczynam się uczyć o znajdowaniu ścieżki i przyglądam się algorytmowi A *, a moim głównym zmartwieniem jest to, że wszystkie przykłady, które widziałem, pokazują przeszkody statyczne, które oblicza.

Jeśli mam poruszające się przeszkody, powiedzmy na przykład inne postacie, poruszające się także, że postać musi znaleźć drogę, zakładam, że będę musiał uruchomić algorytm dla każdej klatki, ale martwię się, że będzie to dość drogie dla sprzętu przetwarzającego każdą klatkę dla każdego poruszającego się aktora.

Czy A * jest nadal wystarczająco wydajny, aby używać go, gdy przeszkody również się poruszają, czy też istnieje inna metoda wyszukiwania ścieżki, która bardziej elokwentnie radzi sobie z poruszającymi się przeszkodami?

Odpowiedzi:


27

Istnieje wiele algorytmów, które są znacznie szybsze niż A *, gdy trzeba ponownie obliczyć ścieżkę z poruszającymi się przeszkodami. Zobacz tutaj pod „Proste przeliczenia”.

Jednak prawdopodobnie nie znajdziesz gotowego rozwiązania dla któregokolwiek z nich, więc w 99% przypadków są one nadmierne dla gry. Lepiej byłoby spędzić czas, korzystając z istniejącego, w pełni zoptymalizowanego rozwiązania A * i korzystając ze zwykłych istniejących sztuczek, aby przyspieszyć wyszukiwanie ścieżek w grach:

  • Ponowne obliczanie najlepszej ścieżki w rzadkich odstępach czasu
  • Dzielenie się najlepszymi ścieżkami między wieloma jednostkami ( przykład )
  • Tworzenie wykresu hierarchicznego, aby wystarczyło ponownie obliczyć część ścieżki

itp. Możesz znaleźć więcej informacji o tych sztuczkach i więcej w całej tej witrynie lub na stronach A * Amita


10

Tak. Prawie zawsze jest to możliwe *. To obliczanie kosztu węzła staje się dynamiczne, a zatem bardziej skomplikowane w obliczaniu i śledzeniu.

Jeśli już wiesz, gdzie będą się poruszać przeszkody w przyszłości, twój A * może uwzględnić czasowość przeszkód w funkcji kosztów.

Np .: ten węzeł zostanie osiągnięty w 4 kleszczach, zajmowanych od kleszcza # 3 do kleszcza # 6, więc koszt podróży w tym węźle wynosi 6 - 4 = +2 kleszczy. To wciąż może być najlepsza ścieżka.

Należy również uwzględnić kierunek jazdy przeszkody.

Jeśli nie wiesz z góry, nie możesz zakładać żadnych przeszkód i ponownie obliczyć ścieżkę, gdy przeszkody zostaną osiągnięte, ale musisz coś zrobić z impasami i blokadami żywymi. (To samo dotyczy sytuacji, gdy możesz przewidzieć, gdzie będą przeszkody, ale samo w sobie jest rodzajem impasu / unikania blokady na żywo i może być wystarczające dla twojego celu).

Zakleszczenie występuje, gdy oboje czekają, aż drugi się poruszy i żaden się nie poruszy.

Blokada jest wtedy, gdy oba ( lub więcej <- należy to wziąć pod uwagę) poruszają się, aby uniknąć drugiego w tym samym kierunku i kończą się tam iz powrotem bez postępu.

Rozwiązywanie blokad żywych może być bardzo skomplikowane, a to zależy wyłącznie od zasad i mechaniki kolizji gry (np. Czy powinny walczyć i niszczyć przeszkodę?).

Często powraca do planowania rezerwacji węzłów / ścieżek przez ruchome obiekty (nie zapomnij anulowania, gdy zmieniają ścieżkę lub umierają), aby inne ruchome obiekty mogły planować z wyprzedzeniem.

Po uzyskaniu tych informacji możesz również zaplanować przechwytywanie.


19
O mój boże, „livelock” - opisałeś tę okropną lewą i prawą unik, którą ciągle muszę robić na korytarzach.
Ethan The Brave

2
Prostym rozwiązaniem na żywo / impasu jest losowe wybieranie dostępnych opcji (np. 50% szansy na brak ruchu i 50% szansy na ruch w lewo). Tak długo, jak każdy aktor wybierze losowo, istnieje niezerowa szansa, że ​​zamek zostanie rozwiązany.
Draco18s,

@ Draco18s I wykładniczo zwiększaj rozmiar wymachiwania tam iz powrotem, aż ktoś ustąpi (mogłem właśnie opisać, w jaki sposób rozwiązuje się kolizje Ethernetowe!)
Cort Ammon - Przywróć Monikę

Podejrzewam, że zamiast tego mogliby grać w Rock Paper Scissors lub przyjazną grę Dylemat Więźnia Petriego . ; P
Draco18s
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.