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

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?

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

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.