34

Matematyka w służbie graczom

Całka, wektor, graf. Dla wielu osób słowa te brzmią obrzydliwie, jednakże bez zastosowania matematyki nie byłoby możliwe stworzenie żadnej wartej uwagi gry komputerowej. Przyjrzyjmy się jakie znaczenie ma królowa nauk w rozrywce wirtualnej. Grafika 3D Aby poprawnie i realistycznie wygenerować obraz gry w ułamkach sekund musi zostać wykonany szereg złożonych obliczeń matematycznych. Tym zadaniem zajmuje się silnik graficzny, […]

Całka, wektor, graf. Dla wielu osób słowa te brzmią obrzydliwie, jednakże bez zastosowania matematyki nie byłoby możliwe stworzenie żadnej wartej uwagi gry komputerowej. Przyjrzyjmy się jakie znaczenie ma królowa nauk w rozrywce wirtualnej.

Grafika 3D

Aby poprawnie i realistycznie wygenerować obraz gry w ułamkach sekund musi zostać wykonany szereg złożonych obliczeń matematycznych. Tym zadaniem zajmuje się silnik graficzny, a więc ta część kodu gry, która odpowiada za tworzenie grafiki na ekranie komputera. Oczywiście stworzenie takiego oprogramowania wymaga od jego twórców opanowania co najmniej kilku działów matematyki wyższej, przede wszystkim algebry liniowej, czyli działu matematyki zajmującego się wektorami i macierzami, ale także geometrii, trygonometrii (sinusy, kosinusy, itd.) oraz analizy matematycznej (m.in. zmora wielu studentów kierunków technicznych czyli całka). Programiści muszą też umieć posługiwać się trójwymiarowym układem kartezjańskim.

Oto przykładowy problem – w punkcie (1,2,5) znajduje się środek pudła w kształcie sześcianu o długości krawędzi równej 5 i w kolorze #0000ff. Gracz (czyli de facto kamera) znajduje się w punkcie (10,20,30). Jedyne źródło światła znajduje się w punkcie (100,100,100), ma ono kolor #f0f9b7 i natężenie 3000 lx. W jaki sposób pudło powinno być odwzorowane na ekranie? Pomiń wpływ światła odbitego od otoczenia. Fakt, iż z takim zagadnieniem świetnie sobie silnik radzi świadczy o bardzo dobrej znajomości zasad zachowania się światła i kunszcie matematycznym jego twórców.

Prawa fizyki

Silnik fizyczny jest to część kodu gry, która odpowiada za symulację układów fizycznych. Odpowiada między innymi za realistyczne odzwierciedlenie zachowania brył sztywnych oraz detekcję kolizji. Pięknym wyglądem falującej wody w Assassin’s Creed IV: Black Flag możemy się cieszyć dzięki zastosowaniu równań całkowych i rachunku różniczkowego, a na wygląd każdej fali wpływ ma także rachunek prawdopodobieństwa. Silnik fizyczny określa też z jakim przyspieszeniem spadają obiekty w grze. Aby był zachowany realizm muszą one spadać ruchem jednostajnie przyspieszonym, a przyspieszenie musi być równe grawitacyjnemu na Ziemi, tj. 9,81m/s2. Oczywiście przy założeniu że akcja gry toczy się na naszej planecie.

Duże znaczenie ma matematyka przy symulowaniu zjawisk związanych z kinematyką, czyli ruchem. Jeżeli chodzi o królową nauk, to przy stosunkowo prostych grach takich jak Angry Birds do zaprogramowania ruchu obiektów przeważnie wystarczy wiedza absolwenta liceum o profilu mat-fiz (funkcje kwadratowe, trygonometria, wektory), z drugiej jednak strony konieczna jest bardzo dobra znajomość kinematyki od strony fizycznej.

Gameplay

W rozgrywce matematyka ma zastosowanie o wiele szersze niż sprawdzenie czy można jeszcze umieścić jakiś przedmiot w przepełnionym ekwipunku albo jakie łącznie obrażenia zadaje gracz po zsumowaniu wszystkich bonusów. We wszelkiego rodzaju algorytmach (na przykład sortujących przedmioty w ekwipunku lub sprawdzających czy postać może się wdrapać na stojący przed nią klif) stosuje się kilka działów matematyki dyskretnej, tj. logika matematyczna (czyli działania których wynikiem jest prawda lub fałsz) i teoria zbiorów. Natomiast do określenia złożoności obliczeniowej algorytmów, od której zależy jak mocno będzie przeciążony procesor, stosuje się notację „duże O”, która informuje nas o tempie wzrostu funkcji (programiście zależy na tym, aby ten wzrost był jak najmniejszy). Oto jak w uproszczeniu wygląda lista kroków przykładowego algorytmu wykorzystywanego w grach FPS:

  1. Gracz A strzela do gracza B.
  2. Czy istnieje punkt wspólny z bryłą geometryczną reprezentującą gracza B oraz półprostą wychodzącą z lufy broni gracza A?
  3. Jeśli tak, to zostaje sprawdzone do jakiej części ciała należy punkt wspólny. W oparciu o tę informację zostaje wyznaczona wartość zadanych obrażeń, która zostaje odjęta od HP gracza B.
  4. Czy liczba HP gracza B jest równa lub mniejsza od 0?
  5. Jeśli tak, wówczas gracz B musi zaczekać na respawn.

Duże znaczenie przy symulowaniu sztucznej inteligencji, widoczne szczególnie wyraźnie w grach RTS, ma zagadnienie pathfindingu, czyli wyznaczanie najkrótszej ścieżki po której jednostka może przejść z punktu A do punktu B. W rozwiązaniu tego problemu może pomóc nam między innymi algorytm Dijkstry, reprezentujący dział matematyki jakim jest teoria grafów. Dobrym przykładem gier, które dobrze ukazują wykorzystanie wiedzy z zakresu grafów są dwie pierwsze części serii The Settlers, w której mali osadnicy poruszali się po wyznaczonych przez gracza ścieżkach.

Rachunek prawdopodobieństwa i statystyka matematyczna ma duże zastosowanie w balansowaniu rozgrywki. Jest to tak stary jak gry komputerowe problem polegający na takim zaprojektowaniu broni, ataków czy cywilizacji dostępnych w grze, aby żadne z nich nie było nadmiernie potężne względem innych. Na przykład w grze jest dostępny potężny czar, ale wymaga on bardzo dużej ilości many w wyniku czego nie jest nadużywany. Warto jednak nadmienić, że stworzenie idealnie zrównoważonej gry jest niemożliwe – wszakże nawet w szachach ktoś musi wykonać ruch jako pierwszy.

Problem balansowania rozgrywki staje się szczególnie uciążliwy w grach wieloosobowych, takich jak LoL. To właśnie nie do końca poprawne zrównoważenie wszelkich parametrów i zdolności bohaterów sprawia, że co każdą rotację jeden z nich jest wybierany podczas gry wyraźnie częściej niż pozostali. Jest też inny problem – jaką cenę powinien mieć dany przedmiot, aby była ona rozsądna względem bonusów jakie daje? Z odpowiedzią na te pytanie przychodzą pewne tajne formuły matematyczne wykorzystywane przez twórców, które każdemu przedmiotowi przypisują pewną uniwersalną, również niejawną wartość zależną od jego kosztu, bonusów i efektów nakładanych na wroga.

Wpływ królowej nauk na sam gameplay widać wyraźnie zwłaszcza w grach RTS, gdzie każdy aspekt rozgrywki jest oparty o wzory. Formuły matematyczne są używane na przykład do określenia prędkości z jaką poruszają się jednostki robotnicze w grze StarCraft 2 (ich prędkość nie jest bowiem stała), jak też do bardziej istotnych zagadnień takich jak zależność czasu wznoszenia budynku od liczby konstruujących go robotników w Age of Empires 2.

Kryptografia

Matematyka ma w produkcji gier jeszcze jedno ciekawe zastosowanie, nie mające bynajmniej na celu uprzyjemnienie zabawy lecz utrudnienie jej pewnej grupie graczy. Mowa oczywiście o systemach zabezpieczających przed piraceniem gier (tzw. DRM) opartych o mechanizmy kryptograficzne.

Specjaliści zajmujący się tworzeniem i obsługą tego typu mechanizmów muszą wykazać się znajomością między innymi krzywych eliptycznych, kombinatoryki (silnia, itp.), teorii liczb (szczególne zainteresowanie dotyczy liczb pierwszych), arytmetyki modularnej oraz teorii pierścieni i ciał (ciekawostką jest, iż w ciele Z3 2+2=1). Warto zauważyć, że rozwiązania matematyczne zastosowane przy tworzeniu algorytmów kryptograficznych zależą jedynie od wyobraźni autorów, toteż każdy dział matematyki może zostać w nich użyty. Liczy się tylko to, aby powstały system był niezawodny.

Królowa nauk

Jeśli ktoś, podobnie jak wielu uczniów i studentów uważa matematykę za stratę czasu, która nigdy nie przydaje się w życiu, to prawdopodobnie ma rację – o ile nie ma zamiaru zostać twórcą gier komputerowych. Każda gra komputerowa jest to bowiem jeden wielki algorytm, który bez przerwy coś rachuje, a efekty tych obliczeń są następnie widoczne na ekranie.

Foto binary background via Shutterstock.

Wykorzystane materiały:1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20.

  • gość

    No w końcu nie byle kto powiedział, że „Matematyka jest alfabetem którym Bóg opisał Wszechświat”. Polecam jeden z ciekawszych „wstępniaków” na temat grafiki i fizyki na YouTube autorstwa doktora Macieja Matyki.

    • Feyd

      Bez przesady. Jest ważna, ale konstruowanie aplikacji ma więcej z pracy z architekta/konstruktora niż matematyka.

    • michaś

      Zgadzam sie ale nie gdy piszesz gry.

    • Feyd

      Nawet jak piszesz gry, to ilość pracy powiązana z matematyką jest kilkukrotnie mniejsza od zwykłej roboty programistycznej. Zabawa z matematyką to creme de la creme tworzenia gier.

    • michaś

      Noo ja pisałem też hobbistycznie gierki i tam było to na porządku dziennym. Może rzeczywiscie nie super skomplikowane rzeczy ale jak ktos chciał bajery to musiał to ogarniać.

    • Marek Smoliński‮

      W wielkim stopniu zależy od gry. :)

    • gość

      Nie wiem kim jesteś i co potrafisz, ale jeśli mówi Ci coś „rozwiązanie numeryczne równań Naviera – Stokesa”, oglądnąłeś choć część dorobku doktora Matyki na YouTube i formie książek to zdajesz sobie sprawę o osobie / programiście / naukowcu jakiej klasy mówimy :-)

    • Feyd

      No właśnie pokazujesz jakim ignorantem jesteś. Wpychanie programowania w kanon matematyki jest największym błędem jakim można popełnić. 90% roboty w tej branży z matematyka nie ma nic wspólnego. W polsce niestety przez komune informatyka wyrosła zbyt mocno ze środowiska matematyków. W USA już dawno zauważyli, że umiejętności projektowania UI, poprawnej konstrukcji architektury aplikacji, technik tworzenia dobrego kodu jest o wiele ważniejsza od zabaw z matematyką. Ja w swojej ponad 20 letniej karierze dewelopera z matematyką wyższą niż liceum styknąłem się wyłącznie przy hobbistycznym pisaniu gier. W biznesowych aplikacjach ważniejsze od algorytmów matematycznych jest umiejętność stworzenia skalowalnej i rozszerzalnej architektury.

    • gość

      Acha :-) Widzę, że Twoje ego zostało mocno ubodzone. Jeszcze raz zachęcam Cię zamiast pisania komentarzy w stylu powyżej do zapoznania się z wykładem o którym wspomniałem.

    • Feyd

      Nie o ego chodzi, a wciskany w polsce kit o znaczeniu matematyki wyższej. Pisanie symulacji nawet najbardziej skompilowanych równań jest programistycznie zadaniem o wiele łatwiejszym niż tworzenie skalowanych i reaktywnych aplikacji. Mam ogromny szacunek do ludzi znajdujących rozwiązania róznych zjawisk naukowych. Natomiast czym innym jest praktyczne ich zastosowanie. Co da graczowi najlepsza mechanika płynów w grze RPG, skoro cała najważniejsza jej część czyli questy będą skopane.

      Na koniec, sektor IT jest najbardziej dotknięty brakiem pracowników. Myśl za tym idąca jest taka, że na uczelni zostają dwa typy ludzi. Idealiści, którzy za marną kase uczelnianą chcą sie poświęcić nauce i totalne dupy, które nie znalazły by dobrej pracy na rynku. Plagą polskich uczelni jest nie docenienie ludzi z biznesu i branży. Dlatego na polskich uczelniach o grach uczą goście, którzy nigdy żadnej gry AAA nie napisali. A w takich stanach. Najbardziej prestiżowe uczelnie zatrudniają chociażby na jeden wykład w tygodniu ludzi z takich studiów jak Epic, NaughtDog, itp. W polsce jest to nie do pomyślenia by człowiek spoza klanu wykładał przedmiot na którym na prawde sie zna.

    • gość

      Jeszcze raz zachęcam – oglądnij ten film. Najpierw oglądnij a potem będziesz pisał o „praktycznym zastosowaniu”. Po prostu trzeba przyjąć do wiadomości, choć to ciężka nauka i bolesne lanie w tyłek ego, że są tacy co tworzą narzędzia i tacy co z nich korzystają. Co oczywiście wcale nie oznacza, że nie jesteś bardzo dobry w tym co robisz.

    • luke

      Alez własnie @disqus_MUzXFGFHRZ:disqus tłumaczy Ci to od kilku postów: 90% programistów po prostu używa tych narzedzi (ja bym sie posunął nawet to 99%) i skupiają się na innych elementach, które bezpośrednio nijak się wiążą z wyższą matematyką.

    • haw

      owszem, jednak zrozumienie jak dane narzedzie zostalo stworzone pozwala poprawnie rozpoznac mocne i slabe strony oraz z dostepnego zestawu wybrac to ktore najlepiej sie sprawdzi w danym przypadku. warto wiedziec jaki indeks w bazie danych zastosowac, co moze byc przyczyna powolnego dzialania quicksorta czy jaki jest koszt wstawienia elementu do b-drzewa, itp…

    • Maniiiius

      Taaa on w tym siedzi, ale ty widziałeś film na YT więc wiesz lepiej…

    • gość

      Tak myślałem, że kod w JavaScripcie do znajdywania krzywych całkowych napisały za mnie krasnoludki.

    • Maniiiius

      Nie wiem czy krasnoludki czy zielone ludziki, ale tym to mi nie zaimponowałeś. Baa… Ośmieszasz się. Może ktoś, kto w życiu nic nie osiągnął (o ile takie pierdoły nazwiemy osiągnięciem) zrobiłby wielkie oczy. Czyli jakiś licealista albo nieudacznik życiowy. Zapewniam Cię jednak, że tłumów to ty tym nie prowiesz

    • gość

      A kto powiedział, że ja Ci chciałem zaimponować? Ośmieszać się takimi rzeczami? Dobre :-)

    • Maniiiius

      To po co się chwalisz? I tak, to ośmieszanie się. Kupkę też już robisz sam?

    • Kamil Dzióbek

      O który film Ci chodzi? proszę o podanie linku.

    • asd

      W biznesie pewnie zazwyczaj bierze się gotowe silniki, co nie zmienia faktu, że opierają się one (zwłaszcza grafika 3d) na matmie. No i wiadomo, że praca matematyczna odbywa się przy użyciu kartki i długopisu, a oprogramowuje się tylko wyniki (wzory/algorytmy).

    • Piotr Potulski

      Te silniki, to same się piszą?

    • Kamil Dzióbek

      „Pisanie symulacji nawet najbardziej skompilowanych równań jest programistycznie zadaniem o wiele łatwiejszym niż tworzenie skalowanych i reaktywnych aplikacji.”
      Żartujesz.
      Jeśli chodzi o skalowalność to masz OpenMP pod Fortrana i C++. Przeczytasz tutorial i będziesz umiał z tego korzystać. Będziesz pisał tak samo symulacje pod deskopy i superkomputery.
      Jeśli chodzi o aplikacje webowe to piszesz w pythonie i wrzucasz na Google App Engine i ono ci to skaluje na odpowiednią ilość maszyn.
      Twoja reaktywność kojarzy mi się tylko z pancerzem reaktywnym, więc nie wiem jak to skomentować.

      Żeby za symulować jakieś zjawisko trzeba wiedzieć jak je matematyczne opisać. Zwykle trzeba mieć matematyczną wiedzę na temat tego co to jest równanie różniczkowe i znać metodę numeryczną jego rozwiązywania (np hasło w google „Rungego-Kutty metoda”). Tego raczej się nie znajdzie w jednym tutorialu, szczególnie, że często chce się symulować coś co nikt inny jeszcze nie za symulował.

      Wiadomo, że silników fizyki nie piszą programiści tylko matematycy i fizycy. Questy nie piszą programiści tylko scenarzyści.

      „Nie o ego chodzi, a wciskany w polsce kit o znaczeniu matematyki wyższej.”
      Ja mam odwrotne odczucie, na w Polsce na studiach informatyki (przynajmniej na politechnice poznańskiej) olewa się matematykę.

    • Feyd

      > Jeśli chodzi o skalowalność to masz OpenMP pod Fortrana i C++.

      Tak to sobie możesz aplikacje do obliczeń przyspieszyć. Natomiast aplikacji serwerowych z dużym ruchem nie przyspieszysz.

      > Jeśli chodzi o aplikacje webowe to piszesz w pythonie i wrzucasz na Google App Engine i ono ci to skaluje na odpowiednią ilość maszyn.

      Poczytaj o Scali, Akka, Spark, itp To co napisałeś pokazuje twój niski stan wiedzy na ten temat. Co do skalowania poprzez GAE to jak nie liczysz sie z kosztami to OK. Google bedzie mial dobrego klienta

      > Żeby za symulować jakieś zjawisko trzeba wiedzieć jak je matematyczne opisać. Zwykle trzeba mieć matematyczną wiedzę na temat tego co to jest równanie różniczkowe i znać metodę numeryczną jego rozwiązywania

      I jest to nieporównywalne z pisaniem dużych aplikacji. Ktoś kto jest dobrym matematykiem/fizykiem w cale nie jest dobrym programistom ogólnego przeznaczenia.

    • Roman

      I co robisz? CMSy w PHP?

    • Feyd

      Nie aplikacje w Scali

    • Piotr Potulski

      Zależy jakich aplikacji. A raczej – matematyka ma zastosowanie (ostatecznie za takim relacyjnym modelem danych kryje się w cholerę nie tak znowu banalnej matematyki), tylko ktoś już te wzory zapakował w przyjazne biblioteki czy narzędzia i programista nie musi być świadomy co dokładnie robi.

  • Arkadiusz

    Świetny artykuł, w końcu coś co ma wartość merytoryczną i można dowiedzieć się czegoś ciekawego, no i jedna rzecz: brak opinii i wszystko rzetelnie przedstawione. Brawo Panie Adamie!

  • garrappachc

    I kwaterniony!

  • haw

    red dragon, jest taka strategiczna gra przegladarkowa. tworcy niestety kiedys podali wszystkie wzory z ktorych wyliczane jest w jakim czasie generuja sie zasoby itp. gracze policzyli ekstrema funkcji i mogli w absolutnie optymalny sposob ustawic sobie produkcje ;)

  • Marek Smoliński‮

    Artykuł bardzo fajny, szczególnie dla kogoś, kto nie programuje, ale interestuje go jak się tworzy gry.

    Nie grałem w Asasyna, ale w innych grach zawsze mi się wydawało, że fale na wodzie nie są częścią silnika fizycznego, ponieważ nie zmieniają się dynamicznie pod wpływem innych obiektów (płynącego statku, spadających przedmiotów itd.). Z reguły dynamiczne obiekty powodują dodatkowe, minimalne efekty wizualne nałożone na falującą powierzchnię wody.

    Stosowanie rachunku prawdopodobieństwa i statystyki w celu balansowania rozgrywki wydaje mi się bujdą na resorach. Być może w niektórych grach się to stosuje (w tym celu), ale wątpię, żeby rezultaty były zadowalające. Oczywiście w grach multiplayer często twórcy przyglądają się statystykom, ale są to proste dane, obliczane w sposób prymitywny z bardzo luźnym przełożeniem na łatki balansujące. Dobrym przykładem na potwierdzenie moich słów wydaje mi się gra Wiedźmin: Versus, w której z 3 klas: czarodziejka, przeraza, wiedźmin, w ponad 50% przypadków wybierana była ta ostatnia (bo fani marki przyzwyczaili się do gry Geraltem), mimo, że była to klasa najsłabsza.

    Warto jednak nadmienić, że stworzenie idealnie zrównoważonej gry jest niemożliwe – wszakże nawet w szachach ktoś musi wykonać ruch jako pierwszy.

    Czy zrównoważenie nie następuje poprzez wylosowanie lub dobrowolny kompromis w wyborze strony, ewentualnie rozegranie rewanżu przy zamianie stron?

  • przemo

    „kosinusy, itd.) oraz analizy matematycznej (m.in. zmora wielu studentów kierunków technicznych czyli całka)” i w tym miejscu zakonczyłem czytać te wypociny.

  • Kamil Dzióbek

    „Oto przykładowy problem – w punkcie (1,2,5) znajduje się środek pudła w kształcie sześcianu o długości krawędzi równej 5 i w kolorze #0000ff.”

    Ja myślę, że silnik graficzny przekazuje wierzchołki trójkątów z których jest zrobione pudełko do DirectX lub OpenGL. DirectX przekazuje to za pomocą sterowników do karty graficznej, a karta graficzna za pomocą magicznych wzorów oblicza wszystko i wyświetla na ekranie.

    Balansowanie rozgrywki za pomocą wzorów jest raczej niemożliwe, trzeba zatrudnić testerów którzy rozegrają kilkaset meczów różnymi rasami. Myślę że tak ustawiono balans miedzy rasami w Starcraft 2.

    • Piotr Potulski

      No tak (w pewnym przybliżeniu), tylko te magiczne wzory ktoś musi napisać i zakodować w postaci shadera zanim karta to zacznie przetwarzać.

  • Grant Neill

    Sławomir Mrożek w obiektywie Judyty Papp:

    www judytapapp com/mrozek php