velikost textu

Procedural 2D Map Generation for Computer Games

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Procedural 2D Map Generation for Computer Games
Název v češtině:
Procedurální generování 2D map pro počítačové hry
Typ:
Bakalářská práce
Autor:
Bc. Ondřej Nepožitek
Vedoucí:
Mgr. Jakub Gemrot
Oponent:
RNDr. Tomáš Holan, Ph.D.
Id práce:
200702
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra softwaru a výuky informatiky (32-KSVI)
Program studia:
Informatika (B1801)
Obor studia:
Obecná informatika (IOI)
Přidělovaný titul:
Bc.
Datum obhajoby:
22. 6. 2018
Výsledek obhajoby:
Výborně
Jazyk práce:
Angličtina
Klíčová slova:
procedurální generování obsahu, počítačové hry, 2D mapy, místnosti
Klíčová slova v angličtině:
procedural content generation, computer games, 2D maps, rooms
Abstrakt:
V některých videohrách se herní úrovně generují procedurálně, mimo jiné pro zvýšení zážitků z opakovaného hraní. Takto vygenerované úrovně ale často postrádají jakoukoliv strukturu a mohou hráčům připadat až příliš náhodné. Ma et al. (2014) navrhli algoritmus, který tento problém řeší. Na vstupu dostane jejich metoda množinu povolených tvarů místností a k tomu graf, který říká, jaké místnosti chceme vygenerovat a jak mají být mezi sebou propojené. Výstupem je půdorys, který obsahuje všechny specifikované místnosti a respektuje jejich propojení. Jejich algoritmus je založen na dvou hlavních myšlenkách. První myšlenkou je, že místo toho, abychom se snažili najít vyhovující uspořádání pro celý graf najednou, si graf rozdělíme na menší části a ty se snažíme vyřešit jednu po druhé. Druhou myšlenkou je, že si předpočítáme, jak lze jednotlivé dvojice tvarů místností umístit tak, aby se navzájem nepřekrývaly. To poté využijeme k tomu, abychom nemuseli zkoušet všechna možná umístění jednotlivých místností. V této práci prezentujeme úpravu této metody tak, aby byla schopna generovat takzvané tile-based herní úrovně, tedy takové úrovně, které jsou založené na pravidelné čtvercové mřížce. Původní metoda je rozšířena o několik vylepšení, například o možnost propojit jednotlivé místnosti krátkými chodbami. Dále prezentujeme několik způsobů, jak zvýšit rychlost celého algoritmu, například chytřejší rozdělení vstupního grafu na menší části. Výsledný algoritmus je schopen vygenerovat různorodé herní úrovně, což je demonstrováno na různých vstupních grafech a tvarech místností. Z testů výkonu naší metody vyplývá, že jsme dosáhli zrychlení až o dva řády vůči původní metodě.
Abstract v angličtině:
In some video games, levels are procedurally generated to increase game’s replayability. However, such levels may often feel too random, unbalanced and lacking an overall structure. Ma et al. (2014) proposed an algorithm to solve this problem. Their method takes a set of user-defined building blocks as an input and produces layouts that all follow the structure of a specified level connectivity graph. The algorithm is based on two main concepts. The first one is that the input graph is decomposed into smaller chains and these are laid out one at a time. The second one is that configuration spaces are used to define valid relative positions of building blocks. In this thesis, we present an implementation of this method in a context of 2D tile-based maps. We enhance the algorithm with several new features, one of them being a mode to quickly add short corridors between neighbouring rooms. We also propose speed improvements, including a smarter decomposition of the input graph and tweaks of the stochastic method that is used to lay out individual chains. The resulting algorithm is able to quickly produce diverse layouts, which is demonstrated on a variety of input graphs and building blocks sets. Benchmarks of our algorithm show that it can achieve up to two orders of magnitude speedup compared to the original method.
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Bc. Ondřej Nepožitek 2.67 MB
Stáhnout Příloha k práci Bc. Ondřej Nepožitek 45.32 MB
Stáhnout Abstrakt v českém jazyce Bc. Ondřej Nepožitek 62 kB
Stáhnout Abstrakt anglicky Bc. Ondřej Nepožitek 59 kB
Stáhnout Posudek vedoucího Mgr. Jakub Gemrot 338 kB
Stáhnout Posudek oponenta RNDr. Tomáš Holan, Ph.D. 80 kB
Stáhnout Záznam o průběhu obhajoby doc. Ing. Petr Tůma, Dr. 152 kB