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. / 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.
| Identifer | oai:union.ndltd.org:IBICT/oai:teses.usp.br:tde-25032019-144917 |
| Date | 13 November 2018 |
| Creators | Leonardo Tortoro Pereira |
| Contributors | Cláudio Fabiano Motta Toledo, Daniel Abram Ashlock, Luiz Chaimowicz, Fernando Santos Osório |
| Publisher | Universidade de São Paulo, Ciências da Computação e Matemática Computacional, USP, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | English |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da USP, instname:Universidade de São Paulo, instacron:USP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.003 seconds