Szukanie drogi do ucieczki

Jak wiesz, istnieje wiele rozwiązań, gdy wędrujesz, aby znaleźć najlepszą ścieżkę w dwuwymiarowym środowisku, które prowadzi z punktu A do punktu B.

Ale jak obliczyć ścieżkę, gdy obiekt znajduje się w punkcie A i chce uciec od punktu B tak szybko i daleko, jak to możliwe?

Trochę informacji w tle: Moja gra wykorzystuje środowisko 2D, które nie jest oparte na kafelkach, ale ma zmiennoprzecinkową dokładność. Ruch jest oparty na wektorze. Wyszukiwanie ścieżek odbywa się poprzez podzielenie świata gry na prostokąty, które można chodzić lub których nie można chodzić, i budując wykres z ich rogów. Mam już wyszukiwanie ścieżek między punktami przy użyciu algorytmu Dijkstras. Przypadek użycia algorytmu ucieczki polega na tym, że w niektórych sytuacjach aktorzy w mojej grze powinni postrzegać innego aktora jako zagrożenie i uciekać przed nim.

Trywialnym rozwiązaniem byłoby po prostu przesunięcie aktora w wektorze w kierunku przeciwnym do zagrożenia, dopóki nie zostanie osiągnięta „bezpieczna” odległość lub aktor dotrze do ściany, na której następnie kryje się strach.

Problem z tym podejściem polega na tym, że aktorzy będą blokowani przez małe przeszkody, które mogą łatwo ominąć. Dopóki poruszanie się wzdłuż ściany nie zbliżyłoby ich do zagrożenia, mogliby to zrobić, ale wyglądałoby mądrzej, kiedy unikali przeszkód:

Kolejny problem, jaki widzę, to ślepe zaułki w geometrii mapy. W niektórych sytuacjach istota musi wybierać między ścieżką, która prowadzi ją teraz szybciej, ale kończy się ślepym zaułkiem, w którym zostałaby uwięziona, lub inną ścieżką, która oznaczałaby, że początkowo nie byłaby tak daleko od niebezpieczeństwa (lub nawet trochę bliżej), ale z drugiej strony miałaby znacznie większą długoterminową nagrodę, ponieważ w końcu doprowadziłaby ich znacznie dalej. Tak więc krótkoterminową nagrodę za szybkie ucieczkę należy w jakiś sposób wycenić w stosunku do długoterminowej nagrody za ucieczkę daleko .

Istnieje również inny problem z oceną w sytuacjach, w których aktor powinien zaakceptować zbliżenie się do niewielkiego zagrożenia, aby uciec od znacznie większego zagrożenia. Ale całkowite ignorowanie wszystkich drobnych zagrożeń również byłoby głupotą (dlatego aktor z tej grafiki robi wszystko, aby uniknąć niewielkiego zagrożenia w prawym górnym rogu):

Czy są jakieś standardowe rozwiązania tego problemu?

To może nie być najlepsze rozwiązanie, ale udało mi się stworzyć uciekającą sztuczną inteligencję dla tej gry .

Krok 1. Przekształć algorytm Dijkstry w A * . Powinno to być proste poprzez dodanie heurystyki, która mierzy minimalną odległość do celu. Ta heurystyka jest dodawana do przebytej odległości podczas oceniania węzła. W każdym razie powinieneś wprowadzić tę zmianę, ponieważ znacznie zwiększy ona swoją wyszukiwarkę ścieżek.

Krok 2. Utwórz odmianę heurystyki, która zamiast szacować odległość do celu mierzy odległość od niebezpieczeństwa (ów) i neguje tę wartość. To nigdy nie osiągnie celu (ponieważ nie ma go), więc musisz zakończyć wyszukiwanie w pewnym momencie, być może po określonej liczbie iteracji, po osiągnięciu określonej odległości lub po obsłużeniu wszystkich możliwych tras. To rozwiązanie skutecznie tworzy wyszukiwarkę ścieżek, która znajduje optymalną drogę ucieczki z danym ograniczeniem.

Jeśli naprawdę chcesz, aby twoi aktorzy byli sprytni w ucieczce, zwykłe szukanie ścieżki Dijkstra / A * nie będzie tego robić. Powodem tego jest to, że aby znaleźć optymalną drogę ucieczki od wroga, aktor musi również rozważyć, w jaki sposób wróg będzie się poruszał w pogoni.

Poniższy schemat MS Paint powinien zilustrować szczególną sytuację, w której użycie tylko statycznego szukania ścieżki w celu zmaksymalizowania odległości od wroga doprowadzi do nieoptymalnego wyniku:

Tutaj zielona kropka ucieka od czerwonej kropki i ma dwie możliwości wyboru ścieżki. Zejście ścieżką po prawej stronie pozwoliłoby jej znacznie przekroczyć obecną pozycję czerwonej kropki , ale ostatecznie uwięziłoby zieloną kropkę w ślepym zaułku. Zamiast tego optymalna strategia polega na tym, że zielona kropka wciąż krąży po okręgu, próbując pozostać po jej przeciwnej stronie niż czerwona kropka.

Aby poprawnie znaleźć takie strategie ucieczki, potrzebujesz algorytmu wyszukiwania przeciwnika, takiego jak wyszukiwanie minimax lub jego udoskonalenia, takie jak przycinanie alfa-beta . Taki algorytm, zastosowany w powyższym scenariuszu z wystarczającą głębokością wyszukiwania, poprawnie wydedukuje, że przyjęcie ślepej uliczki w prawo nieuchronnie doprowadzi do przechwytywania, podczas gdy pozostanie na kole nie (dopóki zielona kropka może przekroczyć czerwony).

Oczywiście, jeśli istnieje wielu aktorów dowolnego rodzaju, wszyscy będą musieli zaplanować własne strategie - osobno lub, jeśli aktorzy współpracują, razem. Takie wieloosobowe strategie pościgu / ucieczki mogą stać się zaskakująco złożone; na przykład jedną z możliwych strategii dla uciekającego aktora jest próba odwrócenia uwagi wroga, prowadząc go do bardziej kuszącego celu. Oczywiście wpłynie to na optymalną strategię drugiego celu i tak dalej ...

W praktyce prawdopodobnie nie będziesz w stanie wykonywać bardzo głębokich wyszukiwań w czasie rzeczywistym z wieloma agentami, więc będziesz musiał polegać na heurystyce. Wybór tej heurystyki określi następnie „psychologię” twoich aktorów - jak inteligentni działają, ile uwagi poświęcają różnym strategiom, jak bardzo współpracują lub są niezależni itp.

Masz wyszukiwanie ścieżek, więc możesz zredukować problem do wybrania dobrego miejsca docelowego.

Jeśli na mapie znajdują się całkowicie bezpieczne miejsca docelowe (np. Wyjścia, przez które zagrożenie nie może podążać za twoim aktorem), wybierz jeden lub więcej pobliskich i dowiedz się, który z nich ma najniższy koszt ścieżki.

Jeśli twój uciekający aktor ma dobrze uzbrojonych przyjaciół lub jeśli mapa zawiera zagrożenia, na które aktor jest odporny, ale zagrożenie nie jest, wybierz wolne miejsce w pobliżu takiego przyjaciela lub zagrożenie i znajdź drogę do tego.

Jeśli twój uciekający aktor jest szybszy niż jakikolwiek inny aktor, którym zagrożenie może być również zainteresowane, wybierz punkt w kierunku tego innego aktora, ale poza nim, i znajdź ścieżkę do tego punktu: „Nie muszę wyprzedzać niedźwiedzia , Muszę cię tylko wyprzedzić. ”

Bez możliwości ucieczki, zabicia lub rozproszenia zagrożenia twój aktor jest skazany, prawda? Więc wybierz dowolny punkt do ucieczki, a jeśli tam dotrzesz, a zagrożenie wciąż Cię ściga, do diabła: odwróć się i walcz.

Ponieważ określenie odpowiedniej pozycji docelowej może być trudne w wielu sytuacjach, warto rozważyć następujące podejście oparte na mapach siatek zajętości 2D. Jest powszechnie nazywany „iteracją wartości”, aw połączeniu z gradientem opadania / wznoszenia daje prosty i dość wydajny (w zależności od implementacji) algorytm planowania ścieżki. Ze względu na swoją prostotę jest dobrze znany w robotyce mobilnej, w szczególności do „prostych robotów” poruszających się w pomieszczeniach zamkniętych. Jak sugerowano powyżej, takie podejście zapewnia sposób znalezienia ścieżki od pozycji początkowej bez wyraźnego określenia pozycji docelowej w następujący sposób. Pamiętaj, że opcjonalnie można określić pozycję docelową, jeśli jest dostępna. Ponadto podejście / algorytm stanowi pierwsze wyszukiwanie,

W przypadku binarnym dwuwymiarowa mapa obłożenia jest mapą dla zajętych komórek siatki i zerową gdzie indziej. Zauważ, że ta wartość zajętości może być również ciągła w zakresie [0,1], wrócę do tego poniżej. Wartość danego ogniwa siatkowego g _i wynosi V (g _i ) .

Wersja podstawowa

1. Zakładając, że komórka siatki g ₀ zawiera pozycję początkową. Ustaw V (g ₀ ) = 0 i umieść g ₀ w kolejce FIFO.
2. Weź kolejną komórkę siatki g _i z kolejki.
3. Dla wszystkich sąsiadów g _j z g _i :
   • Jeśli g _j nie jest zajęty i nie był wcześniej odwiedzany:
     • V (g _j ) = V (g _i ) +1
     • Oznacz g _j jako odwiedzone.
     • Dodaj g _j do kolejki FIFO.
4. Jeśli dany próg odległości nie został jeszcze osiągnięty, przejdź do (2.), w przeciwnym razie przejdź do (5.).
5. Ścieżkę uzyskuje się po najbardziej stromym wzniesieniu, zaczynając od g ₀ .

Uwagi na temat kroku 4.

• Jak podano powyżej, krok (4) wymaga śledzenia maksymalnego pokonywanego dystansu, który został pominięty w powyższym opisie ze względu na jasność / zwięzłość.
• Jeśli podano pozycję docelową, iteracja zostaje zatrzymana, gdy tylko pozycja docelowa zostanie osiągnięta, tzn. Przetworzona / odwiedzona w ramach kroku (3.).
• Oczywiście można również po prostu przetworzyć całą mapę siatki, tzn. Kontynuować, aż wszystkie (wolne) komórki siatki zostaną przetworzone / odwiedzone. Czynnikiem ograniczającym jest oczywiście rozmiar mapy siatki w połączeniu z jej rozdzielczością.

Rozszerzenia i dalsze komentarze

Równanie aktualizacji V (g _j ) = V (g _i ) +1 pozostawia dużo miejsca na zastosowanie wszelkiego rodzaju dodatkowej heurystyki poprzez obniżenie V (g _j )lub składnik addytywny w celu zmniejszenia wartości niektórych opcji ścieżki. Większość, jeśli nie wszystkie, takie modyfikacje można ładnie i ogólnie wprowadzić za pomocą mapy siatki o ciągłych wartościach od [0,1], co skutecznie stanowi etap wstępnego przetwarzania początkowej, binarnej mapy siatki. Na przykład dodanie przejścia od 1 do 0 wzdłuż granic przeszkód powoduje, że „aktor” najlepiej pozostaje wolny od przeszkód. Taką mapę siatki można na przykład wygenerować z wersji binarnej poprzez rozmycie, ważoną dylatację lub podobne. Dodając zagrożenia i wrogów jako przeszkody o dużym promieniu rozmycia, karze ścieżki, które do nich zbliżają się. Można również zastosować proces dyfuzji na ogólnej mapie siatki w następujący sposób:

V (g _j ) = (1 / (N + 1)) × [V (g _j ) + suma (V (g _i ))]

gdzie „ suma ” odnosi się do sumy wszystkich sąsiednich komórek siatki. Na przykład zamiast tworzenia mapy binarnej wartości początkowe (całkowite) mogą być proporcjonalne do wielkości zagrożeń, a przeszkody stanowią „małe” zagrożenia. Po zastosowaniu procesu dyfuzji wartości siatki należy / należy przeskalować do [0,1], a komórki zajmowane przez przeszkody, zagrożenia i wrogów należy ustawić / zmusić do 1. W przeciwnym razie skalowanie w równaniu aktualizacji może nie działa zgodnie z życzeniem.

Istnieje wiele odmian tego ogólnego schematu / podejścia. Przeszkody itp. Mogą mieć małe wartości, podczas gdy wolne komórki siatki mają duże wartości, które mogą wymagać opadania gradientu w ostatnim kroku, w zależności od celu. W każdym razie podejście to jest zaskakująco wszechstronne, dość łatwe do wdrożenia i potencjalnie dość szybkie (w zależności od rozmiaru / rozdzielczości mapy sieci). Wreszcie, podobnie jak w przypadku wielu algorytmów planowania ścieżki, które nie przyjmują określonej pozycji docelowej, istnieje oczywiste ryzyko utknięcia w ślepych zaułkach. Do pewnego stopnia może być możliwe zastosowanie dedykowanych kroków przetwarzania końcowego przed ostatnim krokiem w celu zmniejszenia tego ryzyka.

Oto kolejny krótki opis z ilustracją w Java-Script (?), Chociaż ilustracja nie działała w mojej przeglądarce :(

http://www.cs.ubc.ca/~poole/demos/mdp/vi.html

Dużo więcej szczegółów na temat planowania można znaleźć w następującej książce. Iteracja wartości została szczegółowo omówiona w rozdziale 2 sekcja 2.3.1. Optymalne plany o stałej długości.

http://planning.cs.uiuc.edu/

Mam nadzieję, że pomaga, pozdrawiam, Derik.

A może skoncentrować się na drapieżnikach? Po prostu raycast 360 stopni na pozycji Predatora, z odpowiednią gęstością. I możemy mieć próbki schronienia. I wybierz najlepsze schronienie.

Jednym ze sposobów, jakie mają w Star Trek Online dla stad zwierząt, jest wybranie otwartego kierunku i skierowanie się na to, szybkie, odradzanie zwierząt po pewnym dystansie. Ale jest to głównie uwielbiana animacja odradzania dla stad, które powinny wystraszyć cię przed atakiem, i nie nadaje się do prawdziwych mobów bojowych.