Zderzenie piłki z piłką - wykrywanie i obsługa

Z pomocą społeczności Stack Overflow napisałem całkiem prosty, ale zabawny symulator fizyki.

Kliknij i przeciągnij myszą, aby uruchomić piłkę. Odbije się i ostatecznie zatrzyma na „podłodze”.

Kolejną ważną funkcją, którą chcę dodać, jest zderzenie piłki z piłką. Ruch piłki jest podzielony na wektor ax i y prędkości. Mam grawitację (małe zmniejszenie wektora y na każdym kroku), mam tarcie (małe zmniejszenie obu wektorów przy każdym zderzeniu ze ścianą). Piłki szczerze się poruszają w zaskakująco realistyczny sposób.

Myślę, że moje pytanie składa się z dwóch części:

1. Jaka jest najlepsza metoda wykrywania kolizji piłki z piłką?
   Czy mam po prostu pętlę O (n ^ 2), która przechodzi przez każdą piłkę i sprawdza każdą inną piłkę, aby sprawdzić, czy jej promień się pokrywa?
2. Jakich równań używam do obsługi zderzeń piłki z piłką? Fizyka 101
   Jak to wpływa na prędkość dwóch kulek wektorów x / y? W jakim kierunku zmierzają obie piłki? Jak zastosować to do każdej piłki?

Obsługa wykrywania kolizji „ścian” i wynikających z tego zmian wektora była łatwa, ale widzę więcej komplikacji w przypadku zderzeń piłki z piłką. W przypadku ścian musiałem po prostu wziąć ujemny odpowiedni wektor x lub y, po czym poszedłby we właściwym kierunku. Z piłkami nie sądzę, że tak jest.

Kilka szybkich wyjaśnień: dla uproszczenia jestem na razie z idealnie elastycznym zderzeniem, również wszystkie moje piłki mają teraz tę samą masę, ale mogę to zmienić w przyszłości.

Edycja: zasoby, które uważam za przydatne

Fizyka kuli 2d z wektorami: zderzenia dwuwymiarowe bez trygonometrii.pdf
Przykład 2d wykrywania kolizji kuli: Dodawanie detekcji kolizji

Sukces!

Wykrywanie kolizji z piłką i reakcja działają świetnie!

Odpowiedni kod:

Wykrywanie kolizji:

for (int i = 0; i < ballCount; i++)  
{  
    for (int j = i + 1; j < ballCount; j++)  
    {  
        if (balls[i].colliding(balls[j]))  
        {
            balls[i].resolveCollision(balls[j]);
        }
    }
}

Spowoduje to sprawdzenie kolizji między każdą piłką, ale pominie zbędne kontrole (jeśli musisz sprawdzić, czy piłka 1 koliduje z piłką 2, nie musisz sprawdzać, czy piłka 2 koliduje z piłką 1. Pomija również sprawdzanie kolizji ze sobą) ).

Następnie w mojej klasie ball mam metody colliding () i resolCollision ():

public boolean colliding(Ball ball)
{
    float xd = position.getX() - ball.position.getX();
    float yd = position.getY() - ball.position.getY();

    float sumRadius = getRadius() + ball.getRadius();
    float sqrRadius = sumRadius * sumRadius;

    float distSqr = (xd * xd) + (yd * yd);

    if (distSqr <= sqrRadius)
    {
        return true;
    }

    return false;
}

public void resolveCollision(Ball ball)
{
    // get the mtd
    Vector2d delta = (position.subtract(ball.position));
    float d = delta.getLength();
    // minimum translation distance to push balls apart after intersecting
    Vector2d mtd = delta.multiply(((getRadius() + ball.getRadius())-d)/d); 


    // resolve intersection --
    // inverse mass quantities
    float im1 = 1 / getMass(); 
    float im2 = 1 / ball.getMass();

    // push-pull them apart based off their mass
    position = position.add(mtd.multiply(im1 / (im1 + im2)));
    ball.position = ball.position.subtract(mtd.multiply(im2 / (im1 + im2)));

    // impact speed
    Vector2d v = (this.velocity.subtract(ball.velocity));
    float vn = v.dot(mtd.normalize());

    // sphere intersecting but moving away from each other already
    if (vn > 0.0f) return;

    // collision impulse
    float i = (-(1.0f + Constants.restitution) * vn) / (im1 + im2);
    Vector2d impulse = mtd.normalize().multiply(i);

    // change in momentum
    this.velocity = this.velocity.add(impulse.multiply(im1));
    ball.velocity = ball.velocity.subtract(impulse.multiply(im2));

}

Kod źródłowy: Pełne źródło zderzacza piłka-piłka.

Jeśli ktoś ma jakieś sugestie dotyczące ulepszenia tego podstawowego symulatora fizyki, daj mi znać! Jedną z rzeczy, które muszę jeszcze dodać, jest moment pędu, aby kule toczyły się bardziej realistycznie. Jakieś inne sugestie? Zostaw komentarz!

Aby wykryć, czy dwie kule zderzają się, po prostu sprawdź, czy odległość między ich środkami jest mniejsza niż dwukrotność promienia. Aby wykonać idealnie elastyczną kolizję między kulkami, musisz tylko martwić się składową prędkości, która jest w kierunku kolizji. Drugi element (styczny do zderzenia) pozostanie taki sam dla obu piłek. Możesz uzyskać komponenty kolizji, tworząc wektor jednostkowy skierowany w kierunku od jednej kulki do drugiej, a następnie biorąc iloczyn iloczynu za pomocą wektorów prędkości kul. Następnie można podłączyć te komponenty do idealnie elastycznego równania kolizji 1D.

Wikipedia ma całkiem dobre podsumowanie całego procesu . W przypadku kulek o dowolnej masie nowe prędkości można obliczyć za pomocą równań (gdzie v1 i v2 są prędkościami po zderzeniu, a u1, u2 są przedtem):

Jeśli kule mają tę samą masę, wówczas prędkości są po prostu zmieniane. Oto kod, który napisałem, który robi coś podobnego:

void Simulation::collide(Storage::Iterator a, Storage::Iterator b)
{
    // Check whether there actually was a collision
    if (a == b)
        return;

    Vector collision = a.position() - b.position();
    double distance = collision.length();
    if (distance == 0.0) {              // hack to avoid div by zero
        collision = Vector(1.0, 0.0);
        distance = 1.0;
    }
    if (distance > 1.0)
        return;

    // Get the components of the velocity vectors which are parallel to the collision.
    // The perpendicular component remains the same for both fish
    collision = collision / distance;
    double aci = a.velocity().dot(collision);
    double bci = b.velocity().dot(collision);

    // Solve for the new velocities using the 1-dimensional elastic collision equations.
    // Turns out it's really simple when the masses are the same.
    double acf = bci;
    double bcf = aci;

    // Replace the collision velocity components with the new ones
    a.velocity() += (acf - aci) * collision;
    b.velocity() += (bcf - bci) * collision;
}

Jeśli chodzi o wydajność, Ryan Fox ma rację, powinieneś rozważyć podzielenie regionu na sekcje, a następnie wykrycie kolizji w każdej sekcji. Pamiętaj, że kule mogą kolidować z innymi kulkami na granicach sekcji, więc może to znacznie skomplikować kod. Wydajność prawdopodobnie nie będzie miała znaczenia, dopóki nie będziesz mieć kilkuset piłek. Aby otrzymać punkty bonusowe, możesz uruchomić każdą sekcję na innym rdzeniu lub podzielić przetwarzanie kolizji w ramach każdej sekcji.

Cóż, lata temu stworzyłem program taki, jak tutaj.
Istnieje jeden ukryty problem (lub wiele, zależy od punktu widzenia):

• Jeśli prędkość piłki jest zbyt wysoka, możesz przegapić kolizję.

A także, prawie w 100% przypadków, twoje nowe prędkości będą błędne. Cóż, nie prędkości , ale pozycje . Musisz obliczyć nowe prędkości dokładnie w odpowiednim miejscu. W przeciwnym razie wystarczy przesunąć kulki na niewielką ilość „błędu”, która jest dostępna z poprzedniego dyskretnego kroku.

Rozwiązanie jest oczywiste: musisz podzielić przedział czasowy, aby najpierw przejść do właściwego miejsca, a następnie zderzyć się, a następnie przejść do końca pozostałego czasu.

Do rozwiązania tego problemu należy użyć partycjonowania przestrzeni.

Przeczytaj o partycjonowaniu przestrzeni binarnej i quadtreesach

Jako wyjaśnienie sugestii Ryana Foxa, aby podzielić ekran na regiony i sprawdzać tylko kolizje w regionach ...

np. podziel obszar gry na siatkę kwadratów (która arbitralnie powie, że mają długość 1 jednostki na bok) i sprawdź kolizje w obrębie każdego kwadratu siatki.

To jest absolutnie prawidłowe rozwiązanie. Jedyny problem z tym (jak wskazał inny plakat) polega na tym, że problemem są kolizje ponad granicami.

Rozwiązaniem tego problemu jest nałożenie drugiej siatki z przesunięciem pionowym i poziomym o 0,5 jednostki w stosunku do pierwszej.

Następnie wszelkie kolizje, które miałyby miejsce ponad granicami w pierwszej siatce (a zatem nie zostały wykryte), będą się mieścić w kwadratach siatki w drugiej siatce. Tak długo, jak śledzisz kolizje, które już sobie poradziłeś (ponieważ może się zdarzyć, że się nakładają), nie musisz się martwić o obsługę przypadków skrajnych. Wszystkie kolizje będą w obrębie kwadratu siatki na jednej z siatek.

Dobrym sposobem na zmniejszenie liczby kontroli kolizji jest podzielenie ekranu na różne sekcje. Następnie porównujesz tylko każdą piłkę z piłkami w tej samej sekcji.

Jedną rzecz, którą widzę tutaj do optymalizacji.

Chociaż zgadzam się, że kule uderzone, gdy odległość jest sumą ich promieni, nigdy nie należy tak naprawdę obliczać tej odległości! Zamiast tego obliczyć kwadrat i pracować z nim w ten sposób. Nie ma powodu do tak kosztownej operacji pierwiastka kwadratowego.

Ponadto po znalezieniu kolizji musisz kontynuować ocenę kolizji, aż nie będzie już więcej. Problem polega na tym, że pierwszy może spowodować, że inni będą musieli zostać rozwiązani, zanim uzyskasz dokładny obraz. Zastanów się, co się stanie, jeśli piłka uderzy w piłkę na krawędzi? Druga piłka uderza w krawędź i natychmiast zbiera się w pierwszą piłkę. Jeśli uderzysz w stos piłek w rogu, możesz mieć całkiem sporo kolizji, które trzeba rozwiązać, zanim będziesz mógł powtórzyć następny cykl.

Jeśli chodzi o O (n ^ 2), wszystko, co możesz zrobić, to zminimalizować koszt odrzucenia tych, które przegapią:

1) Piłka, która się nie porusza, nie może trafić niczego. Jeśli na podłodze leży rozsądna liczba piłek, może to zaoszczędzić wielu testów. (Pamiętaj, że nadal musisz sprawdzić, czy coś uderzy w nieruchomą piłkę).

2) Coś, co może być warte zrobienia: Podziel ekran na kilka stref, ale linie powinny być rozmyte - kule na krawędzi strefy są wymienione jako znajdujące się we wszystkich odpowiednich (może być 4) strefach. Chciałbym użyć siatki 4x4, przechowywać strefy jako bity. Jeżeli ORAZ stref dwóch stref piłek zwraca zero, koniec testu.

3) Jak wspomniałem, nie rób pierwiastka kwadratowego.

Znalazłem doskonałą stronę z informacjami na temat wykrywania kolizji i reakcji w 2D.

http://www.metanetsoftware.com/technique.html

Próbują wyjaśnić, jak to się robi z akademickiego punktu widzenia. Zaczynają od prostego wykrywania kolizji między obiektami, a następnie przechodzą do odpowiedzi na kolizję i sposobu jej skalowania.

Edytuj: zaktualizowano link

Masz na to dwa proste sposoby. Jay opisał dokładny sposób sprawdzania od środka piłki.

Najłatwiejszym sposobem jest użycie prostokątnego obwiedni, ustawienie rozmiaru pudełka na 80% wielkości piłki, a całkiem dobrze symulujesz kolizję.

Dodaj metodę do swojej klasy piłki:

public Rectangle getBoundingRect()
{
   int ballHeight = (int)Ball.Height * 0.80f;
   int ballWidth = (int)Ball.Width * 0.80f;
   int x = Ball.X - ballWidth / 2;
   int y = Ball.Y - ballHeight / 2;

   return new Rectangle(x,y,ballHeight,ballWidth);
}

Następnie w swojej pętli:

// Checks every ball against every other ball. 
// For best results, split it into quadrants like Ryan suggested. 
// I didn't do that for simplicity here.
for (int i = 0; i < balls.count; i++)
{
    Rectangle r1 = balls[i].getBoundingRect();

    for (int k = 0; k < balls.count; k++)
    {

        if (balls[i] != balls[k])
        {
            Rectangle r2 = balls[k].getBoundingRect();

            if (r1.Intersects(r2))
            {
                 // balls[i] collided with balls[k]
            }
        }
    }
}

Widzę, że jest to wskazane tu i tam, ale możesz też najpierw wykonać szybsze obliczenia, na przykład porównać ramki graniczne dla nakładania się, a NASTĘPNIE wykonać nakładanie oparte na promieniu, jeśli ten pierwszy test się powiedzie.

Matematyka dodawania / różnicowania jest znacznie szybsza w przypadku ramki ograniczającej niż wszystkie wartości wyzwalające dla promienia, i w większości przypadków test ramki ograniczającej wyklucza możliwość kolizji. Ale jeśli następnie ponownie przetestujesz za pomocą trig, uzyskasz dokładne wyniki, których szukasz.

Tak, to dwa testy, ale ogólnie będzie szybciej.

Jest KineticModelto implementacja cytowanego podejścia w Javie.

Zaimplementowałem ten kod w JavaScript za pomocą elementu HTML Canvas, który wygenerował wspaniałe symulacje przy 60 klatkach na sekundę. Symulację rozpocząłem od zebrania kilkunastu piłek o losowych pozycjach i prędkościach. Zauważyłem, że przy wyższych prędkościach kolizja pomiędzy małą i znacznie większą kulą sprawiała, że ​​mała kulka przylepiała się do krawędzi większej kuli i przesuwała się do około 90 stopni wokół większej kuli przed rozdzieleniem. (Zastanawiam się, czy ktokolwiek zaobserwował to zachowanie).

Niektóre zapisy obliczeń wykazały, że minimalna odległość translacji w tych przypadkach nie była wystarczająco duża, aby zapobiec zderzeniu się tych samych piłek w następnym kroku. Przeprowadziłem eksperymenty i odkryłem, że mogę rozwiązać ten problem, zwiększając MTD w oparciu o prędkości względne:

dot_velocity = ball_1.velocity.dot(ball_2.velocity);
mtd_factor = 1. + 0.5 * Math.abs(dot_velocity * Math.sin(collision_angle));
mtd.multplyScalar(mtd_factor);

Sprawdziłem, że przed i po tej poprawce całkowita energia kinetyczna była zachowywana dla każdego zderzenia. Wartość 0,5 w współczynniku mtd_ była w przybliżeniu minimalną wartością, która zawsze powoduje, że kule się rozdzielają po zderzeniu.

Chociaż ta poprawka wprowadza niewielki błąd w dokładnej fizyce systemu, kompromis polega na tym, że teraz bardzo szybkie kule można symulować w przeglądarce bez zmniejszania rozmiaru kroku czasowego.