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 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.