Gameplay progression in procedurally generated dungeons

How to build games that build themselves

By Mathias Bruin

Table of contents

  1. Concept
  2. Procedural generation
    • 2.1 BSP
  3. Generating meshes
    • 3.1 Generating doors
    • 3.2 Generating walls
  4. Gameplay progression
    • 4.1 Spawning
    • 4.2 Introducing enemies
    • 4.3 Ramping difficulty
  5. Future reference

Introduction

Do you like spending a lot of time making stuff that makes stuff, so you can save time on making stuff? Try looking into PCG. PCG or, Procedural Content Generation, is one of the methods that can be used for creating game elements, such as levels, by generating dungeon rooms of variant sizes and layouts. But how do you create fun and interesting gameplay progression in a procedurally generated environment? And what principles are used to create procedurally generated dungeon rooms? This blog aims to answer those questions and more.

1. Concept

PCG has always seemed like an interesting concept to me. The idea behind automatically creating different levels by programming algorithms seems very useful when developing games with varying dungeon layouts. This is why I was particularly looking forward to the workshop about PCG. Sadly, due to the planning of this semester, the workshop was “cancelled” (or rather, turned into a individual assignment). Despite the lack of of a fully fletched out workshop, or perhaps because of it, I decided I wanted to look further into PCG and how the concepts behind it could be used to create procedural dungeon layouts.

Having a procedural dungeon is great, but doesn’t help much if you still need to manually design each dungeon level with enemy placements and ramping difficulty. That’s why I wanted to implement some basic game design concepts into the procedural dungeon generation algorithms as well.

2. Procedural Generation

Procedural generation is essentially a way for game developers to introduce carefully controlled elements of randomness into their work (Baker, 2016). This method of creation is particularly useful for generating game elements that would otherwise require way too much manual labor to create (think all the different planets in ‘No Man’s Sky’).

To get started on Procedural Dungeon Generation, first there are a couple of different algorithms to choose from. The two mayor algorithms are ‘Cellular Automata’ which is used to create more natural dungeons/cave systems, and secondly there is ‘Binary Space Partitioning’, which is often used to create more rectengular rooms. Since the goal is to create a dungeon consisting of a multitude of differently sized rectengular rooms, this is the algorithm we will be using.

2.1 BSP

The tricky part in procedural generation is not to make things random, but to make them in a consistent way despite it’s randomness. In particular, when making a dungeon you have to face the problem of filling the space with elements in a natural way. (Uribe, 2019).

One of the methods that can be used to achieve this, is Binary Space Partitioning (BSP). BSP is a method that recursively splits cells untill each subsections of the dungeon is room-sized. To achieve this method we keep splitting nodes in random directions (vertical/horizontal) untill we achieve the desired results.

To achieve this, first a BSP node class needs to be created that holds the information of the nodes (such as position and size) and the logic for the splitting of the nodes (one thing to note is that we start with a root node that contains the level size).

Now that we have a class that holds most of the information necessary to create and split the nodes, we still need logic to split the nodes and set the sizes of each rooms. This is handled by the split method which is used to determine the split direction of each leaf by simply checking if the room is wider than it is tall to split vertically or taller than it is wide to split horizontally and setting the size.

After creating the split method we can start actually creating the nodes.

//Main.cs

void CreateRooms()
{
    //root handles level size
    root = new BSPLeaf(0, 0, levelSizeX, levelSizeY);

    leaves.Add(root);

    for (int i = 0; i < leaves.Count; i++)//(BSPLeaf leaf in leaves)
    {
        if (leaves[i].leftChild == null && leaves[i].rightChild == null) //if this leaf is not already split
        {
            if (leaves[i].Split())
            {
                //If we did split, add child leafs
                leaves.Add(leaves[i].leftChild);
                leaves.Add(leaves[i].rightChild);
            }
        }
    }

}

Now that all the nodes are placed and properly sized, we can get started on generating the meshes.

3. Generating Meshes

Meshes contain vertex data and “face” data, with faces most often being triangles. The mesh face data, i.e. the triangles it is made of, is simply three vertex indices for each triangle. For example, if the mesh has 10 triangles, then the triangles array should be 30 numbers, with each number indicating which vertex to use. The first three elements in the triangles array are the indices for the vertices that make up that triange; the second three elements make up another triangle and so on. Unity (2020).

Since the logic for our rooms generates squares/rectangles. The most obvious course of action would be to generate planes (Unity gameObjects) at the position of the nodes, with the specified width and height. Looking at the wireframe of the plane shown below however, we can see that the plane is made up of 200 triangles.

Wireframe of Unity Plane gameObject

To combat this problem, we can use one of Unity’s different ways to generate meshes. Unity has a multitude of ways to generate low performance planes. One of which, would be to simply generate the entire mesh through code by generating the desired vertices, connecting them via triangles and adding a mesh to it. This can be of great use if the mesh needs to be alterable through script during runtime for example. For our concept however, this will not be necessary. Unity has another solution for this without the need to manually generate the objects, namely generating Primitive Quads.


The quad primitive resembles the plane but its edges are only one unit long and the surface is oriented in the XY plane of the local coordinate space. Also, a quad is divided into just two triangles whereas the plane contains two hundred. A quad is useful in cases where a scene object must be used simply as a display screen for an image or movie. Simple GUI and information displays can be implemented with quads, as can particles, sprites and “impostor” images that substitute for solid objects viewed at a distance (Unity, 2020).

The same shape is generated but the amount of triangles is severely reduced

The code used to generate the quads during runtime is as follows:

    quad = GameObject.CreatePrimitive(PrimitiveType.Quad);
    quad.transform.position = new Vector3(x + (width * 0.5f), y + (height * 0.5f), 0f);
    quad.transform.localScale = new Vector3(width, height, 1f);

This combined with the logic of creating the rooms, generates our dungeon layout with this being the result, where every different colored quad resembles a dungeon room:

One of the possibilities generated by the PCG algorithm

3.1 Generating Doors

Now that the rooms are generated we can get started on generating the walls and doors. To to this, we first need to understand Unity’s Transforms. Every object in a Scene has a Transform. It’s used to store and manipulate the position, rotation and scale of the object. Every Transform can have a parent, which allows you to apply position, rotation and scale hierarchically Unity (2020).

Another useful thing to note is that a cube (with a scale of 1) resembles 1 Unity size measurement or, Unity unit (Unity 2020). Knowing this, and the fact that Unity Transforms by default start at the center of an object, we can start figuring out our door placements.

To get the full range of a room in the Unity scene, we need to figure out the spread of the minimum X, minimum Y, maximum X and maximum Y values that a room can reach. Since transforms start at the center of an objec, the scaling happens form the center aswell. So a cube with a scale of 10 on the ‘X’ axis will have it’s endpoint at position 5 on the ‘X’ axis in the inspector.

the endpoint of the scaled cube

Therefore, if we want to calculate the endpoints of a quad, we can simply take the transform.position (center of the object) and for each axis add or subtract half the local scale of said axis. For example, to get the maximum Y value that the room reaches we can take the transform.position.y + transform.localScale.y /2.

The code to get the endpoints of each room is as follows:

    minY = transform.position.y - transform.localScale.y / 2;
    maxY = transform.position.y + transform.localScale.y / 2;
    minX = transform.position.x - transform.localScale.x / 2;
    maxX = transform.position.x + transform.localScale.x / 2;

Since the transform of each object is at the center of each room, we can safely assume that if the center of a room lies within the reaches of another room that (that we know attaches to it, by checking if the minX/minY of the room is the same as the maxX/maxY of the room that we’re checking from) we can say that the dooropening should be somewhere around the transforms center at either the far end of the X axis or the far end of the Y axis. To do this, we generate two door pieces, one on the leftside or bottomside and one on the rightside or topside (depending on if it’s a vertical or horizontal door). Once we’ve checked if the rooms are horizontally or vertically connected, we can add them to the corresponding list of the checking room and get started on generating the doors. The code to generate the vertical doors looks like this:

        for (int i = 0; i < rightChildren.Count; i++)
        {
            //Create 2 doors on either side of the transform of the child with doorWidth as the space in between 
            GameObject RDoor1 = Instantiate(wall, new Vector3(transform.position.x + transform.localScale.x / 2, 
                rightChildren[i].transform.position.y, main.wallHeight / -2), Quaternion.identity);
            RDoor1.transform.localScale = new Vector3(wall.transform.localScale.x, (rightChildren[i].transform.localScale.y / 2)
                - (main.doorWidth), main.wallHeight);
            RDoor1.transform.position = new Vector3(RDoor1.transform.position.x, (RDoor1.transform.position.y - (main.doorWidth))
                - (RDoor1.transform.localScale.y / 2), RDoor1.transform.position.z);
            RDoor1.name = "door";
            RDoor1.transform.SetParent(main.doorHolder, true);

            GameObject RDoor2 = Instantiate(wall, new Vector3(transform.position.x + transform.localScale.x / 2,
                rightChildren[i].transform.position.y, main.wallHeight / -2), Quaternion.identity);
            RDoor2.transform.localScale = new Vector3(wall.transform.localScale.x, (rightChildren[i].transform.localScale.y / 2)
                - (main.doorWidth), main.wallHeight);
            RDoor2.transform.position = new Vector3(RDoor2.transform.position.x, (RDoor2.transform.position.y + (main.doorWidth))
                + (RDoor2.transform.localScale.y / 2), RDoor2.transform.position.z);
            RDoor2.name = "door";
            RDoor2.transform.SetParent(main.doorHolder, true);

        }

And the code to generate the horizontal doors looks like this:

            for (int i = 0; i < bottomChildren.Count; i++)
        {
            //Create 2 doors on either side of the transform of the child with doorWidth as the space in between 
            GameObject BDoor1 = Instantiate(wall, new Vector3(bottomChildren[i].transform.position.x, transform.position.y - 
                transform.localScale.y / 2, main.wallHeight / -2), Quaternion.identity);
            BDoor1.transform.localScale = new Vector3((bottomChildren[i].transform.localScale.x / 2) - 
                (main.doorWidth), wall.transform.localScale.y, 20);
            BDoor1.transform.position = new Vector3((BDoor1.transform.position.x - (main.doorWidth)) - 
                (BDoor1.transform.localScale.x / 2), BDoor1.transform.position.y, BDoor1.transform.position.z);
            BDoor1.name = "door";
            BDoor1.transform.SetParent(main.doorHolder, true);

            GameObject BDoor2 = Instantiate(wall, new Vector3(bottomChildren[i].transform.position.x, transform.position.y - 
                transform.localScale.y / 2, main.wallHeight / -2), Quaternion.identity);
            BDoor2.transform.localScale = new Vector3((bottomChildren[i].transform.localScale.x / 2) - 
                (main.doorWidth), wall.transform.localScale.y, 20);
            BDoor2.transform.position = new Vector3((BDoor2.transform.position.x + (main.doorWidth)) + 
                (BDoor2.transform.localScale.x / 2), BDoor2.transform.position.y, BDoor2.transform.position.z);
            BDoor2.name = "door";
            BDoor2.transform.SetParent(main.doorHolder, true);
        }

With this being the result:

PCG dungeon with generated doors

3.2 Generating Walls

Since the list of BSP nodes contains our root node with information about the level size, we can simply call on those values to generate our walls and roof. Following the same principles as the door generation. The code to generate our walls and roof looks like this: 

    GameObject leftWall = Instantiate(wall, new Vector3(main.levelSizeX, main.levelSizeY / 2, main.wallHeight/-2), Quaternion.identity);
    leftWall.transform.localScale = new Vector3(wall.transform.localScale.x, main.levelSizeY, main.wallHeight);
    leftWall.name = wall.name;

    GameObject rightWall = Instantiate(wall, new Vector3(0, main.levelSizeY / 2, main.wallHeight / -2), Quaternion.identity);
    rightWall.transform.localScale = new Vector3(wall.transform.localScale.x, main.levelSizeY, main.wallHeight);
    rightWall.name = wall.name;

    GameObject bottomWall = Instantiate(wall, new Vector3(main.levelSizeX / 2, main.levelSizeY, main.wallHeight / -2), Quaternion.identity);
    bottomWall.transform.localScale = new Vector3(main.levelSizeX, wall.transform.localScale.y, main.wallHeight);
    bottomWall.name = wall.name;

    GameObject topWall = Instantiate(wall, new Vector3(main.levelSizeX / 2, 0, main.wallHeight / -2), Quaternion.identity);
    topWall.transform.localScale = new Vector3(main.levelSizeX, wall.transform.localScale.y, main.wallHeight);
    topWall.name = wall.name;

    GameObject roof = Instantiate(wall, new Vector3(main.levelSizeX / 2, main.levelSizeY / 2, -main.wallHeight), Quaternion.identity);
    roof.transform.localScale = new Vector3(main.levelSizeX, main.levelSizeY, wall.transform.localScale.z);
    roof.name = "roof";

With this being the result (minus the roof):

4. Gameplay Progression

Progression gameplay is a game design term that refers to video game mechanics in which the designer sets a course of action that a player must complete to move forward in the game. Progression gameplay depends heavily on checkpoints that a character must reach to advance to the next level. These checkpoints vary according to the game genre. (Techopedia, 2017). For our game, the player has to explore dungeon rooms while defeating enemies, to collect 3 orbs that will teleport the player to the boss area.

4.1 Spawning

4.1.1 BossOrbs

For the orbs the player has to collect to spawn the boss, we need to spawn them in random rooms spread around the dungeon. To achieve this, we make use of Fisher–Yates Shuffle. The way the Fisher-Yates Shuffle does this is to “pull a random card from the deck repeatedly and set it aside, incrementally building a new stack. As long as you pick each remaining card from the deck with equal probability, you’ll have a perfectly-unbiased random stack when you’re done” (Bostock 2015):

void FisherYatesShuffle(int[] roomIndex)
{
    //Loops through array
    for (int i = roomIndex.Length - 1; i > 0; i--)
    {
        //Randomize a number between 0 and i (so that the range decreases each time)
        int rnd = Random.Range(0, i);

        //Save the value of the current i, otherwise it'll overright when we swap the values
        int temp = roomIndex[i];

        //Swap the new and old values
        roomIndex[i] = roomIndex[rnd];
        roomIndex[rnd] = temp;
    }

    for (int i = 0; i < orbAmount; i++)
    {
        bossOrbs.Add(roomIndex[i]);
    }
}

After the rooms are picked we simply spawn the orbs with a slight offset away from the walls to make sure they don’t spawn with parts of them stuck inside the walls. The code that spawns the orbs looks like this:

void SpawnOrbs()
{
    foreach(int index in bossOrbs)
    {
        roomGenerator = rooms[index].GetComponent<RoomGenerator>();

        float randomSpawnX = Random.Range(roomGenerator.minX + offset, roomGenerator.maxX - offset);
        float randomSpawnY = Random.Range(roomGenerator.minY + offset, roomGenerator.maxY - offset);

        GameObject InstantiatedOrb = Instantiate(orb, new Vector3(randomSpawnX, 2, randomSpawnY), Quaternion.identity);
    }
}

4.1.2 Enemies

The spawning of the enemies happens in largely the same manner as the orbs, with the only addition being that enemies “respawn” in an area around the player when the player tries to enter a new room while not having cleared the current room he’s in. This discourages speedrunning as well, as you will undoubtedly get swarmed if you try to progress while still being chased.

4.2 Introducing Enemies

To create our enemies, we must first better understand why we need/want enemies in our gameplay progression loop. According to gamedev.net (2015) “The clear intent is to create an obstacle that the player must first analyse and then devise a plan to overcome”. So how will that help us create our gameplay loop? gamedev.net (2015) also states that “The obvious approach to doing this is creating monsters that have progressively more life and deal more damage. Doing so however hardly challenges the player’s ability to observe and react which, in practice, take a lot more time than simply becoming better at honing one’s reflexes. If all enemies in the game were Sword Soldiers of varying strength, not only would the game become boring quickly, but it would also be much easier and faster to complete as whatever the player has learned to beat the sword soldier would apply to all other soldiers. So how, exactly, should monsters be created to enforce player observation and pattern recognition?”. So if simply increasing enemy strenght won’t work, what will? The article also mentions different Enemy types and Functions and how they can sometimes differ from eachother. This could be of great use when designing gamemechanics, like shooting or attacking.

Applying the gathered knowledge is of great importance for the player to feel rewarded for paying attention to and learning from unfamiliar situations. Therefore simply introducing new enemies each time the player enters a new area wouldn’t be optimal, since the player than never gets the chance to apply the knowledge gathered throughout the game. This is why, for the gameplay progression in this project, I deciced I would first introduce new enemies in an environment familiar to the player.

To achieve this, each enemy gets assigned a depth level at which it can be introduced to the player (each subsequent unvisited room the player enters resembles a depth level). Once the player has reached said depth, a dice is rolled to check if the enemy should be introduced or not. Should this not be the case, the EnemyGenerator.cs script will only generate enemies that are already familiar to the player. Otherwise the script will make sure 1 (and only 1) of the enemies that are about to spawn is the new enemy. After the enemy is introduced, the player can expect to see more of them combined with other previously introduced enemies in dungeon rooms to come.

4.3 Ramping Difficulty

To create a difficulty level in the precedurally generated dungeon, I created a system that spawns enemies based on the current depth of the player. Like previously discussed the depth of the player equals the room he’s in up till a maximum that is currently set to 5. This means that the player will progressively get more and a wider variety of enemies the further he gets in the dungeon. The system is created in way that makes it easily possible to increase the maximum depth the player can achieve, to spawn in more enemies.

Besides spawning more enemies, the player will also face a wider array of new enemies depending on the depth he’s currently in. For now the only pivotal depth point for the player is depth 2, where the ranged enemy can be introduced.

After the difficulty (depth) has reached it’s peak and the player has collected all the orbs, the player will be teleported to a boss level where he will face the endgame boss and can attempt to win the game.

5. Future Reference

Because the project was relatively short, not every system is fully fletched out. The introduction mechanic works well, but currently only introduces 1 enemy, the combat system is not good (this project mainly focussed mainly on the algorithms) and the door placement might feel a little repetative due to the fact that the guidelines for the PCG state the doors may only be generated in the middle of the end of a room. Therefore in the future these problems would need to be addressed before the project can become a fully fletched out game.

After that I would like to look further into the dungeon generation aspect of the project, and look into different height levels for the generated dungeons. That way the dungeon has impactful variation in not only the x and z axis but also the y axis.

Also in the future, it would be nice if some sort of lock-and-key system would be implemented to make the dungeon feel more like a puzzle than it currently does. I tried to gain this result by implementing the boss-orbs but would have liked to have done a lot more on this subject. Also traps would be a nice addition to keep the player on his/her toes throughout their exploring of the dungeon.

Texturing, lighting and sound are three other things that didn’t get done during this project. In the future the addition of these elements could really help elevate the look and feel of the dungeon to give it a spookier atmosphere.

Sources

Tags: , ,

Related Posts

Procedural planet generator