Rozdzielczość kolizji w przypadku kolizji z wieloma obiektami

Mam obiekty statyczne i ruchome. Zderzenia są wykrywane za pomocą twierdzenia o osi oddzielającej.

Na przykład w tej sytuacji mam dwa obiekty statyczne (na czerwono):

i ruchomy obiekt między nimi:

Mój algorytm jest w stanie obliczyć kolizję między dwoma z tych obiektów, a także wyrzuca wektor doskonałej rozdzielczości (co oznacza wektor minimalnego przemieszczenia) na kolizję.

Na przykład, kiedy sprawdzam kolizję między zielonym prostokątem a prawym czerwonym prostokątem, algorytm wyrzuca wektor, który mówi mi, jak muszę przesunąć zielony prostokąt, aby rozwiązać kolizję:

Zauważ, że właśnie szybko narysowałem to w MSPaint, więc na tym zdjęciu może być tak, że wektor minimalnego tłumaczenia wypycha zielony prostokąt na górę, ale zakładam tutaj, że wypycham go w lewo / prawo jest w rzeczywistości krótsze.

Ogólnym sposobem podejścia do tego byłoby rozwiązanie kolizji tylko jednej kolizji na ramkę, zamiast wszystkich naraz. Ale w moim przypadku spowodowałoby to przerzucanie:

Po pierwsze, solver wykrywa dwie kolizje, ale rozwiązuje tylko kolizję między prawym prostokątem a zielonym prostokątem:

Następnie w następnej ramce wykrywa tylko jedną kolizję między lewym czerwonym prostokątem a zielonym prostokątem i rozwiązuje go:

Jak widać, tak naprawdę nie rozwiązuje to kolizji (na przykład wypychając zielony prostokąt do góry), a zamiast tego po prostu nieskończenie przerzuca klapy między dwoma stanami.

Jak mogę to rozwiązać?

W zależności od tego, co dokładnie próbujesz osiągnąć (wysoka dokładność fizyczna lub po prostu wystarczająco dokładna symulacja w czasie rzeczywistym), możesz spróbować użyć spekulacyjnych kontaktów.

Oto szczegóły: http://www.wildbunny.co.uk/blog/2011/03/25/speculative-contacts-an-continuous-collision-engine-approach-part-1/

W tym artykule opisuje, co musisz wiedzieć, aby go wdrożyć, i jest to bardzo proste w porównaniu z innymi podejściami (takimi jak rzucanie kuli, a następnie sortowanie rozdzielczości kolizji według czasu uderzenia).

Jeśli potrzebujesz / chcesz więcej, możesz kupić jego kod źródłowy za (IIRC) 7 USD.

Oto wideo z mojej implementacji w 3D: http://www.youtube.com/watch?v=JvT2H1RmOas

Zauważ, jak stabilna jest symulacja za pomocą tylko jednej iteracji. Możesz łatwo użyć wielu iteracji na ramkę, aby rozwiązać wiele kolizji do stanu stabilnego, co byłoby dokładniejsze.

Możesz najpierw obliczyć wszystkie wektory potrzebne do rozwiązania każdego kolizji, a następnie obliczyć wynikową z nich.

Jedynym przypadkiem, w którym możesz to bajtować, jest to, że te wektory wzajemnie się niwelują, tak jak w twoim przykładzie. W takim przypadku kolizji nie można rozwiązać.

Jeśli przyjrzysz się temu uważnie, ten stan obiektów jest (lub powinien być) nieosiągalny.

Niech lewy czerwony kształt będzie kształtem R1, a prawy czerwony kształt będzie kształtem R2. Niech zielony kształt będzie G.

tzn. biorąc pod uwagę rozmiar i geometrię wszystkich trzech obiektów oraz biorąc pod uwagę, że wszystkie obiekty nie są przenikalne:

 (1) G could not have been just directly to the left of R2, since R1 has been there 
     already. Consequently, the translation of G from left to right, penetrating R2
     could not have occurred.
 (2) G could not have been just directly to the right of R1 since R2 has been there 
     already. Consquence of which is the same as that from (1).
 (3) Had G come from the top, the movement will be blocked by both R1 and R2, given
     that their geometry and Y coordinate is the same.

Teraz sprowadza się do tego, że jeśli algorytm odpytuje twoje obiekty jeden po drugim, jest to kwestia współbieżności, tj. W pewnym sensie algorytm ma sprawdzać WSZYSTKIE obiekty w tym samym czasie, ale algorytm ogranicza cię do zrobienia obiekty i przetwarzaj je pojedynczo ...

Jeśli G jest sprawdzane względem R1 po sprawdzeniu względem R2, wydaje się, że G legalnie znajduje się po prawej stronie R1 (jeśli G powiedzmy zbliża się do R1 z kierunkiem wektora <-1, -1> z dowolną wielkością (lub odległością) ), ponieważ pozwala na to sprawdzenie między R1 a G, i zapomina o sprawdzeniu między R2 a G, które zostało wykonane wcześniej.

Rozwiązaniem, które możesz zrobić, jest zebranie wszystkich wektorów minimalnego przemieszczenia w tablicy lub dowolnej innej strukturze danych i wybranie takiego, który okaże się legalny dla WSZYSTKICH Obiektów.

Zauważ, że w danej ramce obiekt (na przykład G) może mieć tylko JEDEN kierunek. (o rany, brzmi jak opaska chłopięca ...)