Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2016-07-12T11:59:57Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Luca Bezerra Dias - Dissertação de Mestrado (versão final) - Capas Oficiais e Normas ABNT [Digital].pdf: 5112956 bytes, checksum: 8c627192221d904c973b582471a171dc (MD5) / Made available in DSpace on 2016-07-12T11:59:57Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Luca Bezerra Dias - Dissertação de Mestrado (versão final) - Capas Oficiais e Normas ABNT [Digital].pdf: 5112956 bytes, checksum: 8c627192221d904c973b582471a171dc (MD5) Previous issue date: 2015-08-31 / FACEPE / Os avanços na área de computação musical ao longo dos anos trouxeram no-vas possibilidades e também novas perguntas. A área de geração automática de con-teúdo musical ganhou bastante interesse (BILES, 1994); (SAMPAIO, TEDESCO e RAMALHO, 2005); (GIFFORD, 2013), e com ela, surgiram questões mais profundas sobre o conteúdo gerado por estes sistemas. Qual a aplicabilidade de tais sistemas? Como trabalhar com conceitos como melodia e harmonia? É possível gerar música que não seja apenas um combinado aleatório de notas ou excertos musicais? Reduzindo o escopo da discussão para sistemas geradores de composições percussivas, um elemento essencial fica em evidência: o ritmo. Qual o impacto de um ritmo destoante dentro de uma música? É possível gerar ritmos neutros, que se en-caixem em qualquer composição? Como gerar automaticamente um bom ritmo? Para responder a essas questões, é necessário antes chegar à resposta de uma pergunta mais fundamental: como saber se um ritmo A combina com um ritmo B? A literatura (inclusive musical) sobre esse assunto é escassa e, na sua maioria, subjetiva, pessoal e sem bases empíricas. Em geral, o caminho tomado pelos traba-lhos costuma se basear no que pode ser feito algoritmicamente, para depois encaixar os resultados dentro do conceito de ritmo, tornando os resultados questionáveis. Diante disso, resolvemos seguir o caminho inverso, partindo de teorias e con-ceitos para só depois chegarmos ao algoritmo. Para tal, pedimos que músicos e estu-diosos apresentassem definições de ritmo e suas características fundamentais, a par-tir das quais construímos hipóteses para responder à pergunta deste trabalho. Isto demandou buscar junto aos músicos possíveis hipóteses, encontrar uma forma de representá-las computacionalmente, levantar exemplos concretos (dados) musicais e decidir como representa-los computacionalmente, planejar experimentos que pudes-sem confrontar hipóteses e dados, para, enfim, tirar conclusões com respeito à per-gunta de pesquisa. Neste trabalho, que se insere na linha do uso de computadores como ferramenta de auxílio ao musicólogo, narramos este processo de investigação, elencando as dificuldades, justificando as escolhas, apresentando os resultados obti-dos e discutindo as lições aprendidas. / The advances in the computer music field throughout the years have brought new possibilities, and also new questions. The automatic generation of music content field has aroused a lot of interest (BILES, 1994); (SAMPAIO, TEDESCO e RAMALHO, 2005); (GIFFORD, 2013), and, with it, many deeper questions about the content gen-erated by these systems were brought into attention. What is the point of such sys-tems? How some concepts such as melody and harmony can be dealt with? Is it pos-sible to generate music that is not just a random sequence of notes or musical ex-cerpts? Narrowing the scope to percussive compositions generative systems, an essen-tial element stands out: the rhythm. What is the impact of a dissonant rhythm within a song? Is it possible to generate neutral rhythms, which could fit into any composition? How to generate a good rhythm? To answer these questions, first of all it is necessary to find the answer to a more fundamental question: how to tell if rhythm A matches rhythm B? The academic literature (including the musical one) on this subject is scarce, and mostly subjective, relying on personal opinions and without empirical basis. In general, the path chosen on the studies is based on what can be done algorithmically, to only then fit the results within the concept of rhythm, making the results unreliable. Therefore, we have decided to take the opposite way, starting from theories and concepts, to only then think about the algorithm. In order to do so, we have asked musicians and researchers to provide us with definitions for rhythm and its most fun-damental characteristics, from which we have built the hypotheses to answer this re-search’s main question. To achieve this, we had to ask musicians for possible hypoth-esis, find a way of representing them computationally, find concrete musical examples (data) and decide how to represent this data computationally, plan experiments that could compare hypothesis against data to, finally, get to conclusions about this re-search’s main question. In this work, which is highly linked with using computers as an auxiliary tool for the musicologist, we describe this investigation process, revealing the difficulties, justifying the choices made, presenting the results obtained and discussing the lessons learned.

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.

Spel idag kräver en enorm mängd arbetstimmar för att skapas, därför behövs alltid sätt att spara tid och automatisera processer. Algoritmer för polygoniseringen av skalärfält, som Marching Cubes, har under de senaste åren blivit ett allt vanligare tillvägagångssätt för att automatiskt generera terräng. Scenkomplexiteten och kraven för visuell kvalitet i dagens spel ökar ständigt. Därmed kommer också kravet för prestandaeffektiva renderingsmetoder. Deferred rendering är en renderingsmetod som kan hantera scener med stora mängder ljuskällor och hög scenkomplexitet samtidigt. För att undersöka integreringen mellan procedurellt skapad terräng och en deferred rendering pipeline, skapades en applikation i DirectX 11 för att undersöka implementeringen och potentiella optimeringar av denna integration. / Detta projekt handlar om slumpmässig procedurell skapning av digital terräng för bruk inom datorspel, och hur man i denna kontext kan ta nytta av en grafikmotor som använder renderingstekniken deferred rendering. / Carl Engström can be reached at: Phone: 076-102 86 00 Mail: Lemmibl@gmail.com Felix Nawrin Oxing can be reached at: Mail: felix@nawrin-oxing.se

Procedural content generation for video games (PCGG) has seen a steep increase in the past decade, aiming to foster emergent gameplay as well as to address the challenge of producing large amounts of engaging content quickly. Most work in PCGG has been focused on generating art and assets such as levels, textures, and models, or on narrative design to generate storylines and progression paths. Given the difficulty of generating harmonically pleasing and interesting music, procedural music generation for games (PMGG) has not seen as much attention during this time. Music in video games is essential for establishing developers' intended mood and environment. Given the deficit of PMGG content, this paper aims to address the demand for high-quality PMGG. This paper describes the system developed to solve this problem, which generates thematic music for non-player characters (NPCs) based on developer-defined attributes in real time and responds to the dynamic relationship between the player and target NPC. The system was evaluated by means of user study: participants confront four NPC bosses each with their own uniquely generated dynamic track based on their varying attributes in relation to the player's. The survey gathered information on the perceived quality, dynamism, and helpfulness to gameplay of the generated music. Results showed that the generated music was generally pleasing and harmonious, and that while players could not detect the details of how, they were able to detect a general relationship between themselves and the NPCs as reflected by the music.

This paper investigates the effectiveness of expressive range and controllability for 2-dimensional tile-based procedural content generation. Procedural content generation (PCG) is the automation of content, often in games, and tile-based PCG is when the generated content is constrained to a grid structure. Mixed-initiative PCG, which is the integration of user control into PCG, has been researched previously for tile-based PCG but the implementations have been limited by lack of breadth and user control over the algorithm. As a result, the expressive ranges and controllabilities of their algorithm have not been comprehensive, and in turn, the concepts of expressive range and controllability not thoroughly scrutinized. For the purpose of examining the concepts of expressive range and controllability, an implementation of declarative modelling, named Mixed-initiative Tile-based Designer (MTD), is made. The MTD combines the mission and shape grammar algorithm proposed by Dormans’ and the level generation system in Spelunky. Nine sets of input parameters, scenarios, are tested, each with 2000 levels generated. For each scenario, the expressive range of its output is examined using the standard evaluation metrics linearity and leniency. The results of the data sampling indicated that an analysis based on expressive range needs to be supported by additional analyses for the insights drawn to be more general. In particular, expressive range needs to be complemented by manual inspection, and linearity when applied to sufficiently complex levels needs to be complemented by additional evaluation metrics. On the other hand, controllability was found to have more significant limitations in its current form because of the normalization of the data that goes into the expressive range. One solution is instead to visualize the raw data of the expressive range and make liberal use of manual inspection. As a secondary study, the feasibility of implementing declarative modelling into 2-dimensional tile-based PCG is investigated through analyzing the MTD. In particular, the MTD’s user interface, procedural output and controllability is examined to determine whether declarative modelling is feasible for 2-dimensional tile-based PCG. / Denna artikel undersöker effektiviteten av uttrycksomfång och kontrollerbarhet för generering av 2-dimensionell rut-baserad procedurinnehåll. Procedurell innehållsgenerering (PCG) är automatisering av innehåll, ofta i spel, och rut-based PCG är när det genererade innehållet är begränsat till en rutnätsstruktur. Blandinitiativ PCG, som är integrationen av användarkontroll i PCG, har undersökts tidigare för rut-baserad PCG men implementeringarna har begränsats av brist på bredd och användarkontroll över algoritmen. Som ett resultat har uttrycksomfången och kontrollerbarheten av deras algoritm inte varit heltäckande, och i sin tur har begreppen uttrycksfullt omfång och kontrollerbarhet inte granskats noggrant. I syfte att undersöka begreppen uttrycksomfång och kontrollerbarhet görs en implementering av deklarativ modellering, benämnd Mixed-initiative Tile-based Designer (MTD). MTD:n kombinerar uppdrags-och formgrammatikalgoritmen som föreslagits av Dormans och nivågenereringssystemet i Spelunky. Nio uppsättningar ingångsparametrar, scenarier, testas, var och en med 2000 genererade nivåer. För varje scenario undersöks det uttrycksomfånget för dess utdata med hjälp av standardutvärderingsmåtten linjäritet och svårighet. Resultaten indikerade att en analys baserad på uttrycksomfång måste stödjas av ytterligare analyser för att insikterna ska bli mer generella. Speciellt måste uttrycksomfång kompletteras med manuell inspektion, och linjäritet när den tillämpas på tillräckligt komplexa nivåer måste kompletteras med ytterligare utvärderingsmått. Å andra sidan visade sig kontrollerbarhet ha mer betydande begränsningar i sin nuvarande form på grund av normaliseringen av data som går in i uttrycksomfånget. En lösning är istället att visualisera rådata från uttrycksomfånget och använda sig av manuell inspektion. Som en sekundär studie undersöks möjligheten att implementera deklarativ modellering i 2- dimensionell rut-baserad PCG genom att analysera MTD. I synnerhet undersöks MTD:s användargränssnitt, procedurutdata och kontrollerbarhet för att avgöra om deklarativ modellering är genomförbar för 2-dimensionell rut-baserad PCG.

This paper aimed to discover how player satisfaction is affected by context-aware elements based on physical, real-world factors in an action role-playing game. The possibility of utilizing player modelling to counteract the reduction in player empowerment in a game heavily influenced by external factors was also explored. This was accomplished by creating an ARPG heavily integrated with various weather, and daytime, context data obtained from web-based APIs. Followed by conducting qualitative tests with help of eleven participants during a time period of a week. The evaluated results were presented in a manner of relevance for both context-driven applications as a whole, and for further exploration within game developments utilization of state of the art technology.

This thesis explores the procedural generation of 3D buildings from the floor plan all the way to the fa¸cade and building’s details such as doors, windows, and roof. Through this, the study explores several techniques and approaches to create different layers of the building generation pipeline. The focus is on implementing a set of algorithms that, when running sequentially, are able to create complete 3D buildings in a short time (so they can be used in online generation), could be used in any open-world game, and with a limited count of triangles per building. Furthermore, the tool provides a clear and easy-to-use interface for designers in Unity, where they can interact with the multiple parameters of each building layer, giving designers a high degree of controllability. The tool is evaluated using the resulting buildings based on different metrics and how individual changes to different parameter starting from a template affect the output of the generator in terms of the metrics and the resulting building. The result from the analysis show that the polygon mathematics is well suited for generating 3D buildings for games.

This study investigated the possibility of procedural generation of skill trees which are similar to skill trees in contemporary video games. A set of randomly-selected skill trees from contemporary video games, from differ- ent game genres, was compiled, and an analysis was performed to extract relevant observations from the set. Using the observations, models for skill tree generation, and for skill tree comparison were proposed, and they were followed for the generation and analysis of the results. It was found that the method of Graph Grammars provided satisfying results compared to the set of skill trees from video games. Additionally, the other methods researched, L-Systems and Naive Randomized Graph Generation, while both may still require improvements discussed in the thesis in order to provide more satis- fying results, they may still be used for particular needs by game designers as they are. 1

Title: Application of hierarchical graph grammars in procedural 3D world gen- eration Author: Jakub Svoboda Abstract: Procedural content generation (PCG) is an often-used technique in video games. It allows us to generate large quantities and permutations of con- tent. A common problem in utilizing PCG in level design is that it is challenging to generate content close to what a human would create in overall quality and structure. One way of solving these problems is using graph grammars to rep- resent relations in the game world. Implementing a working graph generator using graph grammars and applying it to generate worlds is not very well docu- mented. This thesis will try to overcome this problem by implementing such a generator and extending it to use hierarchical graph grammars. The generator will be used to generate a 3D open world. The generator should be suitable for levels in other types of games. Keywords: procedural content generation, game development, hierarchical graphs, graph grammars, procedural level design

Det här arbetet beskriver implementationen av en rytmbaserad algoritm för att procedurellt generera plattformsbanor och hur den anpassats för att passa nedåtgående spel, i syfte att undersöka vilken kapacitet det resulterande programmet har för att skapa banor som skiljer sig från varandra. Undersökningen utfördes genom att låta artefakten generera ett större antal banor och jämföra värden mellan olika rytmer. Mätvärdena som iakttogs baserades på hur mycket banorna avvek från en mittlinje och på frekvensen av banelement som innebar konsekvenser för spelaren. Resultatet av undersökningen tyder på att rytmbaserad bangenerering har förmågan att generera vitt skilda banor för nedåtgående plattformsspel och att det därför finns ett värde i fortsatt utveckling och undersökningar i form av användarstudier av hur utmanande eller underhållande banorna upplevs, samt för att utveckla algoritmen till att ha parametrar för att låta bandesigners styra hur olika rytmer kan kombineras till banor. / <p>Det finns övrigt digitalt material (t.ex. film-, bild- eller ljudfiler) eller modeller/artefakter tillhörande examensarbetet som ska skickas till arkivet.</p><p>There are other digital material (eg film, image or audio files) or models/artifacts that belongs to the thesis and need to be archived.</p>