Název:
Procedurální generování 2D map pro počítačové hry
Překlad názvu:
Procedural 2D Map Generation for Computer Games
Autoři:
Nepožitek, Ondřej ; Gemrot, Jakub (vedoucí práce) ; Holan, Tomáš (oponent) Typ dokumentu: Bakalářské práce
Rok:
2018
Jazyk:
eng
Abstrakt: [eng][cze] 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...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...
Klíčová slova:
2D mapy; místnosti; počítačové hry; procedurální generování obsahu; 2D maps; computer games; procedural content generation; rooms