Matematyka w programowaniu. Gdzie używa się jej w grach i w telekomunikacji?

Matematyka w informatyce – dla jednych przykra konieczność, dla innych pasja i hobby, a dla większości doświadczonych informatyków trudniących się projektowaniem, rozwojem tudzież utrzymaniem oprogramowania – potężne i niezbędne narzędzie do pracy. Różni ludzie różnie powiedzą, ale większość zapewne zgodzi się ze stwierdzeniem, że w aplikacjach do badań naukowych lub w systemach bankowo-finansowych matematyka będzie potrzebna. A w telekomunikacji czy w sieciach komputerowych? Niekoniecznie. Pilnowanie uprawnień użytkowników, administracja bazy danych, filtrowanie pakietów na sieci – ileż tam może być tej poważnej matematyki?

Zgoda, że przyda się czasem trochę statystyki ruchu, żeby ocenić jakość działania i wydajność sieci. A w grach komputerowych? To przecież głównie ładna grafika, płynnie animowana, pomysł na fabułę i najlepiej jeszcze wciągający tryb multiplayer. Jednak u podstaw tych wszystkich zagadnień leży właśnie matematyka.

W dalszej części artykułu przybliżę konkretne przypadki występowania wspomnianych wyżej zagadnień oraz opiszę, gdzie oraz jaka matematyka jest tam użyta. Nie będę twierdził ani próbował dowieść, że konieczna jest szczegółowa znajomość wszelkich mniej lub bardziej karkołomnych teorii, dowodów i ich zastosowania. To zwyczajnie nie byłoby prawdą.

Idąc za takim rozumowaniem łatwo dojść do absurdalnego wniosku jakoby każdy programista, co do zasady, powinien biegle liczyć transformatę Fouriera, jak również znać wszystkie procesy obróbki krzemu przy konstrukcji procesora i innych układów scalonych komputera. Bynajmniej, nigdy bym nie zachęcał do fanatyzmu czy fundamentalizmu.

Dobry i szanujący się programista powinien mieć na tyle wiedzy ogólnej z różnych dziedzin nauki i nie tylko, aby móc zrozumieć zagadnienia, które napotka w swojej profesji. Takie zrozumienie bardzo ułatwia projektowanie systemu, wybór możliwie wydajnych algorytmów czy przewidywanie zapotrzebowania na zasoby, takie jak pamięć operacyjna i moc obliczeniowa.

Matematyka w grach

Przez ostatnie dwadzieścia kilka lat rozwój gier komputerowych odbywał się w szalonym tempie. Mam tu na myśli przede wszystkim szatę graficzną i bogactwo świata, w jakim gracz może poruszać się w grze. Aby móc się poruszać, konieczny jest jakiś układ odniesienia i sposób na opisanie tego ruchu. Zastosowano tutaj kartezjański układ współrzędnych z tradycyjnej geometrii na płaszczyźnie (a w każdym razie był on stosowany mniej więcej do połowy lat 90. ubiegłego wieku). Dlaczego?

Ówczesne procesory były w stanie wykonać obliczenia konieczne do wyznaczenia położenia i narysowania różnych obiektów na płaszczyźnie, a także stwierdzenia, które z nich ewentualnie kolidują ze sobą. Wyżej wspomniane obliczenia to nic innego jak podstawowe równania mechaniki Newtona łączące przebytą drogę, czas, który upłynął, prędkość i przyspieszenie.

Źródło.

Sama fizyka nie była szczególnie skomplikowana, problemem stawała się duża ilość obiektów, dla których obliczenia trzeba było wykonać. Jednak zagadnieniem, które cierpiało o wiele bardziej z powodu deficytu mocy obliczeniowej, była graficzna reprezentacja wirtualnego świata stworzonego w grach. Dlatego też większość gier do początku lat 90. zasadniczo pracowała w trybie 2D, gdzie pokazanie obrazu ograniczało się właściwie do wycięcia odpowiedniego fragmentu z całej mapy wirtualnego świata.

W ówczesnych grach tworzy się iluzje trójwymiarowości poprzez nierównomierne skalowanie elementów tła, co daje pewne poczucie głębi w obserwowanym obrazie. Iluzję uzupełnia się skalowanymi obrazami aktywnych obiektów w grze, które umieszczano na perspektywicznie narysowanym tle.

Przykładowo, rysunek jezdni zwężającej się ku górze ekranu, z nałożonymi nań obrazami pojazdów, zmniejszanymi im wyżej na ekranie są umieszczane, daje obserwatorowi poczucie, że pojazdy położone wyżej na ekranie znajdują się jednocześnie dalej od obserwatora. Niemniej wymiar głębi w tym systemie jako taki nie istnieje. Symuluje się tylko jego przybliżone konsekwencje. Mówiąc czysto technicznie, widoczne elementy są jedynie skalowane w dwóch wymiarach, zależnie od pozycji na ekranie.

Poniższe ilustracje pokazują jak można prostymi operacjami stworzyć iluzję trójwymiarowości.

Na płaskiej powierzczhni umieszczono kilka prostokątów różnej wielkości. Kwadrat A jest ewidentnie większy niż B. Górny bok szarego prostokąta zostanie skrócony tak by powstał szary trapez.

Odległość między górną i dolną podstawą szarego trapezu jest identyczna, jak w przypadku szarego prostokąta na poprzednim rysunku. Jednak zabieg wprowadza poczucie głębi i od razu wygląda to jak fragment prostej drogi biegnącej po horyzont. Obiekt A jest wciąż większy niż B. Na następnym rysunku przesunięto B kawałek do góry i lekko w lewo.

Teraz ten sam identyczny obiekt B jest postrzegany jako bardziej oddalony od obserwatora a wielkościowo porównywalny do A.

Efekt końcowy nie jest idealny i wykazuje niekiedy pewne niespójności, aczkolwiek przeważnie jest (a raczej był w tamtych czasach) wystarczająco dobry, żeby nie zwracać uwagi obserwatora. Mózg człowieka automatycznie uzupełnia/filtruje wiele brakujących/niepoprawnych elementów.

Nasuwa się może pytanie dlaczego w 2D jest mniej do liczenia niż w 3D. Przecież ekran jest płaski i w tym samym rozmiarze w obydwu przypadkach, zatem ilość pikseli do stworzenia obrazu pozostaje taka sama. To prawda, ale dane wejściowe w przypadku trybu 2D są inne niż w 3D. Aby móc pokazać wirtualny trójwymiarowy świat na płaskim ekranie komputer musi wykonać tę samą operację, którą wykonuje ludzkie oko i mózg czy też aparat fotograficzny. Mam na myśli proces powstawania obrazu na siatkówce jednego oka, w odróżnieniu od percepcji rzeczywistości 3D, gdzie mózg interpretuje obrazy z obojga oczu.

Powstanie obrazu na siatkówce to projekcja układu współrzędnych 3D na 2D. W matematyce tym zagadnieniem zajmuje się algebra liniowa i teoria macierzy. Obiekty w wirtualnym świecie 3D składają się ze struktur trójkątów zawieszonych w przestrzeni 3D, które tworzą płaszczyzny, powierzchnie lub bryły. Im bardziej skomplikowany geometrycznie obiekt, tym więcej wymaga trójkątów, aby go wystarczająco dokładnie odwzorować w wirtualnym świecie. Każdy trójkąt jest definiowany przez 3 wektory określające współrzędne jego wierzchołków. Czysto praktycznie, projekcja każdego trójkąta z 3D do 2D wymaga przemnożenia współrzędnych wszystkich jego wierzchołków {V1, V2, V3} przez macierz projekcji M.

Na potrzeby manipulacji obiektami w świecie 3D używa się i przechowuje kilka takich macierzy, każda odpowiedzialna za kolejny krok przy tworzeniu obrazu (np. transformacja samego obiektu, potem umieszczenie go w globalnej przestrzeni świata, aby na końcu dokonać projekcji, typowo perspektywicznej, na ekran).

Więcej szczegółów na temat układów współrzędnych w grafice 3D można znaleźć na przykład tutaj: shot511.github.io/2017-09-25-uklady-wspolrzednych/.

Jak widać z powyższego, samo powstanie rzeczywistego obrazu 2D z jego abstrakcyjnej formy 3D jest obliczeniowo dość kosztowne. Tych kosztów nie ma przy grafice 2D, ponieważ kosztowne operacje “zostały wykonane” wcześniej offline, podczas projektowania tła, krajobrazu itp., które w trakcie działania gry są tylko wybierane do pokazania, a nie generowane. Jest to pewnego rodzaju uproszczenie, ponieważ w konstrukcji gier 3D wykorzystuje się często mieszankę technik ze świata 2D i 3D, aby zmniejszyć koszty obliczeniowe powstawania obrazu.

Ale metody budowy silników graficznych do gier to temat na inny artykuł. Rzeczywistość 3D daje o wiele większą elastyczność i możliwości w konstrukcji scenerii – myślę na przykład o dynamicznym oświetleniu, cieniach obiektów itd. W grafice 2D można co najwyżej stwarzać pewne iluzje. Dla zainteresowanych polecam kilka haseł z zakresu modelowania oświetlenia do poszukiwań w internecie – zarówno w zastosowaniach w czasie rzeczywistym, jak i generowania fotorealistycznych scenerii:

• photorealistic rendering,
• ray tracing,
• subsurface scattering,
• real-time shadow rendering.

Matematyka w telekomunikacji

Wspomniałem wcześniej o udziale telekomunikacji w tym wszystkim. Dawniej wspólne granie odbywało się najczęściej w ograniczonym liczebnie towarzystwie, ze względu chociażby na trudność współdzielenia jednej klawiatury z więcej niż jedną osobą. Zgoda, można jeszcze używać joysticków lub padów, ale nadal rząd wielkości to kilka osób. Ten model ewoluował przez lata do dzisiejszego stanu rzeczy, gdzie każdy z graczy dysponuje całym komputerem lub konsolą, a te z kolei są połączone przez sieć komputerową.

Zachowanie spójności

Ze względu na często duże odległości, a zatem długi czas propagacji sygnałów oraz niepewność w doręczaniu informacji pomiędzy urządzeniami, z powodu zakłóceń w mediach transmisyjnych i samego charakteru budowy internetu pojawiły się nowe wyzwania. Dotyczyły one głównie zachowania spójności widzianego świata u wszystkich uczestników, aktualności tego obrazu, jak również jego prawdziwości. Przykładowym rozwiązaniem jest serwer, który z założenia ma zawsze aktualny i prawdziwy obraz sytuacji i tenże obraz propaguje wśród wszystkich uczestników gry.

Spójność obrazu sytuacji wśród graczy wymaga, by do wszystkich docierała taka sama informacja. Przy dużej ilości uczestników przepustowość sieci nie wystarczy, jeśli aktualizacje stanu świata gry będą zbyt częste lub zbyt obszerne. Dlatego też serwer wysyła ograniczone próbki sytuacji w grze (np. pozycje innych graczy, ich aktualne zasoby itp.), a komputery uczestników na podstawie tych próbek obliczają stany pośrednie i je prezentują, tak by przejścia między jedną a drugą próbką były możliwie płynne. Matematyka nazywa to interpolacją.

Sumy kontrolne

Informacja wysyłana pomiędzy serwerem a uczestnikami powinna być gwarantowanie prawdziwa, aby nie być w stanie zakłamać wysyłanej informacji celem nieuczciwego pozyskania przewagi w grze. Do takich zabezpieczeń można stosować na przykład szyfrowanie bądź sumy kontrolne, które zdradzą próby manipulacji przesyłanej wiadomości lub jej uszkodzenie w czasie transmisji. Te mechanizmy często oparte są na obliczeniach na dużych liczbach pierwszych, których wyszukanie jest na tyle czasochłonne, że ingerencja w dane byłaby zbyt późna, więc i bezskuteczna.

Oferty pracy z

Trzecia ważna kwestia to aktualność informacji. Tutaj bardzo ważny jest możliwie krótki czas transmisji danych. Przestarzałe dane są bezużyteczne, ponieważ podjęte na ich podstawie decyzje siłą rzeczy są natychmiast nieaktualne. Jednym ze sposobów przesyłu danych jest komunikacja przez bezprzewodowe sieci komórkowe. W ostatnich latach możliwości transmisji danych pakietowych w tych sieciach dogoniła to, co wcześniej było możliwe zasadniczo tylko na stałych mediach transmisyjnych, jak np. kable lub światłowody.

W omawianej bezprzewodowej komunikacji jako medium transmisyjne użyto promieniowania elektromagnetycznego o częstotliwościach rzędu 2-10 GHz. Potocznie ten przedział spektrum bywa nazywany falami radiowymi bądź mikrofalami – w dużej mierze zależnie od przypadku konkretnego użycia co czasem powoduje pewien zamęt.

Przykładowo, kuchenka mikrofalowa używa częstotliwości 2,4 GHz, czyli prawie takiej samej jak sieć Wi-Fi. Ale potocznie raczej powiemy “nadajnik radiowy Wi-Fi” niż “mikrofalowy”. Niezależnie od nomenklatury pozostaje pytanie jak w promieniowaniu elektromagnetycznym przesłać dane.

Modulacja częstotliwości sygnału radiowego

Poniżej opiszę koncepcyjnie, jakie dziedziny matematyki znajdują w tym zastosowanie. Dokładny opis, jak się to dzieje, to obszerniejszy temat na inną okazję zahaczający również o fizykę, która opisuje właściwości ruchu falowego. Chodzi głównie o koncepcję modulacji częstotliwościowej sygnału radiowego. Wiadomo zatem, że można wysłać jeden sygnał między nadajnikiem a odbiornikiem. Włączając więcej nadajników na pierwszy rzut oka robi się tylko jeden wielki szum i nic nie da się zidentyfikować. Tu na pomoc przychodzi matematyka z transformatą Fouriera. Definicja (jedna z nich, dla ścisłości) wygląda dla nie matematycznego oka niekoniecznie zrozumiale:

Praktycznym aspektem jest to, że każdy sygnał można przedstawić jako sumę (ewentualnie nieskończoną) sygnałów o różnych częstotliwościach. Matematyka stawia pewne szczegółowe wymagania dla tych sygnałów, ale na potrzeby aktualnego tematu wystarczy stwierdzić, że są one spełnione bez ich wyliczania. Najważniejsze jest to, że dzięki tym właściwościom i transformacie można wyłowić z powrotem poszczególne indywidualne sygnały. A co za tym idzie, można mieć więcej niż jeden nadajnik i więcej niż jeden sygnał wysyłany jednocześnie.

W idealnym teoretycznym świecie, gdzie nie ma niedoskonałości rzeczywistego świata, wystarczyłoby to do połączenia wszystkich ze wszystkimi. Istnieją jednak takie zjawiska, jak straty energii, a więc zanik sygnału, odbicia sygnału, niedoskonałości sprzętu elektronicznego itp., co powoduje trudności w poprawnej identyfikacji odebranych sygnałów. Na przykład odbicia i rozproszenia sygnału od budynków powodują, że do odbiornika dociera ten sam sygnał, ale z różnych stron i o różnym czasie. Tutaj również matematyka przychodzi z pomocą z macierzami o odpowiednich właściwościach.

W dużym skrócie, przemnażając cyfrową reprezentację sygnału przez taką macierz można wyłuskać pierwotny sygnał z odebranego bałaganu. Pojęciowo mowa tutaj o “ortogonalnych kodach” w technice przesyłu Wideband Code Division Multiple Access (WCDMA) i ogólnie CDMA (nie mylić z Collision Detection). Zainteresowani mogą poszukać więcej informacji w kontekście “signal processing” pod hasłem “orthogonal codes multiple access”. Pojęcie ortogonalności znalazło też zastosowanie w kolejnej, piątej już generacji sieci komórkowych, w sposobie rozdzielania sygnałów poprzez technikę Orthogonal Frequency Division Multiple Access (OFDMA).

Podsumowanie

Jak widać, zaawansowana matematyka stoi u podstaw bardzo wielu zagadnień z codziennego życia, obecnie być może postrzeganych jako nic niezwykłego. Mam nadzieję, że zaprezentowane informacje zachęcą do poszukiwania lepszego zrozumienia zagadnień matematyki pomimo że na pierwszy rzut oka mogą się wydawać tylko sztuką dla sztuki bez praktycznego zastosowania.

---

Zdjęcie główne artykułu pochodzi z unsplash.com.