Geração procedural de mapas dungeon crawl baseada em gramática de grafos para uso em jogos roguelike
Abstract
This paper features the conception and the implementation of a procedural level generation engine, based in graph grammars, for roguelike games. The featured implementation explores the multithreaded programming over multiprocessed architectures, enabling the use of this tool in execution time, considering the high computational cost due to the use of graph grammars. The obtained results were very positive, both regarding performance gain and success of map generation, enabling the use of this dungeon crawl level generation technique in execution time. These results are illustrated by the introduction of the instance of a game and the discussion about the performance of the concurrent execution in a computer with gaming specifications.
References
[Adams 2002] Adams, D. (2002). Automatic generation of dungeons for computer games. Bachelor thesis, University of Sheffield, UK.
[Dormans and Bakkes 2011] Dormans, J. and Bakkes, S. (2011). Generating missions and spaces for adaptable play experiences. IEEE Transactions on Computational Intelligence and AI in Games, 3(3):216–228.
[Karp and Miller 1969] Karp, R. M. and Miller, R. E. (1969). Parallel program schemata. J. Comput. Syst. Sci., 3:147–195.
[Shaker et al. 2016] Shaker, N., Togelius, J., and Nelson, M. J. (2016). Procedural content generation in games. In Computational Synthesis and Creative Systems.
[Sharma et al. 2008] Sharma, A., Bahir, S., Narsale, S., and Tambe, U. (2008). A parallel algorithm for finding subgraph isomorphism.
[Ullmann 1976] Ullmann, J. R. (1976). An algorithm for subgraph isomorphism. J. ACM, 23(1):31–42.
[Zampelli et al. 2007] Zampelli, S., Deville, Y., Solnon, C., Sorlin, S., and Dupont, P. (2007). Filtering for subgraph isomorphism. In CP.
[Dormans and Bakkes 2011] Dormans, J. and Bakkes, S. (2011). Generating missions and spaces for adaptable play experiences. IEEE Transactions on Computational Intelligence and AI in Games, 3(3):216–228.
[Karp and Miller 1969] Karp, R. M. and Miller, R. E. (1969). Parallel program schemata. J. Comput. Syst. Sci., 3:147–195.
[Shaker et al. 2016] Shaker, N., Togelius, J., and Nelson, M. J. (2016). Procedural content generation in games. In Computational Synthesis and Creative Systems.
[Sharma et al. 2008] Sharma, A., Bahir, S., Narsale, S., and Tambe, U. (2008). A parallel algorithm for finding subgraph isomorphism.
[Ullmann 1976] Ullmann, J. R. (1976). An algorithm for subgraph isomorphism. J. ACM, 23(1):31–42.
[Zampelli et al. 2007] Zampelli, S., Deville, Y., Solnon, C., Sorlin, S., and Dupont, P. (2007). Filtering for subgraph isomorphism. In CP.
Published
2019-11-08
How to Cite
SOUZA, Renã; JUNIOR, Braz; FOSS, Luciana; CAVALHEIRO, Gerson Geraldo; CAVALHEIRO, Simone.
Geração procedural de mapas dungeon crawl baseada em gramática de grafos para uso em jogos roguelike. In: SYMPOSIUM ON HIGH PERFORMANCE COMPUTING SYSTEMS (SSCAD), 20. , 2019, Campo Grande.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 193-203.
DOI: https://doi.org/10.5753/wscad.2019.8668.
