Procedurální generování 2D map pro počítačové hry

Nepožitek, Ondřej

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...

host :: přihlásit Digitální repozitář
		Hledej		Nový záznam		Nápověda		O repozitáři