• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
10.11606/D.55.2019.tde-25032019-144917
Documento
Autor
Nome completo
Leonardo Tortoro Pereira
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Carlos, 2018
Orientador
Banca examinadora
Toledo, Cláudio Fabiano Motta (Presidente)
Ashlock, Daniel Abram
Chaimowicz, Luiz
Osório, Fernando Santos
Título em inglês
Procedural Generation of Dungeon Maps, Missions and Rooms
Palavras-chave em inglês
Adaptive game content
Evolutionary algorithm
Level generation
Mission generation
Procedural content generation
Resumo em inglês
The present research proposes two procedural content generation approaches for missions and play space in a game with dungeons, and a game prototype developed as a proof of concept for the feasibility of the algorithm and as a test framework for user-based experiments. The first approach will define missions by generating dungeon maps together with locked doors and keys through the use of an evolutionary algorithm. The second approach will populate the generated dungeon space by filling the content of dungeon rooms using space-filling curves and cellular automata algorithms. The evolutionary algorithm evolves tree structures encoding information about the dungeon. The goal is to converge the generated dungeons as close as possible to satisfy the set of parameter inputs provided by a game designer. The dungeon holds information about the amount of rooms, the connections between them and their position in a 2D map. There are also relevant semantic information in the content for the generation of narrative, which presents itself by the placement of unique pairs of keys and locks throughout it. Thus, a feasible way to finish the dungeon can be procedurally generated. The content of rooms are generated using space-filling curves algorithms such as Hilbert and Moore curves as well as Conways Game of Life Cellular Automata. Computational results report that the evolutionary algorithm provides dungeons with up to a 100 rooms very close to the desired ones for a range of different parameter inputs. The early validation tests with humans show no statistical difference between levels procedurally generated and those made by humans. Further user-centred validation tests with the game prototype show the algorithm-generated levels are perceived as equally or even more human-made than their human-authored counterparts, as well as funnier and more difficult. Thus, the research aims to generate gameplay elements combining different algorithms for a single solution, which could be easily adapted to a range of different games.
Título em português
Geração Procedural de Mapas de Calabouço, Missões e Salas
Palavras-chave em português
Algoritmo evolutivo
Conteúdo adaptativo de jogo
Geração de missão
Geração de nível
Geração procedural de conteúdo
Resumo em português
O projeto propõe duas abordagens de geração de conteúdo para missões e mapas em um jogo com calabouços, e um protótipo de jogo desenvolvido como prova de conceito da factibilidade do algoritmo e também como plataforma de testes para experimentos com usuários. A primeira abordagem define missões ao gerar mapas de calabouço em conjunto com chaves e portas trancadas através do uso de um algoritmo evolutivo. Já a segunda abordagem irá popular o espaço do calabouço criado ao preencher o conteúdo de suas salas usando algoritmos de curvas de preenchimento de espaço e autômatos celulares. O algoritmo evolutivo evolui uma estrutura em árvore que codifica informações sobre o calabouço. O objetivo é convergir os calabouços gerados para se aproximar ao máximo da configuração de entrada fornecida por um designer de jogos. O calabouço possui informação sobre as salas, como a quantidade das mesmas, as conexões entre elas e suas posições em um mapa 2D. Também contam com informações semânticas relevantes para a geração de narrativa no calabouço, que são o posicionamento de pares únicos de chaves e fechaduras através do calabouço. Portanto, uma maneira factível para o término do mesmo pode ser gerada proceduralmente. O conteúdo das salas é gerado usando curvas de preenchiment de espaço como as de Hilbert e Moore, além do autômato celular do Jogo da Vida de Conway. Resultados computacionais demonstram que o algoritmo evolutivo é capaz de criar calabouços com propriedades muito próximas às desejadas para uma grande variedade de entradas para calabouços com até 100 salas. Resultados preliminares de validação com humanos mostraram não haver diferença estatística entre os níveis gerados proceduralmente daqueles feitos por humanos. Testes posteriores de validação centrados em humanos com o protótipo de jogo mostram que os níveis gerados pelo algoritmo são percebidos como feitos por humanos de maneira semelhante ou até em maior grau do que suas contrapartidas geradas de fato por humanos, assim como são percebidos como mais divertidos e difíceis do que estas. Portanto, esta pesquisa objetiva gerar elementos de jogabilidade combinando diferentes algoritmos em uma única solução, que pode ser facilmente adaptada para uma variedade de jogos diferentes.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2019-03-25
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2019. Todos os direitos reservados.