Posts tagged ‘game development’

Kontenery haszujące w Visual C++

2008-06-11 21:10

W standardowej bibliotece pojemników (STL) języka C++ jest póki co poważny brak. Nie ma mianowicie kontenerów opierających się na mechanizmie haszowania (hashing), znanego też pod mniej jednoznaczną nazwą mieszania. Mówiąc zupełnie najprościej, takie pojemniki są pewnym uogólnieniem zwykłych tablic, które nie są jednak indeksowane liczbami całkowitymi, a kluczami dowolnego typu. Klucze te są jednak wpierw przepuszczane przez pewną funkcję (funkcję haszującą) i dopiero wynik używany jest do znalezienia wartości, z którą ów klucz jest związany. Istnieje też kilka metod rozwiązywania problemu kolizji, gdy kilka kluczy zostanie odwzorowanych na to samo miejsce w tablicy.
Zaletą haszowania jest szybkość: średnio dostęp do wartości związanej z danym kluczem jest wykonywanym w czasie stałym. Tak, stałym, czyli O(1). Jakkolwiek można być pesymistą i przewidywać, że przy odpowiednio złośliwym doborze kluczy czas ten urośnie do liniowego (O(n), ale w praktyce tablice haszujące zachowują się świetnie. No a to jest przecież najważniejsze :)

W STL nie ma jednak kontenerów używających haszowania. Mimo to wiele kompilatorów oferuje je we własnym zakresie. I tak nasz ulubiony Visual C++ udostępnia dwa “półstandardowe” nagłówki: hash_set i hash_map. Zawierają one klasy (multi)map oraz (multi)zbiorów, z wierzchu wyglądających właściwie identycznie jak zwykłe mapy i zbiory (std::map i std::set) z STL. Klasy te nazywają się hash_set, hash_map, itp., i celem zachowania zgodności ze standardem C++ umieszczone są nie w przestrzeni std, lecz stdext.

O istnieniu tych klas warto pamiętać, gdy tworzymy kod kluczowy pod względem wydajności. W programowaniu gier często są to na przykład przeróżne menedżery zasobów, które odwzorowują pewne identyfikatory (np. łańcuchy znaków) na obiekty w rodzaju modeli, tekstur, próbek dźwiękowych, itd. Szybkość działania przechowujących je pojemników może być ważna i warto poszukać alternatyw dla standardowej klasy map (która przecież teoretycznie “wyciąga” tylko O(logn) dla wyszukiwania). Jeśli przy okazji martwimy się przenośnością na inne kompilatory niż VC++ lub zgodnością ze standardem, to możemy spróbować przełączania między zwykłymi a haszującymi pojemnikami, np. tak:

  1. #if defined(_MSC_VER) && !defined(STANDARD_COMPLIANCE)
  2.     typedef stdext::hash_map<std::string, Object*> ResourceManagerMap;
  3. #else
  4.     typedef std::map<std::string, Object*> ResourceManagerMap;
  5. #endif

Naturalnie ‘kod niezależny od kontenera’ to dość często utopia, ale przy korzystaniu tylko z prostych operacji typu wstawianie-usuwanie-wyszukiwanie nie powinniśmy napotkać większych problemów.

Tags: , , ,
Author: Xion, posted under Uncategorized » 3 comments

Vista i Eksplorator gier

2008-05-06 19:40

Oprócz wsparcia dla wielkiej i wspaniałej wersji 10 biblioteki DirectX, system Windows Vista ma przynajmniej jeszcze jeden feature związany z programowaniem gier (i przy okazji z graniem w nie). Nie jest on aczkolwiek aż tak szeroko znany, chociaż wszystkie niezbędne narzędzia potrzebne do korzystania z niego są zawarte – nomen omen – w DirectX SDK.

Eksplorator gier w Windows Vista
Eksplorator gier z zaznaczoną
najciekawszą pozycją ;-)

To Eksplorator gier – małe, dosyć niepozorne, ale w gruncie rzeczy całkiem potężne narzędzie – w tym sensie, że potrafi ono czasami… zablokować dostęp do niektórych plików na dysku :) To aczkolwiek robota kontroli rodzicielskiej, czyli funkcji bardzo ściśle z wspomnianym Eksploratorem związanej. Ale po kolei.
Eksplorator gier (dostępny przez Start > Gry) to program, za pomocą którego możemy przeglądać gry zainstalowane na naszym komputerze. Prezentuje on nam ich nazwy, loga, gatunki, wymagania sprzętowe (w postaci Indeksu wydajności Windows), klasyfikację treści (wymagany wiek, zawartość przemocy, wulgaryzmów, itp.) i oczywiście pozwala także rzeczone gry uruchamiać – o ile nie zabrania tego ewentualna kontrola rodzicielska. Niby proste, chociaż na pierwszy rzut oka można by przypuszczać, że aplikacja ta dysponuje jakąś sztuczną inteligencją lub zdolnościami paranormalnymi. No bo skąd właściwie bierze ona te wszystkie informacje?…

Edytor plików GDF
Edytor plików GDF
zawarty w DXSDK

Prawda jest naturalnie taka, że wszystkie te dane muszą być podane przez twórców gier. W tym celu należy stworzyć tzw. Game Definition File (GDF), który jest plikiem XML opisującym różne parametry gry. Do niego możemy też dołączyć kilka grafik, a następnie całość należy zlinkować jako zasoby (resources) do jakiegoś pliku wykonywalnego – .exe lub .dll. Część tych czynności jest wspomagana przez Game Definition File Editor – niewielkie narzędzie dostarczane wraz z DirectX SDK począwszy od zeszłego roku. Potrafi ono mianowicie wyprodukować skrypt zasobów (plik .rc), który możemy dołączyć np. do projektu w Visual C++, skompilować do .res i z linkować z naszą grą.

Taphoo w Eksploratorze gier
Klasyfikacji treści wymaga
niestety (albo raczej stety)
cyfrowego podpisania gry

Lecz niestety nie jest to koniec zabawy :) Cały ten system, dzięki któremu Eksplorator posiada informacje o zainstalowanych grach, działa częściowo w oparciu o COM, a sama gra wymaga rejestracji w systemie w dość specjalny sposób, zanim będzie ona widoczna w programie. Ten sposób spokojnie można nazwać “ręcznym”, bo obejmuje on:

  1. Stworzenie instancji interfejsu COM IGameExplorer.
  2. Wywołanie jego metody VerifyAccess z podaniem pliku GDF.
  3. Wywołanie metody AddGame z kilkoma parametrami, m.in. wspomnianym plikiem i ścieżką do katalogu instalacyjnego gry.
  4. Stworzeniu przynajmniej jednego skrótu (w ściśle określonym miejscu), który pozwoli np. uruchomić grę przy pomocy Eksploratora.

Urocze, prawda? ;-) Żeby było śmieszniej, wszystkie te czynności powinny być wykonane w trakcie instalacji gry (a dokładniej: na sam jej koniec), co wymaga intensywnej grzebaniny w używanym programie instalacyjnym (w celu wywołania funkcji z pomocniczej biblioteki DLL) lub po prostu napisania małego programiku, który zostanie odpalony na końcu setupu i wszystkim się zajmie. O ile mi wiadomo, ani InstallShield, ani Windows Installer, ani freeware’owy Inno Setup nie wspierają natywnie procesu rejestracji gier w podobny sposób jak chociażby instalacji czcionek w systemie.

“A więc po co to wszystko?”, można zapytać. Ano chociażby po to, żeby nasza cudna produkcja jakoś się wyróżniała :] Obecnie gry retailowe w większości rejestrują się Eksploratorze, lecz z pewnością czyni tak mniejszość gier typu casual czy share/freeware. Możemy więc choć trochę zabłysnąć w oczach przyszłego użytkownika (chociaż zasadniczo zalecam świecenie innymi zaletami).
Na koniec – jeśli zdecydujemy pobawić się całym tym mechanizmem – warto pamiętać o tym, że Eksplorator gier to rzecz istniejąca jedynie na Viście, więc tylko na tym systemie powinniśmy przeprowadzać proces rejestracji.

Sinus, cosinus

2008-04-08 16:18

Jeśli w praktyce obliczamy wartości funkcji sinus lub cosinus dla danego kąta, to bardzo często zdarza się, że tak naprawdę potrzebujemy ich obu. Jest tak przy obliczaniu punktów okręgu, przy rozkładzie wektorów sił i jeszcze dla wielu innych okoliczności. Zależy nam naturalnie, aby policzyć to wszystko tak szybko, jak tylko się da, dlatego dobrze jest stosować funkcje w rodzaju sincos, które wyznaczają obie wartości jednocześnie.

Niestety nie każdy język programowania taką funkcję posiada. Mają ją języki shaderowe (GLSL, HLSL i asembler GPU) oraz np. Delphi, ale już nasz ulubiony C++ nie. Można by oczywiście uzupełnić ten brak poprzez taką implementację:

  1. void sincos(float angle, float* sine, float* cosine)
  2.     { *sine = sin(angle); *cosine = cos(angle); }

ale chyba nie trzeba nikogo przekonywać, że większego sensu ona nie ma :) Nie występuje tu bowiem żaden zysk na wydajności, bo wartości są obliczane oddzielnie.

Co więc można zrobić? Ano wykorzystać to, co drzemie w jednostce zmiennoprzecinkowej procesora, ale nie jest używane przez wszystkie języki wyższego poziomu. Istnieje mianowicie instrukcja FSINCOS, która wykonuje całą potrzebną “magię”. Należy ją tylko opakować:

  1. void sincos(float angle, float* sine, float* cosine)
  2. {
  3.     __asm
  4.     {
  5.         mov eax, sine
  6.         mov edx, cosine
  7.        
  8.         fld     angle
  9.         fsincos
  10.         fstp    dword ptr [edx]
  11.         fstp    dword ptr [eax]
  12.     }
  13. }

Jakkolwiek tajemniczo to może wyglądać, funkcja ta po prostu ładuje argument (kąt) na stos FPU, by potem odebrać wyniki – cosinus i sinus. W przypadku operowania na liczbach typu float nie ma możliwości podania zbyt dużego/małego argumentu, więc nie trzeba sprawdzać rejestru flag.

I tyle – funkcja mała, acz użyteczna. Asembler czasem się przydaje, proszę państwa ;P

Tags: , ,
Author: Xion, posted under Programming » 13 comments

Tekstury do wszystkiego

2008-02-17 21:10

W potocznym rozumieniu tekstura to taki obrazek, który nakłada się obiekt trójwymiarowy, aby w ten sposób imitować wygląd jego powierzchni. Rzeczywiście, dawno temu była to ich jedyna funkcja. Tego rodzaju tekstury (nazywane teksturami rozproszenia) są oczywiście nadal niezbędne. Obok nich powstało jednak całe mnóstwo innych rodzajów tekstur, które są wykorzystywane podczas renderowania scen 3D.

Wśród nich są na przykład takie, które zawierają pewne niezbędne informacje na temat obiektów na scenie – nie tylko zresztą geometrii. Są to chociażby:

  • Przykład mapy wysokości
    Przykład mapy wysokości

    Mapy wysokości (height maps). To czarno-białe tekstury, używane do modelowania terenu. Jasność konkretnego piksela odpowiada wysokości terenu w danym punkcie. Taka tekstura musi być naturalnie przetworzona na odpowiednie trójkąty (co specjalnie trudne nie jest), ale jej używanie zamiast innych reprezentacji ma dwie wyraźne zalety. Po pierwsze, umożliwia regulowanie stopnia szczegółowości (Level of Detail, LoD) wyświetlanego terenu. Po drugie, mapy wysokości są bardzo łatwe do wykonania za pomocą dowolnego programu graficznego nawet przez średnio uzdolnionego w tym kierunku kodera :)

  • Przykład mapy normalnych
    Odpowiadająca jej
    mapa normalnych

    Mapy normalnych (normal maps) obrazują z kolei wektory normalne punktów powierzchni. Pomysł jest bardzo prosty: kolor każdego piksela w formacie RGB odpowiada normalnej o współrzędnych XYZ. Ponieważ współrzędne te są ograniczone (długość normalnej to zawsze 1), mogą być zapisane jako kolor. Mapa normalnych jest potem wykorzystywana przy obliczeniu oświetlenia per-pixel.

  • Mapy światła (light maps) reprezentują natomiast rozkład oświetlenia na scenie lub wokół źródła światła. W tym pierwszym przypadku chodzi o użycie wygenerowanego wcześniej jakąś kosztowną metodą (np. śledzenia fotonów) “wzorca” oświetlenia sceny. Ma to rzecz jasna sens tylko wtedy, gdy oświetlenie jest statyczne. Z kolei lightmapa dla źródła światła obrazuje kształt promieni świetlnych, które rzekomo z niego wychodzą. W obu przypadkach jasność pikseli odpowiada intensywności oświetlenia, chociaż mapy światła nie muszą być monochromatyczne.

Tego rodzaju tekstury są przygotowywane wcześniej i obok modeli, tekstur rozproszenia i innych danych stanowią informacje umożliwiają renderowanie sceny. Oprócz nich w trakcie samego rysowania wykorzystywane są też inne tekstury, tworzone na bieżąco i zwykle niezachowywane na później. Wśród tych efemerycznych tekstur mamy na przykład:

  • Mapy cieni (shadow maps). Są one używane przy jednej z technik liczenia cieni. Pojedyncza mapa to po prostu zapis bufora głębokości dla sceny widzianej z punktu widzenia źródła światła. Dzięki temu możliwe jest następnie określenie, który piksel jest widoczny dla tegoż źródła, a który jest w cieniu. To dość prosty sposób obliczenia cieniowania, w podstawowej wersji wymaga jednak dodatkowego przebiegu dla każdego źródła światła.
  • Imbryk z mapą sześcienną
    Imbryczek z cubemapą

    Mapy odbić środowiskowych (environmental maps) służą do symulowania przedmiotów o powierzchniach lustrzanych. Podobnie jak wyżej, wymagają osobnego przebiegu renderowania, i to często nawet niejednego (jak w przypadku map sześciennych). Tak powstałe obrazy odbić są potem nakładane na przedmiot, który dzięki temu sprawia wrażenie, jakby odbijał w sobie resztę sceny.

  • Bufory geometrii (G-buffers) to w zasadzie nie jedna, a zestaw tekstur, z których każda zawiera informacje o pewnym parametrze materiału dla danego piksela z gotowego obrazu sceny. Po wypełnieniu ich informacjami, “bufor” ten jest wykorzystywany np. dla obliczeń związanych z oświetleniem i cieniowaniem we wszystkich technikach opatrzonych modnym przydomkiem ‘deferred‘. Dzięki temu oszczędza się każdorazowego przekształcania całej geometrii dla każdego przebiegu renderowania przez wszystkie macierze.

Potencjalnych i aktualnych zastosowań tekstur jest o wiele więcej. Ale już na tych przykładach widać, że tekstury tak naprawdę nie są obrazkami, a jedynie zbiorami jakichś informacji, które tylko z konieczności są zapisywane w postaci kolorów pikseli. Być może niedługo staną się one pełnoprawną “pamięcią operacyjną” kart graficznych, którą można będzie np. alokować i zwalniać w kodzie shaderów. Jak dotąd możliwy jest ich odczyt oraz w pewnym stopniu zapis (zależnie od modelu shaderów), ale kto wie – może wkrótce doczekamy się czegoś więcej?…

Nie całkiem brakujące ogniwo DirectX

2008-02-12 20:49

Wszyscy wiedzą, że przesiadka na Vistę ma jedną niezaprzeczalną zaletę. Jeśli mianowicie dysponujemy odpowiednią kartą graficzną, to możemy cieszyć się całym bogactwem Shader Model 4 oraz dziesiątej wersji DirectX. Nadal jednak niewiele gier posiada jakieś efekty (oczywiście w(y)łączalne) uzyskiwane przy pomocy nowej wersji biblioteki. Najwyraźniej Microsoft nieumyślnie wpadł tutaj w rodzaj błędnego koła, które zapobiega powszechnemu wykorzystaniu DirectX 10.
Nie pomaga tu też za bardzo specjalna wersja “dziewiątki”, czyli tak zwany Direct3D 9Ex. Cóż to za zwierz?…

Jest to mianowicie pewne rozszerzenie znanej i lubianej wersji biblioteki, które wprowadza nowe możliwości, częściowo zbieżne z tym, czego można doświadczyć w D3D10. Wśród nich mamy chociażby:

  • Praktyczny brak zjawiska utraty urządzenia. W zasadzie począwszy od DirectDraw, gdzie mieliśmy tzw. utratę powierzchni, była to zawsze spora niedogodność. Jak wiemy, utrata urządzenia DirectX dotąd następowała wtedy, gdy użytkownik przełączał się z aplikacji pełnoekranowej, zmieniając tryb graficzny (rozdzielczość, głębię kolorów, itd.). Powodowała ona stratę wszystkich zasobów przechowywanych w pamięci karty graficznej, czyli głównie tekstur, i konieczność ich ponownego ładowania – co było i jest dość kłopotliwe. W D3D9Ex utrata urządzenia następuje tylko w dwóch ekstremalnych sytuacjach sprzętowo-sterownikowych i właściwie nie trzeba się nią przejmować.
  • Współdzielenie zasobów. Funkcje DirectX 9 miały od dawna tajemniczy parametr pSharedHandle. Był on opisany jako zarezerwowany i należało w jego miejsce przekazywać NULL. Rezerwacja ta jednak nie przepadła i w 9Ex jest on wykorzystywany do współdzielenia zasobów między urządzeniami – nawet takimi, które są w oddzielnych procesach. Mogę sobie wyobrazić zastosowanie tego mechanizmu chociażby do przełączania trybów graficznych bez konieczności ponownego tworzenia wszystkich tekstur, buforów, itp.
  • Przydatne funkcje w nowym interfejsie IDirect3DDevice9Ex. Jest wśród nich na przykład WaitForVBlank, służąca do ręcznej synchronizacji pionowej.

Wszystkie te możliwości prezentują się całkiem nieźle. Żeby jednak z nich korzystać, muszą być spełnione dwa warunki. Po pierwsze, sprzęt musi wspierać tak zwany WDDM (Windows Device Driver Model), co w przypadku popularnych kart graficznych dotyczy z grubsza tych, które udostępniają Shader Model 3.
A drugi warunek?… Niejako wynika on z pierwszego, bowiem WDDM jest częścią systemu Windows Vista. Aplikacje wykorzystujące Direct3D 9Ex będą więc działały wyłącznie na tym systemie. To pewnie trochę zniechęcające, prawda? Ale cóż, Microsoft próbuje jak może ;-)

Kompilowanie efektów w locie

2007-11-24 22:26

Model subtraktywny programowalnego potoku graficznego (nie ma to jak kilka trudnych słów na początek ;P) charakteryzuje się tym, że kody shaderów są w nim dość rozdęte objętościowo. Wynikową postać shadera otrzymuje się bowiem poprzez wybranie części kodu odpowiadającej aktualnym potrzebom związanym np. z materiałem i oświetleniem. Rzeczone części są wydzielone przy pomocy dyrektyw podobnych do preprocesora z C: #if, #else, itd.

Najprościej jest wtedy, gdy korzystamy z plików efektów (.fx) z DirectX. Wtedy można użyć funkcji D3DXCreateEffectFromFile lub D3DXCreateEffectFromFile, którym można przekazać wartości makr potrzebnych w danym przebiegu renderowania. Działa to tak, jakbyśmy użyli dyrektywy #define bezpośrednio w kodzie efektu i podobnie do makr definiowanych w wierszu poleceń kompilacji w przypadku normalnych programów.
Otrzymany w ten sposób skompilowany shader należy oczywiście zachować, aby można było szybko przełączać między potrzebnymi wersjami w czasie renderowania. Wciąż jednak wymaga to ponownej kompilacji wszystkich używanych wersji shadera przy każdym uruchomieniu aplikacji – co jest marnotrawieniem czasu, jeżeli plik z kodem efektu się nie zmienia.

Można coś na to poradzić, stosując interfejs ID3DXEffectCompiler zamiast zwykłego ID3DXEffect. Ten pierwszy ma bowiem dodatkową, bardzo przydatną metodę CompileEffect:

  1. HRESULT ID3DXEffectCompiler::CompileEffect(
  2.   DWORD Flags,
  3.   LPD3DXBUFFER * ppEffect,
  4.   LPD3DXBUFFER * ppErrorMsgs
  5. );

W wyniku jej użycia możemy dostać bufor (czyli w gruncie rzeczy kawałek pamięci wypełniony danymi binarnymi) zawierający efekt w postaci skompilowanej. Najważniejsze jest to, że w tej postaci możemy zapisać go do pliku (zwykle z rozszerzeniem .fxo) i później tylko szybko odczytać – bez czasochłonnej rekompilacji. W ten sposób można stworzyć mechanizm cache‘owania skompilowanych shaderów, który przyspieszy uruchamianie aplikacji.

Tags: ,
Author: Xion, posted under Programming » Comments Off on Kompilowanie efektów w locie

Finalne demo Rega

2007-11-20 0:31

Regedit zaprezentował dzisiaj w końcu demko prezentujące możliwości jego silnika, który – jak sam utrzymuje – niedawno ukończył. Wprawdzie ja nadal mam wątpliwości, czy wyrazy ‘silnik’ i ‘ukończony’ w ogóle powinny pojawiać się obok siebie, ale nie zmienia to faktu, że przynajmniej aktualnie istniejąca część jego engine‘u prezentuje się imponująco. Moje gratulacje!

The Final Quest by Regedit - screen z dema The Final Quest by Regedit - screen z dema The Final Quest by Regedit - screen z dema

Po więcej szczegółów zapraszam tutaj:

The Final Quest

A ja w międzyczasie mogę dumać nad tym, ile to jeszcze miesięcy i lat zajmie mi dojście do podobnego poziomu ;)

Tags: , , ,
Author: Xion, posted under Internet, Programming » Comments Off on Finalne demo Rega
 


© 2017 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.