Implementacja drutu owijającego (takiego jak Worms Ninja Rope) w silniku fizyki 2D


34

Ostatnio wypróbowałem fizykę lin i odkryłem, że „standardowe” rozwiązanie - wykonanie liny z szeregu przedmiotów połączonych ze sprężynami lub stawami - jest niezadowalające. Zwłaszcza gdy kołysanie liną ma znaczenie dla rozgrywki. Naprawdę nie dbam o to, by lina mogła się owijać lub zwisać (i tak można to sfałszować dla celów wizualnych).

W rozgrywce ważna jest zdolność liny do owijania się wokół środowiska, a następnie rozwijania. Nie musi nawet zachowywać się jak lina - wystarczyłby „drut” złożony z odcinków linii prostej. Oto ilustracja:

Lina ninja, owijająca się wokół przeszkód

Jest to bardzo podobne do „Ninja Rope” z gry Worms.

Ponieważ używam silnika fizyki 2D - moje środowisko składa się z wypukłych wielokątów 2D. (W szczególności używam SAT w Farseer.)

Moje pytanie brzmi zatem: w jaki sposób zastosowałbyś efekt „zawijania”?

Wydaje się dość oczywiste, że drut będzie składał się z szeregu odcinków linii, które „dzielą” i „łączą”. Ostatnim (aktywnym) odcinkiem tej linii, do którego przyłącza się ruchomy obiekt, będzie złącze o stałej długości.

Ale na czym polega matematyka / algorytm określania, kiedy i gdzie należy podzielić aktywny segment linii? A kiedy trzeba go połączyć z poprzednim segmentem?

(Wcześniej to pytanie dotyczyło również robienia tego w środowisku dynamicznym - postanowiłem podzielić to na inne pytania).

Odpowiedzi:


18

Aby ustalić, kiedy należy rozdzielić linę, należy spojrzeć na obszar, w którym lina pokrywa każdą ramę. To, co robisz, to sprawdzanie kolizji z pokrywanym obszarem i geometrią poziomu. Obszar, który pokrywa huśtawka, powinien być łukiem. Jeśli dojdzie do kolizji, musisz zrobić nowy odcinek do liny. Sprawdź narożniki, które kolidują z kołyszącym się łukiem. Jeśli istnieje wiele narożników, które zderzają się z łukiem zamachowym, należy wybrać ten, w którym kąt między liną podczas poprzedniej ramy a punktem zderzenia jest najmniejszy.

Pomocny schemat sytuacji liny ninja

Wykrywanie kolizji polega na tym, że dla podstawy bieżącego segmentu liny, O, pozycji końcowej liny na poprzedniej ramie, A, pozycji końcowej liny na bieżącej ramie, B, i każdego punktu narożnego P w wielokącie geometrii poziomu, obliczasz (OA x OP), (OP x OB) i (OA x OB), gdzie „x” oznacza przyjęcie współrzędnej Z iloczynu krzyżowego między dwoma wektorami. Jeśli wszystkie trzy wyniki mają ten sam znak, ujemny lub dodatni, a długość OP jest mniejsza niż długość odcinka liny, punkt P znajduje się w obszarze objętym huśtawką i powinieneś rozdzielić linę. Jeśli masz wiele kolidujących punktów narożnych, możesz użyć pierwszego, który uderza w linę, co oznacza ten, w którym kąt między OA a OP jest najmniejszy. Użyj iloczynu, aby określić kąt.

Jeśli chodzi o łączenie segmentów, wykonaj porównanie między poprzednim segmentem a łukiem bieżącego segmentu. Jeśli bieżący segment przesunął się z lewej strony na prawą lub odwrotnie, należy dołączyć do segmentów.

Do matematyki łączenia segmentów użyjemy punktu zaczepienia poprzedniego odcinka liny, Q, a także tych, które mieliśmy dla skrzynki rozdzielającej. Więc teraz będziesz chciał porównać wektory QO, OA i OB. Jeśli znak (QO x OA) różni się od znaku (QO x OB), lina przecięła się od lewej do prawej lub odwrotnie, i powinieneś dołączyć do segmentów. Może się to oczywiście zdarzyć, jeśli lina będzie się obracać o 180 stopni, więc jeśli chcesz, aby lina mogła owinąć pojedynczy punkt w przestrzeni zamiast wielokąta, możesz dodać do tego specjalny przypadek.

Ta metoda oczywiście zakłada, że ​​wykonujesz wykrywanie kolizji dla obiektu zwisającego z liny, aby nie znalazł się w geometrii poziomu.


1
Problem z tym podejściem polega na tym, że błędy precyzji zmiennoprzecinkowej umożliwiają linę „przejście” przez punkt.
Andrew Russell

16

Minęło trochę czasu, odkąd grałem w Worms, ale z tego, co pamiętam - kiedy lina owija się wokół rzeczy, jest tylko jeden (prosty) odcinek liny, który porusza się w danym momencie. Reszta liny staje się statyczna

Tak więc w grę wchodzi bardzo mało faktycznej fizyki. Aktywną sekcję można modelować jako pojedynczą sztywną sprężynę z masą na końcu

Interesującym bitem będzie logika do dzielenia / łączenia nieaktywnych odcinków liny do / z aktywnego odcinka.

Wyobrażam sobie, że będą 2 główne operacje:

„Split” - lina coś przecięła się. Podziel go na skrzyżowaniu na nieaktywną sekcję i nową, krótszą, aktywną sekcję

„Połącz” - aktywna lina przesunęła się do pozycji, w której nie ma już najbliższego skrzyżowania (może to być zwykły test iloczynu kąta / kropki?). Dołącz ponownie do 2 sekcji, tworząc nową, dłuższą, aktywną sekcję

W scenie zbudowanej z wielokątów 2D wszystkie punkty podziału powinny znajdować się w wierzchołku siatki kolizji. Wykrywanie kolizji może uprościć coś do czegoś w stylu „Jeśli lina przechodzi nad wierzchołkiem w tej aktualizacji, rozdzielić / dołączyć linę w tym wierzchołku?


2
Ten facet był na miejscu ... Właściwie to nie jest „sztywna” sprężyna, obracasz tylko jakąś prostą linię wokół ...
ścigający

Twoja odpowiedź jest poprawna technicznie. Ale w pewnym sensie założyłem, że posiadanie segmentów linii oraz dzielenie i łączenie ich było oczywiste. Interesuje mnie faktyczny algorytm / matematyka. Uściśliłem moje pytanie.
Andrew Russell,

3

Sprawdź, jak zaimplementowano linę ninja w Gusanos :

  • Lina działa jak cząstka, dopóki się do niej nie przyczepi.
  • Po przymocowaniu lina po prostu wywiera siłę na robaka.
  • Dołączanie do obiektów dynamicznych (podobnie jak innych robaków) jest nadal TODO: w tym kodzie.
  • Nie pamiętam, czy obsługiwane jest owijanie się wokół obiektów / narożników ...

Odpowiedni fragment strony ninjarope.cpp :


void NinjaRope::think()
{
    if ( m_length > game.options.ninja_rope_maxLength )
        m_length = game.options.ninja_rope_maxLength;

    if (!active)
        return;

    if ( justCreated && m_type->creation )
    {
        m_type->creation->run(this);
        justCreated = false;
    }

    for ( int i = 0; !deleteMe && i < m_type->repeat; ++i)
    {
        pos += spd;

        BaseVec<long> ipos(pos);

        // TODO: Try to attach to worms/objects

        Vec diff(m_worm->pos, pos);
        float curLen = diff.length();
        Vec force(diff * game.options.ninja_rope_pullForce);

        if(!game.level.getMaterial( ipos.x, ipos.y ).particle_pass)
        {
            if(!attached)
            {
                m_length = 450.f / 16.f - 1.0f;
                attached = true;
                spd.zero();
                if ( m_type->groundCollision  )
                    m_type->groundCollision->run(this);
            }
        }
        else
            attached = false;

        if(attached)
        {
            if(curLen > m_length)
            {
                m_worm->addSpeed(force / curLen);
            }
        }
        else
        {
            spd.y += m_type->gravity;

            if(curLen > m_length)
            {
                spd -= force / curLen;
            }
        }
    }
}

1
Uhmn ... to wcale nie odpowiada na moje pytanie. Cały sens mojego pytania dotyczy owijania liny wokół świata zbudowanego z wielokątów. Wydaje się, że Gusanos nie ma świata zawijania i bitmap.
Andrew Russell

1

Obawiam się, że nie mogę podać konkretnego algorytmu z góry mojej głowy, ale przychodzi mi do głowy, że tylko dwie rzeczy mają znaczenie dla wykrycia kolizji z liną ninja: wszystkie potencjalnie kolidujące wierzchołki na przeszkodach w promieniu ostatniego „podziału” równego pozostałej długości odcinka; oraz aktualny kierunek obrotu (zgodnie z ruchem wskazówek zegara lub przeciwnie do ruchu wskazówek zegara). Jeśli utworzyłeś tymczasową listę kątów od „podzielonego” wierzchołka do każdego z pobliskich wierzchołków, twój algorytm musiałby się tylko przejmować, czy twój segment ma zamiar przekroczyć ten kąt dla dowolnego wierzchołka. Jeśli tak jest, musisz wykonać operację podziału, co jest łatwe jak ciasto - To tylko linia od ostatniego wierzchołka podziału do nowego podziału, a następnie obliczana jest nowa reszta.

Myślę, że tylko wierzchołki mają znaczenie. Jeśli grozi ci uderzenie w odcinek między wierzchołkami przeszkody, normalne wykrywanie kolizji przez faceta wiszącego na końcu liny powinno się uruchomić. Innymi słowy, lina będzie się zawsze „zaczepiać” i tak skręca, więc segmenty pomiędzy nie będą miały znaczenia.

Przepraszam, nie mam nic konkretnego, ale mam nadzieję, że doprowadzi cię to tam, gdzie trzeba, koncepcyjnie, aby tak się stało. :)


1

Oto post, który zawiera linki do artykułów na temat podobnych rodzajów symulacji (w kontekście inżynieryjnym / akademickim, a nie do gier): https://gamedev.stackexchange.com/a/10350/6398

Próbowałem przynajmniej dwóch różnych podejść do wykrywania kolizji + reakcji dla tego rodzaju symulacji „drutowej” (jak widać w grze Umihara Kawase); przynajmniej myślę, że o to ci chodzi - wydaje się, że nie ma określonego terminu dla tego rodzaju symulacji, po prostu nazywam to raczej „drutem” niż „liną”, ponieważ wydaje się, że większość ludzi uważaj „linę” za synonim „łańcucha cząstek”. A jeśli chcesz zachować przyczepność liny ninja (tzn. Może pchać ORAZ ciągnąć), jest to bardziej sztywny drut niż lina. Tak czy inaczej..

Odpowiedź Pekuji jest dobra, możesz zaimplementować ciągłe wykrywanie kolizji, rozwiązując czas, gdy podpisany obszar trzech punktów ma wartość 0.

(Nie mogę w pełni przypomnieć OTOH, ale możesz do niego podejść w następujący sposób: znajdź czas t, kiedy punkt a jest zawarty w linii przechodzącej przez b, c, (Myślę, że zrobiłem to, rozwiązując przypadek, gdy kropka (ab, cb) = 0, aby znaleźć wartości t), a następnie biorąc pod uwagę prawidłowy czas 0 <= t <1, znajdź pozycję parametryczną s na odcinku bc, tj. A = (1-s) b + s c, a jeśli a jest pomiędzy b i c (tzn. jeśli 0 <= s <= 1) jest to prawidłowa kolizja.

AFAICR możesz podejść do tego również na odwrót (tzn. Rozwiązać s, a następnie podłączyć to, aby znaleźć t), ale jest to o wiele mniej intuicyjne. (Przepraszam, jeśli to nie ma sensu, nie mam czasu na kopanie notatek i minęło kilka lat!)

Możesz więc teraz obliczyć wszystkie czasy, w których zdarzają się zdarzenia (tzn. Należy włożyć lub usunąć węzły liny); przetworz najwcześniejsze zdarzenie (wstaw lub usuń węzeł), a następnie powtarzaj / powtarzaj, aż nie będzie już żadnych zdarzeń między t = 0 it = 1.

Jedno ostrzeżenie o tym podejściu: jeśli obiekty, które lina może owijać, są dynamiczne (zwłaszcza jeśli je symulujesz ORAZ ich wpływ na linę i odwrotnie), mogą wystąpić problemy, jeśli obiekty te przeciągną się / przejdą przez siebie inne - drut może się zaplątać. I zdecydowanie wyzwaniem będzie zapobieganie tego rodzaju interakcjom / ruchom (rogi obiektów prześlizgujących się między sobą) w symulacji fizyki w stylu box2d. Niewielkie przenikanie między obiektami jest normalnym zachowaniem w tym kontekście.

(Przynajmniej .. to był problem z jedną z moich implementacji „drutu”.)

Innym rozwiązaniem, które jest znacznie bardziej stabilne, ale w niektórych warunkach brakuje niektórych kolizji, jest po prostu użycie testów statycznych (tj. Nie martw się o zamówienie według czasu, po prostu rekurencyjnie podziel każdy segment w kolizji, gdy go znajdziesz), który może być o wiele bardziej wytrzymały - drut nie zaplątuje się w rogach, a niewielka penetracja będzie w porządku.

Myślę, że podejście Pekuja też do tego służy, jednak istnieją alternatywne podejścia. Jednym z zastosowanych przeze mnie podejść jest dodanie pomocniczych danych kolizji: na każdym wypukłym wierzchołku v na świecie (tj. Na rogach kształtów, które może owinąć lina), dodaj punkt u tworzący skierowany odcinek linii uv, gdzie u jest trochę punkt „w rogu” (tj. w świecie, „za” v; aby obliczyć u, możesz rzucić promień do wewnątrz od v wzdłuż jego interpolowanej normalnej i zatrzymać pewną odległość po v lub zanim promień przecina się z krawędzią świata i wychodzi z obszaru bryłowego lub możesz po prostu ręcznie pomalować segmenty na świecie za pomocą wizualnego edytora narzędzi / poziomów).

W każdym razie masz teraz zestaw „narożnych linii” uv; dla każdego ultrafioletu i każdego odcinka ab w przewodzie sprawdź, czy przecinają ab i ultrafiolet (tj. zapytanie statyczne, boolean lineseg-lineseg przecięcia); jeśli tak, powtórz (podziel linię ab na av i vb, tj. wstaw v), rejestrując, w którym kierunku wygięta jest lina w v. Następnie dla każdej pary sąsiednich linii, ab, bc w drucie, sprawdź, czy bieżący kierunek zgięcia w b jest taki sam, jak w przypadku wygenerowania b (wszystkie te testy „kierunku zgięcia” są tylko testami obszaru ze znakiem); jeśli nie, połącz dwa segmenty w ac (tj. usuń b).

A może połączyłem, a potem podzieliłem, zapominam - ale na pewno działa w co najmniej jednym z dwóch możliwych zamówień! :)

Biorąc pod uwagę wszystkie segmenty drutu obliczone dla bieżącej ramki, możesz następnie symulować ograniczenie odległości między dwoma punktami końcowymi drutu (i możesz nawet zaangażować punkty wewnętrzne, tj. Punkty kontaktu między drutem a światem, ale jest to nieco bardziej zaangażowane ).

W każdym razie, mam nadzieję, że to się przyda ... papiery w poście, które również zamieściłem, powinny również dać ci kilka pomysłów.


0

Jednym podejściem jest modelowanie liny jako zderzających się cząstek połączonych sprężynami. (dość sztywne, być może nawet jako kość). Cząsteczki zderzają się z otoczeniem, upewniając się, że lina owija się wokół przedmiotów.

Oto demo ze źródłem: http://www.ewjordan.com/rgbDemo/

(Przejdź na prawo na pierwszym poziomie, jest czerwona lina, z którą możesz wchodzić w interakcje)


2
Uh - tego właśnie nie chcę (patrz pytanie).
Andrew Russell,

Ach To nie było jasne z pierwotnego pytania. Dziękujemy za poświęcenie czasu na wyjaśnienie tego. (Świetny schemat!) Wciąż stosowałbym serię bardzo małych stałych połączeń, w przeciwieństwie do wykonywania dynamicznych podziałów - chyba że jest to ogromny problem z wydajnością w twoim środowisku, o wiele łatwiej jest napisać kod.
Rachel Blum,
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.