Please use this identifier to cite or link to this item: http://monografias.ufrn.br/handle/123456789/8940
Title: Geração automática de níveis de masmorras com barreiras para jogos digitais
Other Titles: Automatic dungeon level generation with barriers for digital games
Authors: Viana, Breno Maurício de Freitas
Keywords: Geração Procedural de Esboços de Níveis;Procedural Sketch Level Generation;Masmorras;Dungeon;Jogos Digitais;Digital Games;Estudo Sistemático de Níveis de Masmorras;Sistematic Study about Dungeon Levels;Algoritmo Genético;Genetic Algorithm
Issue Date: 14-Jun-2019
Publisher: Universidade Federal do Rio Grande do Norte
Citation: VIANA, Breno Maurício de Freitas. Geração automática de níveis de masmorras com barreiras para jogos digitais. 2019. 107f. Trabalho de Conclusão de Curso (Graduação em Ciência da Computação). - Departamento de Ciência da Informação, Universidade Federal do Rio Grande do Norte, Natal, 2019.
Portuguese Abstract: Geração procedural de conteúdo (PCG) é um método de criação automatizada de conteúdo digital. Um dos desafios da área é gerar uma variedade de conteúdos, com custo computacional baixo e com garantia de validade. O presente trabalho aborda a geração procedural de níveis típicos de jogos do gênero Dungeon Crawler (Exploração de Masmorras). Em particular, estávamos interessados em geração de níveis com a mecânica de barreiras. Barreiras são elementos presentes nos níveis que impedem o progresso do jogador e, portanto, precisam ser resolvidos por meio de elementos do jogo como a localização e utilização de chaves, resolução de puzzles, ou aquisição e utilização de novas habilidades. O trabalho considera quatro formas de barreiras com chaves, dependendo da relação entre quantidades de chaves (C) e barreiras (B): 1C para 1B, MC para 1B, 1C para NB e MC para NB. A geração automática de esboços de níveis que suportem essas combinações de C/B pode ser mapeado como um problema de satisfação de restrições (PSR), visto que B e C possuem restrições de posicionamento dentro de regiões do cenário; isto é, devemos evitar a geração de uma barreira cuja solução seja inalcançável dentro do nível. Uma das formas de solucionar PSRs é por meio de técnicas de busca. Portanto, a proposta ora apresentada utilizada uma combinação de Algoritmo Genético (AG) com um algoritmo de geração-e-teste (não baseado em busca) para gerar níveis com suporte a múltiplas combinações B/C. Os resultados preliminares demonstraram que, apesar de surgirem soluções inviáveis, a maioria das buscas executadas com o método proposto resultaram em níveis viáveis com a mecânica de barreiras.
Abstract: Procedural content generation (PCG) is a digital content creation method performed by algorithms. One of the challenges of the area is to generate a variety of content, with low computational cost and with validity guarantee. The present work addresses the procedural generation of typical game levels of the Dungeon Crawler genre. In particular, we were interested in generating levels with the mechanics of barriers. Barriers are elements present at levels that impede the progress of the player and, therefore, need to be solved through elements of the game such as the location and use of keys, by solving puzzles, or the acquisition and use of new skills. The work considers four forms of barriers with keys, depending on the relationship between the amount of keys (K) and barriers (B): 1K for 1B, NK for 1B, 1K for MB and NK to MB. The automatic generation of level sketches that support these K/B combinations can be mapped as a constraint satisfaction problem (CSP), since B and K have position constraints within scenario regions; that is, we must avoid generating a barrier whose solution is unreachable within the level. One of the ways to solve CSP is by means of search techniques. Therefore the proposal presented here uses a combination of a Genetic Algorithm (AG) with a generate-and-test (non-search-basead) algorithm to generate levels with support for multiple B/K combinations. Preliminary results have shown that, although it generate infeasible solutions, most solutions generated by our method are feasible levels with the mechanics of barriers.
URI: http://monografias.ufrn.br/handle/123456789/8940
Other Identifiers: 20180008183
Appears in Collections:Ciência da Computação

Files in This Item:
File Description SizeFormat 
GeracaoAutomaticaNiveisJogosDigitais_Viana_2019.pdf10.89 MBAdobe PDFThumbnail
View/Open


This item is licensed under a Creative Commons License Creative Commons