Reakcja na zderzenie w grze 2D: SAT i minimalne przemieszczenie wzdłuż danej osi?

Próbuję wdrożyć system kolizji w tworzonej przeze mnie grze 2D. Twierdzenie o osi oddzielającej (opisane w samouczku dotyczącym kolizji metanetu ) wydaje się wydajnym i niezawodnym sposobem obsługi wykrywania kolizji, ale nie podoba mi się metoda odpowiedzi na kolizję, której używają. Algorytm przesuwając się na oś wzdłuż osi najmniejszego zachodzenia na siebie, po prostu ignoruje poprzednią pozycję poruszającego się obiektu, co oznacza, że ​​nie zderza się on z nieruchomym obiektem tak bardzo, jak wchodzi w niego, a następnie się odbija.

Oto przykład sytuacji, w której miałoby to znaczenie:

Zgodnie z opisaną powyżej metodą SAT prostokąt wyskoczyłby z trójkąta prostopadłego do jego przeciwprostokątnej:

Jednak realistycznie prostokąt powinien zatrzymać się w prawym dolnym rogu trójkąta, ponieważ byłby to punkt pierwszego zderzenia, gdyby poruszał się w sposób ciągły wzdłuż wektora przemieszczenia:

Teraz może to nie mieć znaczenia podczas gry, ale chciałbym wiedzieć, czy istnieje sposób na skuteczne i generalne uzyskanie dokładnych przemieszczeń w ten sposób. Przez ostatnie kilka dni zastanawiałem się nad tym i nie chcę się jeszcze poddawać!

(Przesłane z StackOverflow, mam nadzieję, że nie jest to niezgodne z regułami!)

Oto metoda, którą znalazłem. Może być wadliwy, ale nie znalazłem z tym żadnych problemów w mojej pobieżnej analizie. Działa również w przypadku dowolnych wielokątów z kilkoma drobnymi modyfikacjami.

Na poniższych ilustracjach niebieski obiekt się porusza, a czerwony jest nieruchomy. Krok 1: Dla każdego wielokąta znajdź dwa najdalsze punkty wzdłuż rzutu tego wielokąta na linię prostopadłą do wektora ruchu. Krok 2: Podziel każdy wielokąt wzdłuż linii łączącej te punkty. Połowa wielokąta zwrócona w stronę drugiego wielokąta wzdłuż wektora ruchu to „kadłub do przodu”. To jedyna część wielokąta, która może się zderzyć. Krok 3:Rzutuj wektor z każdego punktu na „przedni kadłub” wielokąta wzdłuż wektora ruchu w kierunku przeciwnego wielokąta i sprawdź, czy nie przecina się z każdą krawędzią „przedniego kadłuba” wielokąta. (Prawdopodobnie powoli, ale komputery są obecnie dość szybkie - prawda?) (Przepraszamy za przechyloną strzałkę. Wszystkie strzałki powinny być równoległe.) Krok 4: Weź najkrótszy wektor. Jest to dokładna odległość kolizji. Krok 5: Voila!

Sprawdź to podobne pytanie: Rozwiązanie kolizji

A także z http://www.metanetsoftware.com/technique/tutorialA.html#section5 (do którego zamieściłeś link :))

SEKCJA 5: Szybko poruszające się obiekty

Jak wspomniano powyżej, małe i / lub szybko poruszające się obiekty mogą powodować problemy podczas korzystania ze statycznego testu zderzenia. Istnieje kilka metod postępowania z takimi obiektami - najprostszym jest ograniczenie projektu gry, aby takie obiekty nie były potrzebne.

Jeśli absolutnie musisz je mieć, istnieją dwie typowe metody radzenia sobie z małymi i / lub szybko poruszającymi się obiektami: testy zderzeniowe i multisampling.

- = testy wobulacji = -

Zamiast testować przecięcie dwóch statycznych kształtów, możemy zamiast tego tworzyć nowe kształty, przesuwając oryginalne kształty wzdłuż ich trajektorii i sprawdzając, czy te kształty się pokrywają.

Podstawowa idea została opisana w [Gomez], dla testów koła i koła AABB-AABB.

- = multisampling = -

Znacznie prostszą alternatywą dla testów zamiatanych jest wielokrotne próbkowanie; zamiast wykonywania pojedynczego testu statycznego w nowej pozycji obiektu, wykonaj kilka testów w kilku pozycjach położonych między poprzednią a nową pozycją obiektu. Ta technika została wykorzystana do zderzenia ragdoll w N.

Jeśli upewnisz się, że próbki są zawsze rozmieszczone w odległościach mniejszych niż promień obiektu, da to doskonałe wyniki. W naszej realizacji ograniczamy maksymalną liczbę próbek, więc bardzo duże prędkości czasami powodują problemy; jest to coś, co można ulepszyć w zależności od konkretnej aplikacji.

EDYTOWAĆ

Podsumowując i AFAIK, istnieje kilka rozwiązań

1. Ogranicz swoją grę, aby nigdy nie mieć małego i / lub szybko poruszającego się obiektu, który mógłby to spowodować
2. Zaimplementuj system, który zapobiega faktycznym kolizjom, jak opisano w pierwszym linku, który opublikowałem
3. Zwiększ częstotliwość próbkowania dla szybkich i / lub małych ruchomych obiektów
4. ... prawdopodobnie więcej, ale nie jestem ekspertem.

To zależy, czy chcesz tylko ruch liniowy, czy też musisz poradzić sobie z ruchem kątowym.

Alternatywa dla używania SAT:

Tylko w przypadku liniowości można rzutować promieniowo na Różnicę Minkowskiego dwóch wielokątów od początku w kierunku delta prędkości liniowej obiektów.

Jeśli promień trafi w MD, dwa obiekty zderzą się, a punkt trafienia pokaże Ci czas, w którym zderzyły się.

Teraz, jeśli obiekty się poruszają i obracają , staje się to trudniejsze, ale nadal możesz użyć podobnej techniki. Postępowanie zachowawcze pozwoli ci zająć się tą sprawą. Ta technika jest iteracyjna; każda iteracja wygeneruje nową MD i zbliży Cię do czasu skrzyżowania.

Oto oryginalny dokument w sprawie postępów konserwatywnych:

http://www.continuousphysics.com/BulletContinuousCollisionDetection.pdf

Napisałem tutaj artykuł szczegółowo wyjaśniający tę technikę:

http://www.wildbunny.co.uk/blog/2011/04/20/collision-detection-for-dummies/

Mam nadzieję, że te pomoc!