Pracuję nad czysto ciągłym silnikiem fizyki i muszę wybrać algorytmy wykrywania kolizji w fazie szerokiej i wąskiej. „Czysto ciągły” oznacza, że ​​nigdy nie przeprowadzam testów przecięcia, ale zamiast tego chcę znaleźć sposoby na złapanie każdej kolizji, zanim to nastąpi, i umieszczenie każdej z nich w stosie „planowanych kolizji”, zamówionym przez TOI.

Faza szeroka Jedyną ciągłą metodą fazy szerokiej, jaką mogę wymyślić, jest zamknięcie każdego ciała w kręgu i sprawdzenie, czy każde koło kiedykolwiek zachodzi na inne. Wydaje się to jednak okropnie nieefektywne i pozbawione jakiegokolwiek uboju.

Nie mam pojęcia, jakie ciągłe analogi mogą istnieć w dzisiejszych dyskretnych metodach eliminowania kolizji, takich jak drzewa quad. Jak mogę zapobiegać niewłaściwym i bezcelowym szerokim testom, takim jak dyskretny silnik? Chciałbym także widzieć kolizje więcej niż o 1 klatkę przed nimi.

Wąska faza
Udało mi się dostosować wąski SAT do ciągłego sprawdzania, a nie dyskretnego, ale jestem pewien, że istnieją inne lepsze algorytmy w dokumentach lub witrynach, z którymi mogliście się spotkać.
Jakich różnych szybkich lub dokładnych algorytmów sugerujesz użyć i jakie są zalety / wady każdego z nich?

Uwaga końcowa:
mówię techniki, a nie algorytmy, ponieważ jeszcze nie zdecydowałem, w jaki sposób będę przechowywać różne wielokąty, które mogą być wklęsłe, wypukłe, okrągłe, a nawet mieć dziury. Planuję podjąć decyzję w oparciu o to, czego wymaga algorytm (na przykład, jeśli wybiorę algorytm, który rozkłada wielokąt na trójkąty lub wypukłe kształty, po prostu zapiszę dane wielokąta w tej formie).

Naprawdę po prostu rzucam tutaj pomysły. Zakładając, że masz (przynajmniej) currentpozycję i nextpozycję; dla każdej ramki.

Potrzebne byłyby dwie oddzielne szerokie fazy, a następnie wąska faza:

• Taki, z którego wynika, że ​​nastąpi kolizja.
• Taki, który z grubsza określa, gdzie faktycznie dochodzi do kolizji (np. Faza szeroka / niedokładna SAT)
• Wreszcie twoja wąska faza poprawiłaby wynik drugiej szerokiej fazy.

Początkowa faza szeroka

Możesz spojrzeć na haszowanie przestrzenne (używając nextpozycji, nie current) dla początkowej szerokiej fazy. W ten sposób ładnie podzielisz przestrzeń problemową na grupy kandydatów na kolizję.

Druga faza szeroka

Wykonaj binarną próbkę wielokrotną, używając opisanej metody przecięcia okręgu. Innymi słowy:

left = current
right = next
midpoint = (left + right) / 2
loop a desired amount of times tweaked to the accuracy you want:
  is a collision occuring at midpoint?
    right = midpoint
  else?
    left = midpoint
  midpoint = (left + right) / 2
pointOfCollision = midpoint

Ta poprawka dokładności może również brać pod uwagę odległość - myślę, że użycie „długości do kwadratu” next - currentdałoby wynik w pikselach.

Wąska faza

Wykonaj binarną próbkę wielokrotną, używając czegoś takiego jak PMask - logika będzie dokładnie taka sama jak powyżej; po prostu używając innej procedury kolizji.

Wreszcie

Będziesz w stanie wypracować time-of-skrzyżowania z pointOfCollision, currenta prąd speedi acceleration(zakładając, że masz wystarczającą integrator).

Dobra, widziałem, że zaktualizowałeś swoje pytanie, aby było bardziej szczegółowe. Spróbuję ci jeszcze pomóc.

W przypadku pierwszej kontroli w fazie szerokiej zdecydowanie polecam haszowanie przestrzenne .

Zasadniczo dzielisz ekran na siatki o równej wielkości. Następnie, jeśli obiekt leży w siatce, dodajesz go do „segmentu” w tabeli skrótów 1D.

To twoja pierwsza kontrola. Jeśli obiekty nie znajdują się w tym samym wiadrze, niemożliwe byłoby ich przecięcie.

Kontynuując, masz teraz listę wiader z obiektami (potencjalnie) w nich. Możesz tutaj wykonać kolejną kontrolę fazy:

A.) Podzielenie tego segmentu na 4 inne segmenty i sprawdzenie wynikowej tabeli skrótów 1D. Jeśli nie są w tym samym wiadrze, nie ma kolizji.

Lub:

B.) Przeprowadzenie prostej kontroli odległości i pamiętanie o szerokości i / lub wysokości obiektu w celu zapewnienia dokładności.

Ale co, kiedy potencjalnie masz kolizję?

Następnie poleciłbym coś podobnego do tego . Zasadniczo jest to mieszanka zderzenia wielokąta (dla skomplikowanych kształtów) lub prostokąta / okręgu dla mniej skomplikowanych kształtów.

Ponadto, jeśli naprawdę chcesz „złapać kolizje, zanim one się zdarzą, i je zapisać”, zawsze możesz zrobić coś takiego:

Jeśli dwa obiekty znajdują się w tym samym wiadrze, mogą się zderzyć.

Ponadto, czy obiekty są wystarczająco blisko, aby wkrótce mogły się zderzyć? (Biorąc pod uwagę prędkość, rozmiar i odległość obiektu)

Jeśli odpowiedź na oba pytania brzmi „tak”, zapisz ją i wykonaj test skrzyżowania później.

„ Stara odpowiedź

Cóż, niestety straciłem orientację w moim podręczniku „Wszystkie typy kolizji i do czego służą”. :)

Jednak pomimo tego, że jest to bardzo szeroki queston, zacznę od ciebie.

Jest to dobry (odpowiedzi) pytanie odnoszące się do czegoś takiego tutaj .

Jak również artykule ludzi, którzy dokonali N i N + ponad tutaj .

Nie wspominając, że masz dobrą rezerwę na kolizję na piksel .

Szczerze wątpię, aby ktokolwiek miał pod ręką listę każdego rodzaju kolizji, ale to powinno pomóc ci zacząć.

Powinienem jednak wspomnieć, że rodzaj kolizji, którego potrzebujesz (i w końcu z niej skorzystasz), w dużej mierze zależy od rodzaju tworzonej gry. Dlatego znajdziesz tutoriale - większość ludzi zakłada, że ​​masz pojęcie o tym, czego chcesz, więc pomagają ci w tym konkretnym obszarze. Zdaję sobie sprawę, że większość moich linków to tutoriale na określony temat, ale myślę, że tutorial szczerze ci pomoże. Lista to jedna rzecz, ale jeśli sam przeczytasz o każdym punkcie kuli, możesz podjąć bardziej wykształconą decyzję, która najprawdopodobniej będzie bardziej odpowiadać Twoim potrzebom.