Skutecznie odnajduje wielu uciekających wrogów wokół przeszkód

Pracuję nad ulepszeniem wyszukiwania ścieżek dla wrogów mojej gry. W tej chwili po prostu stale poruszają się w kierunku dokładnej pozycji gracza, obliczając kąt między sobą a graczami i poruszając się w tym kierunku. Mam również algorytm uciekający, który zapobiega gromadzeniu się wrogów na sobie, dzięki czemu będą się grupować, a nie przenikać.

Jednak teraz, gdy dodałem mapę opartą na kafelkach, potrzebuję wrogów, aby mogli także na przykład omijać przeszkody i ściany. Początkowo próbowałem dodać wartość separacji do płytek „niepodlegających chodzeniu”, aby algorytm flokowania traktował ściany i przeszkody jako obiekty, z których można się oddalić. Muszę jeszcze ustalić, czy jest to wykonalne, ponieważ mój pierwszy test wykazał, że wrogowie uderzają w niewidzialną „ścianę”, w której nie ma płytek, na których nie można chodzić, ale z jakiegoś powodu uderzają ją i zaczynają szaleć.

Zastanawiałem się, czy obliczenie ścieżki do gracza za pomocą A * może być zbyt trudne, a następnie użyć algorytmu flokowania, aby zapobiec zbijaniu się. Początkowo moja gra miała być strzelanką opartą na falach, ale zamiast tego zdecydowałem, że będę oparty na poziomie w stylu Hotline Miami, więc prawdopodobnie będę miał mniej wrogów, z sporadyczną hordą, i po prostu stworzę je silniejsze.

Czy to realne rozwiązanie? Używam Java z Slick2D jako moim silnikiem gry. A może istnieje lepsze rozwiązanie / algorytm, który rozwiązuje oba te problemy?

java algorithm ai path-finding Darin Beaudreau
źródło

Jak opisałem w edycji, „czy to zbyt ciężkie” jest pytaniem, które należy zadać profilerowi, ponieważ będzie to zależeć od implementacji, docelowego sprzętu, budżetu wydajności i kontekstu gry - wszystkie rzeczy, które ty i twój profiler znacie ściśle, ale obcy internet nie. Jeśli chcesz skutecznie znaleźć stado, możemy zaproponować strategie, które pomogą Ci w tym, ale tylko twoje własne profilowanie może odpowiedzieć na to, co jest wystarczająco wydajne dla twoich potrzeb. Jeśli profilujesz i identyfikujesz konkretny problem z wydajnością, możemy również pomóc Ci znaleźć sposób rozwiązania tego problemu.

DMGregory

Sposób ich wdrożenia wpływa na wydajność. Na przykład uruchamianie A * tylko na liderach i poleganie na uciekaniu się do obserwujących.

Pikalek

Jeśli twoja gra opiera się głównie na walce z tymi wrogami, zastosowany algorytm będzie miał ogromny wpływ na to, jak się czujesz. Powinieneś więc wypróbować różne podejścia, np. Czy masz wrażenie, że wrogowie doskonale znają poziom i pozycję gracza i śledzą go tak, jak kieruje wszechwiedząca sztuczna inteligencja? - inne podejścia mogą polegać na tym, że wrogowie mogą biec w ogólnym kierunku, w którym gracz hałasuje i tylko w bezpośredniej linii wzroku biegną w jego kierunku, lub krzyczą i informują innych wrogów, gdzie gracz jest ...

Falco

@Falco Ponieważ gra nie jest już oparta na falach i będzie oparta na poziomie, a ponieważ wrogowie to zombie ... Zastanawiałem się nad tym, abyś albo cię zobaczył, albo hałasował, aby cię znaleźli. Więc jeśli używasz głośnej broni? Emituje dźwięk w zasięgu i wszystkich wrogów znajdujących się w zasięgu w kierunku lokalizacji emitowanego dźwięku, a następnie losowo przesuwa się po tym obszarze.

Darin Beaudreau

Odpowiedzi:

To brzmi jak przypadek użycia Flow Fields.

W tej technice wykonujesz pojedyncze zapytanie identyfikujące ścieżkę na zewnątrz od obiektów gracza, zaznaczając każdą napotkaną komórkę komórką, z której do niej dotarłeś.

Jeśli wszystkie kafelki / krawędzie mają taki sam koszt przejścia, możesz użyć prostego wyszukiwania w pierwszej kolejności. W przeciwnym razie działa algorytm Dijkstry (jak A * bez celu / heurystyka).

Tworzy to pole przepływu: tabela odnośników, która łączy każdą komórkę z następnym krokiem w kierunku najbliższego obiektu gracza z tej pozycji.

Teraz twoi wrogowie mogą spojrzeć na swoją bieżącą pozycję w polu przepływu, aby znaleźć następny krok na swojej najkrótszej, omijającej przeszkody ścieżce do najbliższego obiektu gracza, bez potrzeby wykonywania własnych zapytań.

To skaluje się coraz lepiej, im więcej wrogów masz w stadzie. Dla pojedynczego wroga jest droższy niż A *, ponieważ przeszukuje całą mapę (choć możesz wyjść wcześniej, gdy dotrzesz do wszystkich agentów szukających ścieżki). Ale gdy dodajesz kolejnych wrogów, mogą oni dzielić coraz większy koszt poszukiwania ścieżki, obliczając dzielone segmenty ścieżki raz, a nie w kółko. Uzyskujesz także przewagę dzięki temu, że BFS / Dijkdtra są prostsze niż A * i zazwyczaj tańsze do oceny w odniesieniu do kontrolowanej komórki.

Dokładnie tam, gdzie dochodzi do progu rentowności, od indywidualnego A *, który jest tańszy, do A * z zapamiętywaniem, który jest tańszy (gdzie ponownie wykorzystujesz niektóre wyniki dla zapytania szukającego ścieżki w przeszłości, aby przyspieszyć następny), do pól przepływu taniej, będzie zależeć od twojej implementacji, liczby agentów i wielkości twojej mapy. Ale jeśli kiedykolwiek zaplanujesz duży rój wrogów zbliżających się z wielu kierunków w ograniczonym obszarze, jedno pole przepływu będzie prawie na pewno tańsze niż iterowane A *.

Jako skrajny przykład możesz zobaczyć tutaj wideo z 20 000 agentów jednocześnie szukających ścieżki na stosunkowo małej siatce .

DMGregory
źródło

Ta technika brzmi naprawdę schludnie. Sprawdzę to.

Darin Beaudreau,

Możliwe jest zastosowanie algorytmu hybrydowego, który konstruuje pole częściowego przepływu bez przeszukiwania większej ilości mapy niż powtarzane wywołania do A * i nigdy nie przeszukuje tej samej pozycji dwa razy. Podstawową ideą jest wybranie dowolnego wroga i rozpoczęcie od gracza poszukiwania A * w kierunku tego wroga, oznaczając komórki podczas ich napotkania, tak jak podczas normalnego generowania pola przepływu. Gdy wyszukiwanie znajdzie wroga, wybierz innego wroga (którego jeszcze nie znalazłeś) jako cel, ponownie posortuj otwarty zestaw zgodnie z nową heurystyką i kontynuuj wyszukiwanie. Zatrzymaj się, gdy znajdziesz wszystkich wrogów.

Ilmari Karonen,

Co z unikaniem kolizji? Jest to (nieco) wspomniane w OP (unikanie przycinania, gdy docierają do odtwarzacza). Wydaje mi się, że musiałbyś ponownie uruchamiać pełne djikstrasy za każdym razem, gdy cokolwiek się poruszyło (lub dodać jakąś dodatkową logikę)

Mars

@Mars OP mówi o uciekaniu, więc zakładam, że wszystkie osoby mogą poruszać się z tą samą prędkością; jedynymi miejscami, w których mogą wystąpić kolizje, są wąskie gardła, które wymagają, aby część stada zatrzymała się i czekała. Jednak tak naprawdę nie musi zmieniać wyszukiwania ścieżek - prosta kolejka prawdopodobnie działałaby wystarczająco dobrze w większości przypadków, a niektóre promowanie ścieżek (niektóre pseudolosowe wybieranie alternatywnych ścieżek o podobnych kosztach) zadziała, aby stworzyć bardziej naturalnie wyglądające stado przepływy, które również omijają całe stado próbujące przejść przez jedną szczelinę pojedynczych kafelków :)

Luaan

@Luaan W grze opartej na kafelkach będziesz zaskoczony, jak często zdarzają się kolizje. Osobiście uważam, że opcja „kolejkowania” jest mniej niż optymalna. Ponadto, jeśli jednostki nie mogą się przedostać, musisz ponownie przeliczyć, kiedy jednostki zaczną dostawać się do swojej ostatecznej pozycji i kilka innych przypadków krawędzi. Flokowanie jest trudne;)

Mars,

A * nie jest ciężkie pod względem wydajności. Do tej sytuacji podszedłbym, zmieniając algorytmy. Od czasu do czasu wykonuj A * i sprawdzaj, czy następny krok jest wolny, czy potrzebujesz uciec.

Na przykład śledź odległość graczy od lokalizacji docelowej A *, jeśli jest ona powyżej progu, ponownie oblicz *, a następnie po prostu wykonaj ruchy aktualizacji. Większość gier wykorzystuje kombinację punktów na drodze, np. Uproszczoną siatkę do wyszukiwania ścieżek i logikę, która obsługuje ruch między punktami za pomocą algorytmów sterowania unikaniem za pomocą raycast. Moim zdaniem agenci próbują biec do odległego punktu, manewrując wokół przeszkód w ich pobliżu.

Najlepiej jest tu pracować z automatami skończonymi i przeczytać książkę Matta Bucklanda „Programowanie gry AI według przykładu”. Książka oferuje sprawdzone techniki rozwiązywania problemów i szczegółowe informacje na temat wymaganej matematyki. Kod źródłowy z książki jest dostępny w Internecie; książka jest w C ++, ale niektóre tłumaczenia (w tym Java) są dostępne.

D3d_dev
źródło

Przy rzadko aktualizowanym podejściu A * pomocne może być rozłożenie twoich aktualizacji, utrzymując budżet na liczbę przeciwników, którzy mogą przemieścić się na jednej klatce. W ten sposób możesz utrzymać maksymalny koszt poszukiwania ścieżki na klatkę na poziomie ograniczonym i solidniej obsługiwać wiele ścieżek AI, amortyzując ich całkowity koszt na kilku klatkach. Sztuczna inteligencja wykorzystująca nieaktualną ścieżkę dla ramki lub dwóch, gdy budżet dla ramki został przekroczony, lub wraca do martwego liczenia, jeśli jest blisko, zwykle nie będzie zakłócająca.

DMGregory

Prawdopodobnie jest to oczywiste, ale jeśli zamierzasz zaktualizować tylko niektóre ścieżki w danej ramce, możesz chcieć systemu priorytetowego opartego na odległości od gracza. Prawdopodobnie ważniejsze jest, aby wrogowie w pobliżu gracza aktualizowali swoje ścieżki, natomiast prawdopodobnie wrogowie z daleka mogą korzystać ze starej ścieżki.

Nie tylko jest to wykonalne, ale sądzę, że dokonano tego w komercyjnej grze z lat 90. - BattleZone (1998).

Ta gra miała jednostki 3D z wolnym ruchem nie opartym na płytkach i bazową konstrukcją opartą na płytkach.

Tak to wyglądało:

Po pierwsze, A * lub coś podobnego (prawdopodobnie odmiana A * ze ścisłymi limitami długości ścieżki, którą może znaleźć, więc nigdy nie zajmuje zbyt wiele zasobów, ale nie zawsze znajduje ścieżkę do celu) służyłby do znalezienia drogi dla poduszkowca, aby dostać się do miejsca docelowego bez utknięcia w przeszkodach wyłożonych płytkami.

Następnie czołg latałby wokół wyznaczonego miejsca, jakby był przyciągany do środka pobliskiej płytki na swojej drodze i odpychany przez przeszkody, inne pobliskie czołgi itp.

Robyn
źródło

Więc jaki jest dobry sposób radzenia sobie ze ścieżką, ale nie do końca? Jeśli pozwolę dziecinnemu pokonywaniu zakrętów, muszę być w stanie powstrzymać wrogów przed zderzeniem się z rogiem przeszkody. Czy powinienem zachować zachowanie uciekające zarówno wrogów, jak i przeszkód i dodać A *, aby poradzić sobie w takich sytuacjach?

Darin Beaudreau