Jak wykonuje się lokalne unikanie RTS?

Obecnie symuluję siły uderzenia fizyki w celu lokalnego unikania jednostek, ale ta metoda czasami wypycha jednostki z formacji i ma bardzo niepożądane skutki, gdy jednostki się zlepią.

Jak robi się lokalne unikanie w grach RTS, takich jak Starcraft 2? Czy symulowana jest fizyka, czy kontroler wszechkierunkowy decyduje, gdzie wszystko powinno być? Wiem, że to pytanie może być nieco ogólne, więc pytam konkretnie, jak osiągnąć lokalne zachowania unikania w Starcraft 2; choć wszystko, co działa, będzie bardzo mile widziane.

Nie szukam żadnego kodu - tylko użyteczne zasoby lub wyjaśnienia, w jaki sposób Starcraft 2 (lub podobne gry) radzi sobie z unikaniem lokalnym.

Obecnie mam zaimplementowane wykrywanie kolizji (z wektorem penetracji), siły kolizji i ruch według prędkości. Każda jednostka jest porównywana z drugą pod kątem kolizji - jeśli zderzą się, obiekty zostaną natychmiast przesunięte przez wektor penetracji, a następnie zastosowana zostanie siła zderzenia. Następnie kolejna pętla przesuwa obiekty według ich prędkości i stosuje prędkości do prędkości. Przesunięcie łagodzi problem nadmiernych sił kolizji przykładanych do skupionych jednostek, ale jednostki wciąż czasami strzelają.

Rozwiązanie, którego szukam, musi spełniać następujące wymagania (jak w Starcraft 2):

• Obiekty nie mogą się nakładać; lub przynajmniej nakładanie się musi zostać ostatecznie rozwiązane.
• Przedmioty nie odpychają się bardziej niż to konieczne, więc 2 jednostki mogą stać i poruszać się obok siebie w szyku.
• Nie powinno być żadnych dziwnych zachowań, gdy obiekty zbijają się w kierunku tego samego miejsca docelowego.
• Może obsługiwać jednostki o różnych rozmiarach, a nawet o różnych wypukłych kształtach.

Do tej pory myślałem o wykrywaniu kolizji, wykrywaniu przyszłych kolizji, aby nakładanie się nigdy nie miało miejsca. Następnie zastosuj ograniczenie, upewniając się, że prędkości 2 jednostek nie powodują, że się nakładają. Nadal majstruję przy algorytmie ograniczania ruchu poza nakładanie się.

Wygląda na to, że szukasz algorytmu optymalnego wzajemnego unikania kolizji . Poprzedzające papier jest również warto przeczytać. Chociaż praca może być nieco zaangażowana, teoria algorytmu jest dość prosta:

Załóżmy, że masz już symulację (grę) z agentami (jednostkami), które mają wokół siebie jakąś ograniczającą objętość. Ten wolumin ograniczający jest prawdopodobnie tym, czego już używasz do wykrywania i reagowania na kolizję. Dla każdego agenta określ preferowaną prędkość, v_pktóra może, ale nie musi, zależeć od celu agenta.

Teraz, aby wykonać symulację:

1. Dla każdego agenta, zakładając, że jest on nieruchomy, obliczyć wszystkie prędkości, które spowodowałyby zderzenie go w dowolnym momencie w przyszłości z dowolnym innym agentem ruchomym. Można to przedstawić w „przestrzeni prędkości” jako zbiór przecinających się półpłaszczyzn (znanych również jako przeszkoda prędkości ).
2. Określ punkt w tej najbliższej przestrzeni v_p, jest to nowa prędkość jednostki.

Jeśli wszyscy agenci korzystają z tego samego algorytmu, wybiorą prędkości, które wzajemnie się uzupełniają i będą unikać innych agentów. W niektórych sytuacjach możesz powodować oscylacje, takie jak ta niezręczna rzecz, która zdarza się, gdy wchodzisz bezpośrednio do kogoś na korytarzu i oboje próbujesz zejść z drogi w tym samym kierunku, ale dokumenty opisują, jak tego uniknąć.

Aby obliczyć dwa etapy powyższego algorytmu, możesz użyć Sumów Minkowskiego, aby określić, czym jest przeszkoda prędkości, a następnie użyć liniowego modelu programowania (takiego jak algorytm Simplex ), aby określić najbliższy punkt, v_pktóry omija przeszkodę prędkości. Również kod umożliwiający unikanie kolizji jest dostępny dla twojej analizy i został przeniesiony do C # do użycia w silnikach gier, takich jak Unity. Ta technika została zastosowana przynajmniej w Warhammer 40,000: Space Marine i może w innych grach .

Nie wiem, jak działają twoje jednostki, ale zakładam, że są one jak machina stanu:

Możliwe stany

• Uruchamianie do (x, y, z)
• Atakowanie (wrogi_id)
• Zbieranie zasobów (ressource_id)

Jeśli zwrócisz uwagę na podejście StarCrafta do tego problemu, przekonasz się, że:

1. Jeśli jest miejsce na ruch w danym kierunku, charachter porusza się w tym kierunku.
2. Jeśli nie ma miejsca, jednostka na drodze przesunie się, aby zrobić miejsce
3. Jeśli jednostka, która musi się poruszyć, aby zrobić miejsce, ma już polecenie, zachowa polecenie, ale nieznacznie je zmodyfikuje, aby ostatecznie zająć miejsce.

Oto scenariusz 1:

Czy mam tam miejsce? Tak ? Więc idź

Scenariusz 2:

Czy mam tam miejsce? Nie? Hej, możesz zrobić dla mnie trochę miejsca, blokujesz mnie. Mam już rozkaz, aby ruszyć w przód, ale cię zakwateruję.

Co będziesz musiał wdrożyć:

• Jednostki muszą być świadome swojego otoczenia
• Jednostki muszą mieć możliwość komunikowania się ze sobą
• Musisz wdrożyć sposób wykonywania polecenia podczas akomodacji innej jednostki

Jednym ze sposobów na to jest automatyczne tworzenie formacji jednostek i próba pozostania w pozycji względem środka formacji . Następnie zamiast przesuwać każdą jednostkę indywidualnie, przesuń środek formacji.

Oto podstawowy sposób na zrobienie tego za pomocą formowania skrzynek i prostych sprężyn, aby utrzymać jednostki w odpowiednich pozycjach:

// Defines a phalanx (box) formation
class Formation
    // Center of the box in the world
    Position center;
    // Width in # of units
    int width;
    // Height in # of units
    int height;
    // Space between units
    float scale;
    // How much force units will apply to stay near
    // their assigned spot.
    float springforce;

    // Return a position of a unit at the given row and column
    // Todo: add a rotation to this formation so it can rotate when moving.
    Position GetUnitPhalanxPosition(int row, int column)
        return new Position(center.X + column * scale - width * scale /2, 
                            center.Y + row * scale    - height* scale / 2);

// Represents a simple point object with a velocity and position;
// it belongs to a formation.
class Unit
    Position pos;
    Velocity vel;
    Formation formation;
    // What's our assigned spot in the formation?
    int row;
    int column;

    void Update(float dt)
        // Get the desired target position in the formation
        Position target = formation.GetUnitPhalanxPosition(row, column);
        // Apply a spring force toward the position (todo: you might want to damp this)
        vel += (target - position) * dt * formation.springforce;
        // Move along the velocity vector.
        pos += vel * dt;

Wiem, że niektórzy ludzie marszczą braki w odrzucaniu linków, ale znalazłem wieloaspektowe podejście oparte na potencjale w przypadku botów do gier strategicznych w czasie rzeczywistym marudzą z powodu odrzucania (ISBN 978-91-7295-160-0) jest bardzo pouczające i oczywiście przekazuje o wiele więcej niż mógłbym rozwinąć. Artykuł bada sztuczne pola potencjalne (koncepcja wywodząca się z robotyki), aby ułatwić lokalne unikanie kolizji w kontekście rozwoju gry.