Procedural Content Generation (PCG) has become one of the hottest topics in Computational Intelligence and Artificial Intelligence (AI) game research in the past few years. PCG is the process of automatically creating content for video games, rather than by hand, and can offer great benefits for video games companies by helping to bring costs down and quality up. By guiding the process with AI it can be enhanced further and even be made to personalize content for target players. Among the current research into PCG, search-based approaches overwhelmingly dominate. While search-based algorithms have been shown to have great promise and produce several success stories there are a number of open challenges remaining. In this thesis, we present the Learning-Based Procedural Content Generation (LBPCG) framework, which is an alternative, novel approach designed to address some of these challenges. The major difference between the LBPCG framework and contemporary approaches is that the LBPCG is designed to learn about the problem space, freeing itself from the necessity for hard-coded information by the game developers. In this thesis we apply the LBPCG to a concrete example, the classic first-person shooter Quake, and present results showing the potential of the framework in generating quality content.

Open-world video games give players a large environment to explore along with increased freedom to navigate and manipulate that environment. These requirements pose several problems that must be addressed by a game's graphics engine. Often there are a large number of visible objects, such as all of the trees in a forest, as well as objects comprised of large amounts of geometry, such as terrain. An open-world graphics engine must be able to render large environments at varying levels of detail and smoothly transition between detail levels to provide a believable experience. Often this involves finding a way to both store and generate the large amounts of geometry that represent the environment. In this thesis we present a system for generating and rendering large exterior environments, with a focus on terrain and vegetation. We use a region-based procedural generation algorithm to create environments of varying types. This algorithm produces content that can be rendered at multiple levels of detail. The terrain is rendered volumetrically to support caves, overhangs, and cliffs, but is also rendered using heightmaps to allow for large view distances. Vegetation is implemented using procedurally generated meshes and impostors. The volumetric terrain is editable in real time, which limits our ability to pre-generate or cache large amounts of geometry, and also limits the number of assumptions we can make with regard to visibility. We support a view distance of at least 25 miles in each direction, though distant objects are rendered at low resolution. The heightmap terrain used to achieve this view distance consists of over 360,000 triangles. Our system runs at 180 frames per second on commodity desktop hardware.

Die Arbeit bildet einen Einstieg in das Themengebiet der prozeduralen Karten Generierung mit Cellular Automata und verweist auf fortführende Möglichkeiten. Es wird gezeigt, wie eine zwei-dimensionale und hexagonale Terrain-Karte für Strategiespiele mit Cellular Automata erzeugt werden kann. Dazu wird eine allgemeine Einführung zu zellulären Automaten gegeben. Zusätzlich werden Fashion-based Cellular Automata und Cellular Automata mit mehreren aktiven Zellen erklärt. Es werden die Anforderungen an eine Karte des Strategie-Genres bestimmt, wobei der Fokus, auf dem durch Civilisation definierten Sub-Genre liegt. Anschließend wird gezeigt, wie die verschiedenen Bestandteile der Karte jeweils mit einem Cellular Automaton generiert werden können. Zu diesen werden Vorteile und Nachteile dargestellt und dabei auf die Performance eingegangen. Es zeigt sich das zelluläre Automaten in der Lage sind eine geeignete Karte zu erzeugen.:1 Einleitung 1.1 Videospiele im Trend 1.2 Produktionsaufwand 1.3 Prozedurale Content Generierung 1.4 Cellular Automata 1.5 Kartengenerierung 1.6 Aufbau der Arbeit 1.7 Verwendete Werkzeuge 2 Hintergrund 2.1 Cellular Automata 2.1.1 Grundsätze 2.1.2 Initiale globale Konfiguration eines CA 2.1.3 CA-Ansätze 2.1.3.1 Lattice Gases 2.1.3.2 CA mit mehreren aktiven Zellen 2.1.3.3 Fashion-based 3 Anforderungsanalyse 3.1 Eingrenzung der Karte 3.2 Betrachtete Spiele 3.3 Analyse der Karten 3.4 Anforderungen 4 Implementierung 4.1 Schichtenmodell 4.1.1 Regionen 4.1.1.1 Ansatz 4.1.1.2 Resultat 4.1.2 Höhenstufen 4.1.2.1 Ansatz 4.1.2.2 Resultat 4.1.3 Flüsse 4.1.3.1 Initiale Konfiguration 4.1.3.2 Flussrichtung 4.1.3.3 Resultat 4.1.4 Ressourcen 4.1.4.1 Wälder 4.1.4.2 Allgemeine Ressourcen 4.1.4.3 Siedlungen 4.1.5 Dynamische Veränderungen 4.1.6 Performance 5 Fazit 5.1 Ausblick 6 Verzeichnisse 6.1 Literaturverzeichnis 6.2 Abbildungsverzeichnis 6.3 Tabellenverzeichnis

No description available.

Detta arbete handlar om Procedural Content Generation (PCG) i form av algoritmer som skapar osymmetriska banor, och fokuserar på att ge en översikt av prestanda avseende tid, storlek och tillgänglighetsgaranti. Tre olika algoritmer testades på hur lång tid det tog att skapa en bana, och hur stora dess banor blev, och om dessa banor tillåter att man kan nå alla gängliga områden. En Agentbaserad algoritm, Cellular Automata och Diffusion-limited Aggregation (DLA) studerades avseende dess styrkor och svagheter. Efter experimentet så drogs slutsatsen att DLA var mest effektiv inom tid och garanti dock skapade den små banor. Cellular Automata lyckades skapa stora rum men kunde de inte godkännas på punkten garanti, och den tog för lång tid att köra. Den Agentbaserade algoritmen misslyckades att skapa banor överhuvudtaget.

Procedural Content Generation innebär att spelinnehåll genereras automatiskt för att dels minska arbetsbelastningen hos designers men också för att öka variationen i spel. Ett användningsområde för detta är rumsbaserad bangenerering där banor byggs upp av fördefinierade rum. Målet med det här arbetet var att implementera och jämföra tre olika algoritmer som kan åstadkomma detta; Binary Space Partitioning, Shortest path och en evolutionär algoritm. De kriterier som algoritmerna utvärderades på var tidseffektivitet, variation och möjligheten att nå alla rum. Resultatet visade att Binary Space Partitioning och Shortest path var de två algoritmer som var bäst lämpade att användas i ett spel där genereringen ska ske under körtiden. Detta eftersom de genererade banor förhållandevis snabbt och av god kvalitet. Om arbetet skulle fortsätta i framtiden skulle det vara intressant att utföra fler tester med fler olika värden samt använda algoritmerna i ett spel och sedan låta spelare bedöma banorna som genereras.

Role-playing games (RPGs) rely on interesting and varied experiences to maintain player attention. These experiences are often provided through quests, which give players tasks that are used to advance stories or events unfolding in the game. Traditional quests in video games require very specific conditions to be met, and for participating members to advance them by carrying out pre-defined actions. These types of quests are generated with perfect knowledge of the game world and are able to force desired behaviors out of the relevant non-player characters (NPCs). This becomes a major issue in massive multiplayer online (MMO) when other players can often disrupt the conditions needed for quests to unfold in a believable and immersive way, leading to the absence of a genuine multiplayer RPG experience. Our proposed solution is to dynamically create quests from real-time information on the unscripted actions of other NPCs and players in a game. This thesis shows that it is possible to create logical quests without global information knowledge, pre-defined story-trees, or prescribed player and NPC behavior. This allows players to become involved in storylines without having to perform any specific actions. Results are shown through a game scenario created from the Panoptyk Engine, a game engine in early development designed to test AI reasoning with information and the removal of the distinction between NPC and human players. We focus on quests issued by the NPC faction leaders of several in-game groups known as factions. Our generated quests are created logically from the pre-defined personality of each NPC leader, their memory of previous events, and information given to them by in-game sources. Long-spanning conflicts are seen to emerge from factions issuing quests against each other; these conflicts can be represented in a coherent narrative. A user study shows that players felt quests were logical, that players were able to recognize quests were based on events happening in the game, and that players experienced follow-up consequences from their actions in quests.

Background. Procedural content generation (PCG) is a powerful tool used in manydifferent areas within game development. One of these areas are texturing where procedural generation have several advantages, including increased effectiveness, reducedstorage cost and unlimited texture resolution. Procedural texturing has long beenused in realistic games and the resulting textures can be indistinguishable from photographs, but when used in stylized games there is still a clear difference in aestheticbetween generated and traditionally painted textures. Objectives. By studying the visual properties of hand-painted stone tile textures,the different characteristic elements could be isolated. These elements can then beimplemented in procedural generation to recreate the iconic look. Methods. 37 different hand-painted textures were analyzed in accordance with aframework for objective art analysis used in art history. The elements identified inthe visual study were recreated in two different procedurally generated textures withthe use of Adobe Substance 3D Designer, a popular software for procedurally generating textures. Lastly a user study was conducted to investigate the impact of thedifferent elements. Results. The implementation resulted in 25 different versions which were rankedin the user study. 24 people in the ages 20-35 participated in the user study, andwhile one of the textures showed clear preference for certain elements over others,this pattern was not reflected in the second texture. Several different reasons for thisis discussed, as well as external factors that might have affected the outcome. Conclusions. The study successfully identified several elements commonly foundin hand-painted textures of stone tiles. However, the user study did not provide aclear answer to the impact of the different elements.

Målet med studien var att undersöka skalning av tidsåtgång och minnesanvändning utifrån tre stycken algoritmer som procedurellt genererar banor. De algoritmerna som används är Binary Space Partitioning (BSP), Shortest Path (SP) och Delaunay Triangulation (DT). Skalningen utvärderas genom att se hur tidsåtgången och minnesanvändningen påverkas då algoritmerna ska hantera större banor. Värdena för tid och minne sammanställdes sedan för att avgöra hur de skalade, till vilken grad de var användbara och vilken av algoritmerna som presterade bäst. Utvärderingen visade att BSP presterade bäst i båda kategorierna med relativt jämna värden. SP hade generellt väldigt spretiga tidsvärden. DT var långsammast av de tre algoritmerna i avseende på tid men presterade bättre än SP när det kom till minnesanvändning. Skalning av minne visade sig vara ett mindre problem än förväntat vilket inte är något problem för plattformar som inte är begränsade inbäddade system, exempelvis mikroprocessorer. Framtida studier hade kunnat testa andra algoritmer. / <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 introduce an alternative method for open-world scene generation. In this thesis, Graph-based Wave Function Collapse (GWFC) is integrated with Space Colonization Algorithm (SCA) and used to place objects in an unstructured 3D environment. This combined algorithm, Space Colonization Graph-based Wave Function Collapse (SC-GWFC), leverages the constraint-based capabilities of GWFC and the ability of SCA to populate arbitrary 3D volumes. We demonstrate that objects of variable scale can be successfully used with SC-GWFC. Since this algorithm is run in an interactive environment, we demonstrate iterative modifications to a partially complete scene and incorporate PCG into a scene editing process. As part of the implementation, we also introduce our Scene Modeling Application for rendering and editing 3D scenes. This modeling application allows for editing and viewing constraints for our SC-GWFC scene generator. We evaluate the performance characteristics of SC-GWFC in the Scene Modeling Application to demonstrate that SC-GWFC can be used interactively. Through the application, users can specify adjacency requirements for objects, and SC-GWFC will attempt to place objects in patterns that respect these rules. We demonstrate the ability to place up to 5000 items on a terrain using our proposed SC-GWFC technique.