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.

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.

This Master s thesis proposes a non-assisted procedural method for 3D canyons scenes generation based on techniques of computer graphics, computer vision and graph search algorithm. In order to define all the features to be reproduced in our scenes, we have analyzed several images of real canyons and have categorized them in two canyon features models: a recursive and an ordinary one. The proposed approach manipulates a heightmap, created using Perlin noise, in order to imitate the geological features formation previously analyzed. Several parametrizations are used to guide and constraint the generation of terrains, canyons features, course of river, plain areas, soft slope regions, cliffs and plateaus. This work also uses the Mean Shift algorithm as mechanism of segmentation to define regions of interest. A binary mask, with plain areas, is defined based on a threshold operation by a given data set provided by the Mean Shift algorithm. Thereafter a connected-component labeling algorithm is executed using the previously binary mask. This algorithm finds all plains centroids. Right after that, the Dijkstra s algorithm is performed in order to connect all plain areas, creating a valid path between the centroids. The Dijkstra s algorithm is executed again to define the river s course. Finally, a Gaussian smoothing operation is applied to interpolate the soft slope regions. The combination of all those techniques produces as a result automatically generated feature-rich canyons. / Esta dissertação propõe um método procedural não assistido, baseado em técnicas de computação gráfica, visão computacional e busca em grafos, para a geração de cenários 3D de cânions com foco em jogos digitais. Para definir as características a serem reproduzidas, foram analisadas diversas imagens de cânions reais chegando-se em dois modelos, um comum e outro recursivo. A abordagem proposta manipula um reticulado gerado com ruído de Perlin, moldando assim as características inerentes a essa formação geológica. São levadas em conta as diversas parametrizações necessárias para permitir que o algoritmo construa cânions com curso de rio, áreas de planícies, regiões de encosta suave, estruturas de penhascos e, por fim, planaltos nas regiões mais altas. Para atingir o resultado final, o trabalho utiliza o algoritmo Mean Shift como mecanismo de segmentação, definindo dados e regiões de interesse. Munido dos dados do algoritmo de clusterizacao, é definido um limiar para a criação de uma máscara binária com a definição das planícies. Em um segundo momento, um algoritmo de rotulação de componentes conectados é executado, extraindo-se os centróides de cada planície. Por sua vez, o algoritmo de Dijkstra encaixa-se na definição de rotas que conectam estas planícies. O algoritmo de Dijkstra é, então, executado novamente, tendo por base uma função de custo de inclinação, para definir o curso do rio. Por fim, uma filtragem espacial baseada em um filtro Gaussiano é aplicada para interpolar as regiões de encostas de declive suave. A combinação dessas técnicas gera terrenos com grande variabilidade e com as características inerentes à formação geológica de cânions.

Na última década diversos algoritmos baseados em busca foram desenvolvidos para a geração de níveis em diferentes tipos de jogos. O espaço de busca para geração de níveis geralmente possui restrições, uma vez que a mecânica de um jogo define regras de factibilidade para os níveis. Em alguns métodos, a avaliação de factibilidade requer uma simulação com um agente inteligente que controla o jogo. Esse processo de avaliação geralmente possui ruído, causado por componentes aleatórios no simulador ou na estratégia do agente. Diversos trabalhos têm utilizado simulação como forma de avaliação de conteúdo, no entanto, nenhum deles discutiu profundamente a presença de ruído neste tipo de abordagem. Assim, esse trabalho apresenta um algoritmo genético capaz de gerar níveis factíveis que são avaliados por um agente inteligente em uma simulação ruidosa. O algoritmo foi aplicado a jogos de quebra-cabeças baseados em física com a mecânica do Angry Birds. Uma representação dos níveis em forma de indivíduos é introduzida, a qual permite que o algoritmo genético os evolua com características diferenciadas. O ruído na função de aptidão é tratado por uma nova abordagem, baseada em uma sistema de cache, que auxilia o algoritmo genético a encontrar boas soluções candidatas. Três conjuntos de experimentos foram realizados para avaliar o algoritmo. O primeiro compara o método de cache proposto com outros métodos de redução de ruído da literatura. O segundo mede a expressividade do algoritmo genético considerando as características estruturais dos níveis gerados. O último avalia os níveis gerados considerando aspectos de design (como dificuldade, imersão e diversão), os quais são medidos por meio de questionários respondidos por jogadores humanos via Internet. Os resultados mostraram que o algoritmo genético foi capaz de gerar níveis distintos que são tão imersíveis quanto níveis produzidos manualmente. Além disso, a abordagem de cache lidou apropriadamente com o ruído nos cálculos de aptidão, permitindo uma correta evolução elitista. / In the last decade several search-based algorithms have been developed for generating levels in different types of games. The search space for level generation is typically constrained once the game mechanics define feasibility rules for the levels. In some methods, evaluating level feasibility requires a simulation with an intelligent agent which plays the game. This evaluation process usually has noise, caused by random components in the simulator or in the agent strategy. Several works have used a simulation for content evaluation, however, none of them have deeply discussed the presence of noise in this kind of approach. Thus, this paper presents a genetic algorithm capable of generating feasible levels that are evaluated by an intelligent agent in a noisy simulation. The algorithm was applied to physics-based puzzle games with the Angry Birds mechanics. A level representation in the form of individuals is introduced, which allows the genetic algorithm to evolve them with distinct characteristics. The fitness function noise is handled by a new approach, based on a cache system, which helps the genetic algorithm finding good candidate solutions. Three sets of experiments were conducted to evaluate the algorithm. The first one compares the proposed cache approach with other noise reduction methods of the literature. The second one measures the expressivity of the genetic algorithm considering the structural characteristics of the levels. The last one evaluates design aspects (such as difficulty, immersion and fun) of the generated levels using questionnaires answered by human players via Internet. Results showed the genetic algorithm was capable of generating distinct levels that are as immersive as levels manually designed. Moreover, the cache approach handled properly the noise in the fitness calculations, allowing a correct elitist evolution.

Na última década diversos algoritmos baseados em busca foram desenvolvidos para a geração de níveis em diferentes tipos de jogos. O espaço de busca para geração de níveis geralmente possui restrições, uma vez que a mecânica de um jogo define regras de factibilidade para os níveis. Em alguns métodos, a avaliação de factibilidade requer uma simulação com um agente inteligente que controla o jogo. Esse processo de avaliação geralmente possui ruído, causado por componentes aleatórios no simulador ou na estratégia do agente. Diversos trabalhos têm utilizado simulação como forma de avaliação de conteúdo, no entanto, nenhum deles discutiu profundamente a presença de ruído neste tipo de abordagem. Assim, esse trabalho apresenta um algoritmo genético capaz de gerar níveis factíveis que são avaliados por um agente inteligente em uma simulação ruidosa. O algoritmo foi aplicado a jogos de quebra-cabeças baseados em física com a mecânica do Angry Birds. Uma representação dos níveis em forma de indivíduos é introduzida, a qual permite que o algoritmo genético os evolua com características diferenciadas. O ruído na função de aptidão é tratado por uma nova abordagem, baseada em uma sistema de cache, que auxilia o algoritmo genético a encontrar boas soluções candidatas. Três conjuntos de experimentos foram realizados para avaliar o algoritmo. O primeiro compara o método de cache proposto com outros métodos de redução de ruído da literatura. O segundo mede a expressividade do algoritmo genético considerando as características estruturais dos níveis gerados. O último avalia os níveis gerados considerando aspectos de design (como dificuldade, imersão e diversão), os quais são medidos por meio de questionários respondidos por jogadores humanos via Internet. Os resultados mostraram que o algoritmo genético foi capaz de gerar níveis distintos que são tão imersíveis quanto níveis produzidos manualmente. Além disso, a abordagem de cache lidou apropriadamente com o ruído nos cálculos de aptidão, permitindo uma correta evolução elitista. / In the last decade several search-based algorithms have been developed for generating levels in different types of games. The search space for level generation is typically constrained once the game mechanics define feasibility rules for the levels. In some methods, evaluating level feasibility requires a simulation with an intelligent agent which plays the game. This evaluation process usually has noise, caused by random components in the simulator or in the agent strategy. Several works have used a simulation for content evaluation, however, none of them have deeply discussed the presence of noise in this kind of approach. Thus, this paper presents a genetic algorithm capable of generating feasible levels that are evaluated by an intelligent agent in a noisy simulation. The algorithm was applied to physics-based puzzle games with the Angry Birds mechanics. A level representation in the form of individuals is introduced, which allows the genetic algorithm to evolve them with distinct characteristics. The fitness function noise is handled by a new approach, based on a cache system, which helps the genetic algorithm finding good candidate solutions. Three sets of experiments were conducted to evaluate the algorithm. The first one compares the proposed cache approach with other noise reduction methods of the literature. The second one measures the expressivity of the genetic algorithm considering the structural characteristics of the levels. The last one evaluates design aspects (such as difficulty, immersion and fun) of the generated levels using questionnaires answered by human players via Internet. Results showed the genetic algorithm was capable of generating distinct levels that are as immersive as levels manually designed. Moreover, the cache approach handled properly the noise in the fitness calculations, allowing a correct elitist evolution.