The aim of this thesis is to evaluate the use of Search-based Procedural Content generation (SBPCG) to help a designer create levels for different game styles. I show how SBPCG can be used for level generation in different game genres by surveying both paper and released commercial solutions. I then provide empirical data by using a Genetic Algorithm (GA) to evolve levels in two different game types, first one being a space puzzle game, and the second a platform game. Constraints from a level designer provide a base to create fitness functions for both games with success. Even though difficulties with level representation make it hard for a designer to work with this technique directly, the generated levels show that the technique has promising potential to aid level designers with their work.

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.

Made available in DSpace on 2014-12-17T15:48:00Z (GMT). No. of bitstreams: 1 PhilipMD_DISSERT.pdf: 3999230 bytes, checksum: fd3b6c186bc10448c63b511e10e6017e (MD5) Previous issue date: 2012-02-26 / Conselho Nacional de Desenvolvimento Cient?fico e Tecnol?gico / The game industry has been experiencing a consistent increase in production costs of games lately. Part of this increase refers to the current trend of having bigger, more interactive and replayable environments. This trend translates to an increase in both team size and development time, which makes game development a even more risky investment and may reduce innovation in the area. As a possible solution to this problem, the scientific community is focusing on the generation of procedural content and, more specifically, on procedurally generated levels. Given the great diversity and complexity of games, most works choose to deal with a specific genre, platform games being one of the most studied. This work aims at proposing a procedural level generation method for platform/adventure games, a fairly more complex genre than most classic platformers which so far has not been the subject of study from other works. The level generation process was divided in two steps, planning and viusal generation, respectively responsible for generating a compact representation of the level and determining its view. The planning stage was divided in game design and level design, and uses a goaloriented process to output a set of rooms. The visual generation step receives a set of rooms and fills its interior with the appropriate parts of previously authored geometry / Recentemente a ind?stria de jogos vem experimentando um aumento consistente nos custos de produ??o de jogos. Parte deste aumento ? referente ? tend?ncia atual de se ter ambientes cada vez maiores, mais interativos e rejog?veis. Esta tend?ncia se reflete num aumento das equipes e do tempo de desenvolvimento, o que torna o desenvolvimento de jogos um investimento de risco e pode reduzir a inova??o na ?rea. Como uma poss?vel solu??o para este problema, a comunidade cient?fica vem apostando na gera??o procedural de conte?do e, mais especificamente, na gera??o procedural de cen?rios. Dada a grande diversidade e complexidade dos jogos, a maioria dos trabalhos opta por trabalhar em g?neros espec?ficos, sendo os jogos de plataforma um dos g?neros mais estudados. Este trabalho prop?e um m?todo de gera??o de cen?rios para jogos de plataforma/ aventura, um g?nero mais complexo que jogos de plataforma cl?ssicos e que at? o momento n?o foi alvo de estudo de outros trabalhos. Dividimos a gera??o de cen?rios em etapas de planejamento e gera??o visual, respons?veis respectivamente por gerar proceduralmente uma representa??o compacta de cen?rio e determinar sua visualiza??o. A etapa de planejamento se divide em game design e level design, e se utiliza de um processo orientado a objetivos para produzir como sa?da um conjunto de salas. A etapa de gera??o visual recebe um conjunto de salas e preenche seus interiores com partes adequadas de geometria previamente constru?das

Context. Procedural content generation (PCG) refers to algorithmical creation of game content (e.g. levels, maps, characters). Since PCG generators are able to produce huge amounts of game content, it becomes impractical for humans to evaluate them manually. Thus it is desirable to automate the process of evaluation. Objectives. This work presents an automatic method for evaluation of procedural level generators for 2D platform games. The method was used for comparative evaluation of four procedural level generators developed within the research community. Methods. The evaluation method relies on simulation of the human player's behaviour in a 2D platform game environment. It is made up of three components: (1) a 2D platform game Infinite Mario Bros with levels generated by the compared generators, (2) a human-like bot and (3) quantitative models of player experience. The bot plays the levels and collects the data which are input to the models. The generators are evaluated based on the values output by the models. A method based on the simple moving average (SMA) is suggested for testing if the number of performed simulations is sufficient. Results. The bot played all 6000 evaluated levels in less than ten minutes. The method based on the SMA showed that the number of simulations was sufficiently large. Conclusions. It has been shown that the automatic method is much more efficient than the traditional evaluation made by humans while being consistent with human assessments.

This paper explores what attributes are important for the creation of environment art tools. The purpose of this is to make sure that when a tool is to be developed, it will be done properly within a given time frame. This is important since the cost of tool development is high in both time and capital spent. Being able to make sure that when those resources are spent, that the resulting tool is of high quality and solving the problem which the development team set out to do. Through interviews, forms and the creation of our own tool I hope to find these attributes and to be able to provide insights into how a studio or team might apply them for their own purposes.

This thesis describes the implementation and evaluation of a genetic algorithm (GA) for procedurally generating levels with controllable difficulty for a motion-based 2D platform game. Manually creating content can be time-consuming, and it may be desirable to automate this process with an algorithm, using Procedural Content Generation (PCG). An algorithm was implemented and then refined with an iterative method by conducting user tests. The resulting algorithm is considered a success and shows that using GA's for this kind of PCG is viable. An algorithm able to control difficulty of its output was achieved, but more refinement could be made with further user tests. Using a GA for this purpose, one should find elements that affect difficulty, incorporate these in the fitness function, and test generated content to ensure that the fitness function correctly evaluates solutions with regard to the desired output.