bakalářská práce
Herní jádro pro práci s objemovými elementy Martin Morávek
Květen 2014
Ing. Jaroslav Sloup České vysoké učení technické v Praze Fakulta elektrotechnická, Katedra počítačové grafiky a interakce
Poděkování Rád bych poděkoval panu Ing. Jaroslavu Sloupovi za cenné rady, věcné připomínky a vstřícnost při konzultacích a za další pohled na danou problematikou této bakalářské práce.
Prohlášení Prohlašuji, že jsem předloženou práci vypracoval samostatně, a že jsem uvedl veškeré použité informační zdroje v souladu s Metodickým pokynem o dodržování etických principů při přípravě vysokoškolských závěrečných prací. iii
Abstrakt Pro urychlení vývoje herních titulů se využívají herní jádra, vývojáři se tak mohou soustředit pouze na implementaci herních mechanizmů. Tato bakalářská práce porovnává rozdíly mezi existujícími herními jádry a následně se zabývá samotnou implementací voxelového herního jádra vhodného pro hry s kompletně modifikovatelným herním světem. Implementované herní jádro využívá 3D DDA algoritmu pro průchod voxelovou sítí, je implementované v programovacím jazyce C++ a využívá OpenGL API.
Klíčová slova Herní jádro; voxel; 3DDDA, Minecraft; OpenGL; C++
iv
Abstrakt Game engines are used to accelerate the development time of game titles. This allows game developers to focus on implementation of game mechanics. This bachelor’s thesis weights differences between current game engines and then focuses on implementation voxel based game engine aimed for games with fully modifiable game world. Implemented game engine uses 3D DDA algorithm for walk through voxel matrix and it is implemented in programming language C++ and uses OpenGL API.
Keywords Game engine; voxel; 3DDDA, Minecraft; OpenGL; C++
v
Obsah 1. Úvod 1.1. Současný stav herních enginů . . . . . . 1.2. Hry založené na voxelových elementech . 1.2.1. Minecraft . . . . . . . . . . . . . 1.2.2. Synthetic world . . . . . . . . . . 1.2.3. FortressCraft: Unity . . . . . . . 1.2.4. Blockland . . . . . . . . . . . . . 1.2.5. Ace of Spades . . . . . . . . . . . 1.2.6. Terraria . . . . . . . . . . . . . . 1.2.7. Starbound . . . . . . . . . . . . . 1.3. Porovnání . . . . . . . . . . . . . . . . . 1.4. Shrnutí . . . . . . . . . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
1 2 2 3 3 3 4 4 4 5 5 6
2. Analýza 2.1. Požadavky . . . . . . . . . . . . . . . 2.1.1. Funkční požadavky . . . . . . 2.1.2. Nefunkční požadavky . . . . 2.2. Celkový pohled . . . . . . . . . . . . 2.3. Moduly herního jádra . . . . . . . . 2.3.1. Herní jádro . . . . . . . . . . 2.3.2. Modul herního světa . . . . . 2.3.3. Modul s počasím . . . . . . . 2.3.4. Osvětlení . . . . . . . . . . . 2.3.5. Vytváření herní mapy . . . . 2.3.6. Komunikace herních modulů 2.3.7. Vykreslování voxelů . . . . . 2.3.8. Herní smyčka . . . . . . . . . 2.3.9. Entity, modely, animace . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
7 7 7 8 8 9 9 9 9 9 11 12 13 13 14
. . . . . . . . . . . . . . .
17 17 17 18 18 19 19 21 21 21 22 23 24 24 24 25
3. Implementace 3.1. Programovací jazyk a knihovny . 3.2. Moduly herního jádra . . . . . . 3.2.1. Modul herního jádra . . . 3.2.2. Herní svět a jeho prvky . 3.2.3. Vykreslování . . . . . . . 3.2.4. Generátor mapy . . . . . 3.2.5. Komunikace modulů . . . 3.2.6. Pomocné třídy . . . . . . 3.2.7. Procházení voxelů pomocí 3.2.8. Entity . . . . . . . . . . . 3.2.9. Počasí . . . . . . . . . . . 3.3. Alternativy implementace . . . . 3.3.1. Herní mapa . . . . . . . . 3.3.2. Animace . . . . . . . . . . 3.3.3. Herní framework XNA . . vi
. . . . . . . . . . . . . . . . 3D . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . DDA . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
4. Testování 4.1. Testování pomocí demo scény . . . . . . . . . . . . . . . . . . . . . . . . 4.2. Unit testování . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3. Testování rychlosti vytváření chunku . . . . . . . . . . . . . . . . . . . .
26 26 26 27
5. Závěr 5.1. Porovnání výsledků s ostatními voxelovými herními jádry . . . . . . . . 5.2. Prostor ke zlepšení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29 29 29
Přílohy A. Kompilace programu
31
B. Uživatelský manuál
33
Literatura
34
vii
Zkratky Seznam použitých zkratech a cizích slov. chunk voxel mesh GUI seed 3D DDA sprite
viii
skupina voxelů objemová částice v třídimenzionální mřížce sít vertexů tvořících objekt grafické uživatelské rozhraní klíč pro inicializaci pseudonáhodného generátoru algoritmus využívaný pro sledování paprsků dvourozměrný obrázek nebo animace
1. Úvod Hry jsou velmi specifické ve svých potřebách. Při jejich vývoji je potřeba široké spektrum lidí z všemožných oborů. Na vývoji se tak podílejí analytici, programátoři, grafici, animátoři, zvukaři, herní designeři, atd. Tato bakalářská práce bude zaměřená na softwarovou část celého procesu. Každé herní studio se v průběhu vývoje dostalo do stavu, kdy se muselo rozhodnout, jestli využije již existující herní jádro, nebo upraví, popřípadě postaví herní jádro vlastní. Špatné rozhodnutí tohoto problému může dokonce vést k úspěchu nebo neúspěchu hry, neboť nevhodně zvolené herní jádro negativně ovlivní kvalitu grafické stránky hry, rychlost reakce na ovládání, kvalitu zvuku a neschopnost plnit požadavky designérů. Nejprve se podíváme, k čemu takové herní jádro je. Přestože jsou hry velmi rozdílné, všechny potřebují několik společných věcí. Jmenujme například implementaci herní smyčky, vkládání grafických a zvukových prvků do hry a zpracování pohybu. Herní jádro, které by obsahovalo zmíněný seznam funkcionalit, by bylo extrémně univerzální a stále by vyžadovalo značné úsilí pro herní vývojáře. Herní jádra se dělají specifičtěji a přívětivěji pro konkrétní a přesto velmi širokou podmnožinu her. Hry můžeme rozdělit do žánrů, strategie, střílečky, adventury, atd. Každý tento žánr je specifický svými potřebami. U stříleček je potřeba vysoký počet snímků a malý počet detailních objektů do scény. U strategií je situace opačná. Na scéně je třeba tisíce objektů, u kterých příliš nevadí, že při bližším pohledu nevypadají příliš dobře. U adventur je pak situace ještě odlišnější. Vzpomeňme například na adventuru Atlantis (viz obr. 1), velmi propracovaná a detailní grafika byla možná jen díky před-připravení všech scén a následně pouze ukazování jednotlivých snímků. Takový přístup není možný pro ostatní žánry. Herní jádra se vytvářejí pro konkrétní typ hry, aby co nejvíce pomohla hernímu studiu a splňovala konkrétní požadavky daného herního titulu. Jako příklad můžeme uvést střílečku Unreal Tournament (viz obr. 2) a herní jádro postavené pro něj Unreal Engine[1]. Spolu s propracovaným editorem definovaly tvar soudobých her, jako například
Obrázek 1. Atlantis rok vydání 1998.
1
1. Úvod
Obrázek 2. Unreal Tournament 3, hra postavená v Unreal Engine 3.
cyberpunkové Deus Ex[2]. Pro klasický příklad strategie se můžeme podívat na hru Warcraft 3[3] a její herní jádro. S propracovaným herním jádrem se početné komunitě dařilo dělat zázraky a dokonce vytvořit úplně nový herní žánr reprezentovaný hrou Defence of the Ancients[4]. Herní jádra jsou rozdílná a pro konkrétní herní žánr. S voxelovými hrami je to velmi podobné. Přestože Minecraft je ve své podstatě střílečkou, nevěnuje zdroje počítače na překrásnou grafiku, ale na procedurální generování herního voxelového světa a jeho vykreslování co možná do největší vzdálenosti. Část herního jádra, která se stará o herní svět a jeho vykreslování, světla, stíny, atd. by byla z klasického herního jádra pro střílečky nepotřebná, nebo by se musela komplikovaně a neoptimálně upravovat.
1.1. Současný stav herních enginů Na trhu je mnoho kompletních herních systémů pro střílečky. Zmínit můžeme již dříve uvedený Unreal engine, dále pak Crytek engine [5], Source engine [6], Unity (univerzálnější) [7], Ogre (opensource) [8], atd. Všechna tato herní jádra ale stavějí na herní mapě složené z klasického meshe a nemají podporu pro voxelové herní světy. Nepodporují jeho modifikaci, nebo jen v omezené míře. Podporu voxelového herního světa je proto potřeba do enginu dopsat, bohužel to nese mnoho komplikací v podobě potřeby modifikovat i ostatní moduly herního jádra. Výsledné hry proto obsahují značná omezení, přestože díky špičkovým herním jádrům vypadají velice dobře. Tato práce se bude soustředit na udržení značného dohledu ve scéně a neomezenosti herního světa ve všech rozměrech.
1.2. Hry založené na voxelových elementech Může se zdát, že hry založené na voxelech jsou novinkou, ale není tomu tak. Sám autor Minecraftu zmiňuje, že se nechal inspirovat hrou InfiMiner. Jak už název napovídá, v této hře se těží minerály ve dvourozměrném herním světě s procedurálně generovanou mapou. Následující kapitola bude o hrách, které pracují s voxelovým herním světem. 2
1.2. Hry založené na voxelových elementech
Obrázek 3. Ukázka herního prostředí hry Minecraft.
1.2.1. Minecraft Nejviditelnějším zástupcem her s voxelovým herním světem je Minecraft (viz obr. 3). Hra založená na voxelovém světe byla jedna z prvních, které se podařilo herní žánr obsahující voxelový herní svět dramaticky zpopularizovat. I ona ale trpěla značnými problémy při vývoji. Zprvu dokonce obsahovala pouze velmi omezený herní svět, stínování na plochu voxelu (jde stále zapnout v nastavení), nikoli na vertex a další značná omezení. Většinu neduhů postupným vývojem úspěšně překonala a dnes díky moderské komunitě jen vzkvétá. Minecraft přesto nepodporuje osvětlení jako jsme zvyklí z klasických her, místo toho světlo padá po voxelech z nejvyššího místa herní mapy. Nemá tedy ani stíny. Je naprogramován v Jave a využívá grafické aplikační rozhraní OpenGL.
1.2.2. Synthetic world Synthetic world (viz obr. 4) připomíná svým provedením Source engine [6]. Osvětlovací model a GUI vypadá velmi podobně, autoři zřejmě čerpali informace z dokumentace nebo využili přímo některé součásti. Engine podporuje osvětlení i se stíny ze slunce a dynamické střídání dne a noci. Terén je modelován na základě voxelů, ale je dále vyhlazován a vytváří tak plynulou krajinu. Vegetace je vložená rovněž pomocí voxelů, ale ty jsou stejně jako krajina uhlazeny. Hra je zdarma ke stažení na oficiálních stránkách [9].
1.2.3. FortressCraft: Unity Jak už název napovídá, FortressCraft: Unity (viz obr. 4) využívá služeb opensource enginu Unity. To umožnilo autorům velmi rychle postavit kompletní hru a nezabývat se příliš s technickými věcmi. Hra tím zároveň i trpí. Mapa je nahrávána po blocích, zřejmě 32 × 32 × 32 voxelů a je nekonečná ve všech rozměrech, to spolu s nenapsáním enginu na míru, přispělo k až překvapivě krátkému dohledu. Globální osvětlení využívá osvětlovací modulu Unity jádra a neobsahuje stíny. Více na oficiálních stránkách [10]. 3
1. Úvod
Obrázek 4. Synthetic world a FortressCraft: Unity.
Obrázek 5. Blockland a Ace of Spades.
1.2.4. Blockland Blockland je postaven na Torgue enginu (viz obr. 5). Hra se svým grafickým zpracováním podobá legu, obsahuje jednobarevné voxely, které dále tónuje globální světlo i se stíny. Hra je dostupná na herní platformě Steam[11] a je stále ve vývoji. Více na oficiálních stránkách [12].
1.2.5. Ace of Spades Ace of Spades (viz obr. 5) je placenou hrou, mixující Team Fortress[13] od Valve s Minecraftem. Hra je akčně pojatá, cílem bylo vytvořit střílečku, ve které má hráč plně modifikovatelný herní svět. Aby hráči byli dostatečně blízko u sebe, hra nepotřebuje nekonečný herní svět. Ten je naopak velmi omezený a umožnil snížit nároky na server, který se může plně věnovat hráčům a poskytovat co nejnižší latence. Hra neobsahuje dynamické stíny, pouze podle okolí ztmavuje některé vertexy při generování meshe, podobně jako Minecraft. Více na oficiálních stránkách [14].
1.2.6. Terraria Následující dvě hry jsou trochu odlišné od dříve zmíněných. Patří totiž mezi hry s dvourozměrným herním světem. Terraria6 tedy není trojrozměrná a ani nekonečná v jakémkoliv směru, ale určitě si zaslouží být ve výběru, neboť i ona musela řešit podobné problémy jako její trojrozměrné verze. Grafika hry pracuje s pohledem z boku na hráče. Herní svět je složen ze dvou hloubek voxelů. Maximální rozměry mapy jsou 8400 voxelů na šířku, 2400 na výšku a již zmíněné 2 do hloubky. Její paměťová náročnost i celkové technické nároky jsou tedy mnohem menší než u Minecraftu a her jemu podobných. Hra neobsahuje ani dynamické osvětlení nebo stíny. Světla jsou řešena podobným algoritmem přes voxely, jako Minecraft. Díky tomu hra nemá velké požadavky na hardware [15]. Více na oficiálních stránkách [16]. 4
1.3. Porovnání
Velikost světa
Osvětlení1
Počasí2
Typ animací
Minecraft Synthetic world FortressCraft: Unity Blockland Ace of Spades Terraria Starbound Bakalářská práce
Grafické API
Hra
Programovací jazyk
Obrázek 6. Terraria a Starbound.
Java C++ C# C++ C++ C# C++ C++
OpenGL OpenGL Direct3D i OpenGL OpenGL[20] Direct3D i OpenGL OpenGL OpenGL OpenGL
∞ × 256 × ∞ omezená[18] ∞ × ∞ × ∞[19] — 512 × 240 × 512[21] 8400 × 2400 × 2 omezená ×∞3 ∞×∞×∞
V S D S V V S D
ano ne ano ne ne ano ano ano
vertex žádné — — — sprite sprite vertex
Tabulka 1. Seznam her pracující s voxelovým herním světem a porovnání jejich funkcionalit.
1.2.7. Starbound Část vývojářů podílejících se na Terraria se přesunula na vývoj nové hry. Starbound (viz obr. 6) je tak fakticky nástupcem Terrarie. Osvětlení bylo upraveno, hráč má nově k dispozici směrové nebo bodové světlo. To pomáhá atmosféře, když hráč postupuje temnou chodbou s baterkou v ruce, která vytváří reálné stíny. Hra má stále omezený herní svět, ale hráči je umožněno cestovat mezi jednotlivými herními mapami. Je tedy zvláštností. Na rozdíl od ostatních voxelových her Starbound nedovytváří herní svět za chodu, ale místo toho je pomocí herních mechanizmů hráči umožněno aktuální herní svět opustit a teleportovat se na jiný. Více na oficiálních stránkách [17].
1.3. Porovnání Výše zmíněné ukázky voxelových her a jejich funckionality byly shrnuty do následující tabulky. U některých her se bohužel nepodařilo zjistit, jak je konkrétní položka udělaná nebo taková věc nebyla patrná z dostupných materiálů. V úvodní kapitole byla ukázána existující řešení a jejich výtah shrnut do přehledné tabulky. V následujících kapitolách bude popsán samotné herní jádro, nejprve analýza, 1
Osvětlení může být třech typů. Zapečené do vertexů[V], dynamické bez stínů[D] a dynamické se stíny[S]. 2 Hra podporuje počasí, například déšť nebo sněžení 3 Herní mapa je omezená, ale hráč má přístup do 12.667 biliard různých map[22]
5
1. Úvod poté implementace a na závěr testování.
1.4. Shrnutí Základem bude herní modul, který se postará o prvky specifické pro herní jádra, tj. aktualizaci scény, zavolání vykreslovacích funkcí. Od toho se odvíjí část pro zapouzdření herního světa. Terén bude nekonečný a plně modifikovatelný a bude generovaný za běhu hry. Modifikace herního terénu bude implementovaná pomocí vhodného algoritmu a pouze po jednotlivých voxelech. V případě potřeby nebude problém upravit funkcionalitu tak, aby dokázala odstranit i více voxelů najednou. Pro tuto funkcionalitu bude ideální využít systém na posílání zpráv mezi entitami. Další částí herního jádra jsou modely, jejich integrace do světa a animace. Vzhledem ke komplexnosti modelů bude vytvořena pouze základní část týkající se přehrávání. Je pak na uživateli, jak si vykreslování upraví podle sebe, aby odpovídalo přesně jeho požadavkům. Posledním úkolem bude vytvoření simulace počasí. K tomu bude využit generátor částic, ten přirozeně vygeneruje tisíce částic, o které se postará včetně jejich pádu. K počasí se pak váže ještě simulace denní doby a mlhy, i to bude herní jádro umět.
6
2. Analýza V této kapitole probereme analýzu herního jádra a jeho požadavků. V prvních několika podkapitolách budou popsány požadavky, jejich rozdělení na funkční a nefunkční a popis samotných požadavků a jejich motivace. Dále budou popsány jednotlivé moduly herního enginu a jejich funkce.
2.1. Požadavky Ze zadání vyplynula celá řada požadavků, které můžeme rozdělit na funkční (viz obr. 7) a nefunkční (viz obr. 8). Funkční požadavek je funkce, kterou herní jádro bude uskutečňovat. Příkladem může být funkční požadavek na simulaci počasí. Protikladem jsou nefunkční požadavky, které říkají, jaké vlastnosti bude herní jádro mít. Jako příklad můžeme vzít naprogramování v jazyce C++.
Obrázek 7. Funkční požadavky.
2.1.1. Funkční požadavky Základem herního jádra bude herní svět z jednotlivých voxelů. Pro herní mapu se nepoužije otexturovaný mesh, jako je pro hry zvykem. Dalším požadavkem je téměř nekonečná herní mapa a s tím je spojené procedurální generování. Přestože, herní svět nemůže být ze své podstaty nekonečný (konečná přesnost datových typů pro pozice voxelů a chunků, omezení operační paměti, disku, atd.), cílem je dosáhnout dostatečné rozlohy tak, aby se svět jevil jako nekonečný a nešlo v rozumném čase dojít nakonec. 7
2. Analýza Svět bude obsahovat kopce vytvářené pomocí generátoru výškové mapy. Herní svět nemůže existovat bez počasí, proto nebude chybět i zde v podobě deště, sněhu, mlhy. Na závěr jsou zmíněné modely a animace. Přestože se hra zakládá na voxelech, kompletní voxelová grafika nebyla cílem a proto půjdou do herního jádra importovat modely ve formátu obj1 . Shrnutí funkčních požadavků 1. Herní svět postavený na objemových tělesech. 2. Herní mapa téměř nekonečná ve třech rozměrech. 3. Procedurální generování herního světa. 4. Jednoduchá simulace počasí. 5. Modely a jejich animace vložené ve formátu obj.
2.1.2. Nefunkční požadavky Nefunkční požadavky se soustředí na prvky softwaru, který nekoná žádnou funkci. V tomto případě je úkolem napsat herní jádro v programovacím jazyce C++. Tento programovací jazyk byl zvolen pro svou robustnost a rychlost. Grafická část nebude psána v Direct3D, kvůli jeho omezení na operační systém Windows, místo toho bude vyžito OpenGL. To umožňuje využít herní jádro na mnohem větší škále operačních systémů. Shrnutí nefunkčních požadavků 1. Naprogramované v jazyce C++. 2. Grafická část aplikace psaná pro aplikační rozhraní OpenGL. 3. Využít systém posílající zprávy pro komunikaci mezi moduly.
Obrázek 8. Nefunkční požadavky.
2.2. Celkový pohled Herní jádro je specifické svou provázaností (viz obr. 9). Téměř vše potřebuje komunikovat se vším a to vytváří značné problémy s implementací a udržením rozumné struktury aplikace. Vysoká provázanost je jedním z velkých problému při údržbě softwaru a při jeho drobných změnách. Malá změna kódu pak může vyvolat nečekané následky napříč 1
8
Wavefront obj je formát pro reprezentaci trojrozměrných objektů.
2.3. Moduly herního jádra celým systémem, neboť díky vysoké provázanosti není úplně patrné, co se kde děje. Dalším problémem je problematická výměna modulů. S vysokou provázaností systému jde v ruce i nepřiměřené využívání statických metod a proměnných, které je pak třeba speciálně mapovat pro nový modul. Jedním z cílů se bude vyhnout tomuto nešvaru a udělat herní jádro co možná nejčistější.
2.3. Moduly herního jádra Vhodné řešení komplexnosti herního jádra bude jeho rozdělení na jednotlivé moduly, každé se specifickým úkolem. Komunikaci modulů mezi sebou pak obstará speciální modul nebo v případě logických a přímočarých událostí bude komunikace probíhat přímo.
2.3.1. Herní jádro Základním stavebním kamenem bude samotné jádro. Při spuštění programu se začnou provádět instrukce právě v tomto modulu. Zprvu se inicializují všechny objekty. Následovat bude vytvoření vykreslovacího okna, ve kterém se bude zobrazovat herní scéna. K tomu se využije knihovna SFML. Následovat bude spuštění herní smyčky (podrobnější popis v samostatné kapitole) a vyčkávání na ukončovací událost. Po přijmutí požadavku na ukončení se herní smyčka zastaví a začne se s ukončovacím procesem. Odstraní se všechny objekty a zavře okno pro vykreslování.
2.3.2. Modul herního světa Další klíčovou částí herního enginu je samotný modul pro správu herního světa. Modul herního světa bude rozcestí pro další části aplikace jako herní mapa, počasí, entity, atd. Úlohou tohoto modulu je tedy, starat se o potřeby herních prvků. Provádět na nich aktualizace, volat funkce na vykreslování.
2.3.3. Modul s počasím Jedním z požadavků byla simulace počasí, to lze vytvořit pomocí textur se skupinou kapek umístěných do prostoru. Za pomoci vhodně zkombinované mlhy, změny textur a naklonění jednotlivých textur lze docílit velmi realistického a přitom nenáročného efektu. Problém nicméně bude v procházení textur skrz voxely ve členitém a modifikovatelném terénu, proto bude v této práci implementován způsob simulující jednotlivé kapky deště včetně jejich fyziky. Bude implementován modul (viz obr. 10), který se o tento konkretní požadavek bude starat. Modul se bude skládat ze samotného simulátoru počasí a vlastních částic. Úlohou simulátoru bude poskytnout částicím aktualizaci. Konkrétně samotné částice posunout o snímek dál, dále se postará i o vykreslení částic.
2.3.4. Osvětlení Osvětlení budeme řešit pomocí Phongova osvětlovacího modelu (viz obr. [23]). Jedná se o aproximaci reálného osvětlení pomocí tří komponent. První je ambientní složka, která se chová jako základní podkladové světlo, které je všude v herní mapě. Některé, především hororově laděné hry, nastavují hodnotu ambientního světla velmi nízkou až nulovou. Docílí tak absolutní tmy v místech, kde není žádné světlo. Hráč pak opravdu nevidí a je nucen využívat zdroje světla. Moderní hry se s příliš silně nastavenou ambientní složkou světla moc netrápí a bohužel bývá ve hře vidět i v absolutní tmě. To může 9
2. Analýza
Obrázek 9. Provázání jednotlivých tříd.
10
2.3. Moduly herního jádra
Obrázek 10. Třídy pro počasí.
kazit herní zážitek nebo snižovat obtížnost. Další složkou Phongova osvětlovacího modelu je složka difuzní (viz obr. 11). Tu je třeba vypočítat za pomoci normály plochy, na kterou světlo dopadá a vzdálenosti světla. Difuzní složka tvoří hlavní prvek Phongova osvětlovacího modelu. Zrcadlová komponenta je aproximací odlesku materiálu. Dodává osvětlenému prvku lesklost, tedy je potřeba postupovat při zadávání parametrů do zrcadlové složky opatrně. Přestože toto herní jádro bude využívat Phongův osvětlovací model, samozřejmě existují i jiné způsoby jak scénu osvětlit. Minecraft se vydal cestou záplavového šíření světla a jeho následným zapečením do meshe. Oproti Phongově osvětlovacímu modelu se značně liší. Osvětlení není dynamické, není počítáno při každém snímku, ale pouze při úpravě terénu. Algoritmus umístí do prázdných voxelů v nejvyšším patře herní mapy světlo a postupuje po voxelech směrem dolů. Pokud je voxel prázdný nebo průhledný, algoritmus zapeče do voxelu světlo z horního voxelu, nebo z okolních snížených o útlumovou hodnotu. Aby algoritmus mohl fungovat. je potřeba konečná herní mapa na výšku. To se dá obejít, například považováním dosud nevygenerovaných chunků za prázdné, nicméně i to by vyžadovalo při každém přepočtu analyzovat veškerou mapu nad upravovaným voxelem.
2.3.5. Vytváření herní mapy Pro procedurální vytváření herní mapy je potřeba využít nějaký sofistikovanější generátor náhodných hodnot, než je funkce rand a její podobné. Šum, který by rand vytvořil, by nebral ohled na hodnoty v okolí. Skákal by mezi maximem a minimem zcela náhodně. My ale potřebujeme plynulý přechod, aby se po mapě dalo chodit a vypadala jako terén. Šumu který produkuje plynulý přechod mezi hodnotami se říká gradientní šum. Druhým úkolem našeho generátoru je potřeba generovat herní mapu z parametru. Tomuto parametru budeme říkat seed a po vložený tohoto seedu do generátoru by měla vyjít vždy stejná herní mapa. Generátorů šumu, které by vyhovovaly, je celá řada. Prvně se podíváme na Perlinův šum, který umí procedurální generování gradientního šumu. Je hojně využíván umělci při vytváření efektů - ohňů, kouře, mraků a výškových map. Poslední zmíněné je právě využití, které potřebujeme pro generování herní mapy. V roce 2001 přišel autor Perlinova šumu s novým algoritmem, který pojmenoval Simplex šum. 11
2. Analýza
Obrázek 11. Ukázka difuzní složky(vlevo) a difuzní spolu se zrcadlovou složkou(vpravo) Phongova osvětlovacího modelu.
Obrázek 12. Porovnání Perlinova šumu (vlevo) a simplex noise (vpravo).
Ten je do výstupu značně podobný (viz obr. 11), ale nevyžaduje takové hardwarové nároky a je rychlejší především ve výpočtu šumu ve vyšších dimenzích. Jeho rychlejší výpočet byl hlavním důvodem pro využití v herním jádře.
2.3.6. Komunikace herních modulů V úvodu jsem zmiňoval potřebu vyvarovat se vysoké provázanosti jednotlivých komponent. Dejme příklad. Hráč při vstupu na určitou způsobí změnu počasí. Jak taková věc bude fungovat? Jako nejlepší způsob se jeví využit návrhového vzoru pozorovatel[24]. Tento návrhový vzor přiděluje objektům role vydavatele a předplatitele. Vydavatel vydá zprávu a všichni jeho předplatitelé ji obdrží. Jako ukázku můžeme využít situaci, kdy hráč (vydavatel) spadne z vysoké výšky. Vydá tedy zprávu informující předplatitele o pádu. Zvukový modul (předplatitel) poslouchá na takové zprávy a po přijetí přehraje zvuk. Programovací jazyk C++ má na to obzvláště vhodné podmínky, zajišťující mini12
2.3. Moduly herního jádra
Obrázek 13. Herní smyčka.
mální nárůst prodloužení provádění jednotlivých událostí.
2.3.7. Vykreslování voxelů Samotné vykreslování by šlo udělat triviálně, pomocí průchodu voxelového pole a vykreslení každého voxelu zvlášť. Výsledkem by ale byl masivní odpad v podobě ploch, které se dotýkají dalšího voxelu a potřebě volat vykreslení pro každou kostku. Bylo by to ohromné plýtvání zdrojů, jehož důsledkem by byla neschopnost vykreslit více než jeden chunk v rozumném čase. Samozřejmě by se situace dala vylepšit, při generování jednotlivé vertexy ukládat do společného zásobníku. Tím eliminujeme množství vykreslovacích volání, ale přibude problém s tím, co se bude dělat, pokud je třeba některý voxel odstranit. Jednou možností je spolu se zásobníkem vertexů vyrábět mapu, která bude ukazovat kde jaký voxel začíná, případně kde končí nebo jak je dlouhý. Výhodou takového řešení by byla absence potřeby přegenerovávat mesh po změně, ale s tím spojené komplikace při údržbě. Druhou cestou je rozdělit herní svět na jednotlivé skupiny voxelů, říkejme jim chunk, a pracovat s nimi odděleně. Výhodou tohoto řešení je konstantní náročnost při upravení libovolného množství voxelů v daném chunků. Nevýhodou pak potřeba opětovně generovat meshe z chunků, protože pouhá úprava meshe není možná. V herním jádře byla implementována možnost druhá, tedy rozdělení herního světa na chunky a s těmi se pracuje samostatně. Bylo by možné využít obou metod a dosáhnout tak optimálního chodu jak při malých změnách, tak při velkých. Samozřejmostí obou metod je při generování ploch jednotlivých voxelu kontrola protějšího voxelu, pokud se tam nachází další neprůhledný voxel, nebude se zde plocha generovat. Tato optimalizace je potřeba v každém případě, neboť šetří enormní množství zdrojů.
2.3.8. Herní smyčka Herní smyčka[25] (viz obr. 13) je část kódu, ve které se provádí aktualizace a vykreslení herní scény. Aktualizací se myslí upravení pozic jednotlivých herních entit, zpracování požadavků od uživatele a samotné vykreslení. Tato sada operací se děje pořád dokola, dokud samotná hra neskončí. while ( isRun ning ) { // z p r a c o v a t u d a l o s t i od u z i v a t e l e processUserInput ( ) ; // a k t u a l i z o v a t scenu update ( ) ; 13
2. Analýza
// v z k r e s l i t scenu draw ( ) ; } Přestože, výše napsaná herní smyčka logicky neobsahuje problém a podobné se dokonce využívali na starých počítačích, dnes už díky variabilní frekvenci procesoru a dalším okolnostem nemohla fungovat. Jejím hlavním problémem je absence měření času. Pokud entita neví o kolik se od poslední aktualizace posunul čas, nemůže vědět, kam se má aktualizovat. Proto je třeba zavést měření času pro jednotlivé aktualizace a tento delta čas pak předávat jednotlivým aktualizovaným entitám. GameTime gameTime ; while ( isRun ning ) { // c a s od p o s l e d n i a k t u a l i z a c e deltaTime = gameTime . getDeltaTime ( ) ; // v y r e s e t o v a n i h od in gameTime . r e s e t ( ) ; p r o c e s s U s e r I n p u t ( deltaTime ) ; update ( deltaTime ) ; draw ( ) ; } Ukázaný pseudokód herní smyčky s měřením času je už dostatečný a plně funkční, nicméně lze ještě optimalizovat. Tato herní smyčka bude provádět úkony, co nejrychleji to půjde. To má výhodu v rychlé reakci dané hry, které ocení především hráči náročných FPS stříleček, ale obecně hra působí příjemně a funkčně. Nevýhodou je kompletní vytížení jádra, které se snaží co nejrychleji provádět instrukce. Smyčku můžeme vylepšit přidáním omezení počtu průchodu za sekundu, ideálně na obnovovací frekvenci monitoru. GameTime gameTime ; while ( isRun ning ) { deltaTime = gameTime . getDeltaTime ( ) ; gameTime . r e s e t ( ) ; p r o c e s s U s e r I n p u t ( deltaTime ) ; update ( deltaTime ) ; draw ( ) ; // c e k a t na d a l s i a k t u a l i z a c i s l e e p ( 1/60 − gameTime . getDeltaTime ( ) ) ; } Výsledná smyčka už je velmi dobrá, příliš nezatěžuje procesor, šetří tedy výkon pro další vlákna nebo energii a přesto poskytuje dostatečnou rychlost, aby hráč nic nepoznal.
2.3.9. Entity, modely, animace Další částí potřebnou pro herní jádro jsou modely a jejich animace (o animacích více v [25]). Naivním způsobem by bylo pro každou entitu načíst její model, ale pro více 14
2.3. Moduly herního jádra entit by se pak muselo držet v operační paměti mnoho kopií stejných modelů. Z tohoto důvodu je třeba oddělit entitu od modelu a pracovat s nimi samostatně. Každá entita tedy bude mít odkaz na svůj model. Protože entity je potřeba někde seskupit a hromadně na nich volat akce, bude třeba ještě správce, který se o ně postará. Naložení s animacemi je o poznání komplikovanější. Existují dva hlavní způsoby, jak mohou být modely animovány. Pohyb entit bude řešeno ve dvou krocích. Prvním je určit kterým bod, kam se chce entita dostat. Následuje zjištění, jestli se má entita otočit vlevo, nebo vpravo doplněný krokem vpřed. Kolize budou řešeny porovnáním vzdáleností hráče od okolních entit. Kosterní animace Kosterní animace se podobají reálnému světu. Do objektu se vloží kostra (viz obr. 14), ke které se připoutají vertexy. Ty se pak pohybují podle přiřazené kosti, ty jsou navíc spojeny ve stromové struktuře. Pokud se tedy pohne páteř, pohyb se přenese na kosti rukou a z kostí rukou na vertexy rukou. Nevýhodou je větší náročnost na výpočetní výkon procesoru. Animátor navíc nemůže animovat drobné detaily nebo je donucen použít velké množství kostí a umístit je například do rtů, tváří, atd. To sice samozřejmě ničemu nevadí, není smyslem kostí, aby reprezentovali reálnou strukturu kostí, ale celková komplexnost rychle narůstá. Vertexová animace Alternativou k dříve uvedené animaci je nepoužít kosti a místo toho vyexportovat z grafického editoru přímo model v jednotlivých snímcích animace. Výhody jsou vidět na první pohled. Žádné nároky na výpočetní výkon procesoru. Animace jsou už hotové a jdou rovnou do grafické karty. Ta interpoluje pozice vertexů, aby pohyb neskákal. Nevýhodou je tedy pouze násobně větší velikost modelu. Výhodou je navíc, že animátor má absolutní kontrolu nad modelem. Může animovat jednotlivé vertexy, jak se mu zlíbí. Tento postup byl využíván především v dřívějších hrách, kdy procesor nebyl dostatečně výkonný, aby v reálném čase zvládal provést všechny animace. Najde však využití i dnes pro animace, které jsou příliš komplexní.
15
2. Analýza
Obrázek 14. Kostra uvnitř demo objektu.
16
3. Implementace Třetí část této práce se bude zabývat uskutečňováním dříve popsaných teoretických prvků. Nejprve se podíváme na konkrétní prostředky, programovací jazyk, knihovny. Následně projdeme jednotlivé moduly a prvky herního jádra. Nejprve bude popsáno samotné herní jádro, následovat bude herní svět a jeho prvky. Dále bude popsaná implementace vykreslování a generátoru mapy. Kromě dalšího budeme implementovat i 3D DDA algoritmus pro procházení voxelové mapy a entity. Na závěr se pak podíváme na části implementace, které šli udělat jiným způsobem.
3.1. Programovací jazyk a knihovny Pro implementaci bude využit jazyk C++ a pro grafickou stránku aplikace OpenGL. Důvody jsou prosté, multiplatformovost a vyzrálost. Nevýhodou může být komplikovaná instalace a kompilace projektu, zvláště po nasazení několika knihoven. Dalším problémem může být jisté ztížení samotné práce oproti programování například v C#, jelikož C++ je značně přímočarý programovací jazyk. Dále pak samotný herní engine má svá specifika a vyžaduje funkce, které jsou sice potřeba pro každé herní jádro, ale v programovacím jazyku nemají co dělat. Je tedy logické využít dostupných knihoven a zvýšit tak produktivitu a kvalitu samotného herního jádra. Je nesmysl programovat již věci jednou naprogramované. První využitou knihovnou na seznamu je Boost [26] od Googlu. Jedná se o ohromnou knihovnu, která dokáže vypomoct snad se vším. Některé její části byly postupně dokonce zahrnovány do samotného C++. Konkrétně v mé práci se mi bude hodit jejich persistence instancí a vícerozměrné pole, ale její využití se najde i v případném rozšíření herního jádra o sítový modul. Boost disponuje velice kvalitní neblokující UDP síťovou komunikací. Simple Fast Multimedia Library [27] je druhou knihovnou, bez které by se toto herní jádro neobešlo. Prostředky, kterými disponuje, jsou velmi podobné XNA [28] od Microsoftu. To bohužel už léta není podporované a zároveň využívá Direct3D. SFML je ve světě C++ velmi čerstvou a moderní záležitostí a v této práci bude využita například pro nahrávání shaderů, stopky pro měření herního času, nahrávání textur a správu okna operačního systému. Herní jádro by se samozřejmě neobešlo ani bez dalších, neméně důležitých knihoven, které pomohly v konkrétních úlohách. Zmínit musím GLM [29] pro maticovou algebru využitou pro vykreslování, GLEW [30] pro podporu vyšších verzí OpenGL, dále pak Assimp [31] pro práci s modely a nakonec UnitCpp [32] pro unit testování.
3.2. Moduly herního jádra Herní jádro se bude skládat z jednotlivých modulů pro zajištění optimální provázanosti a separace jednotlivých prvků. V následujících podkapitolách projdu jednotlivé moduly a popíši jejich funkci a konkrétní implementaci. 17
3. Implementace
3.2.1. Modul herního jádra Základem je třída Game, která se postará o vytvoření a ukončení samotné hry. Na samotném začátku si zaregistruje událost pro ukončení a je tak schopna reagovat například na klávesu ESC nebo zmáčknutí křížku okna aplikace. Po její inicializaci se na ni zavolá metoda run, která spustí samotnou hru. Tato metoda, kterou obsahuje každé herní jádro, je implementovaná jako nekonečná smyčka, v které se neustále opakuje vykreslit, aktualizovat, vykreslit, aktualizovat, atd. Aby hra běžela co možná nejrychleji, neobsahuje limit na počet snímků za sekundu. Namísto toho je instance GameTime předávána všem objektům. Ti pak vědí, o kolik se posunul čas od poslední aktualizace a mohou podle toho upravit své operace. Do modulu herního jádra bych ještě zahrnul třídu Window. Ta na svém začátku inicializuje GLEW a spravuje okno operačního systému. Registruje událost na ukončení aplikace a vyměňuje vykreslovací zásobník grafické karty.
3.2.2. Herní svět a jeho prvky Začneme od nejmenší složky herního světa od jednotlivých voxelů. Ty jsou reprezentovány pomocí datového typu short namapovaného na enum. Jednotlivé voxely jsou uloženy v trojrozměrných maticích. Každá matice 32 × 32 × 32 voxelů je reprezentována třídou chunk. Ta zapouzdřuje pole a poskytuje k němu různé přístupové metody. Jako příklad můžeme uvést metodu Block placeBlock(vec3, Block). Při vkládání voxelu do chunku, respektive do pole se nám automaticky vrátí voxel, který jsme přepsali. To je užitečné z herního hlediska, pokud budeme voxely například těžit, nemusíme prvně zjišťovat co na onom místě je, ale rovnou to vyměnit za vzduch. Hezkým vylepšením chunků je jejich znalost, jestli jsou prázdné. To umožňuje optimalizaci jak při vykreslování, kdy daný chunk můžeme s klidným srdcem vynechat, tak i při stavbě meshe. Pokud vložíme prázdný voxel do prázdného chunku, není třeba daný voxel přegenerovávat, neboť víme, že chunk byl prázdný už předtím. Chunk nám dále umožňuje uložit svoji instanci pomocí rozšíření z Boost knihovny. Každý chunk má pro optimalizaci operací při generování meshe odkazy na šest sousedů. Uspořádání chunků v herní mapě si můžeme prohlédnout na obrázku 15. Dalším krokem od chunků výše je samotná Mapa. Ta drží jednotlivé chunky pohromadě v cyklickém trojrozměrném poli. Při vytváření si registruje události kolem změny pozice kamery, takže pokud hráč přejde s kamerou na jiný chunk obdrží o tom informaci, spolu s pozicí hráče. To spustí koloběh událostí. Nejprve je třeba určit směr, kterým hráč změnil chunk oproti původní situaci. Tímto směrem se musí posunout ukazatel v trojrozměrném poli chunků. Následuje vygenerování meshů pro okrajové chunky, které tímto pohybem přibyly a nakonec vygenerování výškové mapy a voxelů pro úplně krajní chunky. Bylo by vhodné vysvětlit ještě, jak samotná mapa drží ony chunky. V trojrozměrném poli jsou ve všech buňkách chunky. Každý chunk má odkaz na svoje sousedy. Komplikace nastává co s okrajovými chunky. Ty sice mají sousedy, ale soused je prostě špatný chunk. Tato situace je řešena tak, že vykreslovaná část pole je o dva chunky do každého směru menší. Díky tomu mohu mesh chunku bezpečně vygenerovat a bez artefaktů vykreslit. Nevýhodou tohoto řešení je, že jsou drženy okrajové chunky pouze pro informaci o jejich hraně. To ale příliš nevadí, velikost jednoho chunku je 65536b. V operační paměti jich tedy můžeme mít stovky a nebude to klást žádná omezení. 18
3.2. Moduly herního jádra
Obrázek 15. Grafická reprezentace cyklického bufferu a jeho krajů pro dvourozměrný případ. Tmavě modře jsou nevykreslované okraje mapy, oranžově je střed mapy.
3.2.3. Vykreslování O vykreslování se každá komponenta musí postarat sama. Jednotlivé chunky jsou natolik specifické, že pro vykreslení musejí nejprve vygenerovat mesh, ten uložit a následně nahrát do grafické karty. U modelů je postup jiný. Nejprve Assimp nahraje model i s animacemi. Celý se následně přesune do grafické karty. Třetí specialitou, kterou je třeba vykreslit je počasí a jeho částice. Všechny z těchto prvků mají vlastní shadery, proto před samotným vykreslením požádají kameru o nahrání modelové, pohledové a projekční matice do shaderu. Hra podporuje i vykreslování mlhy, která houstne se vzdáleností od kamery. Vše je vidět na přiloženém obrázku 16.
3.2.4. Generátor mapy Dynamické vytváření mapy je dalším specifickým problémem, s kterým se musí voxelové herní jádro potýkat. V klasických herních jádrech je herní mapa konečná a hlavně připravená dopředu ve formě meshe. Herní jádro si pak přečte tento mesh a použije ho pro podklad i pro výpočet kolizí, respektive minimální výšky na jakou se hráč může dostat. V případě voxelového herního jádra je situace diametrálně odlišná. Namísto meshe pro zem je použit algoritmus, který generuje výškovou mapu za běhu hry. Výškovou mapu je možné generovat různými způsoby. Triviálním příkladem je využít náhodných hodnot pro naplnění výškové mapy. Takový přístup má ale značnou nevýhodu, neboť výsledná výšková mapa bude vypadat jako šum. Určitě by šlo výsledek vyhladit, respektive použít jen jako řídící body a interpolovat mezi nimi, ale existují i mnohem lepší a kontrolovatelnější řešení. Takovým je použít Perlinův šum, nebo Simplex noise. V herním jádře je použit simplex noise pro generování herní mapy. Ten je reprezentován 19
3. Implementace
Obrázek 16. Demoscéna včetně mlhy a vzorového modelu.
třídou SimplexNoise. Tu zapouzdřuje MapNoise pro pohodlnější práci při generování chunku a další optimalizace. Výsledná výšková mapa je pak příhodně umístěná do herního prostoru a všude pod ní jsou umístěny voxely. Všude nad ní je naopak vzduch. Níže uvedu okomentovaný kus kódu, kterým se generuje chunk z pohledu herní mapy. // v y t v o r e n i noveho chunku pro u r c i t o u p o z i c i Chunk* chunk = new Chunk ( p o s i t i o n ) ; /* * v y g e n e r o v a n i v y s k o v e mapy pro zadanou p o z i c i * v y s k o v a mapa j e v j e d n o d i m e n z i o n a l n i m p o l y i n t e g e r u * pro p r i s t u p k p r v k u j e t r e b a p o c i t a t a + 32 * b */ int * f i e l d = _mn. g e t H e i g h t F i e l d ( p o s i t i o n . x , p o s i t i o n . z ) ; // p r e s v s e c h n y v o x e l y for ( int i = 0 ; i < 3 2 ; ++i ) { for ( int j = 0 ; j < 3 2 ; ++j ) { f o r ( int k = 0 ; k < 3 2 ; ++k ) { // pokud j e v o x e l n i z nez v y s k o v a mapa , // p r i p r a v t r a v u , j i n a k v z d u c h Block b = ( k + p o s i t i o n . y * SIZE ) < f i e l d [ i + j * 32] ? Block : : GRASS : Block : : AIR ; // p r i p r a v v e k t o r pro u m i s t e n i noveho v o x e l u s f : : Vector3i p = s f : : Vector3i ( i , k , j ) ; // u mi s t k o n k r e t n i v o x e l do chunku 20
3.2. Moduly herního jádra chunk−>p l a c e B l o c k ( p , b ) ; } } } // smaz v y s k o v o u mapu delete [ ] f i e l d ;
3.2.5. Komunikace modulů U komplikovanějších programů je potřeba zajistit nízkou provázanost jeho jednotlivých částí. Srdcem komunikačního modulu je tedy EventMessagingSystem, který obsahuje pole možných událostí. Pro každou událost obsahuje odkaz na seznam událostí, které je třeba informovat. Extrémní výhodou tohoto uspořádání je pouze minimální zpomalení samotné aplikace. Není třeba procházet pole při hledání, komu danou událost odeslat. Druhou částí tohoto modulu je IEventMessagingSystem. Tuto část dědí třídy, které se chtějí podílet na komunikaci. Obsahuje metody jak pro odeslání události, tak i pro registraci nebo odhlášení se z registrovaných událostí. EventMessagingSystem spolu s Logovací třídou jsou jediné dostupné přes statické volání. Nejprve se podívejme, jak instance zaregistruje pro poslouchání zpráv. // R e g i s t r a c e kamery pro n a c t e n i MVP m a t i c e EventMessagingSystem em = EventMessagingSystem : : g e t I n s t a n c e ( ) ; em . R e g i s t e r ( Events : : eveCameraDrawWeather , this , ( C a l l b a c k ) & Camera : : drawWeather ); Na událost už instance poslouchá, následující kód se týká instance, která žádá vykonání události. // Jeho n a s l e d n e z a v o l a n i p o s t ( Events : : eveCameraDrawWeather , NULL, 0 ) ;
3.2.6. Pomocné třídy Kvůli využití dvou různých knihoven pro práci s grafickou stránkou aplikace, tedy SFML a GLM bylo potřeba převádět vektory poskytované jednou knihovnou do řeči knihovny druhé. Dále pak bylo potřeba usnadnit vypisování vektorů do std::out a podobné drobnosti. Pro tento úkol byla vytvořena Helper třída se statickými funkcemi. Při debugování generování chunků se rovněž vyskytl problém s příliš velkým množstvím údajů potřebných k analýze. Byla proto vytvořena logovací třída ukládající zapsaná data do souboru pro pozdější analýzu.
3.2.7. Procházení voxelů pomocí 3D DDA Hráči je umožněno volně manipulovat s jednotlivými voxely pouze pomocí klepnutí myší pro aktivaci a vektorem pohledu kamery pro zaměření voxelu. Bylo tedy třeba najít vhodný algoritmus (více v [33]) pro samotné vybrání vhodného voxelu ze zadaného vektoru. V herním jádře je algoritmus pro průchod voxelů ze zadaného vektoru reprezentován třídou DDA a implementuje jedinou metodu traverse. 21
3. Implementace static s f : : Vector3i * traverse ( const glm : : vec3& pos , // p o z i c e const glm : : vec3& n d i f , // n o r m a l i z o v a n y smer int l e n g t h // d e l k a ) { // p r i p r a v i m e p o l e v e k t o r u , do k t e r e h o // p o s t u p n e u l o z i m e s o u r a d n i c e v o x e l u s f : : V e c t o r 3 i * r e t = new s f : : V e c t o r 3 i [ l e n g t h ] ; // // // // // // //
... n a s t a v e n i parametru step − v e k t o r smeru n a s l e d u j i c i h o v o x e l u tMax − v kterem m i s t e p a p r s e k p r e k r o c i p r v n i v o x e l t D e l t a − u r c u j e j a k d a l e k o musi p a p r s e k d o j i t v j e d n o t k a c h tMax , aby d o r o v n a l d e l k u v o x e l u ...
for ( int i =0; i
3.2.8. Entity Implementace entit byla rozdělena na tři části (viz obr. 17). První je třída EntityManager, která drží samotné entity a deleguje jim akce na aktualizaci a vykreslení. Rovněž 22
3.2. Moduly herního jádra se stará o shader potřebný pro animace. Dalším krokem je třída Entity, která slouží jako mezikrok mezi modelem a managerem. Při inicializaci si řekne o model, který potřebuje a pak už jen deleguje aktualizace a vykreslování. Její důležitost je nicméně v pro implementaci herních prvků. Právě do entity se hodí vložit život, mana a podobné atributy, nicméně to už je pak na konkrétní hře. Posledním krokem je implementace modelu. Tato třída při vytvoření načte model včetně animací a disponuje metodami pro vykreslení jak modelu v animaci, tak modelu ve výchozí podobě. Metoda pro vykreslování nezvykle oproti ostatním potřebuje transformační matici od entity, neboť model sdílí vícero entit a není možné tuto transformaci držet v modelu. Byla implementována i podpora kolizí mezi hráčem a entitami, které jsou počítány pomocí aproximací koule.
3.2.9. Počasí Počasí bylo implementováno pomocí částicového systému. Každá kapka je reprezentována vlastním objektem a takové řešení vyžaduje několik optimalizací ze strany programu. Pro každou aktualizaci je potřeba jednotlivé kapky posunout, aby jejich stav odpovídal nové pozici. K tomu je potřeba iterovat přes celé pole s jejich objekty a to stojí drahocenný čas, obzvláště pokud jsou kapek miliony. Není možné umístit kapky přes celou mapu, místo toho je využito triku, při kterém se kapky umisťují pouze v okolí kamery. Pokud se kapka vzdálí, je automaticky zresetována. Pokud kapka dopadne na zem, není odstraněna a vytvářena nová, místo toho se resetují její souřadnice, aby byla opět nad kamerou. V demoscéně je zmíněné chování dobře patrné díky agresivnímu nastavení kapek, pokud se kapkám nastaví vhodnější parametry, bude celý proces nepostřehnutelný. Na kapky dále působí triviální simulace větru reprezentovaná kmitavým vektorem přičítaný při aktualizaci. // i n i c i a l i z a c e v e k t o r u v e t r u s t a t i c glm : : vec3 wind ( 0 , 0 , 1 ) ; // p r e s v s e c h n y c a s t i c e for ( int i = 0 ; i < MAX_PARTICLES; ++i ) { // . . . // a k t u a l i z u j c a s t i c i // . . . } // p r i p r a v e n i nahodneho posunu v e t r u f l o a t r o t = 1 0 . 0 * time . a s S e c o n d s ( ) * f r a n d ( ) ; // r o t a c e v e t r u o nahodne c i s l o wind = glm : : r o t a t e Y ( wind , r o t ) ;
Obrázek 17. Rozvržení tříd pro entity.
23
3. Implementace
Obrázek 18. Grafická reprezentace chunku o velikosti 32 × 32 × 32 voxelů.
3.3. Alternativy implementace Jako každý software i u herního jádra dojde autor do míst, kde se musí rozhodnout jak danou věc implementovat. Přitom může jít o změny drobné, a pokud se ukáže, že tudy cesta nevede nebo řešení není proste optimální, je levné vše vrátit a vydat se cestou druhou. V případě této práce se tak může jednat o postup při herního světa a postupu jakým se staví herní mapa. Některá řešení se ukážou jako částečně přijatelná a je třeba je doplnit o řešení z druhé cesty. Zde se taková věc týká způsobu, jakým se upravují meshe chunků. A samozřejmě poslední možností je celkově špatné rozhodnutí, které by mohlo znamenat začít s prací na herním jádře od začátku.
3.3.1. Herní mapa Prvním větvením, na které jsem při implementaci a analýze narazil byl způsob, jakým postavit a držet herní mapu. Při pohledu jakým Minecraft načítá herní mapu je zřejmé, že postupuje po chunkách z 16 × 256 × 16 voxelů. Mapa je tedy držena v oddělených chunkách, kde každý chunk obsahuje pole pro 65536 voxelů. Chunk (viz obr. 18) odkazuje na svoje sousedy a při vykreslování si sám vytvoří mesh. Takový přístup je logický, umožňuje dobré následné separování mapy pro více vláknové zpracování a je to způsob, jakým je implementováno i toto herní jádro. Další výhodou tohoto postupu je dynamická změna velikosti herní mapy za běhu aplikace. Alternativním způsobem je uložení herní mapy do obřího pole voxelů, například velkého pro 512 × 512 × 512 voxelů. Zprvu šílený nápad má i svoje kouzlo. Odpadá práce s chunky, vše by řešila třída zastřešující toto pole. Odpadly by i dotazy do sousedních chunků, při stavění meshe, nicméně ty by se stejně museli generovat z pod segmentů kvůli limitu grafické karty.
3.3.2. Animace U animací byla situace poněkud jiná. Na výběr bylo z skinning animace, kdy se animuje dle kostry, nebo pomocí snímků modelu. Kosterní animaci využívají velká herní 24
3.3. Alternativy implementace studia a herní jádra. Nevýhodou je ale složitá implementace a především náročnost na výrobní proces animace a modelu pomocí opensource grafického editoru Blender[34] a následný import do herního jádra. Kvůli komplikovanému vyrobení a exportování modelu s animací z opensource grafického editoru byla implementována podpora pro animace pomocí snímků modelů.
3.3.3. Herní framework XNA Herní framework XNA[28], vytvořený Microsoftem pro Xbox a Windows, byl jednou z možností, v čem implementovat voxelové herní jádro. Je postaven pomocí programovacího jazyka C# a využívá Direct3D aplikační rozhraní. Jeho vývoj byl ale po roce 2011 ukončen. Nepodporuje tedy moderní technologie, není multiplatformní, pokud nepočítáme Xbox. Jeho další nevýhodou je absence možnosti zkompilovat výsledné herní jádro pro podporu 64bitů. To obyčejně nevadí, ale pro Herní jádro zaměřené na procedurálně generovaný voxelový herní svět bude brzy omezujícím faktorem.
25
4. Testování Stejně jako ve škole jsou žáci podrobení testování, i testování softwaru je důležitou součástí vývoje, přesto je kvůli zpravidla časovému nebo finančnímu omezení zcela vypuštěno nebo omezeno. V následující kapitole je popsán způsob, jakým bylo herní jádro testováno a jak testy dopadly.
4.1. Testování pomocí demo scény U grafických aplikací je velký problém provést klasické unit testování. Přestože je možné otestovat různé základní funkce herního jádra, samotný výstup na monitor unit test nevidí. Proto je třeba testovat herní jádro pomocí demo scény. Herní jádro již obsahuje připravenou demo scénu a po spuštění je zobrazena. Zprvu je testováno samotné načtení grafického API. Využito je OpenGL ve verzi 3.3, hned na to se spouští okno z operačního systému. Před samotným vykreslením do okna aplikace je nejprve potřeba vygenerovat výškovou mapu. Následuje Vygenerování chunků, meshů, inicializace testovacího počasí a dalších součástí. Na závěr se vkládá demo model s animací pohybu. Pokud se vše provede bez chyby, aplikace se spustí a na obrazovce bude vidět vykreslená scéna (viz obr. 19). Tester pokračuje v testování pomocí vstupů. Může otestovat kolize, tím že nebude moct projít skrz herní mapu. Dále lze otestovat procedurální generování herního světa, při kterém zároveň testuje přegenerování částic počasí způsobené pohybem hráče. Při cestě aplikace je vidět i práce osvětlení (světlo je umístěno v kameře) a střídání dne a nocí. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
Testování kompatibilního grafického adaptéru pro OpenGL v3.3 Okno operačního systému Generování výškové mapy Generování meshu Ukládání meshů do grafické karty Počasí Načtení modelu s animací pohybu Vykreslení animace na obrazovce Zpracování vstupu uživatele Phonguv osvětlovací model Kolize proti herní mapě testovacímu modelu Procedurální generování herního světa Přegenerování částic počasí Ukončení aplikace
4.2. Unit testování Druhým typem testování, které bylo použito pro testování herního jádra, je unit testování. Přestože název zmiňuje unity, co nejkratší kusy kódu, je možné pomocí unit testů testovat i ucelené funkce programu. V herním jádře je tímto způsobem otestováno například ukládání herní mapy na disk. Uživatel tak pustí test, v něm se vygeneruje 26
4.3. Testování rychlosti vytváření chunku
Obrázek 19. Vykreslená demo scéna.
chunk obsahující data pro terén. Celý objekt se uloží na disk. Test pokračuje vytvořením nového chunku načtením dat z disku a porovnáním s původním. Dalším částí, která je otestovaná pomocí unit testů, je komunikační modul pro posílání zpráv mezi objekty.
4.3. Testování rychlosti vytváření chunku Při modifikaci herního světa je potřeba přegenerovat mesh chunku. Dosáhnutí přijatelného a neomezujícího času bylo jednou z klíčových úkolů tohoto herního jádra, neboť uživatel očekává okamžitou odezvu na provedenou změnu. Je velmi rušivé, pokud se voxel vykreslí až o snímek nebo dokonce více později. Cílem bylo tedy dosáhnout standardu dnešních monitorů a vytvořit nový chunk a mesh do 1/60 sekundy. Testování proběhlo na chunku speciálně vytvořeném pro toto testování, kdy obsahoval téměř poloviční počet voxelů uskupených tak, aby mezi každým byla vždy mezera. Takové seskupení je nejhorší možné, generuje se maximum stěn. Bylo provedeno třicet měření, které obsahovalo i výpočet DDA algoritmu a zpracování událostí. Naměřené maximum bylo 7.546ms s a průměr 5.1ms. Je tedy patrné, že herní jádro nemá problém s přegenerováním meshe pod 16ms ani v nejhorších podmínkách. // v y t v o r e n i a z a p n u t i s t o p e k s f : : Clock c ; // k o n t r o l a z m a c k n u t i k l a v e s y pro o d e b r a n i v o x e l u i f ( s f : : Keyboard : : i s K e y P r e s s e d ( s f : : Keyboard : : E ) ) { 27
4. Testování glm : : vec3 *p [ 2 ] ; p [ 0 ] = &p o s i t i o n _ ; p [ 1 ] = &d i r e c t i o n _ ; // o d e s l a n i pozadavku na o d s t r a n e n i v o x e l u Post ( Events : : eveDeleteCube , p , 2 ) ; } // v y p s a n i namereneho casu s t d : : cout<
28
5. Závěr Cílem práce bylo vytvoření herního jádra pro hry s voxelovým herním světem. Navrhnutí algoritmů pro řešení konkrétních problémů týkajících se voxelového herního světa a jejich implementace. Výsledný základ herního jádra umožňuje generování herního světa z voxelů a jejich modifikaci. Herní jádro je rovněž schopné simulovat počasí a střídání dne a noci. Velkým rozdílem vypracovaného herního jádra je nekonečná herní mapa ve všech rozměrech. To ho činí unikátního oproti ostatním hrám stavějícím na voxelové herní mapě. V herním jádře je rovněž implementována podpora počasí a animací, u kterých bohužel není kompletně implementovaný mechanismus pro přehrávání a zastavení různých animací. Implementace v programovacím jazyku C++ a grafickém API OpenGL rovněž pomohla s modularitou a kompatibilitou herního jádra mezi platformami.
5.1. Porovnání výsledků s ostatními voxelovými herními jádry Základ herního jádra se dobře prezentuje i napříč ostatními hrami s voxelovým herním světem. Oproti Minecraftu je herní jádro napsané v programovacím jazyce C++, což snižuje zbytečné nároky při práci v poli, tedy jakékoliv operace s chunkami nebo značné využití ukazatelů pro systém na zasílání zpráv mezi objekty. Oproti Minecraftu rovněž vychází lépe v podobě nekonečné mapy do výšky a Phongovu osvětlovacímu modelu místo záplavovému algoritmu a zapékáním světla do meshe. SyntheticWorld neposkytuje oproti vytvořenému hernímu dynamickou herní mapu, namísto toho se velikost musí navolit při spuštění hry. Rovněž nepodporuje počasí a naopak disponuje stíny generovanými ze slunce. Terraria a Starbound se do porovnání příliš nehodí. Přestože obě hry jsou založené na voxelovém herním světe jejich herní jádro je více podobné plošinovkám než střílečkám. To vytváří jiné problémy v implementaci i jiné závěry. Ani jedna z her nedisponuje nekonečným herním světem, ale Starbound má herní mapu cyklickou.
5.2. Prostor ke zlepšení Herní jádro je velmi komplikovaný a komplexní program, není tedy možné kompletně navrhnout a implementovat za půl roku v jedné osobě. Přesto byl navrhnut solidní základ pro voxelové herní jádro. Prostor pro zlepšení se určitě najde. Zmínit můžeme například absenci modulu pro přehrávání zvuků a hudby. Kvalitní přehrávání zvuků a hudby je důležitou součástí herního jádra, která vždy pomůže v pohlcení hráče do iluze hry. Přesto implementace nebude příliš kompletní a díky modulu pro posílání zpráv i velmi jednoduchá pro propojení s ostatními části herního jádra. Vytváření herní mapy při pohybu potřebuje rozšířit. Momentálně je generování mapy a vytváření meshe implementováno na hlavním vlákně a to způsobuje zdržení při pohybu hráče. Vyčleněním této operace mimo hlavní vlákno a idealně paralelizováním jednotlivých kroků generování, by snížil čas potřebný pro celou operaci a díky vyčlenění, by nebylo třeba čekat, až se okraj mapy zkompletuje. 29
5. Závěr Další částí, která by šla rozšířit je samotné generování meshe. Při úpravě herní mapy dojde ke kompletnímu vygenerování nového meshe, přestože došlo ke změně pouze jednoho chunku. Takové řešení je rychlejší v případě úpravy většího počtu, ale pokud hráč odebere jen jeden voxel během snímku je to zbytečně komplexní zásah. Proto by bylo rozumné pro takový případ implementovat druhé řešení, které by spočívalo v pouhé modifikaci stávajícího meshe. Každý mesh by měl k sobě mapu, v které by bylo napsáno kde který voxel má vertexy. Při změně by se pak algoritmus podíval do mapy a modifikoval vertexy mapou odkazované. Tím by se ušetřil čas a snížili nároky na systém.
30
Příloha A. Kompilace programu Kvůli velkému množství knihoven a frameworků není komplikace rychlou záležitostí. Návod je napsaný pro vývojářském prostředí Netbeans 7.4 [35] a operační systém Windows. Nejprve bude potřeba stáhnout a nastavit veškeré knihovny. Začneme tedy stažením knihoven Boost, SFML, GLM, GLEW a Assimp. Po rozbalení všech knihoven potřebujeme nastavit include cestu v projektu do knihoven (viz obr. 20).
Obrázek 20. Nastaveni vkládání hlaviček do projektu(vlevo) a přídavných složek(vpravo).
Dále do preprocessor definitions nastavíme ENABLE_BOOST_WORKAROUND, GLEW_STATIC a SFML_STATIC. Následuje nastavení Additional Library Directories. To provedeme v záložce Linker (viz obr. 20). Jako poslední věc je třeba vypsat seznam knihoven. To provedeme opět v záložce Linker (viz obr. 21).
Obrázek 21. Nastaveni přídavných složek.
Jedinný problém může nastat s knihovnou Assimp. Pokud použijeme MinGW bude 31
Příloha A. Kompilace programu potřeba si Assimp zkompilovat, k tomu je zapotřebí CMake [36] a postupovat budeme v ruce s oficiálním návodem [37].
32
Příloha B. Uživatelský manuál Ovládní demoscény je zaměřené na kontrolu správného fungování a není myšleno jako doporučení pro uživatele. Ovládání lze doplnit nebo upravit jednoduše, na potřebné místo stačí vložit například tento blok kódu. // k o n t r o l a zmacknute k l a v e s y W pomoci k n i h o v n y SFML i f ( s f : : Keyboard : : i s K e y P r e s s e d ( s f : : Keyboard : :W) ) { // p r o v e d e n i pozadovane a k c e } ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙
Pravé tlačítko myši - uzamkne myš, ovládání jako ve střílečkách Levé tlačítko myši - odstranění voxelu před kamerou W - pohyb vpřed A - úkrok vlevo D - úkrok vpravo S - pohyb vzad E - odstranění voxelu před kamerou Q - přepnutí vykreslovacího módu na síťový ESC - ukončí program
33
Literatura [1] Oficiální stránky pro herní jádro Unreal Engine. 2014. url: https : / / www . unrealengine.com/ (cit. 15. 05. 2014). [2] Hra Deus Ex postavená na herním jádře Unreal Engine. 2000. url: http://en. wikipedia.org/wiki/Deus_Ex (cit. 15. 05. 2014). [3] Oficiální stránky pro hru Warcraft III. 2002. url: http://us.blizzard.com/enus/games/war3/ (cit. 15. 05. 2014). [4] Oficiální stránky hry Defence of the Ancients. 2014. url: http://www.playdota. com/ (cit. 15. 05. 2014). [5] Oficiální stránky pro herní jádro CryEngine. 2014. url: http://www.crytek. com/cryengine/cryengine3/overview (cit. 15. 05. 2014). [6] Oficiální stránky pro herní jádro Source Engine. 2014. url: http : / / source . valvesoftware.com/ (cit. 15. 05. 2014). [7] Oficiální stránky pro herní jádro Unity. 2014. url: https://unity3d.com/ (cit. 15. 05. 2014). [8] Oficiální stránky pro herní jádro Ogre. 2014. url: http://www.ogre3d.org/ (cit. 15. 05. 2014). [9] Oficiální stránky hry Synthetic World. 2014. url: http://www.staudsoft.com/ (cit. 15. 05. 2014). [10] Oficiální stránky hry FortressCraft. 2014. url: http : / / www . fortresscraft . com/ (cit. 15. 05. 2014). [11] Herní platforma Steam. 2014. url: http : / / store . steampowered . com/ (cit. 15. 05. 2014). [12] Oficiální stránky pro herní jádro Torque. 2012. url: http://www.garagegames. com/products/torque-3d (cit. 15. 05. 2014). [13] Oficiální stránky hry Team Fortress. 2014. url: http://www.teamfortress.com/ (cit. 15. 05. 2014). [14] Oficiální stránky hry Ace of Spades. 2014. url: http://www.aceofspades.com/ (cit. 15. 05. 2014). [15] Minimální požadavky pro hru Terraria. 2014. url: http://www.terraria.org/ faq.html (cit. 15. 05. 2014). [16] Oficiální stránky hry Terraria. 2014. url: http : / / www . terraria . org/ (cit. 15. 05. 2014). [17] Oficiální stránky hry Starbound. 2014. url: http://playstarbound.com/ (cit. 15. 05. 2014). [18] Synthetic world - omezená herní mapa. 2014. url: http://www.staudsoft.com/ index.php?id=67 (cit. 15. 05. 2014).
34
Literatura [19] FortressCraft: Unity - velikost herní mapy. 2014. url: http://www.theguardian. com/technology/gamesblog/2013/jul/23/fortresscraft-verus-minecraft (cit. 15. 05. 2014). [20] Blockland podporuje pouze OpenGL. 2014. url: http : / / blockland . us / FAQ . html#p (cit. 15. 05. 2014). [21] Velikost herní mapy Ace of Spades. 2014. url: http://www.aceofspades.com/ community/page/mapeditor (cit. 15. 05. 2014). [22] Počet herních map ve hře Starbound. 2014. url: http://community.playstarbound. com/index.php?threads/a-little-perspective-on-the-size-of-starbound. 27178/#post-1063769 (cit. 15. 05. 2014). [23]
Richard F Lyon. “Phong shading reformulation for hardware renderer simplification”. In: Apple Computer 43 (1993). url: http : / / dicklyon . com / tech / Graphics/Phong_TR-Lyon.pdf.
[24]
Rudolf Pecinovský. Návrhové vzory. 2007. isbn: 9788025115824.
[25]
Jason Gregory. Game Engine Architecture. 2009. isbn: 1568814135.
[26] Oficiální stránky Boost C++ knihovny. 2014. url: http://www.boost.org/ (cit. 15. 05. 2014). [27] Simple and Fast Multimedia Library. 2014. url: http://www.sfml- dev.org/ (cit. 15. 05. 2014). [28] Oficiální stránky frameworku XNA. 2014. url: http://msdn.microsoft.com/ en-us/centrum-xna.aspx (cit. 15. 05. 2014). [29] OpenGL Mathematics. 2014. url: http://glm.g-truc.net/ (cit. 15. 05. 2014). [30] The OpenGL Extension Wrangler Library. 2014. url: http://glew.sourceforge. net/ (cit. 15. 05. 2014). [31] Oficiální stránky knihovny Assimp. 2014. url: http://assimp.sourceforge. net/ (cit. 15. 05. 2014). [32] Oficiální stránky UnitCpp frameworku. 2014. url: http://apps.sourceforge. net/mediawiki/cppunit/ (cit. 15. 05. 2014). [33]
John Amanatides, Andrew Woo et al. “A fast voxel traversal algorithm for ray tracing”. In: Proceedings of EUROGRAPHICS. Sv. 87. 1987, s. 3–10. url: http: //www.cse.yorku.ca/~amana/research/grid.pdf.
[34] Opensource grafický editor Belnder. 2014. url: http://www.blender.org/ (cit. 15. 05. 2014). [35] Vývojářské prostředí Netbeans. 2014. url: https://netbeans.org/ (cit. 15. 05. 2014). [36] CMake, automatizační nástroj pro multiplatformní překlad. 2014. url: http:// www.cmake.org/ (cit. 15. 05. 2014). [37] Instalační manuál pro Assimp. 2014. url: http://assimp.sourceforge.net/ lib_html/cmake_build.html (cit. 15. 05. 2014).
35
