Geração procedural de mapas dungeon crawl baseada em gramática de grafos para uso em jogos roguelike

  • Renã Souza Universidade Federal de Pelotas
  • Braz Junior Universidade Federal de Pelotas
  • Luciana Foss Universidade Federal de Pelotas
  • Gerson Geraldo Cavalheiro UFPel
  • Simone Cavalheiro Universidade Federal de Pelotas

Resumo


Este artigo apresenta a concepção e a implementação de um motor de geração procedural de mapas, baseado em gramáticas de grafos, para jogos do tipo roguelike. A implementação realizada explora a programação multitarefa sobre arquiteturas multiprocessadas, viabilizando o uso desta ferramenta em tempo de execução, tendo em vista o alto custo computacional decorrente do uso de gramática de grafos. Os resultados obtidos foram muito positivos, tanto no que se refere ao ganho de desempenho quanto no sucesso em geração de mapas, viabilizando o uso dessa técnica de geração de mapas dungeon crawl em tempo de execução. Estes resultados são ilustrados com a apresentação da instanciação de um jogo e de uma discussão sobre o desempenho da execução paralela em um computador com configuração gamer.

Referências

[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.
Publicado
08/11/2019
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: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (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.