Kolizja z piłką - wykrywanie i obsługa

Cóż, lata temu stworzyłem program tak, jak prezentowałeś tutaj.
Jest jeden ukryty problem (lub wiele, zależy od punktu widzenia):

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

A także, prawie w 100% przypadków twoje nowe prędkości będą złe. Cóż, nie Prędkości , ale pozycje . Musisz obliczyć nowe prędkości dokładnie we właściwym miejscu. W przeciwnym razie po prostu przesuń kulki na jakąś małą" błąd " kwotę, która jest dostępne od poprzedniego dyskretnego kroku.

Rozwiązanie jest oczywiste: musisz podzielić timestep tak, że najpierw przesuniesz się w odpowiednie miejsce, następnie zderzysz się, a następnie przesuniesz na resztę czasu, który masz.

Powinieneś użyć partycjonowania spacji, aby rozwiązać ten problem.

Czytaj dalej Binarne Partycjonowanie Przestrzeni oraz Quadtrees

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

Np. podziel pole gry na siatkę kwadratów (które arbitralnie powiedzą, że mają 1 jednostkę długości na stronę) i sprawdź, czy w każdym kwadracie nie ma kolizji.

To absolutnie poprawne rozwiązanie. Jedynym problemem z nim (jak zauważył inny plakat) jest to, że kolizje poza granicami są problemem.

The rozwiązaniem jest nałożenie drugiej siatki na 0,5 jednostki przesunięcia pionowego i poziomego do pierwszej.

Wtedy wszelkie kolizje, które byłyby poza granicami w pierwszej siatce (a więc nie wykryte), będą w obrębie kwadratów siatki w drugiej siatce. Tak długo, jak będziesz śledzić kolizje, z którymi już się uporałeś (ponieważ prawdopodobnie pojawią się pewne nakładki), nie musisz się martwić o obsługę przypadków krawędziowych. Wszystkie kolizje będą w kwadracie 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.

Jedna rzecz, którą widzę tutaj, aby zoptymalizować.

Chociaż zgadzam się, że kule trafione, gdy odległość jest sumą ich promieni, nigdy nie należy obliczać tej odległości! Raczej Oblicz, że jest kwadratowy i pracuj z nim w ten sposób. Nie ma powodu do tej kosztownej operacji pierwiastka kwadratowego.

Ponadto, po znalezieniu kolizji musisz kontynuować ocenę kolizji, dopóki nie zostanie już więcej. Problem polega na tym, że pierwszy z nich może spowodować inne, które muszą być rozwiązane zanim uzyskasz dokładny obraz. Zastanów się, co się stanie, jeśli piłka uderzy piłkę na krawędzi? Druga piłka uderza w krawędź i natychmiast odbija do pierwszej piłki. Jeśli uderzysz w stertę piłek w rogu, możesz mieć sporo kolizji, które muszą zostać rozwiązane, zanim będziesz mógł powtórzyć następny cykl.

Co do O (n^2), wszystko co możesz zrobić to zminimalizować koszty odrzucenia tych, które nie trafią:

1) piłka, która się nie porusza, nie może w nic trafić. Jeśli istnieją rozsądna liczba piłek leżących na podłodze może zaoszczędzić wiele testów. (Pamiętaj, że musisz jeszcze sprawdzić, czy coś uderzyło w nieruchomą piłkę.)

2) coś, co może być warte zrobienia: podziel ekran na kilka stref, ale linie powinny być rozmyte-kulki na krawędzi strefy są wymienione jako znajdujące się we wszystkich odpowiednich (może być 4) strefach. Użyłbym siatki 4x4, przechowując strefy jako bity. Jeśli i strefy dwóch stref kulek zwróci zero, koniec test.

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ą się od prostego wykrywania kolizji obiekt-obiekt, a następnie przechodzą do odpowiedzi na kolizje i skalowania jej.

Edit: Updated link

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

Łatwiejszym sposobem jest użycie prostokątnej obwiedni, ustawienie rozmiaru pudełka na 80% wielkości piłki, a będziesz symulować kolizję całkiem dobrze.

Dodaj metodę do 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 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ę to tu i ówdzie, ale możesz też najpierw wykonać szybsze obliczenia, np. porównać obwiedni dla nakładania się, a następnie wykonać nakładanie na Promień, jeśli pierwszy test przejdzie.

Matematyka dodawania/różnicy jest znacznie szybsza dla obwiedni niż wszystkie Tryg dla promienia, a najczęściej test obwiedni odrzuca możliwość kolizji. Ale jeśli następnie ponownie przetestować z Tryg, otrzymujesz dokładne wyniki, które szukasz.

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

To KineticModel jest implementacją cytowanego podejścia w Javie.

Zaimplementowałem ten kod w JavaScript za pomocą elementu HTML Canvas, który produkował wspaniałe symulacje z prędkością 60 klatek na sekundę. Zacząłem symulację od kolekcji kilkunastu kulek w losowych pozycjach i prędkościach. Okazało się, że przy wyższych prędkościach, kolizja między małą piłką a znacznie większą spowodowała, że mała piłka wydawała się trzymać do krawędzi większej piłki i przesunęła się do około 90 stopni wokół większej piłki przed rozdzieleniem. (Ciekawe czy ktoś jeszcze zaobserwował takie zachowanie.)

Niektóre zapisy obliczeń wykazały, że minimalna odległość tłumaczenia w tych przypadkach nie była wystarczająco duża, aby zapobiec zderzeniu tych samych kulek w następnym kroku czasowym. Zrobiłem kilka eksperymentów i okazało się, że mogę rozwiązać ten problem, skalując MTD w oparciu o względne prędkości: {]}

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);

Chociaż ta poprawka wprowadza niewielką ilość błędów w dokładnej fizyce systemu, kompromis polega na tym, że teraz bardzo szybkie kulki mogą być symulowane w przeglądarce bez zmniejszania rozmiaru kroku czasowego.

Jak widzę tutaj, nie wspomniano o lepszym sposobie jego realizacji. odsyłam do "jak symulować bilard i podobne systemy" Borysa D. Lubaczewskiego, dostępnego na arxiv: http://arxiv.org/abs/cond-mat/0503627 na załączonym obrazku jest zrzut ekranu programu, który zamierzam zrobić open source, kiedy go skończę. Nawet na wczesnym etapie działa z 5000 kul całkiem płynnie. Mam nadzieję, że będzie jeszcze lepiej, chociaż nie chcę wdrażać sektorowania, I chcesz, aby Kod był łatwy do zrozumienia. Opis będzie dostępny na stronie http://compphys.go.ro

Później edycja: kod jest już dostępny na Githubie: https://github.com/aromanro/EventMolecularDynamics opis jest na blogu: http://compphys.go.ro/event-driven-molecular-dynamics/