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>

We present a Research through Design project that explores design opportunities and challenges of a personal visualization tool in artistic settings. The research process includes technical material exploration, an approach where state-of-the-art enabling techniques are examined to inspire artistic design decision-making. We propose three experiential qualities of such a tool: uniqueness, memorability, and aesthetics. They also serve as the heuristics throughout the design and evaluation process, aiming for meaningful user experience of personal visualization. Furthermore, we present how proceduralism democratizes user-generated content creation, how immersiveness improves the overall virtual experience, and how various computer graphics techniques are combined to improve the accessibility, learnability, and usability of the tool. / Vi presenterar en forskning genom ett designprojekt som utforskar möjligheter och utmaningar för ett personligt visualiseringsverktyg i konstnärliga scenarier. Forskningsprocessen inkluderar teknisk materialutforskning, ett tillvägagångssätt där state-of-the-art möjliggörande tekniker undersöks för att inspirera till beslutsfattande i konstnärlig design. Vi föreslår tre upplevelsemässiga egenskaper hos ett sådant verktyg: unikhet, minnesbarhet och estetik. Dessa egenskaper agerar även som heuristiken genom hela design- och utvärderingsprocessen, som syftar till en meningsfull användarupplevelse av personlig visualisering. Dessutom presenterar vi hur proceduralism demokratiserar användargenererat innehållsskapande, hur uppslukande förbättrar den övergripande virtuella upplevelsen och hur olika datorgrafiktekniker kan kombineras för att förbättra tillgängligheten, lärbarheten samt användbarheten av verktyget.

As AI develops, grows, and expands, the more benefits we can have from it. AI is used in multiple fields to assist humans, such as object recognition, self-driving cars, or design tools. However, AI could be used for more than assisting humans in their tasks. It could be employed to collaborate with humans as colleagues in shared tasks, which is usually described as Mixed-Initiative (MI) paradigm. This paradigm creates an interactive scenario that leverage on AI and human strengths with an alternating and proactive initiative to approach a task. However, this paradigm introduces several challenges. For instance, there must be an understanding between humans and AI, where autonomy and initiative become negotiation tokens. In addition, control and expressiveness need to be taken into account to reach some goals. Moreover, although this paradigm has a broader application, it is especially interesting for creative tasks such as games, which are mainly created in collaboration. Creating games and their content is a hard and complex task, since games are content-intensive, multi-faceted, and interacted by external users.  Therefore, this thesis explores MI collaboration between human game designers and AI for the co-creation of games, where the AI's role is that of a colleague with the designer. The main hypothesis is that AI can be incorporated in systems as a collaborator, enhancing design tools, fostering human creativity, reducing their workload, and creating adaptive experiences. Furthermore, This collaboration arises several dynamic properties such as control, expressiveness, and initiative, which are all central to this thesis. Quality-Diversity algorithms combined with control mechanisms and interactions for the designer are proposed to investigate this collaboration and properties. Designer and Player modeling is also explored, and several approaches are proposed to create a better workflow, establish adaptive experiences, and enhance the interaction. Through this, it is demonstrated the potential and benefits of these algorithms and models in the MI paradigm.

Processen att skapa innehåll till digitala spel för hand är kostsamt och tidskrävande. Allteftersom spelindustrin expanderar ökar behovet av att minska produktionskostnaderna. En lösning på detta problem som det forskas om idag är procedurell generering av spelinnehåll. Kortfattat innebär detta att en algoritm gör det manuella arbetet istället för en designer. I denna uppsats presenterar vi en sådan metod för att automatisera processen att skapa kartor i digitala spel. Vår metod använder kontrollerbara agenter med blandade initiativ (dvs. designern och algoritmen turas om) för att skapa geometri. Vi använder stokastiska agenter för att skapa variation och deterministiska agenter för att garantera spelbarhet. För att kontrollera dessa agenter använder vi en uppsättning parametrar som kan manipuleras. Däröver har designern tillgång till ett antal verktyg inklusive möjligheten att låsa befintlig geometri, konvertera geometri till andra typer, lägga till geometri manuellt, och även möjligheten att använda agenter på specifika områden på kartan. Vi tittar på spelläget Battle i det digitala spelet Mario Kart 64 och visar hur vår metod kan användas för att skapa sådana kartor. Vi utförde en användarstudie på outputen från metoden och resultatet visar att kvaliteten är i allmänhet gynnsam. / The process of creating content for digital games by hand is a costly and time consumingone. As the game industry expands, the need to reduce costs becomes ever more pressing.One solution to this problem being research today is procedural generation of content.In short, this means that an algorithm does the labor rather than a designer. In thisthesis we present such a method for automating the process of creating maps in digitalgames. Our method uses controllable software agents and mixed initiative (i.e. allowingthe designer and algorithm to take turns) to create geometry. We use stochastic agentsto create variation and deterministic agents to ensure playability. To control these agentswe use a set of input parameters which can be manipulated. Furthermore, the designerhas access to a number of tools including the ability to lock existing geometry, convertgeometry to other types, add geometry manually, as well as the ability to use agents onspecific areas of the map. We look at the game mode Battle in the digital game MarioKart 64 and show how our method can be used to create such maps. We conducted auser study on the output of the method and the results show that the quality is generallyfavorable.

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.

As the video gaming industry continues to grow, developers face increasing pressure to produce innovative content swiftly and cost-effectively. Procedural Content Generation (PCG), the use of algorithms to automate content creation, offers a solution to this problem. This paper explores the PCG algorithm wave function collapse’s (WFC) potential for replicating the stylistic design in video games. We provide an exploration of how the WFC algorithm works and discuss the methodology used to evaluate the generator’s ability to generate content that mimics a video game style. The study evaluates the algorithm’s efficacy by generating levels in the style of the iconic game Super Mario Bros, highlighting its ability to produce original content while maintaining the game’s stylistic features. Additionally, we do an examination of the research surrounding PCG and Machine Learning in Super Mario Bros, drawing comparisons with our methodology. The paper concludes with an assessment of WFC’s capabilities to replicate style with its generated content with the help of earlier established evaluation metrics. / Med den växande videospelsindustrin så möter utvecklare ett ökande tryck att producera innovativt innehåll snabbt och kostnadseffektivt. Procedural Content Generation (PCG), användningen av algoritmer för att automatisera skapandet av sådant innehåll, erbjuder en lösning på detta problem. Denna artikeln utforskar PCG-algoritmen wave function collapses (WFC) potentiella användning för att replikera design i datorspel. Vi ger en förklaring hur WFC-algoritmen fungerar och diskuterar metodiken som används för att utvärdera generatorns förmåga att generera innehåll som efterliknar ett visst datorspel stil. Studien utvärderar algoritmens effektivitet genom att generera nivåer i samma stil som i det ikoniska spelet Super Mario Bros, vilket betonar algoritmens förmåga att producera originellt innehåll samtidigt som den bevarar spelets stilistiska egenskaper. Dessutom undersöker forskningen kring PCG och maskininlärning i Super Mario Bros, och gör jämförelser med vår egna metodik. Uppsatsen avslutas med en bedömning av WFC:s förmåga att replikera stil med dess genererade innehåll med hjälp av tidigare etablerade utvärderingsmått.

Procedural Content Generators (PCG) typically excel at generating a large amount of content in a short period of time. Whilst this is making PCG very applicable for the game industry, simplistic implementations of PCG lack in Usability whereas complex implementations of PCG lack in Controllability. The purpose of this study is therefore to deepen our understanding on the correlation between Controllability and Usability in algorithmic generators that utilizes a generic and constructive approach to generate terrain in games.Furthermore the findings in this study can be used in the field of procedural terrain generators to study deterministic generators that utilize Automatic generation, from a Usability or Controllability perspective.

<p dir="ltr">Omnidirectional images are a way to visualize an environment in all directions. They have a spherical topology and require careful attention when represented by a computer. Namely, mapping the sphere to a plane introduces stretching of the spherical image content, and requires at least one seam in the image to be able to unwrap the sphere. Generative neural networks have shown impressive ability to synthesize images, but generating spherical images is still challenging. Without specific handling of the spherical topology, the generated images often exhibit distorted contents and discontinuities across the seams. We describe strategies for mitigating such distortions during image generation, as well as ensuring the image remains continuous across all boundaries. Our solutions can be applied to a variety of spherical image representations, including cube-maps and equirectangular projections.</p><p dir="ltr">A closely related problem in generative networks is 3D-aware scene generation, wherein the task involves the creation of an environment in which the viewpoint can be directly controlled. Many NeRF-based solutions have been proposed, but they generally focus on generation of single objects or faces. Full 3D environments are more difficult to synthesize and are less studied. We approach this problem by leveraging omnidirectional image synthesis, using the initial features of the network as a transformable foundation upon which to build the scene. By translating within the initial feature space, we correspondingly translate in the output omnidirectional image, preserving the scene characteristics. We additionally develop a regularizing loss based on epipolar geometry to encourage geometric consistency between viewpoints. We demonstrate the effectiveness of our method with a structure-from-motion-based reconstruction metric, along with comparisons to related works.</p>

Tesis por compendio / [ES] Los videojuegos son proyectos multidisciplinares que implican, en buena medida, el desarrollo de software. Esta tesis trata la faceta del desarrollo de videojuegos relativa al software mediante la Ingeniería del Software basada en Búsqueda (SBSE, Search-based Software Engineering). El objetivo específico de este trabajo es valerse de las características de los videojuegos en pro de una Ingeniería del Software de Videojuegos basada en Búsqueda (SBGSE, Search-based Game Software Engineering), incluyendo el uso de simulaciones de videojuegos para guiar búsquedas, codificación de granularidad fina y operaciones genéticas de mejora. Las aproximaciones propuestas superan a las de referencia en mantenimiento (trazabilidad de requisitos) y creación de contenido (generación de NPCs). El mantenimiento y la creación de contenido son, a menudo, tareas esenciales para garantizar la retención de usuarios por medio de actualizaciones o expansiones. Además, esta investigación aborda la necesidad de estudios de caso industriales. Esta tesis presenta un compendio que incluye tres artículos realizados durante el proceso de investigación y publicados en revistas académicas, con resultados que muestran que las aproximaciones de la Ingeniería del Software de Videojuegos basada en Búsqueda (SBGSE, Search-based Game Software Engineering) pueden mejorar la calidad de las soluciones generadas, así como reducir el tiempo necesario para producirlas. / [CA] Els videojocs són projectes multidisciplinaris que impliquen, en bona part, el desenvolupament de software. Aquesta tesi tracta la faceta del desenvolupament de videojocs relativa al software mitjançant l'Enginyeria del Software basada en Cerca (SBSE, Search-based Software Engineering). L'objectiu específic d'aquest treball és valdre's de les característiques dels videojocs en pro d'una Enginyeria del Software de Videojocs basada en Cerca (SBGSE, Search-based Game Software Engineering), incloent-hi l'ús de simulacions de videojocs per a guiar cerques, codificació de granularitat fina i operacions genètiques de millora. Les aproximacions proposades superen a les de referència en manteniment (traçabilitat de requisits) i creació de contingut (generació de NPCs). El manteniment i la creació de contingut són, sovint, tasques essencials per a garantir la retenció d'usuaris per mitjà d'actualitzacions o expansions. A més, aquesta investigació aborda la necessitat d'estudis de cas industrials. Aquesta tesi presenta un compendi que inclou tres articles realitzats durant el procés d'investigació i publicats en revistes acadèmiques, amb resultats que mostren que les aproximacions de l'Enginyeria del Software de Videojocs basada en Cerca (SBGSE, Search-based Game Software Engineering) poden millorar la qualitat de les solucions generades, així com reduir el temps necessari per a produir-les. / [EN] Video games are multidisciplinary projects which involve software development to a significant extent. This thesis tackles the software aspect of video game development through Search-based Engineering. Specifically, the objective of this work is to leverage the characteristics of video games towards Search-based Game Software Engineering, including the use of video game simulations to guide the search, a fine-grained encoding, and improvement genetic operations. The approaches proposed outperform the baselines in maintenance (requirement traceability) and content creation (NPC generation) tasks. Maintenance and content creation are often essential tasks to ensure player retention by means of updates or expansions. In addition, this research addresses the need for industrial case studies. This thesis presents a compendium that includes three papers produced through the research and published in academic journals, with results that show that Search-based Game Software Engineering approaches can provide improved solutions, in terms of quality and time cost. / This work has been partially supported by the Ministry of Economy and Competitiveness (MINECO) through the Spanish National R+D+i Plan and ERDF funds under the Project ALPS (RTI2018-096411-B-I00). / Blasco Latorre, D. (2024). Towards Search-based Game Software Engineering [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/203655 / Compendio