[Unity 3D] RTS Pathfinding - jaka technika?


#1

Czołem ekipo :slight_smile: Z pasji od jakiegoś czasu tworzę swoją pierwszą grę na silniku Unity. Zdaję sobie sprawę z tego, że “porywanie się” na RTS-a na dzień dobry jest dość ryzykowne, jednak wcześniej realizowałem ten projekt jako modyfikację do C&C 3 Wojny o Tyberum. Więcej o genezie gry pojawi się wkrótce, na razie powiem tylko - wiem co robię.
Dotarłem do momentu, w którym potrzebuję zaprogramować (w C#) Pathfinding. Jak zwykle zrobiłem rozeznanie w temacie przed kombinowaniem, jak temat ugryźć. Na samym początku posta moje skrócone przemyślenia i wnioski na podstawie tego, co przeczytałem, potem chciałbym z wami to przedyskutować jako osobami, które zdecydowanie lepiej znają się na rzeczy :slight_smile:
Wbudowana technika NavMesh raczej się nie nadaje, ze względu na to, że wiele obiektów (choćby jednostek) będzie się przemieszczać w czasie rzeczywistym. Z kolei Pathfinding oparty na gridmapie (jak w tym tutorialu: https://www.youtube.com/watch?v=-L-WgKMFuhE) … cóż, mam wrażenie, że może być poważny problem z optymalizacją - wyznaczanie od nowa trasy w każdej klatce dla każdego obiektu + wygładzanie ścieżki w gratisie?
Myślałem też nad systemem, z którym się nigdzie nie spotkałem (może jestem pierwszy?) - w skrócie:

  1. Jednostka jedzie prosto do celu, dopóki jakiś OBBoX/Collider nie znajdzie się w zdefiniowanym promieniu od jednostki.
  2. W momencie, gdy ten collider zostanie wykryty, jednostka skręca łagodnie w prawo albo w lewo, w zależności od tego, po której stronie collidery zajmują mniejszą powierzchnię terenu (w tym samym promieniu co wcześniej albo np. podwojonym).
  3. Skręt tym ostrzejszy, im bliżej collidera znajduje się jednostka.
    Nie jestem jednak do końca przekonany, czy ma to szansę działać przy bardziej skomplikowanych przeszkodach. Aczkolwiek zaleta byłaby taka, że jednostka nie uwzględniałaby colliderów, które znajdują się poza jej polem widzenia. Musiałbym to przetestować, ale nie jestem jeszcze biegły w programowaniu (choć kiepskim też bym się nie nazwał :stuck_out_tongue: ), a chcę dożyć ukończenia swojej gry (i nie chciałbym poprzestać tylko na niej :wink:

Może mi coś doradzicie? Gra to strategia czasu rzeczywistego w pełnym 3D.


#2

A na jakiej podstawie masz takie wrażenie?
Zamiast kombinować i wymyślać jakieś cudaczne techniki to najpierw zrób sobie symulacje typowej mapy i sprawdź wydajność najpopularniejszych algorytmów.
Pathfinding to akurat coś, co zawsze możesz wyciąć i zastąpić innym kawałkiem kodu, jeśli w tym momencie przeprowadzenie takiej symulacji będzie kłopotliwe/niemożliwe to zwyczajnie odłóż temat na później.


#3

Sam algorytm A* nie jest tak bardzo wymagający, ciężej z wygładzaniem ścieżki bo to już zjada czas, jeszcze kwestia kolizji i omijanie do ogarnięcia. Nie musisz sprawdzać/szukać drogi co klatkę. Drogi szukasz raz, zapamiętujesz ją, postać po niej idzie, jeśli wystąpi kolizja szukasz drogi ponownie. Możesz ograniczyć ilość kroków wyszukiwania do 100, aby skrypt przy ogromnej mapie w nieskończoność nie sprawdzał pól (aby nie obciążył zbytnio procesora). Tym bardziej jeśli obszar gdzie jednostka ma iść byłby niedostępny.
Oprócz samego gridu do poruszania, następny grid do zajętości pola przez inne jednostki, grid przesunięcia od przeszkód jeśli jednostka jest duża, grid “kosztu” pola.
NavMesh nie testowałem ale sądzę, że nie musi być aż tak tragicznie, przetestuj.
Do dużej liczby jednostek stosuje się coś takiego jak Swarm Pathfinding.


#4

NavMesh działa bardzo dobrze. Testowałem na kilkuset jednostkach. Bardzo ładnie sam przelicza ponownie drogę w przypadku kolizji. Jedyny problem jaki występuje, to gdy damy ten sam cel dla wielu jednostek, to będą się kręcić w kółko wokół tego punku. Ale to można rozwiązać na przynajmniej kilka sposobów, np. wykrywać że się kręcimy blisko celu, lub każdej jednostce dać inny punkt docelowy na tyle oddalony od innych aby jednostki nie wchodziły w kolizję.


#5

Hej
Co do twojej metody ze skręcaniem.
Robiłem coś bardzo podobnego 2 lata temu w mojej grze i system mimo, że wydaje się być genialny nie sprawdza się w praktyce. Postacie obijają się co chwila o ściany, a przy ciut bardziej zaawansowanej przeszkodzie potrafią się zaciąć i robić śliczne kółka.
Pozdrawiam


#6

Dziękuję wszystkim za odpowiedzi :slight_smile:

@frozenshade , Może i bezpodstawnie, ale po to pytam ekspertów :wink: Wymyślanie nowych technik nie jest złe, gorzej gdybym poświęcał czas na jego implementację i by się okazało że nic z tego nie wyszło.

@Kazze , Faktycznie, zapamiętywanie wyznaczonej trasy i jej korygowanie dopiero gdy zajdzie taka potrzeba + górna granica kroków wyszukiwania chyba rozwiązuje cały problem.

@Pampas, A przypadkiem nie jest tak że obiekty ruchome nie modyfikują obszarów dostępnych? Przynajmniej ja to ta zrozumiałem, czytając ten tekst (2 cytaty, pod nimi link do całości):

The built-in tools are free and straight-forward to set up. However, there are multiple issues with the Unity Navmesh. The first major problem is that the mesh is baked in advance, so it can’t be changed at runtime. In result, any shape-changing dynamic objects and obstacles won’t work correctly.

To sum up, Unity NavMesh works great for simple games without special pathfinding requirement.

@huncwot A widzisz, dzięki za info, też się obawiałem że taki skrypt może się nie sprawdzać w praktyce, teraz nie muszę tracić czasu na to by to sprawdzić :slight_smile: