Generator świata WorldGen

Celem projektu jest napisanie generatora świata z wokseli. Napisanie tego generatora jest dla mnie jednocześnie okazją do nauki i stworzenia czegoś interesującego, moją pracą inżynierską, a także częścią mojego silnika do gry, która ma bazować właśnie na takim świecie z wokseli (o samej grze na razie jeszcze nic nie zdradzę). Aktualnie projekt jest we wczesnym etapie rozwoju, powiedziałbym, że nawet do wersji alpha jest jeszcze dosyć daleko, ale na blogu będziecie mogli śledzić postępy jakie poczyniłem wraz z kolejnymi postami, które postaram się umieszczać regularnie (jak tylko będę miał czas żeby je pisać, muszę przyznać, że pisanie interesujących artykułów nie jest tak proste jak myślałem i zajmuje więcej czasu niż się spodziewałem ).

Ostatnimi czasy silniki do gier jak i same gry oparte na wokselach stały się dosyć popularne. Jedną z pierwszych gier, które zapoczątkowały ten trend jest dosyć popularna gra Minecraft. To, że światy stworzone z tysięcy małych klocków mogły zagościć na naszych ekranach zawdzięczamy między innymi sporemu postępowi w technice i temu, że aktualnie komputery mogą mieć dosyć duże ilości pamięci RAM. Przechowywanie świata złożonego z małych kawałków w trzech wymiarach nie jest prostym zagadnieniem. Głównym problemem okazuje się wydajne przechowywanie bardzo dużych ilości danych. O ile istnieją pewne sprytne metody, aby zmniejszyć zużycie pamięci, okazuje się, że nie zawsze jest to dobre rozwiązanie. Problem nie polega jedynie na dużej zajętości pamięci komputera, a także na szybkim dostępie do nich. Pewne struktury pozwalają skutecznie minimalizować zużycie pamięci, ale niestety mają także spory wpływ na wydajność aplikacji. Jeśli chcemy mieć do czynienia z grą działającą w czasie rzeczywistym, wydajność musi być na wysokim poziomie.

Ale zacznijmy od początku, czym w ogóle są te całe woksele? Otóż woksel to nic innego jak trójwymiarowy piksel. Piksele jak wiemy (bądź jeszcze nie, ale to się zaraz zmieni ) są to małe kwadraciki na powierzchni monitora. Są one zatem dwuwymiarowe, ponieważ mogą pokrywać pewną powierzchnię. Oczywiście to, że są to kwadraciki jest raczej kwestią umowną, gdyby ktoś się uparł mógłby reprezentować je inaczej, tak jak akurat byłoby mu wygodnie. Tak więc woksel jest rozszerzeniem tej idei do trzech wymiarów. Woksel to pewna jednostka objętości. Dyskretna jednostka objętości, która w najprostszym wypadku może być reprezentowana jako jednostkowy sześcian. Tutaj także jest to reprezentacja umowna, gdyż woksel może być reprezentowany zupełnie inaczej. Nawet dziś istnieją gry wykorzystujące inne reprezentacje wokseli, które tworzą powierzchnie lepiej oddające np. rzeźbę terenu, a jednak wciąż bazują na dyskretnych jednostkach objętości.

Ja, na rzecz tego projektu, przyjąłem jednak, że użyję prostej reprezentacji woksela jakim jest zwykły jednostkowy sześcian. Mój wybór na taką reprezentację woksela padł już dużo wcześniej zanim zacząłem projekt. Wynika to z faktu iż chciałem napisać silnik podobny do tego znanego z gry Minecraft. Sam planuję wykorzystać generator do mojej własnej gry, która ma wykorzystywać właśnie taki świat z dużych klocków. Myślę, że taki styl jest dosyć ciekawy i chociaż powstało już wiele podobnych gier, które próbowały naśladować Minecrafta (zapewne w nadziei, że zarobią na nich super dużo pieniędzy ), moim zdaniem nadal ma pewien potencjał.

Pierwszym z kroków jakie należało podjąć był wybór struktury reprezentującej świat w pamięci komputera. Mój pomysł zakładał wykorzystanie zwykłych tablic trójwymiarowych, które chociaż zajmują dużo pamięci, są bardzo dobre jeśli chodzi o szybkość dostępu do danych. Później, po konsultacji mojego pomysłu, drugą opcją okazało się wykorzystanie drzewa ósemkowego.

Drzewo ósemkowe, to bardzo sprytna struktura, która dzieli przestrzeń zawsze na osiem równych części. To tak jak gdyby sześcian przeciąć po środku po wszystkich trzech płaszczyznach. Po takiej operacji zostało by nam osiem mniejszych kostek, które moglibyśmy dzielić dalej w podobny sposób. Korzystając z takiej struktury można bardzo zmniejszyć zużycie pamięci potrzebne na przechowywanie świata, ponieważ można kończyć podział przestrzeni wtedy kiedy już nic więcej nie da. Jeśli np. cały blok jest wyłącznie wypełniony powietrzem, podział nie ma już sensu, bo i tak mamy pełne informacje o tym kawałku przestrzeni. Dla lepszej wizualizacji, jak takie drzewo dzieli przestrzeń poniżej zamieszczam obrazek z początku moich prac nad projektem. Jest to wizualizacja zaimplementowanego przeze mnie właśnie drzewa ósemkowego, które całe wypełnione jest jednym materiałem, a jedynie w rogu jest jedna mała kostka innego materiału który, aby opisać, drzewo musi podzielić odpowiednio przestrzeń.

Wizualizacja wygenerowanego świta jest jednym z ważniejszych zagadnień. W końcu to czego wszyscy oczekują to, że zobaczą coś fajnego. Ludzie raczej nie bardzo uwierzą na słowo kiedy powiemy im: "wiesz, ta aplikacja generuje taki genialny świat i ma go zapisanego w pamięci... No tylko nie potrafi go wyświetlać, ale uwierz, że jest epicki!" Do wyświetlania mojego wygenerowanego świata (aby nie wystąpiła sytuacja o której przed chwilą pisałem) postanowiłem wykorzystać bibliotekę OpenGL. Oczywiście nie myślcie, że tutaj jest dużo prościej niż w poprzednich krokach. Metod wizualizacji jest także kilka i trzeba wybrać tą, która będzie według nas najlepsza. Jedną, i chyba najbardziej powszechną metodą, jest grafika rastrowa. Oznacza to, że przechowujemy w pamięci informacje o powierzchniach naszych obiektów, a następnie wyświetlamy je obiekt po obiekcie (a to można jeszcze bardziej rozdrobnić, na trójkąt po trójkącie ). Drugą popularną teraz metodą (nie w grach, ale w środowisku naukowym) jest metoda śledzenia promieni. Obydwie te metody mają jak zawsze swoje plusy i minusy.

Metoda rastrowa jest obsługiwana przez praktycznie wszystkie karty graficzne, które zostały stworzone z myślą o takiej właśnie wizualizacji. Zapewnia to, że nie musimy martwić się o wszystko sami, ponieważ niektóre rzeczy są już zrobione za nas. Dodatkowo dzisiejsze karty graficzne radzą sobie świetnie nawet przy wyświetlaniu tysięcy trójkątów. Niestety to podejście ma też swoje minusy. Świat z wokseli będzie z pewnością składał się z bardzo wielu trójkątów. Nawet dla współczesnych kart takie ilości danych do wyświetlanie mogą być wyzwaniem. Dodatkowo, jeśli będziemy chcieli uzyskać ciekawe efekty wizualne takie jak odbicia, czy połysk, cienie itp. wyświetlanie naprawdę może być bardzo wolne (czym obliczenia dla jednego piksela są bardziej skomplikowane, tym bardziej ogólna wydajność spadnie).

Zobaczmy zatem jaką mamy alternatywę i co stoi po drugiej stronie barykady. A jest to metoda śledzenia promieni. Działa ona w nieco inny sposób. Dla każdego piksela, promień jest wysyłany przez dany piksel z wirtualnej kamery. Następnie liczona jest jego trasa, a każde zderzenie może wnosić coś do końcowego koloru piksela. Co więcej, promień może być zaginany i odbijany co tworzy bardzo realistyczne efekty, a do tego wszystkiego perspektywa "tworzy się sama". Zatem niby mamy o wiele lepsze efekty wizualne i to do tego mniejszym kosztem, bo w sumie wystarczy zaimplementować tą metodę i wszystko zrobi się już "samo". Niestety nie jest to aż tak proste. Karty graficzne, nie są przystosowane do metody śledzenia promieni, a przynajmniej same jej nie obsługują. Wprawdzie mają wiele równoległych jednostek obliczeniowych, które idealnie nadają się do metody śledzenia promieni, ale niestety wszystko musielibyśmy pisać sami i to jeszcze prawdopodobnie w shaderze karty graficznej. Wydajność tej metody, też niestety nie jest idealna. O ile wszystkie rzeczy które trzeba robić w tej metodzie to tylko rzutowanie promieni, to niestety dla rozdzielczości powiedzmy 1920x1080 mamy do czynienia z 2 073 600 promieni do obliczania w jednej klatce! Jest to bardzo dużo i dlatego niestety ta metoda nie jest jeszcze zbyt popularna w aplikacjach czasu rzeczywistego. Wprawdzie istnieją metody na przyspieszenie obliczeń (np. puszczanie promieni w pakietach i liczenie wspólnej trasy za jednym razem dla wszystkich), ale samo zaimplementowanie tych metod byłoby wyzwaniem samym w sobie.

Biorąc pod uwagę powyższe rozważania, ja zdecydowałem się jednak na wybór starej dobrej metody grafiki rastrowej, która chociaż nie jest tutaj idelanym wyborem, na pewno sporo ułatwi. Jeśli chodzi o metodę śledzenia promieni, to z pewnością ją też zaimplementuję, bo z samej ciekawości jak to by działało i wyglądało, chętnie bym to zrobił, ale tym zajmę się później, kiedy nie będzie żadnej presji czasu i będę mógł sobie po prostu eksperymentować.

Poruszone tutaj tematy to tylko nieznaczna część tego, co należy zrobić, aby projekt był kompletny. Nie poruszyłem w ogóle tematów takich jak generowanie powierzchni świata, regionów, umieszczania drzew i innych obiektów, a to wszystko razem składa się na sukces całego projektu. Mam nadzieję napisać o tym wszystkim nieco później, wraz z postępami moich prac. Przy odrobinie szczęścia będę w stanie opisywać moje postępy i wstawiać je tutaj dla zainteresowanych osób