Level Design in Open Worlds using PCG

Master's Thesis

This is my master's thesis project, in which I did some deep research about Level Design and how it relates to game experiences and open-world games. I also explored how to implement level design principles algorithmically with Procedural Content Generation (PCG).


Project Overview

In this portfolio entry I summarize my research outcomes (Level Design tab) and implementation details (Tools Programming tab). You can find my full thesis in the next link:

→ Master's Thesis Current Draft (before final corrections)

The work of this thesis spanned over a year and a half. It consisted of 6 months of research, 2 months of design & implementation, and 4 months of writting the final document. The research is framed around four pillars: Game Experiences, Open Worlds, Level Design and Procedural Content Generation (PCG). The two more important pillars are Level Design and PCG, each of which is treated in the 'Level Design' and 'Tools Programming' tabs of this project's description. Here is a summary of the two resulting artefacts of the work in this thesis:

  • Theoretical artefact: Level Design Guidelines. These are a collection of level design concepts, principles, tips, practices, patterns, etc. that serve as the foundation of a taxonomy. Although level design has a purely theoretical nature in this project, it has served me as to grasp the core design principles and practices and become a better designer.
  • Practical artefacts: Two Prototypes in Unity. My first idea consisted of building a small scale open-world prototype. However, due to implementation challenges and time constraints I ditched this project for a simpler proof of concept. The second prototype generates a map following specific level design guidelines.

The Discarded Prototype

My first work hours on this prototype after the design phase focused on getting the character controller and interaction systems running. I implemented gliding controls, health, stamina, and an inventory system.

To implement the character controller I built a metrics playground to test the game feel and measure the distances between platforms. I also made use of a museum to display all my items and test their interactions and looks both on the scene and inside the inventory.

Although I spent quite some time on getting all these previous systems, I came to the realization that I could no longer work on this prototype when I run into a massive hurdle in the level generation, as I imposed myself the task to create an open-world level generator with verticality at its core. Here I decided to jump into the second prototype to use as a proof of concept, instead of a playable artefact. Still, there are several interesting implementation details about the world generation of this first prototype in the 'Tools Programming' tab.

My other research

My research about Game Experiences, Open-world games, and PCG can be summarized in the following diagrams:

Game Experiences are defined through the MDA framework. I explain the nature of goals as game objectives that are born from the player desires. These desires can be self-imposed or induced by the game designers. Game experiences are related to level design through the concept of Goal Negotiation, which determines what the player wishes to do, and what the game offers through its systems and objectives.

'Open World' does not consitute a game genre, but a qualifier that sits on top of the genre that defines some additional characteristics. These characteristics include large continuous worlds, exploration and progression mechanics, non-linearity, and emergent gameplay among others. I used these characteristics to identify specific level design principles and guidelines that were applicable in this context. This is because I wanted the level design guidelines to be broad enough so that they could be applicable to many different contexts. Some examples of games that are considered open-world but that are quite different from one another include: Minecraft, Assasin's Creed, Firewatch, Satisfactory, Elden Ring, and Goat Simulator.

For the PCG research I merged several taxonomies I run into and framed them in a general purpose, since some of them had specific considerations for the game genres they were aiming for. I then listed several types of methods grouping them by recurring properties they shared. With that, I listed several benefits, drawbacks, and considerations which then I related to the needs of open-world games. Finally, I looked into how other people have tried to integrate PCG with handcrafted content and level design principles, finding a major research gap in the latter topic.

Level Design

The Taxonomy

My work on level design research focused on describing a list of guidelines that could serve future designers (such as myself) understand level design principles in a way that they are applicable and easy to grasp. I explored dozens of professional resources and GDC talks to gather a collection of level design concepts, tips, practices, patterns, etc. Then, I arranged them in a diagram, grouping and linking concepts until my current taxonomy of level design emerged. It is not perfect nor finished, but rather a foundation of knoledge that can be expanded methodically.

Here is a diagram where I summarize and link all the concepts I ran into during my research:

These concepts were then translated into 4 different categories, which were then subdivided into 11 guidelines. I define level design as Guidance and Spatial Communication, but Goals and Engagement also serve a crucial role.

  • Goals. This category doubles up as a guideline, explaining how to design objectives and how to apply 'Goal Negotiation'. It links my research on game experiences with level design, and it explains the role of player motivation and desires. It also introduces the concepts of layering goals, presenting goals clearly and reinforcing them, and it talks about the importance of rewards.
  • Engagement. This category explains how to get the player involved with the game and how to keep them invested in spending more time with it. It groups the following three guidelines, while it also acknowledges other important factors such as Challenge, Unpredictability, Variety, and Game Feel:
    • Choices. This is the main characteristic that defines video games as a media. It is related to player agency, and it explains how to create meaningful and conscious choices through several tools: consequences, risk VS reward, not involving randomness, variety, and signposting. It also defends the importance of player intentionality.
    • Meaning. This guideline explains the connections the player experiences with the game. These connections can be cognitive, spatial, personal, and emotional. In terms of level design, the pertinent category is the spatial one. Here, we can make use of environmental storytelling and psychogeography.
    • Pacing. This refers to the speed at which experiences unfold over time. It defines how quickly events, information, or actions are presented to the player. Level design plays a crucial role here, as it is the one in charge of the order in which goals are presented to the player. Here, the usage of variety, layering of goals, and downtime is essential.
  • Guidance. This category refers to how all the design decissions are directed towards conducting the player through the intended game experience. It presents several conceptual and practical tools to effectively apply this guidance.
    • POIs. (Points of Interest) These are locations that have a visually distinctive appearance and which are usually linked to gameplay opportunities. Players can use them as weenies to orient themselves in a space. POIs have several properties (density, frequency, uniqueness, complexity, visual impact...), which both determine and should be determine by the level of interest of the location. Some examples of POIs include HUBs, landmarks, enemy camps, etc.
    • Pathing (resources). This guideline serves as a collection of tools we have to construct levels. These should be used following the principles explained by the rest of the guidelines (meaning, pacing, variety...). These can be divided in four categories:
      • Sightlines. Used to transmit specific bits of information to the player. Some tools include corners, pitch points, and vistas.
      • Flow Control. These include one-way valves, branching, choke points (funnelling)... .
      • Revisiting Areas. Some tools are shortcuts, backtracking, and bidirectional gameplay.
      • Obstacles. This is an important sub-guideline. It explains how to define limits in the player space. It describes boundaries and gates, where gates are types of boundaries that can change state. These can be soft or hard depending on how strict they are. This guideline explains in detail different types of locks and keys, which are quite useful to arrange progression graphs.
    • Curiosity. This guideline explains how to construct mystery to encourage player agency over the intended experience. It has both theoretical and practical tools to incentivize this curiosity. Some theoretical tools include partial information, uncertainty, foreshadowing, denial spaces, and the usage of pockets of tension. The most important practical tool is spatial lures, which are used as 'breadcrumbs'. These are used to create contrast through means such as color, light, sound, scale, or even motion.
  • Spatial Communication. This category also serves as a guideline that explains how to transmit information and emotions through layouts and placement of level elements. An important concept this guideline explains is the visual language. This is a type of implicit communication that makes use of affordances to guide the player. Affordances have to be readable and consistent. This allows players to make conscious choices.
    • Spatial Structure. This guideline explains the physical structure of layouts and their properties. Some of these properties include scale, verticality, openness, tightness, symmetry, etc. It also describes different types of spaces, such as sandbox, playgrounds, or arenas. An important concept explained in this guideline are cognitive maps, which consist of the mental representation the player has of the space. This guideline explains how to construct layouts following a graph approach, describing cycles, backtracking, shortcuts, branching, gating, etc. It essentially explains how to put to practice the tools explained in the rest of the guidelines, with a especial attention to Pathing resources.

Here are two representations of the guidelines. The first image shows a synthesis of the previous block of text. The second image displays a possible sorting of the guidelines in a way that they could be applicable in a production pipeline.

Building a Toolkit

While researching level design I run into the realization that many of the concepts explained throughout the sources didn't quite work as guidelines. These sources provided knowledge of many different shapes: design patterns, considerations, practices, developer insights, consequences, tips... For this reason, I divided these concepts into three separate categories: Design Considerations, Design Practices, and Design Guidelines. In particular, I wanted the guidelines to be easy to grasp, informative, and actionable. For these reasons, I designed the following structure for a guideline:

  • Description.
    • 'What is it?'. This section describes the nature of the guideline, the theory that supports it and its relevance.
    • 'What it achieves/focuses on'. This section explains the practical application of the guideline, why it is important to consider and what effect it is intended to have over the game experience.
    • 'How to apply'. This section covers practical ways of applying the guideline. It describes how to achieve all the effects described on the previous sections.
    • 'Counter Effects'. This section explains different outcomes of not following this guideline. Some of these might be desirable given the intended game experience.
  • Real Industry Examples. This section grounds the theory in real examples, asserting when a guideline is implemented or not, and the effect it has over a game.
  • Metrics and Validation. This section explains tools to ensure you are properly applying the guideline.
  • Related to. This section explains the connection the guideline has with the rest of the body of knowledge, crucial to understand how everything works together.

Guideline Example

Here I present a quick look into the 'Goals' guideline, in a very syntheitc and summarized manner:

  • Description.
    • 'What is it?'. Goals are objectives born from player desires. These are a direct representation of the game's core mechanics.
    • 'What it achieves/focuses on'. Goals are closely related to the MDA framework. They are heavily linked to the concept of goal negotiation. Available goals should align with the intended gameplay experience.
    • 'How to apply'. Goals should encourage the intended experience, but not enforce it. Goals can be layered: provide opportunities to the player to decide which goal to engage with. Goals should be stated clearly, reinforced throughout the game, and offer rewards when completed.
    • 'Counter Effects'. Too few goals can lead to restrictive gameplay. Too many can become overwhelming.
  • Real Industry Examples. Zelda BOTW has a deep layering of goals. The Last of Us presents and reinforces goals by attatching them to visual level elements. Sable offers little to no rewards to achieving its goals, which makes it more unpopular.
  • Metrics and Validation. List your goals and arrange them spatially and chronologically. Assess that there is enough variety and flexibility for your player to choose from. Track the rewards/consequences each goal offers.
  • Related to. Heavily related to Engagement, choices, meaning, pacing, POIs, and Curiosity.

Results

Although I didn't have enough time to write down and evaluate all the guidelines, they served me as a foundation of knowledge and as a starting point to better understand how to approach level design. I intend to further develop these, most probably as a community work instead of writting it all down myself. I also intend to validate them in the future through crowdsourcing and contact senior level designers to provide their insights on them.

Tools Implementation

The implementation of these procedural generators is deeply looked at in my thesis (check the Overview tab). Here I present a summary of the algorithms I had to implement and some of the design decissions I took during the development.

Prototype 1: Floating Islands Generation

In this prototype I wanted to generate a world with floating islands, where the character could glide and fly across them, slowly gathering better materials and resources and improving their movement capabilities. I wanted to have different biomes, which would determine both the looks of the islands and their scale and distribution. I run into the issue of the complexity of measuring distances and constraints between islands, so this prototype wasn't fully implemented. However, here is a quick look at how far I got into it.

Firstly, I defined a 3D grid space where each cell represents a biome, with its particular generation properties. These properties determine the shape, scale, scarcity, and sparsity of the islands. Biomes have specific settings that define where in the world they can appear. e.g. The green biome appears only at the bottom center layer, and purple can only appear in the shape of a torus in higher altitudes. The following image represents the process of populating the grid with biomes. The first image shows how the game occurs inside a dome. In the second image I sample random locations for every biome (following the previous constraints). In the third image I grow these samples to fill up the space. Each of these cells will then contain what I defined as a 'cluster of islands'.

To generate each individual cluster of islands, I sample a Perlin Noise texture filtered with a Sigmoid function and a threshold. This method provides a highly controllable result that looks like the image to the left. Then, to soften the hard cuts of the edges I discard every pixel that is outside the circumscripted circle area. With this texture, I run a CCL (Connected-component labeling) algorithm to identify individual islands, so that I can treat them separately and vary their Y position. For each individual island, I use the brightness of each pixel to discretely determine the altitude of an island piece (given a verticality factor). This translates in the three coloured levels on the image to the right. Once every island piece (1x1) has a set altitude, I group the pieces into larger squares and rects. This serves several purposes: aesthetic, performance, and instancing requirements. The islands look better from below, there are less individual pieces to render, and I can make sure I can instantiate large structures on top of large tiles without them overlapping with other geometry.

I my current implementation I run this process for each biome cell. At the scale I built the world that implied over 500 cells, which then resulted in about 12 seconds of generation time. This is a bit over 2ms of compute time for each cluster, which is quite good given I implemeted this logic on the CPU.

While writting down my results on the thesis I realized a much better and performant way of approaching this generation. Instead of creating every island cluster in runtime for each biome cell, I could generate individual islands offline, discard the islands that collide with the edges of the texture (to avoid weird cutsoffs), and have precalculated metrics to easen the process of placing the islands on the generation step. I intend to implement this in a not so distant future, since I am quite curious about the performance improvement this could pose. This also means that I could generate infinite chunkable worlds if I were to change the biome generation algorithm as well.

Prototype 2: Adventure Map Generation

This prototype was born from the idea to propose a one to one translation of design ideas into algorithms. I didn't want to spend more time implementing game mechanics, I just wanted to get to the point of the thesis, which was to show the feasibility of translating the level design guidelines into procedural algorithms. I also wanted to showcase different types of PCG methods, that's why you can find a diversity of disconnected algorithms, instead of a cohesive generation structure. With this, I decided to create a map generator as a proof of concept (not-playable prototype). Here are some generation results. The first picture shows a top-down view of the map, where rivers, mountains, and paths between towns are visisble. The other two pictures display how buildings are spawned in clusters, usually close to the water. Paths connect nearby buildings.

The map generation starts with the terrain. I first generate the altitude map with 3 octaves of Perlin Noise. I then use a hand-painted texture as input to showcase the integration of an algorithm with high designer controllability. This texture is used to define bodies of water. In the example portrayed in the thesis this texture is shaped as rivers. I calculate a new texture called 'near-water map', where brightests pixels are the ones closest to the water. Then I use this second texture to mask the elevation texture. This method 'paints' the water in the elevation map, and smooths out the areas around it to have more realistic-looking results. Finally, I calculate the gradient of the elevation map, which provides a new texture where brightest pixels represent the steepness of the terrain. These textures are the basic elements required to define spawn constraints of level elements later on.

An interesting type of spawnable element are town buildings, of which there are two types: houses and towers. Towers in particular can alter the terrain and smooth it out in a 3x3 unit area. As design constraints, buildings should be more likely to spawn near water bodies, and they shoud also avoid too steep terrains. I also want to create villages, so that buildings cluster together instead of being randomly scattered across the whole map. To do so, I first sample random pixels with these previous constraints (using the 'near water' texture and the inclination map), and then paint circles at those locations with a random radius (up to 7 units). Then, I use these circles as a mask to create a spawn map for town buildings.

Two other helper textures I generated are the 'global map' and some A* weights. I use the global map to determine safe locations to spawn elements without overlapping. This texture is always applied as a mask on top of the constraints textures of every spawnable element. For every type of spawnable element, I first pick all the required locations following its spawn constraints, and then I update the global map marking all these locations as unavailable all at once for the next pass.

The A* weights texture is used to connect town buildings with paths withing a maximum reach (which avoid paths being created across the whole map between two different buildings). This texture is created using both the water input texture and the 'inclination map' to determine areas where creating a path is more costly.

As a general rule for spawnable elements, I wanted to have configurable parameters to determine their distribution following the POIs guideline. With these, I can define if an element is unique (can only be spawned once). Specific unique locations include the player's spawn point, a dungeon, and the castle. For non-unique elements, I can define their frequency, which is configured through distribution settings such as mean, standard deviation, and min/max thresholds. Each spawnable object also defines its area of influence, which determines its radius to black out from the global map. Some example spawnable elements I included were forest tiles, chests, quest markers, crystal caves, campfires, NPCs, and enemies.

Enemies are quite interesting. The specific type of enemy to instantiate is ruled by two variables: intensity and difficulty. There are 3 levels of intensity (minion, enemy camp, and boss fight), each of which has variations with increasing difficulty. The spawn constraints for enemies are also governed by these two variables. Additionally, enemies are more likely to spawn in higher altitudes. To determine areas with higher difficulty and intensity, I created a system to generate Perlin Noise textures, one for each variable. With these two designer inputs, the system offers a highly controllability over the pacing of the game. One can define pockets of tension and spikes of difficulty organically, and how these combine with each other.

In the future, I want to come back to this project and integrate some specific guidelines on these maps. I particularly want to focus on the Pathing guideline, which would probably require implementing some kind of progression graph generator on top of the map generator. I also want to move some of these generation algorithms into the GPU to get faster results (right now generating this map takes about 15 seconds on an Ryzen 7 2700). A further improvement I would look into would be changing some of the generation rules to allow for infinite worlds generation.