Geração procedural de mapas dungeon crawl baseada em gramática de grafos para uso em jogos roguelike
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
[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.
