jakie jest standardowe rozwiązanie wyszukiwania ścieżki w kierunku ruchomego celu?

Pracuję nad grą podobną do 2D RTS, podstawowa A * doskonale nadaje się do przenoszenia jednostki z punktu A do punktu B.

Ale teraz mam do czynienia z problemem ciągłego odnajdywania ścieżki, jak A atakujący poruszający się obiekt B, wzywaj A * w każdej klatce, gdy tylko zmieni się pozycja obiektu B, co wydaje się nieskuteczne.

więc jaka jest standardowa metoda tego problemu?

Z tego co wiem, możesz rzucić okiem na algorytm D *, który oznacza „Dynamic A *”. Algorytm ten służy do obliczania szukania ścieżki dla dynamicznego środowiska, tutaj z ruchomym celem.

Oto artykuł wykorzystujący D * do znalezienia ruchomej ścieżki docelowej: Moving Target D * Lite

Jedną z opcji jest utworzenie nowej ścieżki tylko raz na kilka ramek. Jeśli zrobiłeś to raz lub dwa razy na sekundę, a nie ponad 60 razy na sekundę, użytkownik raczej nie zauważy, chyba że są to dwa bardzo szybko poruszające się obiekty

Możesz zastosować podejście „krzywej psa”, którego psy najwyraźniej używają podczas polowania na kogoś. Obliczają miejsce, w którym punkt wpływu będzie „w przyszłości”, i zestawy od razu do tej pozycji.

Prostym przybliżeniem może być coś takiego:

A = NPC

B = cel

T = czas dotarcia do pozycji B: s (pozycja początkowa B: s)

Oblicz, gdzie B będzie w czasie „T” (jeśli B będzie kontynuował z tą samą prędkością / kątem) i idź tam.

Nie jest to idealny sposób, ponieważ zmienia się odległość, ale jest znacznie prostszy niż stworzenie idealnego rozwiązania i znacznie lepszy niż próba dostania się do „B”.

Zgadzam się z Kylotanem, że nie ma standardowej metody.

Jedną z metod, które widziałem w pracy, było założenie, że cel nadal porusza się w tym samym kierunku i zmiana pozycji celu podczas przejścia przez algorytm znajdowania ścieżki. Oznacza to, że musisz przechowywać dwie metryki w swoich węzłach A * (koszt i czas, a nie tylko koszt).

Robienie tego lepiej jest bardzo trudne. O ile faktycznie nie masz wiedzy o niezachwianej ścieżce celu, zmierzasz do krainy dość trudnej sztucznej inteligencji, ponieważ będziesz miał drugie odgadywanie AI lub symulowanie zachowania celu, aby zgadnąć, gdzie będą i ścieżkę do tego celu. Ten rodzaj sztucznej inteligencji to gra AB w czasie rzeczywistym z teorii gier, obszar, który nie jest standardem w żadnym zestawie narzędzi AI do gier 3D.

Jednym ze sposobów dynamicznego wyszukiwania ścieżki jest to, by istota przewidziała, dokąd zmierza cel i tam się udaje.

Jednym ze sposobów na to jest użycie serii Taylora.

Nazwę ścieżki celu nazywam w czasie funkcją S (t), gdzie S jest pozycją, a t jest bieżącym czasem, a przybliżenie do ścieżki to A (f) if jest datą w przyszłości, która jest przybliżona .

Zatem najprostszym i najgłupszym przybliżeniem jest A (f) = 0.

Kolejnym najprostszym jest A (f) = S (t), gdzie t to aktualny czas, a f to przyszłość. To przewiduje, że cel po prostu się zatrzyma.

Trzecim najprostszym jest A (f) = S '(t) * f + S (t), gdzie S' jest pochodną S w odniesieniu do czasu. Oznacza to, że cel będzie kontynuował jazdę ze stałą prędkością bez przyspieszenia.

Czwarta najprostsza to A (f) = S '' (t) * f ^ 2/2 + S '(t) * f + S (t). To przewiduje, że cel przyspiesza ze stałą prędkością, jak spadająca piłka.

Wiem, że można to przeformułować pod względem zmiany w czasie, co jest prawdopodobnie wygodniejsze dla gry. Teraz S może być wszystkim. Może to być współrzędna X, może to być współrzędna Y, może to być odległość między obiektami, może to być kąt. Są też prawdopodobnie lepsze metody przewidywania przyszłej ścieżki obiektu, więc rozejrzę się trochę.

Jeśli teren jest dość otwarty, a cel nie znajduje się zbyt daleko od prześladowcy, możesz użyć trybu kierowania przechwytującego. Zasadniczo bierzesz pozycję i prędkość celu, aby obliczyć pozycję przed celem, która nie jest zbyt daleko i nie jest zbyt blisko, i kierujesz ścigającego w kierunku tego punktu (obliczanego każdego w regularnych odstępach czasu).