Jak działa wyszukiwanie ścieżek w grach RTS?

[crossposted from stackoverflow]

W grach takich jak Warcraft 3 lub Age of Empires sposoby, w jakie przeciwnik AI może poruszać się po mapie, wydają się niemal nieograniczone. Mapy są ogromne, a pozycja innych graczy stale się zmienia.

Jak działa wyszukiwanie AI w takich grach? Standardowe metody wyszukiwania grafów (takie jak DFS, BFS lub A *) wydają się niemożliwe w takiej konfiguracji.

W większości przypadków użycie A * w siatce nawigacyjnej (zwykle nazywanej „navmesh”) jest rozwiązaniem do wyszukiwania ścieżek stosowanym przez komercyjne RTS. Istnieje szczegółowe wyjaśnienie, w jaki sposób działają narzędzia nawigacyjne, dlaczego są one lepszym rozwiązaniem niż systemy punktów nawigacyjnych, oraz linki do zasobów implementacyjnych tutaj .

Jeśli planujesz opracować specjalne tryby gry (przechwytywanie punktów / węzłów) lub jednostki, które patrolują, kryją się itp., Prawdopodobnie będziesz chciał zaimplementować warstwę punktów na szczycie swojego navmesh, aby kontrolować zachowanie AI ( nie odnajdywanie ścieżek ).

Sprawdź algorytm Flowfield zastosowany w Supreme Commander 2. Wykonuje on znacznie lepszą pracę niż większość systemów wyszukiwania ścieżek RTS (przejdź kilka razy do 0:50).

Wiele starszych gier korzysta z A *. Oryginalny Starcraft używał A *; co spowodowało pewne problemy w radzeniu sobie z kolizją. Starcraft 2 bardzo dobrze radzi sobie z kolizjami, wykorzystując zachowanie polegające na zamiataniu / flokowaniu w celu utrzymania kontroli płynów w dużych grupach. W tym artykule Gamedev omówiono, jak można to osiągnąć.

Zgadzam się z innymi odpowiedziami, ale już staram się myśleć o WoW / Warcraft3 jako o rzeczywistych światach 2D. Nie różnią się tak bardzo od płytek, to tylko płytki.

Możesz również pomyśleć o tym, jak GPS znajduje najlepszą ścieżkę? istnieje mnóstwo algortimnów do wyszukiwania ścieżek przez połączone mapy.

Myślę, że niektóre z pierwszych skryptów „botów Quake” również mogą ci pomóc, ponieważ zostały opracowane do pracy w „nieznanych obszarach”, ponieważ mogliśmy projektować własne poziomy od zera.

Podsumowując, moim osobistym sposobem radzenia sobie z taką mapą byłoby myślenie o niej jako o wskaźniku A *. Najpierw jednak obliczyłem każdy „punkt kafelkowy” i zindeksowałem je „najbliższym sąsiadem” itd. Następnie, gdy obiekt musiał przejść z punktu A do punktu B, po prostu wyszukaj w punkcie B, zobacz, co jest z nim związane i powtarzaj, aż do momentu osiągnąć cel.

W zależności od rodzaju gry i krajobrazu / scenariusza przydatne mogą być również różne taktyki skanowania wstępnego. Niektóre gry mają bardzo mało przeszkód i mogą to być ruchy „linii prostej” + niektóre „jak się ominąć” dla obiektów.

Mam nadzieję, że to ma trochę sensu i być może dało ci kilka myśli do pracy.

Większość gier korzysta z algorytmu wyszukiwania lub A *, aby znaleźć ścieżki na mapie. AI jest poprawiane w niektórych aspektach, oczywiście ze względu na wydajność.

Zauważysz to w Starcraft 2, gdzie Zerglingi w ogóle nie idą dobrze ścieżką, byłoby koszmarem procesora dla Zerglingów. Po prostu starają się dotrzeć z punktu A do punktu B i nawet nie próbują znaleźć najlepszej ścieżki. Zbliżą się jak najbliżej szyjki butelki do dławików lub pochylni.

Mapa jest siatką. Siatka jest wykresem. * Działa na wykresie, jest to algorytm wyszukiwania wykresów. * Powinien przeszukać kilka węzłów wykresu.

Jak już wspomniano, mogą korzystać z siatki nawigacyjnej. Ale A * (lub coś podobnego) i tak znajdzie się na tej siatce, ponieważ wielokąty tej siatki są tylko węzłami wykresu; A * wyszuka następnie ścieżkę od jednego wielokąta do innego wielokąta.

Nie jestem pewien co do Warcrafta lub gier komercyjnych, ale istnieje również technika o nazwie Collaborative Diffusion i jest bardzo prosta; zwykle odbywa się to na siatce. Istnieje również technika zwana polami potencjału , która jest bardzo podobna do poprzedniej, jeśli nie taka sama.

Możesz także spróbować:

• czy niektóre z tych gier mają dostępny kod źródłowy
• czy niektóre klony tych gier mają dostępne źródło
• czy SDK lub redaktorzy niczego nie sugerują
• zapytaj pracodawców firm tworzących te gry, niektóre z nich chętnie się z tym podzielą

Nie mam doświadczenia, ale uważam, że dobre rozwiązanie opiera się na heurystyce, a nie na kompletnym sprawdzeniu znanej mapy. Heurystyka, o której myślę, opiera się na lokalnych podstawach i doświadczeniu. Lokalne elementy sterujące mogą opierać się na lokalnej kontroli terenu i przeszkodach, poruszając się nadal w wymaganym kierunku. Myślę, że większość map nie wymaga skomplikowanych ruchów przypominających labirynt, ale jest dość połączona. Inną heurystyką jest wykorzystanie poprzednich znanych ścieżek (eksplorowanych przez inne jednostki lub jawnie przez użytkownika) do przenoszenia jednostek na znane lub prawie znane pozycje. Ale mówię o poruszaniu się po dużych mapach, a nie w zamkniętych przestrzeniach, jak powiedział ZorbaTHut. W zatłoczonych przypadkach algorytm może być bardziej złożony, wymagając pewnego rodzaju „przewidywania”, koordynacji między jednostkami tego samego zespołu lub po prostu strategii oczekiwania przypominających semafory. Również,

Myślę, że algorytmy heurystyczne są dobre, ponieważ zwykle zapewniają dobre rozwiązanie na dużych przestrzeniach z rozsądnym czasem obliczeń (co ma znaczenie, gdy przenosisz wiele jednostek).

Przepraszam, jeśli to ogólna odpowiedź: pracowałem z tłumami, ale przestrzeń była dość osobliwa i nie mogę dokładnie wyjaśnić, jak działał algorytm (zresztą był oparty na agentach, a nie globalnie zdefiniowany). Mam nadzieję, że możesz uzyskać przydatne pomysły z mojej odpowiedzi.