web analytics

«

»

Game’s Anatomy: Kolizje, Ciała, Jointy i Moce

Zapraszam na pierwszy wykład z anatomii gier komputerowych. Przyznam, że chciałem zacząć ten cykl tekstem o oświetleniu, jednak to zbyt szeroki temat. Zostawię go więc na nasze następne spotkanie i prawdopodobnie rozbiję na kilka części, żeby Was nie zanudzić i nie zamęczyć. No i żeby nie sprawdzać na razie gdzie leży granica długości pojedynczego tekstu w WordPressie. W każdym razie dzisiaj rozgrzewka, czyli wszystko co chcieliście wiedzieć o detekcji kolizji i fizyce w grach, ale baliście się zapytać. Chcecie wiedzieć dlaczego przedmioty czasem przelatują przez ściany albo zaczynają skakać i kręcić się coraz szybciej? No to czytajcie dalej.

Detekcja kolizji

Czym jest detekcja kolizji chyba nikomu tłumaczyć nie trzeba, ale dla porządku napiszę tę oczywistą oczywistość. To zestaw mechanizmów, dzięki którym postacie i przedmioty w grach stoją na ziemi i zatrzymują na ścianach, zamiast przenikać przez wszystko jak neutrina. A dokładniej mówiąc, detekcja kolizji to wykrywanie kiedy zaczynają to robić. Jak to właściwie działa?

Trochę inaczej niż w rzeczywistości – przynajmniej zakładając, że rzeczywistość (przestrzeń) jest ciągła, co wedle najnowszych teorii fizycznych może wcale nie być prawdą. Tym niemniej, taka z pewnością wydaje się nam na co dzień. W każdym razie, kiedy upuszczamy piłkę, to zatrzymuje się ona na podłodze. Odkształca się, a w bardzo nieznacznym stopniu również podłogę, ale nie wnika w nią ani trochę i ani na moment. W komputerze wygląda to trochę inaczej ze względu na obecność klatek.

Załóżmy, że mamy wspomnianą wcześniej piłkę i podłogę, ale tym razem w symulacji komputerowej. Piłka porusza się (przy użyciu fizyki lub bez niej, to nie ma w tej chwili większego znaczenia) w dół, nieuchronnie zmierzając w stronę podłogi. W każdej kolejnej klatce animacji, system detekcji kolizji (zwanej też coldet albo CD) sprawdza w jakiej odległości piłka znajduje się od powierzchni podłogi. Jeśli ta odległość jest mniejsza niż promień piłki, to znaczy, że piłka znalazła się “wewnątrz” podłogi — przecina się z jej powierzchnią, lub nawet jest dosłownie w jej środku. Tak być z pewnością nie powinno, więc system powiadamia o tym fakcie programistę.

Programista może z tym fantem zrobić dwie rzeczy. W dzisiejszych czasach na ogół podpina pod detekcję kolizji silnik fizyki (najczęściej jest odwrotnie, silnik fizyki ma wbudowany system CD) i, jak mówią słowa piosenki, “ma wszystko w tyle” (czasem nawet trochę za bardzo). Bywa jednak tak, że zachodzi potrzeba “obsłużenia się” samemu. Oto jak wygląda samoobsługowe rozwiązywanie problemu wnikania jednej rzeczy w drugą.

Wspomniany programista nie chce lub nie może skorzystać z fizyki, więc pisze tzw. callback, do którego CD wypluwa informacje dotyczące kolizji. Znajdują się tam przede wszystkim informacje o tym, które dwa (zawsze obsługuje się dwa, nie więcej, na raz) obiekty ze sobą kolidują, a dodatkowo m.in. na jaką głębokość w siebie wniknęły, w którym kierunku i który z nich jest ruchomy, a który statyczny. Korzystając z tych informacji programista wie, że aby “wystawić” jeden obiekt z przestrzeni drugiego musi przesunąć go (w  naszym wypadku piłkę. Głupio byłoby przesuwać podłogę…) o “głębokość penetracji” w kierunku wskazanym przez podany wektor jednostkowy. I to jest cała filozofia.

Najtrudniejszą część roboty odwala sama detekcja, a nie obsługa, kolizji. Przykład z piłką (kula) i podłogą (płaszczyzna) jest o tyle prosty, że sprawdzenie, czy te dwa obiekty ze sobą kolidują ogranicza się do obliczenia odległości środka kuli od płaszczyzny i porównania wyniku z promieniem rzeczonej kuli. Proste i szybkie, jednak detekcja kolizji nie może ograniczać się do tak prostych kształtów. Dlatego najczęściej mamy do dyspozycji również inne bryły, jak równoległobok (zwykle nazywany po prostu “box”), stożek, kapsuła (wygląda jak tabletka Apapu) itd. Tu już robi się trochę trudniej i wolniej, bo sprawdzenie, czy obrócony w trójwymiarze stożek przypadkiem nie wsiąka w obrócony w trójwymiarze sześcian wymaga nieco więcej, nieco bardziej skomplikowanych obliczeń.

Dodatkowo, każdy system CD umożliwia skorzystanie z tzw. mesha, czyli zwykłego modelu 3D. Ale oczywiście za dobrze by było, gdyby dało się po prostu wziąć model, np. samochodu, i użyć go do detekcji kolizji. W prototypie taka prowizorka często sprawdza się znakomicie, ale w grze z masą złożonych obiektów bardzo szybko zjadłaby całą moc obliczeniową procesora. Rozwiązaniem jest stworzenie przybliżenia, czyli uproszczonej wersji modelu. Niezależnie jednak od tego, mesh to najbardziej “procesorożerny” rodzaj “kształtki”, więc raczej się go unika, zwłaszcza w przypadku obiektów dynamicznych. Najczęściej można je przybliżyć łącząc ze sobą kilka wspomnianych wcześniej brył podstawowych.

Mesh nie może też być animowany, czyli zmieniać swojego kształtu, więc detekcja kolizji postaci wygląda zwykle następująco. Do kończyn, głowy i tułowia przyczepia się kapsuły, które pozwalają sprawdzać w jaką część ciała trafił pocisk. Całą postać natomiast otacza się jedną wielką kapsułą, która odpowiada za detekcję kolizji ze ścianami. Dodatkowo, owa kapsuła “lewituje” kilkanaście centymetrów nad ziemią, a od spodu przyczepiony jest do niej promień (kolejna “kształtka”, będąca prostą lub odcinkiem, często używana też do strzelania z broni palnej, czarów, laserowych czujników itp.), utrzymujący określoną wysokość lewitacji, co umożliwia postaci… chodzenie po schodach.

Jak więc widzicie, zbudowanie systemu detekcji kolizji, który obsługiwałby tylko piłki i podłogi nie należy do specjalnie trudnych zadań, ale z każdym kolejnym obiektem ta złożoność bardzo szybko rośnie.

Tunelowanie

W poprzednim rozdziale napisałem, że system sprawdza kolizje w klatkach. Być może niektórym z Was podsunęło to myśl, co będzie, jeśli obiekt będzie poruszał się bardzo szybko, jak na przykład pocisk? W jednej klatce znajdzie się po jednej stronie ściany, a w drugiej będzie już za nią. Czy to oznacza, że system nie zarejestruje spotkania ze ścianą? Odpowiedź brzmi: tak.

Animacja w komputerze polega na “teleportowaniu” obiektów z jednego położenia w drugie. Nie ma stanów pośrednich ponieważ, patrząc z punktu widzenia świata gry, pomiędzy jedną a drugą klatką czas nie istnieje. Jeśli w klatce A piłka jest tu, a w klatce B tam, to jeśli między położeniem A i B jest ściana, o którą piłka w żadnej z tych klatek nie zahacza, to poleci ona dalej i nigdy nie dowie się o ścianie.

Jak to zwykle bywa, rozwiązania tego problemu są dwa. W symulacjach fizycznych zwykle korzysta się z tej bardziej dokładnej, ale i bardziej wymagającej od strony mocy obliczeniowej, tzn. zmniejsza się “długość” klatki. Systemowi można powiedzieć, że detekcja kolizji ma być wykonywana, na przykład, 200, 500 czy 1000 razy na sekundę. W takiej symulacji zwykle wiadomo jaka musi być wartość, żeby zapewnić wystarczającą stabilność systemu, ponieważ zna się prędkość oraz inne parametry obiektów. Problem w tym, że symulacji nie da się odpalać 1000 razy na sekundę rzeczywistego czasu — można jej tylko wmówić, że jest odpalana tak często, a faktycznie odpalać ją, powiedzmy, 30 razy na sekundę. Jak pewnie rozumiecie, to oznacza, że na ekranie wszystko będzie się dziać baaaardzo powoli, a co za tym idzie, takie rozwiązanie do gier się zwyczajnie nie nadaje.

Z tego też powodu wymyślono metodę, która umożliwia z jednej strony uniknięcie tzw. “tunelowania” (nazwanego tak od tunelowania kwantowego, czyli teoretycznej możliwości, że za chwilę zatopisz się w fotel), a z drugiej nadal umożliwia przeprowadzanie “symulacji” w czasie rzeczywistym. Tym rozwiązaniem jest ciągła detekcja kolizji (ang. continuous collision detection, ccd), w odróżnieniu od dyskretnej detekcji kolizji, którą opisywałem do tej pory.

Ciągła detekcja kolizji to wynalazek prosty i elegancki, choć może się wydawać odrobinę siermiężny. Skoro problem bierze się stąd, że obiekt jest w pozycji z klatki A i w pozycji z klatki B, a pomiędzy nimi go nigdy nie ma, to po prostu go tam wsadźmy. I jak pomyśleli tak zrobili – CCD, współpracując z np. silnikiem fizyki, “przewiduje” pozycję obiektu w następnej klatce i tworzy obiekty pomocnicze (niezależnie od kształtu obiektu bazowego najczęściej są to kule, ponieważ są najszybsze) między A i B. Powstaje nieprzerwany łańcuch łączący te dwa położenia, a każda penetracja wykryta na łańcuchu jest uznawana za kolizję naszego głównego obiektu.

Proste, trochę toporne i nie zawsze w 100% dokładne, ale sprawdza się znakomicie, przynajmniej jeśli programiści zadbają o odpowiednie wyregulowanie systemu.

Fizyka

Detekcję kolizji mamy za sobą, więc pogadajmy o fizyce. Wcześniej napisałem, że programista może sam obsłużyć wynik detekcji kolizji, albo wziąć sobie do tego wyrobnika pod postacią silnika fizyki. Rzecz w tym, że opisane wcześniej teleportowanie obiektu o dany wektor pomnożony przez głębokość przenikania może i brzmi matematycznie, ale z fizyką, czy, mówiąc dokładniej, z udawaniem fizyki, jakoś nie ma wiele wspólnego. W taki sposób otrzymamy najprostsze zachowanie, które jest odpowiednie np. dla postaci idącej w stronę ściany, ale ładnie odbijającej się piłeczki (czy granatu… wszyscy lubimy granaty) w ten sposób raczej nie uzyskamy. Do tego potrzebna jest Moc. A dokładniej siła, ale to przecież po angielsku Force.

Fizyka to wektory opisujące siłę, przyspieszenie, prędkość, opór… więcej nie pamiętam, ale za wszystkie żałuję. Jak to się ma do wypychania naszej piłeczki z podłogi? Ano tak, że zamiast ją teleportować, silnik fizyki przykłada do niej odpowiednią siłę, która pozwala ją wypchnąć poza obręb spenetrowanej podłogi. Oczywiście nadal chodzi tu o teleportowanie piłeczki, bo ona zawsze skacze z klatki na klatkę, ale dzięki zastosowaniu precyzyjnie wyliczonej siły piłeczka nie tylko znajdzie się na powierzchni podłogi, ale również się od niej odbije. Obliczenia, które w tym celu wykonuje silnik, biorą pod uwagę obecną prędkość piłeczki, jej masę, “miękkość” i sprężystość zarówno piłeczki jak i podłogi, różne dodatkowe opory (czasem arbitralnie dodawane przez programistę w celu poprawienia efektu) oraz oczywiście głębokość na jaką piłeczka wbiła się w podłogę. I już. Otrzymujemy piłeczkę odbijającą się od podłogi.

W połączeniu z ciągłą detekcją kolizji, rezultaty pracy silników fizycznych dają nam wielki fun od lat, ale potrafią też zaskoczyć i rozbawić z powodu swojego oderwania od, cóż, fizyki. Dobrym przykładem takiego zabawnego problemu jest filmik z zamrożonym niedźwiedziem w Skyrim. Niestety, podobnie jak detekcja kolizji (i wszystko inne) tak i fizyka w grach to przybliżenie przybliżenia, wypaczone przez uproszczenia. To staje się bardzo widoczne z chwilą, kiedy symulowany system nabiera jakiejkolwiek złożoności, a przy tym musi działać w czasie rzeczywistym. Dla jasności, za “jakąkolwiek złożoność” uznaję w tym przypadku nawet obecność dynamicznie niesymetrycznego ciała (w sensie fizycznym), np. prostopadłościanu, który jest “dłuższy niż szerszy”. Wtedy istnieją dwie możliwości, w zależności od zastosowanego solvera (czyli kodu, który oblicza fizykę). Opcja A jest taka, że obiekt będzie się odbijał i kręcił za mało, opcja B — za dużo. Opcji C, idealnej, nie ma, przynajmniej jeżeli chcemy zachować czas rzeczywisty. A chcemy, bo mówimy o grach.

To nie znaczy, że jesteśmy w sytuacji bez wyjścia – oddzieliłem wyraźnie fizykę od detekcji kolizji celowo, żebyście w głowie odłączyli sobie wygląd obiektu od jego reprezentacji w detekcji kolizji, i tą ostatnią od jego fizycznych właściwości. Inaczej mówiąc, możemy mieć obiekt, który z punktu widzenia gracza (wizualnie) będzie niedźwiedziem, z punktu widzenia CD będzie podłużnym prostopadłościanem, a dla fizyki będzie wyglądał jak kula. Mówiłem, uproszczenia na uproszczeniach. Biorąc pod uwagę, że fizyka w grach nie jest, nie była i w najbliższej przyszłości nie będzie rzeczywiście dokładna, to nie robi żadnej różnicy w osiąganym efekcie wizualnym, a rozwiązuje problem niestabilności. Szkoda, że programiści z Bethesdy nie wzięli sobie tego do serca, ale z drugiej strony… pozbawiliby nas widoku skaczącej, niedźwiedziej mrożonki, więc chyba nie mam im tego za złe.

Joints

A teraz będzie o stawach. Nie takich z wodą, tylko takich w kolanie albo w łokciu. Można je też nazwać zawiasami, jeśli komuś tak wygodniej. Ewentualnie “jointami”, ale to chyba niepoprawne politycznie. W niektórych silnikach fizyki określa się je mianem “ograniczeń” (ang. “constraint”), co jest chyba najbardziej trafną nazwą.

Po co stawy? Np. żeby przyczepić drzwi do framugi, ręce ragdolla do tułowia albo koło do samochodu. Przeanalizujmy ostatni przykład. Wiecie jak wygląda zawieszenie w samochodzie, prawda? To dość skomplikowany zestaw części, który musi taki być dlatego, że nie da się przeprowadzić amortyzatora przez koło. Trzeba obok, nie ma bata. Trzeba? Nie w silniku fizyki!

W silniku fizyki bowiem staw to nie obiekt posiadający materialną (nawet rozumianą tylko w kategoriach detekcji kolizji) formę, ale jedynie matematycznie zapisana zależność ograniczająca tzw. stopnie swobody, czyli mówiąca obiektom, że mogą się poruszać tylko tak, a nie inaczej. Podobnie, nawiasem mówiąc, jest również z samymi ciałami fizycznymi – to punktowe, matematyczne obiekty, których przenikanie się nie jest nigdzie rejestrowane (od tego jest detekcja kolizji, która ma swoje bryły). Biorąc to wszystko pod uwagę, w grze można zbudować zawieszenie samochodu z koła przyczepionego do stawu definiującego oś obrotu i ruchu góra-dół, który przyczepiamy z drugiej strony do samochodu. Nie potrzeba nic więcej, dlatego w starszych grach koła po prostu lewitowały pod samochodem, co sprawiało dziwne wrażenie przede wszystkim na rajdowych hopkach.

Stawy też mają swój udział w dziwnych zachowaniach symulacji fizycznych w grach. Problem, ponownie, wynika z konieczności zachowania czasu rzeczywistego, czyli kompromisu między dokładnością a szybkością (no i z floatów). W rezultacie każdy joint ma pewne odchylenia, które sprawiają, że może bez wyraźnej przyczyny eksplodować, wysyłając przyczepione obiekty w przestrzeń z gigantyczną prędkością (tak liniową, jak i kątową), lub implodować, ściskając je ze sobą albo blokując na amen.

Soft body

To, co opisywałem do tej pory w materii fizyki to tzw. ciała sztywne (rigid body). To znaczy takie, które nie odkształcają się w żaden sposób, a więc nie istnieją w rzeczywistości. Jest to chyba największe przybliżenie i przekłamanie w całej growej fizyce, ale sprawdza się bardzo dobrze. Nie pozwala jednak na symulację tkanin czy deformowalnych obiektów 3D. Do tego potrzebne są soft bodies, czyli ciała miękkie.

Soft bodies dzielą się zasadniczo na dwie podgrupy. Najczęściej w grach spotykamy się z symulacją tkanin, czyli obiektów dwuwymiarowych. Choć wymagają one sporej mocy obliczeniowej, w zasadzie łączą po prostu to, co omówiliśmy do tej pory. Bierze się siatkę – wycinek płaszczyzny podzielony na dużo trójkątów – o jakiejś tam gęstości i w miejscach wierzchołków tych trójkątów wstawia się ciała fizyczne (jak pamiętacie, to po prostu punktowe obiekty). Sąsiadujące ze sobą ciała łączy się sprężynami (jointami o określonych parametrach) co sprawia, że poruszają się tylko w ograniczonym stopniu względem siebie. Jeśli któreś z ograniczeń zostanie naruszone o wystarczająco dużą wartość, to zostaje usunięte i otrzymujemy rozprucie w tkaninie.

Dla ścisłości muszę powiedzieć, że to, co napisałem w poprzednim akapicie jest prawdą tylko do połowy. W taki sposób (korzystając de facto z dynamiki ciał sztywnych) da się zbudować dynamikę ciał miękkich, ale zwykle się tego nie robi. Choć już samo to byłoby sporym uproszczeniem, to jednak upraszcza się to jeszcze bardziej, sprowadzając całą siatkę do zestawu rozwiązywanych jedno po drugim równań, biorących pod uwagę głównie pozycje węzłów (a pomijających wiele innych parametrów, które posiadają ciała stałe). Wszystko oczywiście po to, żeby utrzymać wydajność.

To by chyba było na tyle w tym wydaniu naszego nowego cyklu. Następnym razem porozmawiamy sobie prawdopodobnie o oświetleniu, chyba, że macie jakieś inne życzenia. W planach jest jeszcze chociażby (bardzo) sztuczna inteligencja w grach, a potem to zobaczymy.

PS. Dajcie znać w komentarzach, czy taka forma tekstów Wam odpowiada — czy wolelibyście więcej szczegółów (może trochę matematyki?), czy może mam się jeszcze bardziej hamować w tej materii?

  • polo_tuc

    Świetny tekst. I świetny pomysł żeby ilustrować to filmikami z gier. Jak dla mnie możesz wrzucac takie artykuły do samej emerytury.

    Może zrobimy listy do reda… coppera: każdy wrzuci dwój ciekawy filmik z glitch’em a copper będzie móżdżył.
    Kto ma coś fajnego?

  • Kaplus

    Obecna forma bardzo fajna. Tekst jest zrozumiały i jednocześnie nie jest pisany zbyt ogólnikowo, więc można się czegoś nauczyć nie umierając z nudów po drodze.

    Ja jestem jak najbardziej za oświetleniem w następnej części i niech nikt nie próbuje na to wpłynąć.

  • ash_22

    Zbytnia akademickość mogłaby odstraszyć czytelników, informacji i tak jest dużo. Czekam na kolejną część.

  • kornick

    Fajny tekst. Forma w sam raz!

  • polo_tuc

    Doktorze Coppertop, czekamy na kolejną publikację! PubMed odnotuje!

    • Coppertop

      Przepraszam bardzo za opóźnienia, ale tak się akurat złożyło, że ostatnio mam strasznie mało czasu i niestety nie wystarcza go na pisanie (zwłaszcza, że taki tekst wymaga trochę więcej czasu niż inne). Głównie jest to związane z nową pracą. Mam nadzieję, że niedługo tego czasu będzie trochę więcej.

      Dzięki za komentarz — nic tak nie motywuje jak świadomość, że ktoś czeka :).