Generowanie mapy - artykuł dla zuchwałych

Już naprawdę dawno tu nie pisałem. Wiem, że się powtarzam - jednak, w momencie kiedy zobaczyłem, jaką datą opatrzona jest "najnowsza" notka, coś mnie wzięło i postanowiłem - tak, dzisiaj znowu coś napiszę. Choć pracy dosyć jest.

Postaram się też opisać coś w miarę ciekawego i być może niebanalnego, ale nie nieosiągalnego (proszę w tym miejscu polonistów o konsultację w sprawie dobrej pisowni słowa przed nawiasem). Niestety - także troszkę zastałego, gdyż jest to rzecz, nad którą pracowałem bodajże dwa tygodnie temu i od tamtego czasu niewiele się zmieniło. Właściwie to bardzo mało. Słowem - nic.

Mianowicie, mam na myśli generowanie lochów w oparciu o plik z bitmapą, jaki może przygotować w Paintcie każdy, kto ma choć odrobinę weny twórczej i zbyt dużo wolnego czasu. Nie jest to oczywiście postać, w jakiej ten kod zawojowałby świat - umożliwia on jedynie wydrążenie korytarza i nałożeniu wokół niego elementów ściennych. Myślę jednak, że jest całkiem niezłą trampoliną do dalszego rozwijania tego zagadnienia. Czytelnicy poprzedniego wpisu skojarzą pewnie, że wówczas miałem jedynie przygotowany kod na wczytanie mapy z pliku tekstowego. Teraz jest [tadaaam] bardziej wizualnie. Co, nie ukrywam, mnie cieszy.

W odróżnieniu od wielu innych tutoriali, już na początku podam link [ooo, właśnie tutaj], pod którym można znaleźć przygotowany projekt w Visual C++ 2008 EE wraz ze skompilowaną wersją w trybie debug. Jest to też niejako kolejny test integralności elementów mojego frameworka i sprawdzenie, jak się sprawuje. Od razu mówię, że pod Vistą chodzi tragicznie, jak wszystko co jest związane z OpenGL-em, o czym pisałem parę notek temu - i chyba faktycznie zacznę myśleć o przeprowadzce i nauce DirectX-a. Ale na pewno nie teraz - studia dają się we znaki.

Po pobraniu pliku i rozpakowaniu go, przychodzi czas na obejrzenie zawartości. Zatem co my tu mamy:

- CBMP - klasa odpowiedzialna za obsługę plików w formacie BMP (czyli za wczytanie mapki z lochami).
- CCamera - klasa odpowiedzialna za obsługę kamery z widokiem z perspektywy pierwszej osoby.
- CTextureManager - klasa zarządzająca teksturami.
- CTGA - klasa obsługująca pliki w formacie TGA (czyli tekstury).
- CVector3 - struktura wektora z trzema współrzędnymi (dla kamery).
- main.cpp - bliżej niezidentyfikowane połączenie mrożonego bażanta z ruchliwą ściółką leśną wprost z gorących rejonów Antarktydy.

Zdziwić może niektórych fakt, że publikuję podstawowe kody źródłowe frameworka. Nie widzę sensu, dlaczego nie miałbym tego robić - nie jest to żaden supernowoczesny projekt, a w dodatku czerpię algorytmy z innych udostępnionych przykładów. A przy okazji każdy może się zapoznać i coś wynieść - ci bardziej początkujący same mechanizmy, a bardziej zaawansowani troszkę dobrego humoru.

Skupmy się może już na samej generacji mapy (wreszcie...). Zacznijmy od początku - funkcja inicjalizująca.

Tex.InitTex2D(0, "wall001.tga");
Imig.LoadBMP("lochy.bmp");
width = Imig.Width();
height = Imig.Height();
GenerateMap();
// kamera ustawiona tak, żeby być na początku wylotu korytarza Camera.SetCameraPosition(1.0f, 1.5f, 16.0f, 1.0f, 1.5f, 11.0f, 0, 1, 0);

Po wczytaniu tekstury ścian oraz lochów, a także zapisaniu rozmiaru bitmapy oraz (późniejszym) ustawieniu kamery, następuje wywołanie funkcji generacji mapy. Jeśli komuś nastręcza trudności korzystanie z dobrodziejstw klas udostępnionych na potrzeby przykładu - polecam zajrzeć do źródeł lub dokumentacji. Małego wyjaśnienia może jednak wymagać fakt podania takich a nie innych wartości metodzie SetCameraPosition - w tym przypadku po prostu wiedziałem, gdzie umieścić oko kamery, ale można to oczywiście obliczyć automatycznie - w zależności od potrzeb.

Przejdźmy zatem do sedna operacji, czyli funkcji GenerateMap. Na początek jednak, deklaracja paru ważnych zmiennych.

vector vx, vy, vz;

(Przy okazji - proszę zignorować fakt istnienia wskaźnika mapdata - tablica ta używana była w pierwotnej wersji programu, przy tekstowej mapie. Przepraszam za to niedopatrzenie.)

Pewnie parę osób zapyta "a po jaką cholerę wektory?". Otóż - dla ułatwienia. W odpowienim przypadku można by było użyć po prostu dynamicznej tablicy typu float (albo klasy CArrayFloat, która również jest częścią frameworka), aby z kolei dalej używać mechanizmu tablic wierzchołków i znacząco przyspieszyć renderowanie. Implementacja była jednak pisana "na szybko", zatem parę rzeczy może być nie zoptymalizowanych. W niczym to jednak nie przeszkadza, a nawet ułatwia zrozumienie mechanizmu. Zauważmy bowiem, że tak naprawdę nie wiemy, ile konkretnie wierzchołków będzie wygenerowanych - nie da się tego tak szybko stwierdzić patrząc jedynie na obrazek. Dlatego lepiej jest użyć samorozszerzalnego się kontenera. Racja - jeżeli grafik/projektant/inna-pozycja-zawodowa-osoby-wykonującej-ten-element odpowiednio dokładnie planuje mapę, zna tę liczbę i może w jakiś sposób wpłynąć na programistę (np. dobrym słowem albo gumowym kurczakiem), aby ten z góry przewidział odpowiednią wielkość tablicy i zrezygnował z użycia, szczerze mówiąc, wolnych obiektów typu std::vector.

Przejdźmy zatem do rzeczonej funkcji. Początek.

// zmienne przydatne do konstrukcji prymitywów
int whalf, hhalf;
if (width % 2 == 0) // jeśli szerokość parzysta, to dzielimy pół na pół
{
whalf = width;
}
else // jeśli szerokość nieparzysta
{
whalf = width+1;
}
// to samo dla długości mapy
if (height % 2 == 0)
{
hhalf = height;
}
else
{
hhalf = height+1;
}
int templ = 0;
int tempt = hhalf;
int i;
int j;

Jak można było wyżej wywnioskować, width oraz height to wielkości opisujące bitmapę. Następuje tutaj pierwsze poważne założenie - jedna płaszczyzna na mapie będzie miała długość 2 jednostek. Czyli każdy pojedynczy "klocek" lochów będzie sześcianem o wymiarach 2x2x2. Jest to oczywiście znaczne uproszczenie, aczkolwiek na początku sprawdza się całkiem znośnie. Na podstawie tej informacji i podanych danych, generujemy połowę szerokości i długości mapy w grze. Dlaczego połowę? Ponieważ następuje tutaj drugie poważne założenie - środek mapy będzie leżał dokładnie w punkcie (0,0) układu współrzędnych OpenGL. Będziemy zatem generować wierzchołki od -whalf do whalf i od -hhalf do hhalf. A że jeden piksel bitmapy to 2 jednostki mapy w aplikacji - zatem tak to wygląda. Pod koniec deklarujemy również zmienne, które będą nam towarzyszyć w pętli - dwie opisujące "stan" aktualnie badanych współrzędnych oraz dwie będące licznikami w pętli.

for (i = 0, j = 0; i < width * height; ++i, j += 3)
{
// jeśli sześcian (kawałek murku)
if (Imig.Image()[j] == 0x78 || Imig.Image()[j+1] == 0x78 || Imig.Image()[j+2] == 0x78)
{
// przednia ściana
vx.push_back(templ-whalf); vy.push_back(0); vz.push_back(tempt);
vx.push_back(templ+2-whalf); vy.push_back(0); vz.push_back(tempt);
vx.push_back(templ+2-whalf); vy.push_back(2); vz.push_back(tempt);
vx.push_back(templ-whalf); vy.push_back(2); vz.push_back(tempt);
// prawa ściana
vx.push_back(templ+2-whalf); vy.push_back(0); vz.push_back(tempt);
vx.push_back(templ+2-whalf); vy.push_back(0); vz.push_back(tempt-2);
vx.push_back(templ+2-whalf); vy.push_back(2); vz.push_back(tempt-2);
vx.push_back(templ+2-whalf); vy.push_back(2); vz.push_back(tempt);
// tylna ściana
vx.push_back(templ+2-whalf); vy.push_back(0); vz.push_back(tempt-2);
vx.push_back(templ-whalf); vy.push_back(0); vz.push_back(tempt-2);
vx.push_back(templ-whalf); vy.push_back(2); vz.push_back(tempt-2);
vx.push_back(templ+2-whalf); vy.push_back(2); vz.push_back(tempt-2);
// lewa ściana
vx.push_back(templ-whalf); vy.push_back(0); vz.push_back(tempt-2);
vx.push_back(templ-whalf); vy.push_back(0); vz.push_back(tempt);
vx.push_back(templ-whalf); vy.push_back(2); vz.push_back(tempt);
vx.push_back(templ-whalf); vy.push_back(2); vz.push_back(tempt-2);
}

//... tutaj będzie else if, które zaraz nastąpi
//... a tutaj zmiana wartości zmiennych templ i tempt

}

Będziemy teraz wesoło hasać po pętli za pomocą dwóch liczników - i oraz j. Patrząc na pętle, można już wysnuć pewne podejrzenia, które się teraz pewnie potwierdzą - i będzie służyło jedynie do kontynuowania pętli (żadnego większego, a tym bardziej enigmatycznego znaczenia nie posiada), natomiast j odpowiada za kolejne składowe pikseli bitmapy. Dlaczego co trzy? Gdyż rozmiar tablicy danych o pikselach wynosi szerokość * wysokość * 3 i każda współrzędna zapisywana jest za pomocą 3 bajtów opisujących ulubiony atrybut daltonistów, czyli kolor na danej pozycji. Trzeba także wspomnieć o dwóch rzeczach. Pierwsza jest taka, że nie zawsze można dociec, za pomocą jakich składowych (zapisanych w systemie szesnastkowym) jest opisany dany kolor. Nie używam i nie jestem specjalistą w zakresie obsługi specjalistycznych programów graficznych, choć na pewno tam te wartości można znaleźć. W opisywanym przypadku, przy niewielkiej złożoności bitmapy, skorzystał z poglądu heksadecymalnego w IrfanView i po prostu wywnioskowałem, że np. 787878 to kolor szary. Druga ważna rzecz to fakt, że należy te wartości sprawdzać od tyłu (co będzie widoczne na kolejnym fragmencie kodu). Tutaj nie ma co więcej dodawać - po prostu tak musi być. W powyższym kodzie widać, iż program interpretuje szary kolor piksela jako miejsce, gdzie ma postawić "klocek". Następuje zatem zapisywanie do wektorów odpowiednich współrzędnych wierzchołków i możemy przejść dalej. Właśnie tutaj używane są zmienne whalf, hhalf, tempt i templ.

No dobrze, są murki. Ale wypadałoby również odczytać, gdzie mają być wydrążone korytarze, prawda?

else if (Imig.Image()[j] == 0x22 || Imig.Image()[j+1] == 0xB1 || Imig.Image()[j+2] == 0x4C)
{
// podłoga
vx.push_back(templ-whalf); vy.push_back(0); vz.push_back(tempt);
vx.push_back(templ+2-whalf); vy.push_back(0); vz.push_back(tempt);
vx.push_back(templ+2-whalf); vy.push_back(0); vz.push_back(tempt-2);
vx.push_back(templ-whalf); vy.push_back(0); vz.push_back(tempt-2);
// sufit
vx.push_back(templ+2-whalf); vy.push_back(2); vz.push_back(tempt-2);
vx.push_back(templ-whalf); vy.push_back(2); vz.push_back(tempt-2);
vx.push_back(templ-whalf); vy.push_back(2); vz.push_back(tempt);
vx.push_back(templ+2-whalf); vy.push_back(2); vz.push_back(tempt);
}

Tutaj właśnie widać odczytywanie współrzędnych od tyłu - wiąże się to z konwersją pomiędzy formatami RGB i BGR. Kolor zielony, użyty w przykładzie, ma wartość 4CB122, dlatego powyżej odczytujemy to jako 22B14C. Trochę to pogmatwane i nielogiczne, ale nie wiem jak wy - ja już nauczyłem się z tym żyć. Samo ciało instrukcji warunkowej nie pozostawia złudzeń - okrutny algorytm chce zamknąć gracza pomiędzy podłogą a sufitem. Chlip.

// tymczasowa współrzędna x się przesuwa
templ += 2;

// koniec linijki, wyższy wiersz
if ((i+1) % width == 0)
{
templ = 0;
tempt -= 2;
}

Aby generowanie wierzchołków następowało zgrabnie i gibko, należy po "ifach" również odpowiednio przesuwać zmienne tymczasowe. Przy każdym obiegu pętli zmienia się współrzędna x-owa. Warto tutaj wspomnieć, iż poruszamy się od lewego dolnego wierzchołka mapy do prawego górnego, co poniekąd sugerowałem w poprzedniej notce. W przypadku, gdy skończy się wiersz, zerujemy współrzędną templ i zmniejszamy tempt (bo, jak wiadomo, wartości osi z "wgłąb" zmniejszają się).

Mamy zatem wygenerowane lochy. Cieszymy się i radujemy. Nic jednak nam po lochach, gdybyśmy ich nie wyświetlili. Jest to jednak czysta formalność.

Tex.BindTex2D(0);

for (int i = 0; i < vx.size(); i += 4)
{
glBegin(GL_QUADS);

glTexCoord2f(0.0f, 0.0f); glVertex3f(vx[i], vy[i], vz[i]);
glTexCoord2f(1.0f, 0.0f); glVertex3f(vx[i+1], vy[i+1], vz[i+1]);
glTexCoord2f(1.0f, 1.0f); glVertex3f(vx[i+2], vy[i+2], vz[i+2]);
glTexCoord2f(0.0f, 1.0f); glVertex3f(vx[i+3], vy[i+3], vz[i+3]);

glEnd();
}

Zwykła generacja kolejnych czworokątów, w dodatku oteksturowanych.

Jak widać, pominąłem milczeniem całą resztę programu - łącznie z konstrukcją, poruszaniem się, itd. Nie jest to jednak trudne - ich wybadanie i testowanie ustawień polecam bardziej Waszej cierpliwości oraz samozaparciu.

Mam nadzieję, iż każdy, kto tutaj dotarł, poczuł się w choć minimalnym stopniu usatysfakcjonowany. Tak jak napisałem na początku - nie jest to może mistrzostwo świata, ale swoją wagę ma.

Zachęcam do ściągnięcia, testowania i komentowania.

Pozdrawiam i dziękuję - SceNtriC.

Trik przy wczytywaniu mapy

Dzisiaj kolejna notka, tym razem nieco algorytmiczna. Przepraszam przy okazji za brak mojej aktywności na devblogu w ostatnim i przyszłym czasie. Związane jest to z wieloma dziwnymi rzeczami, które muszę wykonać na początku roku akademickiego. Co za tym idzie - skończyła mi się "laba".

Nie znaczy to oczywiście, że nic nie robię. Ostatnio projektuję jeden algorytm, który ma za zadanie generowanie prostych lochów z pliku tekstowego/obrazkowego (póki co, testuję pierwszą opcję). Nie chcę na razie umieszczać efektów swojej pracy, ale podam rozwiązanie na jeden problem, z którym ktoś kiedyś może mieć do czynienia. Otóż, wczytując plik do programu linijka po linijce i zapisując dane do tablicy jednowymiarowej siłą rzeczy, dokonujemy tego od lewego górnego rogu. W niektórych przypadkach jednak algorytm wymaga (albo jest to bardziej optymalne) odczytu poczynając od lewego dolnego rogu, a kończąc w prawym górnym. Tak dzieje się chociażby przy ładowaniu plików graficznych.

Podam to na przykładzie. Oto mapka zawarta w pliku tekstowym:

4
4
1000
0100
0010
0001

Jest ona kompletnie niepraktyczna, ale to w tej chwili nieważne (a przy okazji przypominam niektórym jak wygląda macierz jednostkowa). Pierwsza linijka to szerokość mapy, druga zawiera długość. Następnie znajdują się dane terenu, gdzie każdy znak oznacza odpowiedni typ obiektu na tym polu. Wczytując plik linijka po linijce, w tablicy danych mapy będziemy mieli następującą sytuację:

data[0] = 1; data[1] = 0; data[2] = 0; data[3] = 0;
data[4] = 0; data[5] = 1; data[6] = 0; data[7] = 0;
data[8] = 0; data[9] = 0; data[10] = 1; data[11] = 0;
data[12] = 0; data[13] = 0; data[14] = 0; data[15] = 1;

Chcemy jednak, aby dane były zapisane od lewego dolnego rogu. Czyli tak:

data[0] = 0; data[1] = 0; data[2] = 0; data[3] = 1;
data[4] = 0; data[5] = 0; data[6] = 1; data[7] = 0;
data[8] = 0; data[9] = 1; data[10] = 0; data[11] = 0;
data[12] = 1; data[13] = 0; data[14] = 0; data[15] = 0;

Nie ma sensu wczytywać pliku inaczej - nie byłoby to zbyt praktyczne (a przynajmniej tak mi się wydaje). Zamiast tego, należy zrobić to w normalny sposób i następnie odwrócić. Jak?

Korzystając z tego wzoru:

newdata[i] = data[j], gdzie j = [Szerokość * (Długość - i div Szerokość)] - Szerokość + (i mod Szerokość)

Troszkę czasu zajęło mi zaobserwowanie i przygotowanie tej zależności (jakieś 5 minut), ale wydaje mi się, iż działa poprawnie. Gwoli przypomnienia - "div" oznacza całość z dzielenia, a "mod" resztę.

Cały algorytm zapisany w języku C++ wygląda tak:

// tablica pomocnicza
unsigned char* newdata = new unsigned char[width*height];
// zastosowanie wzoru dla tablicy newdata
for (int i = 0; i < width * height; ++i)
{
newdata[i] = data[(width * (height - (int)(i / width))) - width + (i % width)];
}
// podmienienie właściwych danych na te z newdata
for (int i = 0; i < width * height; ++i)
{
data[i] = newdata[i];
}
// zwolnienie tablicy pomocniczej
delete[] newdata;
newdata = NULL;

Może nie jest to zbyt trudne i ogólnie-kopiące (w skrócie O.K.), ale zamieszczam, bo być może komuś się kiedyś przyda.

Pozdrawiam i dziękuję - SceNtriC.

Wyniki compo i głupia Vista

Dawno nie było notki i tak szczerze mówiąc, wakacyjny wysyp nowych tekstów na tej stronie się niestety skończył. Przyszła smutna rzeczywistość, pierwszy rok studiów i masa spraw do załatwienia. Co nie oznacza, że przestaję pisać całkowicie - po prostu rzadziej będę zamieszczał swoje wypociny.

Dzisiaj dwie sprawy. Pierwsza jest taka, że zgodnie z planem wysłałem Apokalips na Warsztat Summer of Code 2008, niekomercyjny całowakacyjny konkurs dla programistów gier komputerowych organizowany przez serwis - jakże by inaczej - Warsztat. Jakoś strasznie zaskoczony nie jestem - spodziewałem się wielu krytycznych uwag odnośnie sterowania i techniki. Można powiedzieć, iż myślałem nawet o większej ilości rzeczy, jakich nie dopracowałem w "rilejsie". Został za to zauważony mroczny klimat i odpowiednio dobrane dźwięki, co mnie bardzo cieszy. Tak czy inaczej, zająłem piąte miejsce zdobywając 3 i 0,(6) punkta, co mnie w pełni satysfakcjonuje i jakoś zmotywowało do dalszych prób z programowaniem. A wszystkim uczestnikom gratuluję skończenia gry i dziękuję im oraz organizatorom za możliwość sprawdzenia swych umiejętności.

Jednak te próby mogą być teraz utrudnione i to jest druga sprawa, którą chcę poruszyć. Jako posiadacz nowego laptopa i Internetu (wreszcie posiadam takowy na stancji) stałem się (nie)szczęśliwym użytkownikiem systemu Windows Vista. Niestety, wiele błędów, niedoróbek i ogólne mętne wrażenie po usłyszeniu opinii znajomych znalazło swoje potwierdzenie - nowe dziecko Microsoftu jest po prostu durne. Pomijam rozdmuchany system kontroli i inne tego typu rzeczy, gdyż tu wychodzi brak przyzwyczajenia. Graficzna strona Visty też mi się bardzo podoba. Natomiast próba napisania małego programu w OpenGL wraz z WinAPI w tym systemie kończy się zwykle chęcią uduszenia myszki. Nie interesowałem się jeszcze, w czym dokładnie siedzi problem - prawdopodobnie jest on umiejscowiony w punkcie, w którym Microsoft nie chce wyraźnie wspierać OpenGL-a. System jest też chyba mocno wyczulony na operacje zwalniania pamięci, aczkolwiek to również jest w fazie testów. Tak czy inaczej - pierwsze wrażenie jest bardzo złe i rzeczę, iż jeśli tylko posiadacie wybór, pozostańcie przy XP.

Cóż, dosyć krótka notka i do tego mało konstruktywna. Miejmy nadzieję, że następnym razem przedstawię większą. Nawet, jeśli będzie to kolejny Raport z Walki z Vistą (RzWzV).

Pozdrawiam - SceNtriC.