Omijanie się jednostek w RTS opartym na gridzie

[JasonVoorhees]

Hello. Robię małego RTS'a, zaimplementowałem już algorytm wyszukiwania ścieżki A* na gridzie (plansza ułożona z kwadratów) i ładnie moje jednostki omijają przeszkody. Chciałbym oprócz tego zrobić, żeby jednostki nie mogły wchodzić na pola, które są zajęte bądź aktualnie są w trakcie zajmowania przez inne jednostki. Próbowałem różnych podejść, ale są dość zawodne. Jednostki zatrzymują się w miejscu przed polem, na które chcą wejść, albo część zajmuje to samo pole, reszta drugie.

Przydałoby mi się naprowadzenie na jedyne słuszne rozwiązanie. Chciałbym, żeby jednostki zachowywały się jak w Warcraft 2.

[Mr. Spam]

[DanielMz25]

Takie rozwiązania na szybko, chociaż problem znam tylko teoretycznie bo jeszcze nigdy RTSa nie pisałem.
Możesz wysyłać wektor w kierunku w którym idzie jednostka (na kilka metrów w przód) i jeśli jednostka napotka inną jednostkę to skręcać trochę w prawo/lewo.
Druga opcja to zapisywać w nodach czas w jakim będzie on zajęty... Tj podczas przesuwania jednostek zapisywać w kilku najbliższych nodach np że za ok 10s będą one zajęte. Znalazłem tę metodę bodajże gdzieś tutaj: https://takinginitiative.files.wordpress.com/2011/05/thesis.pdf

Nie wiem czy znajdziesz jakieś jedyne słuszne rozwiązanie, bo chyba takich nie ma i każde ma swoje wady i zalety, nie pozostaje nic innego jak eksperymentowanie i dalsze grzebanie w sieci. Chociaż na warsztacie są osoby które już robiły własne RTSy więc może ktoś pomoże. :) Jak znajdziesz rozwiązanie to się podziel :)

[JasonVoorhees]

U mnie jednostki poruszają się "dyskretnie", a nie w sposób ciągły, więc wektor kierunku, czy skręcanie nie jest raczej potrzebne, czy wskazane. Algorytm wyznaczający ścieżkę zwraca kolejkę ze współrzędnymi kwadratów, na które musi najechać moja jednostka, aby dotrzeć do celu. No i jednostka według swojej logiki zajmuje te kwadraty (obraca się w kierunku w jaki ma iść, i idzie).

W sumie na początek wystarczyłoby, żeby jednostka, która jest dalej od danego pola, czekała aż inna jednostka je zajmie lub/i z niego zejdzie.

Dzięki za chęci ;) Muszę wziąć się do roboty.

[laggyluk]

Nie wiem czy o tym pomyślałeś ale jeżeli dwie jednostki nie mogą wejść na to samo pole to mogą się zdarzyć sytuacje w których przejście z jednej części mapy na drugą będzie zablokowane

[JasonVoorhees]

Racja ;) To wtedy postać się zatrzyma i napisze/powie, że tam nie może iść - można napisać algorytm, który:
1) Sprawdzi, czy dwa obszary mają do siebie dostęp.
2) Wyznaczy najbliższy kwadrat leżący przy kwadracie docelowym.

[beermaster]

Kiedyś sobie nad czymś takim myślałem , nic nie napisałem , ale ..... ja bym to zrobił tak że jak jednostka chce wjechać na zajęte pole, to czeka aż się to pole zwolni , a jeśli czekanie trwa za długo , to obliczam nową ścieżkę gdzie zajęte pole to przeszkoda stała.

[laggyluk]

a ja bym zrobił tak że przyjazna jednostka nie blokuje przejścia a jeżeli docelowe pole jest już zajęte to znajduje najbliższe wolne :P

[DanielMz25]

A rezerwacja pól którą opisałem dlaczego odpada?? rezerwujesz sobie pole że za 5 jednostek czasu będzie zajęte na 1 jednostkę czasu. I teraz jak inna jednostka szuka drogi. To już wie że jeśli dojdzie na to pole za 5 jedostek, to wtedy będzie to pole zajęte, więc traktuje je tak jak by była tam przeszkoda, pomimo że jej tam jeszcze nie ma (taka kontrola lotów).

A jak jednostka się zatrzymuje, to traktujemy ją jak zajęte pole, chyba że po prostu damy mu większy koszt i zwyczajnie kiedy ktoś próbuje na nie wejść, to przesuwamy jednostkę która przeszkadza.

No kurcze. To nie jest może idealne, ale zawsze coś :)

[beermaster]

a ja bym zrobił tak że przyjazna jednostka nie blokuje przejścia a jeżeli docelowe pole jest już zajęte to znajduje najbliższe wolne :P

Ale czy w tedy nie będą jednostki zbyt mocno "tańcować" ?

[laggyluk]

Ale czy w tedy nie będą jednostki zbyt mocno "tańcować" ?

nie pamiętam jak było w warcrafcie 2 ale w tych nowszych blizzardach jednostki się "rozstępują" i wygląda to nieźle

[Meic]

Ja bym spróbował sprawdzać czy następne pole w ścieżce jest zajęte. Jeśli tak, to jednostka przełącza się na niepełny bfs (znaczy generuje nie całą ścieżkę ale kilka kroków, mając za cel albo punkt docelowy albo jakiś punkt z używanej ścieżki, który jest "za" zablokowanym). Później, gdy zator zostanie pominięty, wracała by do starej ścieżki lub liczyła nową (to już zależy od implementacji wcześniejszej części). Oczywiście przy takim podejściu trzeba zapisywać zajęte pola (zajęte powinny być co najmniej 2 pola "między którymi" porusza się jednostka) w oddzielnym miejscu. Wspomniane dane o zablokowaniu powinno być używane w bfs i sprawdzaniu kolizji na bieżąco ale nie w A*.

Generalnie, zdaje się że rozwiązanie tego problemu to zwykle jakiś miks tego co określamy jako pathfinding (liczenie całej, konkretnej ścieżki) oraz movement (dynamiczne reagowanie na napotykane otoczenie)...

[Patrulek]

Też kiedyś się zastanawiałem jak to dokładnie działa, ale nigdy samemu nie próbowałem czegoś takiego napisać. Przede wszystkim pomyślałbym najpierw jak będą wyglądać mapy. Jeśli nie będzie map, które będą miały przejścia np. węższe niż 3 jednostki to bym prawdopodobnie próbował rozwiązywać kolizje dopiero w momencie kiedy nastąpią. Czyli:

1) znajdź ścieżkę do celu:
* jeśli cel nieosiągalny to jednostka zaczyna narzekać i się nie rusza
* jeśli osiągalny (jako obszar) ale samo pole jest zajęte to szukałbym pola najbliżej położonego, a jak będziemy się zbliżać do celu to raz jeszcze sprawdzić, czy pole faktycznie jest zajęte
* jeśli pole wolne to ścieżka bezpośrednio do tego pola
2) po znalezieniu ścieżki przesuwamy się po gridzie i badamy czy następne pole do którego chcemy iść nie będzie zajęte:
* jeśli nie to idziemy
* jeśli zajęte to jednostki między sobą muszą rozwiązać tę kolizję; przydałyby się jakieś reguły postępowania w różnych sytuacjach i według tych reguł rozwiązać kolizje np. poprzez dodanie jakiejś sekwencji ruchów do pola/pól obok, po jakimś czasie można odwrócić sekwencję i kontynuować drogę albo obliczyć nową ścieżkę od pola na którym skończyliśmy kolizję;
3) powtarzaj do momentu aż nie dojdziesz do wyznaczonego celu

Jeśli mapy będą zawierać jakieś wąskie przejścia, wąwozy, mosty, cokolwiek to:
1) można spróbować postępować jak wyżej przy czym należałoby dodać odpowiednie reguły przy przechodzeniu przez takie przejścia (np. tak, żeby zminimalizować czas przejścia wszystkich jednostek na drugą stronę); np. ustalić która strona ma pierwszeństwo i oszacować czas jak długo będą zajmowały przejście; po tym czasie jednostki z drugiej grupy skorzystałyby z szansy że przejście jest wolne, jeśli rzeczywiście jest
2) można by oznaczyć w edytorze takie wąskie przejścia i już przy liczeniu ścieżki brać pod uwagę, że będziemy przez nie przechodzić; wtedy jeśli akurat się zdarzy sytuacja że przejście będzie zajęte to podzielić ścieżkę na dwie części, idziemy do punktu przed przejściem, czekamy odpowiednią ilość czasu i kontynuujemy drogę drugą ścieżką / ewentualnie jeśli nie jest to jedyne przejście, a droga będzie wystarczająco długo zablokowana możemy szukać innej drogi; kolizje które by występowały w miejscach innych niż wąwozy rozwiązywać dopiero w momencie wystąpienia
3) podzielić mapę na obszary (logiczne) lub wyznaczyć pewien obszar dookoła jednostek; przy każdej zmianie liczby jednostek w obszarze sprawdzić czy wystąpi kolizja; jeśli tak to ją rozwiązać zanim wystąpi

[pturecki]

Witam. Może się przyda (i naprowadzi na jakąś ideę; komentarze też można przeglądnąć): https://twitter.com/OskSta/status/810157485638189056 ;)