Jak działa silnik kolizji?

Jak dokładnie działa silnik kolizji ?

To jest bardzo szerokie pytanie. Jaki kod sprawia, że ​​rzeczy odbijają się od siebie, jaki kod powoduje, że gracz wchodzi do ściany zamiast przechodzić przez nią? W jaki sposób kod stale odświeża pozycję graczy i pozycję obiektów, aby grawitacja i kolizja działały tak, jak powinny?

Jeśli nie wiesz, co to jest silnik kolizji, zasadniczo jest on ogólnie używany w grach platformowych, aby gracz uderzył w ścianę i tym podobne. Istnieje typ 2D i typ 3D, ale wszystkie osiągają to samo: kolizję.

Co więc powoduje, że silnik kolizji tyka?

Istnieje duża różnica między silnikiem zderzenia a silnikiem fizyki. Nie robią tego samego, chociaż silnik fizyki zasadniczo opiera się na silniku zderzenia.

Silnik kolizji jest następnie dzielony na dwie części: wykrywanie kolizji i reakcja na kolizję. Ten ostatni jest zasadniczo częścią silnika fizyki. Właśnie dlatego silniki kolizji i silniki fizyki są zwykle wtaczane do tej samej biblioteki.

Detekcja kolizji występuje w dwóch postaciach, dyskretnej i ciągłej. Zaawansowane silniki obsługują oba, ponieważ mają różne właściwości. Ogólnie rzecz biorąc, ciągłe wykrywanie kolizji jest bardzo drogie i stosowane tylko tam, gdzie jest naprawdę potrzebne. Większość zderzeń i fizyki jest obsługiwana przy użyciu dyskretnych metod. W dyskretnych metodach obiekty będą się wzajemnie przenikać, a następnie silnik fizyki będzie je rozdzielał. Tak więc silnik tak naprawdę nie powstrzymuje gracza przed przejściem częściowo przez ścianę lub podłogę, po prostu naprawia go po wykryciu, że gracz jest częściowo w ścianie / podłodze. Skoncentruję się tutaj na dyskretnym wykrywaniu kolizji, ponieważ właśnie to mam największe doświadczenie w implementacji od zera.

Wykrywanie kolizji

Wykrywanie kolizji jest stosunkowo łatwe. Każdy obiekt ma transformację i kształt (prawdopodobnie wiele kształtów). Naiwne podejścia sprawiłyby, że silnik kolizji wykonałby pętlę O (n ^ 2) przez wszystkie pary obiektów i sprawdziłby, czy pary nie zachodzą na siebie. W bardziej inteligentnych podejściach istnieje wiele struktur danych przestrzennych (np. Dla obiektów statycznych vs. dynamicznych), obwiednia kształtu dla każdego obiektu i wieloczęściowe wypukłe kształty podrzędne dla każdego obiektu.

Struktury danych przestrzennych obejmują takie rzeczy, jak drzewa KD, drzewa dynamicznego AABB, drzewa ósemkowe / czwórkowe, drzewa partycjonowania przestrzeni binarnej i tak dalej. Każdy ma swoje zalety i wady, dlatego niektóre silniki wyższej klasy wykorzystują więcej niż jeden. Na przykład dynamiczne drzewa AABB są naprawdę bardzo szybkie i dobre do obsługi wielu ruchomych obiektów, podczas gdy drzewo KD może być bardziej odpowiednie dla geometrii poziomu statycznego, z którą zderzają się obiekty. Istnieją również inne opcje.

Faza szeroka wykorzystuje struktury danych przestrzennych i abstrakcyjną objętość ograniczającą dla każdego obiektu. Obwiednia jest prostym kształtem, który otacza cały obiekt, ogólnie w celu zamknięcia go możliwie „ciasno”, pozostając jednocześnie tanim w testach kolizji. Najczęstsze kształty obwiedni to wyrównane do osi pola ograniczające, wyrównane względem obiektu pola ograniczające, kule i kapsułki. AABB są ogólnie uważane za najszybsze i najłatwiejsze (Kule są łatwiejsze i szybsze w niektórych przypadkach, ale wiele z tych struktur danych przestrzennych wymagałoby i tak zamiany kuli w AABB), ale mają również tendencję do niedopasowania wielu obiektów. Kapsułki są popularne w silnikach 3D do obsługi kolizji na poziomie postaci. Niektóre silniki będą używać dwóch ograniczających kształtów,

Ostatnim etapem wykrywania kolizji jest dokładne wykrycie przecięcia geometrii. Zwykle oznacza to użycie siatki (lub wielokąta w 2D), choć nie zawsze. Celem tej fazy jest ustalenie, czy obiekty naprawdę kolidują ze sobą, czy wymagany jest wysoki poziom szczegółowości (powiedzmy, kolizja kulowa w strzelance, w której chcesz ignorować strzały, które ledwo brakuje), oraz aby dowiedzieć się dokładnie, gdzie zderzają się obiekty, co wpłynie na ich reakcję. Na przykład, jeśli pudełko stoi na krawędzi stołu, silnik musi wiedzieć, w których punktach stół naciska na pudełko; w zależności od tego, jak daleko pudełko zwisa, pudełko może zacząć się przechylać i spadać.

Skontaktuj się z Generacją kolektora

Stosowane tutaj algorytmy obejmują popularne algorytmy udoskonalania portalu GJK i Minkowskiego, a także test Osi oddzielającej. Ponieważ popularne algorytmy zwykle działają tylko w przypadku wypukłych kształtów, konieczne jest rozbicie wielu złożonych obiektów na wypukłe podobiekty i wykonanie testów kolizji dla każdego z osobna. Jest to jeden z powodów, dla których uproszczone siatki są często używane do kolizji, a także skrócenie czasu przetwarzania przy użyciu mniejszej liczby trójkątów.

Niektóre z tych algorytmów nie tylko mówią, że obiekty na pewno zderzyły się, ale także tam, gdzie zderzyły się - jak daleko się przenikają i jakie są „punkty kontaktowe”. Niektóre algorytmy wymagają dodatkowych kroków, takich jak obcinanie wielokątów, aby uzyskać te informacje.

Reakcja fizyczna

W tym momencie odkryto kontakt, a silnik fizyki ma wystarczającą ilość informacji, aby go przetworzyć. Obsługa fizyki może być bardzo złożona. Prostsze algorytmy działają w niektórych grach, ale nawet coś tak pozornie prostego, jak utrzymywanie stabilnego stosu pudeł, okazuje się dość trudne i wymaga dużo pracy i nieoczywistych włamań.

Na najbardziej podstawowym poziomie silnik fizyki zrobi coś takiego: weźmie zderzające się obiekty i ich kolektory kontaktowe i obliczy nowe pozycje wymagane do oddzielenia zderzonych obiektów. Przenosi obiekty do tych nowych pozycji. Obliczy również zmianę prędkości wynikającą z tego pchnięcia, w połączeniu z restytucją (sprężystością) i wartościami tarcia. Silnik fizyki zastosuje również wszelkie inne siły działające na obiekty, takie jak grawitacja, w celu obliczenia nowych prędkości obiektów, a następnie (następnej klatki) ich nowych pozycji.

Bardziej zaawansowana reakcja fizyczna szybko się komplikuje. Powyższe podejście ulegnie awarii w wielu sytuacjach, w tym w jednym obiekcie na dwóch innych. Samo radzenie sobie z każdą parą spowoduje „drgania”, a obiekty będą się często odbijać. Najbardziej podstawową techniką jest wykonanie szeregu iteracji z korekcją prędkości na parach zderzających się obiektów. Na przykład, z polem „A” umieszczonym na dwóch innych polach „B” i „C”, kolizja AB zostanie obsłużona jako pierwsza, powodując, że skrzynia A będzie przechylać się dalej do skrzynki C. Następnie kolizja AC jest obsługiwana wieczorem nieco z pól, ale pociągnięcie A w dół i do B. Następnie wykonywana jest kolejna iteracja, więc błąd AB spowodowany przez korekcję AC jest nieco rozwiązany, tworząc nieco więcej błędu w odpowiedzi AC. Jest to obsługiwane przy ponownym przetwarzaniu prądu przemiennego. Liczba wykonanych iteracji nie jest stała i nie ma punktu, w którym stanie się ona „doskonała”, a raczej tylko tyle, ile iteracji przestanie dawać znaczące wyniki. 10 iteracji to typowa pierwsza próba, ale poprawienie wymaga znalezienia najlepszej liczby dla konkretnego silnika i potrzeb konkretnej gry.

Kontakt z buforowaniem

Istnieją inne sztuczki, które okazują się bardzo przydatne (mniej lub bardziej konieczne) w przypadku wielu rodzajów gier. Buforowanie kontaktów jest jednym z bardziej przydatnych. Dzięki pamięci podręcznej kontaktów każdy zestaw kolidujących obiektów jest zapisywany w tabeli odnośników. Każda ramka po wykryciu kolizji jest sprawdzana w tej pamięci podręcznej, aby sprawdzić, czy obiekty były wcześniej w kontakcie. Jeśli obiekty nie były wcześniej w kontakcie, można wygenerować zdarzenie „nowej kolizji”. Jeśli obiekty były wcześniej w kontakcie, informacje można wykorzystać do zapewnienia bardziej stabilnej odpowiedzi. Wszelkie wpisy w pamięci podręcznej kontaktów, które nie zostały zaktualizowane w ramce, wskazują na dwa obiekty, które się oddzieliły i można wygenerować zdarzenie „obiekt oddzielający”. Logika gry ma często zastosowanie w tych zdarzeniach.

Logika gry może także reagować na nowe zdarzenia kolizji i oznaczać je jako ignorowane. Jest to bardzo pomocne w przypadku implementacji niektórych funkcji typowych dla platform, takich jak platformy, na które można przeskoczyć, ale stać. Naiwne implementacje mogą po prostu ignorować kolizje, które mają normalną kolizję w dół -> kolizja postaci normalna (wskazując, że głowa gracza uderza w dolną część platformy), ale bez buforowania kontaktowego, to pęknie, jeśli głowa gracza podniesie się przez platformę, a następnie zacznie upaść. W tym momencie normalny kontakt może skończyć skierowaniem do góry, co spowoduje, że gracz wyskoczy przez platformę, kiedy nie powinien. Dzięki buforowaniu kontaktów silnik może niezawodnie patrzeć na początkową kolizję normalnie i ignorować wszystkie dalsze zdarzenia kontaktu, dopóki platforma i odtwarzacz nie rozdzieli się ponownie.

Spanie

Inną bardzo przydatną techniką jest oznaczanie obiektów jako „uśpionych”, jeśli nie są one obsługiwane. Śpiące przedmioty nie otrzymują aktualizacji fizyki, nie zderzają się z innymi śpiącymi przedmiotami i po prostu siedzą tam zamrożone w czasie, aż zderzy się z nimi inny nieśpiący obiekt.

Skutek jest taki, że wszystkie pary zderzających się obiektów, które tam siedzą i nic nie robią, nie zajmują żadnego czasu przetwarzania. Ponadto, ponieważ nie ma stałej liczby drobnych poprawek fizycznych, stosy będą stabilne.

Obiekt jest kandydatem do spania, gdy ma prawie zerową prędkość dla więcej niż jednej klatki. Zauważ, że epsilon, którego używasz do testowania tej prędkości bliskiej zeru, będzie prawdopodobnie nieco wyższy niż zwykły epsilon porównujący zmiennoprzecinkowy, ponieważ powinieneś spodziewać się pewnych zakłóceń w stosach obiektów i chcesz, aby całe stosy obiektów zasnęły, jeśli „ pozostanie „wystarczająco blisko”, aby uzyskać stabilność. Próg będzie oczywiście wymagał drobnych poprawek i eksperymentów.

Ograniczenia

Ostatnim znaczącym elementem wielu silników fizyki jest narzędzie do rozwiązywania ograniczeń. Celem takiego systemu jest ułatwienie wdrożenia takich rzeczy, jak sprężyny, silniki, oś koła, symulowane ciała miękkie, tkanina, liny i łańcuchy, a czasem nawet płyn (chociaż płyn jest często wdrażany jako zupełnie inny system).

Nawet podstawy rozwiązywania ograniczeń mogą być bardzo intensywne z matematyki i wykraczają poza moje doświadczenie w tej dziedzinie. Polecam przejrzenie doskonałej serii artykułów Randy Gaul na temat fizyki, aby uzyskać bardziej szczegółowe wyjaśnienie tego tematu.

Ogólny problem: ustal, która ze wszystkich możliwych kombinacji obiektów ma niezerową objętość przecięcia.

Naiwne, ogólne podejście jest proste: oblicz każdą objętość przecięcia dla każdej możliwej pary obiektów. Zwykle nie jest to praktyczne, ponieważ wymaga O (n ^ 2) stosunkowo drogich operacji przecięcia.

W związku z tym praktyczne wdrożenia są często wyspecjalizowane, przyjmując pewne założenia pozwalające uniknąć kontroli krzyżowych lub zmniejszyć ich koszty. Partycjonowanie przestrzenne wykorzystuje fakt, że obiekty są zwykle małe w stosunku do całkowitej objętości i zwykle zmniejszają liczbę porównań do O (n log n). Obwiednie wyrównane do osi i kulki ograniczające zapewniają niedrogie zgrubne kontrole przecięcia, o ile obiekty spełniają pewne założenia zwartości. I tak dalej.

Jeden „silnik zderzeniowy”, z którego korzystałem, wydawał się niezwykle łatwy do uchwycenia.

Zasadniczo API dostarczyło rodzaj obiektów posiadających metodę collidesWith, taką jak

1. jego parametrami były różne rodzaje obiektów, które „kwalifikowały się” do kolizji
2. zwrócił prawdę czy fałsz w zależności od tego, czy doszło do kolizji, czy nie
3. istniała opcja pozwalająca wybrać, czy wszystkie prostokąty ograniczające dla obiektów wyzwalają zdarzenie kolizji, czy tylko nieprzezroczyste piksele w tych prostokątach (wykrywanie poziomu pikseli)

W mojej aplikacji tylko okresowo przywoływałem, collidesWithaby dowiedzieć się, czy doszło do kolizji, czy nie.

Całkiem proste, prawda?

Być może jedyną rzeczą, która wymagała niewielkiego wysiłku wyobraźni, było to, że proste prostokąty ograniczające nie były wystarczające do symulacji geometrii zderzających się obiektów. W takim przypadku wystarczy użyć kilku kolidujących obiektów zamiast jednego.

Zasadniczo, gdy odkryjesz, że prostokąt z pojedynczą kolizją nie robi tego, czego potrzebujesz, wymyślasz sposób rozkładania rzeczy na bardziej prostokątne podelementy, aby po połączeniu te elementy symulowały / przybliżały pożądane zachowanie.

• Użytkownicy końcowi po prostu nie dbają o to, ile obiektów znajduje się za sceną. Są szczęśliwi, dopóki efekt końcowy wydaje się taki, jak się spodziewają, np. Dom z ogrodzeniem od podwórza:

  

Myślę, że jesteś trochę zdezorientowany tym, o czym mówisz i mówisz o kilku różnych rzeczach.

umiejętność stwierdzenia, że ​​przedmiot przenosi się z lokalizacji X do lokalizacji Y, zależy od fizyki (to także atakuje sposób, w jaki się poruszają i dlaczego się poruszają)

metoda wykrywania kolizji jest określana na podstawie struktury gry. jeśli twoja gra jest dużym otwartym światem, powinieneś bardzo rozważyć podział na partycje kosmiczne (quad-tree [oct-tree dla 3D], BSP, tradycyjna siatka lub staroświecki test wszystkiego)

najlepszym sposobem na wdrożenie systemu wykrywania kolizji jest zrobienie tego krokami.

1. umieść wszystkie obiekty w ogólnej ograniczającej objętości / kształcie, a następnie przetestuj je

2. jeśli 1 minął, powtórz z bardziej złożonym powtórzeniem objętości / kształtu, aż będzie gotowy do przetestowania geometrii absolutnej

3. przetestuj geometrię bezwzględną liczbę powtórzeń kroku 2 należy określić na podstawie złożoności twoich kształtów i ich dokładności.

powinieneś uważać każdy z tych kroków za wczesny i mieć na celu wyeliminowanie kolizji w miarę upływu czasu i powracanie do prawdziwości na kroku 3, jeśli naprawdę się dotykają.

Następnie ostatnią częścią jest rozwiązanie kolizji. określa to, co dzieje się po znalezieniu kolizji i udowodniono, że tak naprawdę jest kolizją, i co z tym zrobić. zajmuje się to zwykle fizyką.

tradycyjna pętla wygląda następująco:

receive input
update physics
collision detection
collision resolution
render
repeat

Na poziomie karty graficznej (gdzie zwykle mamy do czynienia z trójkątami), ogólną ideą jest podzielenie sceny w jakiś sposób, abyś nie musiał sprawdzać wszystkich N trójkątów (można to zrobić jako etap wstępnego przetwarzania) ), a następnie dowiedzieć się, gdzie jesteś na scenie, i sprawdź tylko te 10–50 trójkątów w tej partycji.

Aby uzyskać więcej informacji, zobacz drzewa BSP i Kd. Istnieją również inne metody partycjonowania.

Po pierwsze, myślę, że najważniejszym zadaniem silnika kolizyjnego jest ustalenie, co nie musi być sprawdzane pod kątem kolizji w konkretnej sytuacji na podstawie klatka po klatce, i wycofanie tych obiektów z dalszych kontroli.

Po drugie, ale także ważne, sprawdź w bardziej szczegółowy (dokładny) sposób w stosunku do pozostałych obiektów, które nie zostały zabite w pierwszym kroku.

Po trzecie, wykorzystaj najbardziej wydajne / odpowiednie metody do przeprowadzania kontroli.