Efekty uboczne

Przy okazji robienia proceduralnego generatora teł do gry przypadkiem wygenerowałem całkiem ciekawe obrazki. Wprawdzie kompletnie bezużyteczne przy mojej aktualnej pracy, ale ruszyły moją wyobraźnię i myślę, że mogłyby mieć spore zastosowanie w demoscenie na przykład. Szczególnie, że generatorem jest zwykły atraktor pickover (kto nie zna, odsyłam do chaoscope) z drobną wariacją, ustalającą kolor na podstawie odległości od źródeł światła, czyli można to zaimplementować w "paru" bajtach dosłownie.

 

Takie efekty uboczne bardzo często są powodem powstawania nowych pomysłów, rozwiązań czy algorytmów. 

Re: Pola i akcesory wewnątrz klas

Do napisania tego posta sprowokował mnie Xion, swoją notką. Kiedyś sam o tym troszkę rozmyślałem, i doszedłem do wniosku, że zwykle wewnątrz klasy lepiej jest się odwołać bezpośrednio do składowych. Są jednak pewne wyjątki. I tutaj historia z życia wzięta, ale rozpisywać się nie będę, bo jak wiadomo jeden pseudokod znaczy więcej niż tysiąc słów :P

class Scene {

// trzy wskazniki na glowne macierze 
const Matrix4x4* modelMatrix;
const Matrix4x4* viewMatrix;
const Matrix4x4* projMatrix;

// od groma wyliczonych z nich macierzy 
Matrix4x4 modelViewMatrix, modelViewProjMatrix, invModel, (...), invModelViewProjMatrix;

bool /* w oryginale tu jest bitset */ modelChanged, (...), invModelViewProjChanged; 

public:

// tylko trzy metody set 
void setModelMatrix(const Matrix4x4* m) const;
void setViewMatrix(const Matrix4x4* m) const;
void setProjMatrix(const Matrix4x4* m) const;

// od groma metod get
const Matrix4x4& getModelMatrix() const; 
(...) 
const Matrix4x4& getInvModelViewProj() const;

};

Do tego dodajmy klasę ShaderManager, która pobiera sobie te macierze (i nie tylko, ale nie będę mieszać tutaj za bardzo, bo do puenty nie dojdę nigdy). I teraz - jak słusznie zauważył Xion użycie metod set na zewnątrz klasy Scene nie budzi (nie powinno!) wątpliwości. W tym przypadku jest to również konieczne wewnątrz. Przyczyna? Ktoś kto uważnie przeczytał pseudokod pewnie się domyśla, że liczenie (bądź co bądź kosztowne, szczególnie w przypadku inverse) macierzy jest odłożone do pierwszego get. Natomiast set aktualizuje odpowiednie wartości "changed". W przypadku nieużywania set trzeba te wartości zmienić ręcznie, co powoduje generalny syf w kodzie.

Pojawia się tutaj pytanie - co jeśli ktoś używa naszej klasy i o tym nie wie, i napisze gdzieś po prostu modelMatrix = identity4x4. Albo (o zgrozo :P) my sami mamy już tak rozdmuchaną klasę, że o tym zapominamy. Znalezienie błędu potem może być dosyć kosztowne. Moje rozwiązanie (które stosuję) polega na wywaleniu całej logiki związanej z macierzami do klasy SceneMatrix, gdzie macierze są w prywatnym obszarze a metody w publicznym, i dziedziczenie po niej. Zaleta jest taka, że w zależności od potrzeb możemy dziedziczyć publicznie lub prywatnie i w ten sposób udostępniać lub chować metody get / set na zewnątrz. Przy takim podejściu nie ma mowy o "zapomnieniu", że trzeba użyć set zamiast operatora=. Wadą jest to, że zwykle prowadzi to do wielodziedziczenia, ale moim zdaniem nie jest to ani błąd ani problem w takim przypadku.

Geometria w C++

Każdy kto pisze silnik graficzny, fizyczny, lub po prostu grę, potrzebuje często używać algorytmów geometrii obliczeniowej - triangulacji, liczenia otoczek wypukłych, operacji Boolowskich na wielokątach lub geometrii 3 wymiarowej, czy choćby prostym sprawdzaniu kolizji punktu z bryłą. Są to algorytmy używane w większości dziedzin związanych z kodowaniem gier i nie tylko, również ważne w CADach, robotyce, sofcie medycznym etc. Ponieważ odkrywanie koła po raz setny jest bezsensowne, postanowiłem znaleźć bibliotekę realizującą takie zadania za nas.

CGAL (Computational Geometry Algorithms Library) wydaje się być strzałem w dziesiątkę. Jest to bardzo dojrzały projekt, rozwijany od 97 roku o ile się nie mylę. Obecnie doczekał się już wersji 3.5. Udostępnia bardzo pokaźną liczbę struktur danych i algorytmów. Poszczególne biblioteki projektu są proste w użyciu i dobrze udokumentowane. Całość napisana jest z myślą o C++, ale z tego co wyczytałem jest również wsparcie dla Pythona (co może się przydać w pisaniu skryptów do AI). Szczegółowy przegląd ficzerów można znaleźć na stronie http://www.cgal.org/

Teraz licencja - do zastosowań niekomercyjnych CGAL jest darmowy (połowicznie na licencji LGPL i QPL). Natomiast w przypadku zastosowań komercyjnych tak różowo nie jest, trzeba zakupić licencję, niestety nie znalazłem ceny na ich stronie.

Wykobi jest dużo mniej rozwiniętym (obecnie wersja 0.0.4), ale również ciekawym i dobrze zapowiadającym się projektem na licencji GNU GPL w przypadku zastosowań niekomercyjnych oraz na płatnej licencji w przeciwnym przypadku. Warto zobaczyć co oferuje, na stronie http://www.wykobi.com/

VGL jest częścią większego pakietu VXL. Nie oferuje zbyt wiele, tak na prawdę jest to zbiór struktur danych oraz kilku podstawowych algorytmów, głównie do transformacji przestrzennych. Jednak uznałem, że warto go odnotować, choćby ze względu na możliwość używania za free po spełnieniu podstawowych warunków o dołączeniu licencji, nie używaniu TM i wyraźnym zaznaczeniu modyfikacji. Cały pakiet VXL oferuje już troszkę więcej - między innymi algorytmy algebry liniowej i operacje na obrazach. http://vxl.sourceforge.net/

Na koniec zostawiłem Generic Geometry Library (GGL), która nie oferuje wprawdzie tyle co CGAL, ale jest całkowicie darmowa. Jest to kandydat do wcielenia w zestaw libów Boost. Udostępnia kilka ciekawych funkcji jak liczenie otoczki wypukłej (algorytm Grahama), clipping czy proste testy kolizyjne (a raczej bazę do takich testów). http://geometrylibrary.geodan.nl/index.html

Muszę jednak wspomnieć o dokumentacji do GGL, która jest... tragiczna. Dobrym przykładem jest opis użycia klasy graham do liczenia otoczki wypukłej. Jest on wygenerowany przez doxygena, co bardzo lubię, ale brakuje tam choćby słowa komentarza od autora.

Na koniec dodam, że jeśli ktoś zna inne ciekawe liby (najlepiej free) to zachęcam do podzielenia się linkiem :)

SSequence, 4k intro sequencer

This small application purpose is to create sounds (like beat or hat) for 4k intros, that can be later composed into music. The sounds are exported directly into C++ header file (in the form of code that generates them). It was created using C++ and wxWidgets. The tool was never released due to lack of time to finish it. Anyway, it was kind of fun.

Złom jako stymulator postępu technologicznego

Ponieważ zmęczyło mnie ostatnio trochę hardcorowe pisanie silnika, postanowiłem zrobić sobie małą odskocznię. Wygrzebałem ze strychu laptopa, sprzęt można by powiedzieć archaiczny, bo z prockiem 266MHz, jakąś dwumegową kartą etc. i postanowiłem napisać na nim bibliotekę fizyki 2d, taką, żeby dało się na niej oprzeć płynnie działającą prostą gierkę z fizyką. Nic niezwykłego - jakiś collision response dla convexów, jakiś tam rigid body model etc. Normalnie pewnie nie zwrócił bym na to uwagi, ale z racji sprzętu jakoś mnie tknęło, gdy w jednej z funkcji musiałem zrobić coś takiego:

// pseudokod
int k = jakies obliczenia;
T* t = new T[k];
// jakies przetwarzanie
delete[] t;

Przy czym funkcja była bardzo krótka, i jak mi się wydawało, alokacja pamięci na heapie była jej wąskim gardłem (na tym sprzęcie jest to wąskie gardło co by nie mówić :P). Mogłem zastosować opcję T t[100] i liczyć, że 100 nie będzie przekroczone, ale to nie jest ani eleganckie ani profesjonalne, w ogóle to jak rosyjska ruletka. No i wtedy mnie tknęło - dlaczego T t[100] jest właściwie szybsze niż new? Dlatego, że alokacja na stosie to tylko przesunięcie wskaźnika stosu, a na heapie to wyszukanie odpowiednio dużego spójnego obszaru, ustawienie flag w jakiejś mapie pamięci (zależnie od niskopoziomowej implementacji zarządzania pamięcią), dopiero potem faktyczne przydzielenie tego obszaru i zwrócenie wskaźnika. Tak powstał pomysł napisania funkcji salloc i sfree. W pełni świadomy problemów z "popieprzeniem stosu" pomiędzy ich wywołaniami postanowiłem zrobić te funkcje jako inline, i tu pojawił się mały problem, leżący w mojej pamięci, a raczej w odwołaniu z niej do specyfikacji C++, która to nie nakazuje aby funkcja inline była faktycznie inline. Mówiąc inaczej - funkcja inline może ale nie musi pomijać całą zabawę z ramką stosu. Tak wpadłem na użycie __forceinline i z bananem na ryju odpaliłem funkcje do testów... banan szybko znikł, segfault, ale dlaczego? Rozkmina chwilę potrwała, w końcu wykonałem taki oto test:

__forceinline int stest() {
int toRet;
__asm mov toRet, esp
return toRet;
}
int t1, t2;
__asm mov t1, esp
t2 = stest;

Po wypisaniu t1 i t2 okazało się, że o ile w trybie release są one takie same, o tyle w trybie debug wartości są różne, o zgrozo! Okazało się, że programiści z Microsoftu zrobili sobie joke, nazywając słowo kluczowe __forceinline, bo tak na prawdę ono wcale nie jest force i robi z funkcji inline kiedy chce i jak chce, czyli powiedzieli "cmoknijcie nas w pompkę my i tak lepiej wiemy kiedy inline jest potrzebne". Zresztą popatrzcie co na to MSDN
Tak więc zapadła decyzja, zrobię to jak koder ANSI C - przy pomocy makro, za co zwolennicy "idealnego C++" by mnie zabili pewnie, ale to nie moja wina, że producenci kompilatorów robią sobie jaja.

#define salloc(PTR, M_SIZE) \
__asm sub esp, M_SIZE \
__asm mov PTR, esp

#define sfree(M_SIZE) \
__asm add esp, M_SIZE

Dobra, teraz pytanie - czy było warto? Do testu odpalałem funkcje w których tylko alokowałem i zwalniałem pamięć (na 1000 intów), w pętli po 10 000 000 razy (na Athlonie XP 2400+). Wyniki przeszły moje oczekiwania, może nie najśmielsze ale zawsze :P

Tryb DEBUG:
new: 23.6571
salloc: 0.596729
Tryb RELEASE:
new: 4.29237
salloc: 0.0172891

Wyniki podane są w sekundach. Zalety są kosmiczne, ale wady też są - wspomniane mieszanie na stosie na pewno nie jest zdrowe dla początkujących koderów, metoda jest raczej przeznaczona dla tych świadomych, rozumiejących co się dzieje na stosie.

Konstruktory, konstruktory

Załóżmy, że mamy klasę, w której nie ma funkcji wirtualnych (!), po niczym nie dziedziczy (w szczególności wirtualnie), i skomponowana jest tylko z niestatycznych i niestałych obiektów podstawowych. Jest to klasyczny przypadek klas typu Vector2, Vector3, Matrix3x3, Matrix4x4, oraz wielu innych matematycznych (i nie tylko) w grach. W takich klasach bardzo często wywoływany jest konstruktor kopiujący, więc warto byłoby się zastanowić jak taki konstruktor napisać optymalnie (*). Najprostszy sposób, to kopiowanie każdej wartości osobno. Inną możliwością jest wywołanie funkcji w rodzaju memcpy, żeby cały blok danych przekopiować na raz (stąd założenie o funkcjach wirtualnych etc., żeby nie nadpisać vtable pointera), co z kolei powoduje nakład na całą zabawę z ramką stosu. Teoretycznie można to jeszcze zoptymalizować przez modyfikator inline dla konstruktora. Ostatnie podejście, które sprawdziłem to... nie pisanie konstruktora ;P
Do testu przygotowałem 4 klasy - A, B, C i D, wykorzystujące wspomniane 4 podejścia. Konstruktory kopiujące dla A, B i C wyglądają następująco (dla testu drugiego, czyli symulacji macierzy 4x4, test pierwszy odpowiadał wektorowi trójelementowemu):

A(const A& a) {
x1 = a.x1; y1 = a.y1; z1 = a.z1; w1 = a.w1;
x2 = a.x2; y2 = a.y2; z2 = a.z2; w2 = a.w2;
x3 = a.x3; y3 = a.y3; z3 = a.z3; w3 = a.w3;
x4 = a.x4; y4 = a.y4; z4 = a.z4; w4 = a.w4;
}

B(const B& b) {
memcpy(this, &b, sizeof(B));
}

inline C(const C& c) {
memcpy(this, &c, sizeof(C));
}

Następnie dla każdej z 4 klas przeprowadziłem identyczny test ( testCycles = 100000000):

for(int i = 0; i < testCycles; i++) {
A acopy = A(a);
}

Jak wspomniałem, test 1 odpowiadał Vector3, test 2 - Matrix4x4.

Można się było domyślać, że narzut wywołania funkcji przewyższy zysk przy małej liczbie elementów do skopiowania. Natomiast wynik dla klasy D, z wygenerowanym automatycznie konstruktorem kopiującym jest dosyć zastanawiający, szczególnie dla przypadku 1 (aż z wrażenia dla pewności sprawdziłem, czy kompilator w ogóle kopiował obiekty :P). Więc moja odpowiedź na pytanie (*) - jak optymalnie napisać taki konstruktor brzmi: nie pisać wcale! Kompilator sobie poradzi.

Przy okazji sprawdziłem jeszcze jedną rzecz. Wielu programistów twierdzi, że lista inicjatorów konstruktora to tylko zabieg stylistyczny i nie różni się od przypisania wartości do obiektu wewnątrz konstruktora. Oczywiście mylnie, bo stosując drugie podejście wywołujemy niejawnie konstruktor obiektu tymczasowego, potem operator przypisania, a potem jeszcze destruktor. Prosty test:

class X {
std::string text;
public:
X() {
text = "text";
}
};

class Y {
std::string text;
public:
Y() : text("text") {}
};

W pętli wywoływałem tym razem zwykły konstruktor, wynik potwierdza to, co napisałem:

Mazanie po murach i inne zabawy

Ostatnio sporo czasu spędzam na oglądaniu produkcji niezależnych twórców, w poszukiwaniu inspiracji / pomysłu / weny - niepotrzebne skreślić. W moje ręce wpadła gierka, która wygrała w kategorii "Best Student Game" na Independent Games Festival 2009, pod złowieszczym tytułem "Tag: The Power of Paint". Po oglądnięciu screenów stwierdziłem, że to jakaś lipa - kiepsko (wręcz obciachowo) wyglądający cel shade'owy FPS, w dodatku nie widać przeciwników. No ale przecież zajął 1 miejsce w jakiejś kategorii, więc nie może być tak źle - ściągnąłem i... zakochałem się, genialna gra. Jest to bardzo nietypowe połączenie FPSa i gry logicznej - gatunków biegunowych. Do dyspozycji mamy 3 bronie - z zieloną, czerwoną i niebieską farbą oraz czwarte psikadełko - do zamazywania, coś jak gumka do ścierania. Każda farba ma pewne właściwości, gdy wejdziemy na pomalowaną nią podłogę... ścianę lub sufit. Zielona - powoduje, że nasza postać skacze, czerwona - że biegnie, niebieska - że przykleja się do ścian (dlatego można łazić po sufitach). Ogólnie chodzi o to, żeby tak bazgrać po planszy, żeby dostać się do punktu docelowego. Momentami trzeba sporo się pogłowić, popróbować różnych rozwiązań. Dodatkowo element zręcznościowy powoduje, że choć wiemy jak przeskoczyć z dachu na dach, to musimy do tego podchodzić kilka razy. No i jeszcze to łażenie po ścianach - kto grał w AVP już to przechodził, ale tutaj jest jakoś bardziej zwariowanie, momentami naprawdę mocno gubi się orientację przestrzenną. Warto zagrać. A jeszcze co ciekawe, w assetach znajdują się nieskompilowane shadery i oskryptowanie całej gry w XMLu, więc można ją sobie troszkę pozmieniać bez grzebania w binarkach.

Przy okazji wspomnę jeszcze o 2 gierkach z tego samego festiwalu. Pierwsza to rewelacyjny pomysł na gameplay - Snapshot Możemy robić screeny różnych przedmiotów (np. słonia, drzwi), potem umieszczać te screeny w jakimś miejscu, przenosząc w ten sposób owe przedmioty - np. stawiamy screena ze słoniem przy jakimś pudle, dzięki czemu słoń je przepchnie, albo drzwi na jakiejś ścianie, dzięki czemu będziemy mogli przez nią przejść. Dodatkowo klimatem przypomina troszkę czasy ośmiobitowców. Druga - FEIST spodobała mi się po prostu pod względem artystycznym, niesamowity klimat, zazdroszczę umiejętności grafikowi i designerowi (takie przeciwieństwo wspomnianego wyżej Tag :D).

A, jeszcze może wypada wspomnieć - samo IGF jest eventem odbywającym się w trakcie GDC. Wspomniana edycja odbyła się już dość dawno, w marcu. Mając fajny projekt na pewno warto się zgłosić, bo nagrody pieniężne są całkiem pokaźne, no i ten prestiż :P