Get best of the week

Creating roguelike in Unity from scratch: dungeon generator

image

This time we will plunge into the implementation of the algorithm of the dungeon generator. In the last article, we created the first room, and now we will generate the rest of the dungeon level.

But before we get started, I would like to fix a mistake from a previous post. In fact, in recent weeks I have learned something new, which is why some of the work I have done is outdated, and I want to talk about it.

Remember the Position class we created? In fact, Unity already has a built-in class that performs exactly the same functions, but with slightly better control - it is easier to declare and process. This class is called Vector2Int. Therefore, before starting, we will remove the Position class from MapManager.cs and replace each Position variable with the Vector2Int variable.


The same thing needs to be done in several places in the DungeonGenerator.cs script. Now let's get down to the rest of the algorithm.

Stage 7 - room / hall generation


We will start with a small change to the function FirstRoom () created last time. Instead of creating another function to generate all the other elements of the map and duplicate a bunch of code, we simply transform this function, turning it into a generalized GenerateFeature (). Therefore, change the name from FirstRoom to GenerateFeature.

Now we will need to pass parameters to this function. First of all, you need to know what function it generates - a room or a corridor. We can just pass a string called type. Next, the function needs to know the starting point of the element, that is, from which wall it comes from (because we always create a new element from the wall of the older element), and for this, passing as the Wall argument is enough. Finally, the first room to be created has special characteristics, so we need an optional bool variable that tells whether the item is the first room. By default, it is false: bool isFirst = false. So the function title will change from this:


on this:


Fine. The next step is to change the way you calculate the width and height of the element. While we calculate them, getting a random value between the min and max values ​​of the height and width of the rooms - this is ideal for rooms, but will not work for corridors. So, so far we have the following:


But the corridors will have a constant size of 3 in width or height, depending on the orientation. Therefore, we need to check what the element is - a room or a corridor, and then perform the appropriate calculations.


So. we check if the item is a room. If yes, then we do the same as before
- we get a random number in the interval between min and max of height and width. But now in else of the same if you need to do something a little different. We need to check the orientation of the corridor. Fortunately, when generating a wall, we save information about which direction it is directed, so we use it to get the orientation of the corridor.


But we have not yet declared the variable minCorridorLength. You need to go back to variable declarations and declare it, right above maxCorridorLength.


Now back to our conditional switch statements. What we are doing here: we get the value of the direction of the wall, that is, where the wall is looking, from which the corridor will go. Direction can have only four possible values: South, North, West and East. In the case of South and North, the corridor will have a width of 3 (two walls and a floor in the middle) and a variable height (length). For West and East, everything will be the other way around: the height will be constantly equal to 3, and the width will have a variable length. So let's do it.


Wow. And that’s where we ended up with sizing the new item. Now you need to decide where to put it. We placed the first room in a random place within the threshold values ​​relative to the center of the map.


But for all other elements, this will not work. They should start next to the random point on the wall from which the element is generated. So let's change the code. First, we need to check if the element is the first room. If this is the first room, then we define the starting points in the same way as before - as half the width and height of the map.


In else, if the element is not the first room, then we get a random point on the wall from which the element is generated. First, we need to check if the wall has a size of 3 (this will mean that it is the end point of the corridor), and if so, then the middle point will always be selected, that is, index 1 of the wall array (with 3 elements, the array has indices 0, 1, 2). But if the size is not equal to 3 (the wall is not the end point of the corridor), then we take a random point in the interval between point 1 and the length of the wall minus 2. This is necessary to avoid passages created in the corner. That is, for example, on a wall with a length of 6, we exclude indexes 0 and 5 (first and last), and select a random point among points 1, 2, 3 and 4.


Now we have the position of the point on the wall at which a new element will be created. But we cannot just start generating an element from there, because this way it will be blocked by already placed walls. It is also important to note that the element begins to be generated from its lower left corner, and then the increment is performed to the right and up, so we must set the initial position in different places, depending on the direction in which the wall is looking. In addition, the first column x and the first row y will be walls, and if we start a new element right next to a point on the wall, we can create a corridor ending in a corner of the room, and not in a suitable place on the wall.

So, if the wall is directed to the north, then it is necessary that the element starts in one position to the north along the y axis, but in a random number of positions to the west along the x axis, in the range from 1 to the width of the room-2. In the south direction, the x axis acts the same, but the starting position on the y axis is the position of the point on the wall minus the height of the room. The western and eastern walls follow the same logic, only with inverted axes.

But before doing all this, we need to save the position of the wall point in the Vector2Int variable so that we can manipulate it later.


Great. Let's do that.


So, we generated an element with the size and position, and the next step is to place the element on the map. But first, we need to find out if there really is space on the map for this element in this position. For now, we just call the CheckIfHasSpace () function. It will be highlighted in red, because we have not yet implemented it. We will do this right after we finish what needs to be done here in the GenerateFeature () function. Therefore, ignore the red underline and continue.


In the next part, walls are created. Until we touch it, with the exception of the fragment in the second for loop .


While writing this post, I noticed that these if-else constructs are completely wrong. For example, some walls in them will receive a length of 1. This happens because when the position is to be added, say, to the north wall, then if it was at the corner with the east wall, it will not be added to the east wall, as it should. This caused annoying bugs in the generation algorithm. Let's eliminate them.

Fixing them is pretty simple. It is enough to delete everything else so that the position passes through all the if constructs , and does not stop at the first if it returned true . Then the last else (the one that is not else if ) is changed to if, which checks that the position has already been added as Wall, and if it is not, adds it as Floor.


Amazing, we're almost done here. Now we have a completely new element, created in the right place, but it is the same as our first room: it is completely enclosed by walls. This means that the player will not be able to get to this new place. That is, we need to convert a point on the wall (which, as we recall, is stored in a variable of type Vector2Int) and the corresponding point on the wall of a new element in Floor. But only when the element is not the first room.


This piece of code checks to see if the new item is the first room. If not, it converts the last position of the wall to the floor, and then checks the direction the wall is looking in order to check which tile of the new element should turn into the floor.

We have reached the last part of the GenerateFeature () function. It already has lines that add information about the element that the function creates.


Here we need to change something. Firstly, the element type is not always equal to Room. Fortunately, the required variable is passed to the function as a parameter, namely the type string. So let's just replace “Room” here with type.


Good. Now, for the algorithm generating all the elements of the game to work correctly, we need to add new data here. Namely, an int that counts the number of items created and a list of all items created. We go up to the place where we declare all the variables and declare an int with the name countFeatures, as well as a List of elements with the name allFeatures. The list of all elements must be public, and the int counter can be private.


Now back to the GenerateFeature () function and add a few lines to the end: incrementing the countFeatures variable and adding a new element to the allFeatures list.


So, our GenerateFeature () is almost complete. Later we will need to return to it to fill in the empty CheckIfHasSpace function, but first we need to create it. That’s what we’ll do now.

Stage 8 - check if there is a place


Now let's create a new function right after the GenerateFeature () function completes. She needs two arguments: the position at which the element begins, and the position at which it ends. You can use two Vector2Int variables as them. The function should return a bool value so that it can be used in if to check for space.


It is underlined in red, because so far it hasn’t returned anything. Soon we will fix it, but for now we will not pay attention. In this function, we will loop through all the positions between the beginning and the end of the element, and check whether the current position in MapManager.map is null or something is already there. If there is something there, then we stop the function and return false. If not, then continue. If the function reaches the end of the loop without meeting the filled places, then return true.

In addition, before checking the position for null, we need a line to check whether the position is within the map. Because otherwise, we may get an array index error and a game crash.


Fine. Now back to the place where we insert this function inside the GenerateFeature () function. We need to fix this call because it does not pass the necessary arguments.

Here we want to insert an if statement to check if there is enough space for the element. If the result is false, then we end the function without inserting a new element into MapManager.map.


We need to pass the required arguments, that is, two Vector2Int variables. With the first, everything is simple, this is the position with the x and y coordinates of the element's start point.


The second is harder, but not by much. This is the starting point plus height for y and width for x, subtracting 1 from both (because the start has already been taken into account).


Now let's move on to the next step - creating an algorithm to call the GenerateFeature () function.

Stage 9 - call generated elements


Back to the GenerateDungeon () function created in the previous part of the article. Now it should look like this:


The call to FirstRoom () is underlined in red because we changed the name of this function. So let's just call the first room generation.


We passed the necessary arguments: “Room” as type, because the first room will always be Room, new Wall (), because the first room will not be created from any other, so we just pass null, and this is quite normal. Instead of new Wall (), you can substitute null , this is a matter of personal preference. The last argument determines whether the new element is the first room, so in our case we pass true .

Now we come to the main point. We use a for loop that will run 500 times - yes, we will try to add elements 500 times. But if the number of created elements (countFeatures variable) is equal to the maximum specified number of elements (maxFeatures variable), then we interrupt this cycle.


The first step in this loop is to declare the element from which the new element will be created. If we have created only one element (the first room), then it will be the original one. Otherwise, we randomly select one of the already created elements.


Now we will choose which wall of this element will be used to create the new element.


Please note that we do not have this ChoseWall () function yet. Let's write it quickly. Go down to the end of the function and create it. It should return a wall, and use an element as an argument, so that the function can select the wall of this element.


I created it between the CheckIfHasSpace () and DrawMap () functions. Note that if you are working in Visual Studio, which is installed with Unity, you can use the - / + fields on the left to collapse / expand parts of the code to simplify the work.

In this function we will find the wall from which the element has not yet been created. Sometimes we will get elements with one or more walls of which other elements are already attached, so we need to check again and again whether any of the random walls is free. To do this, we use a for loop repeated ten times - if after these ten times a free wall is not found, then the function returns null.


Now back to the GenerateDungeon () function and pass the original element as a parameter to the ChoseWall () function.


The line if (wall == null) continue;means that if the wall search function returned false, then the original element cannot generate a new element, therefore the function will continue the cycle, that is, it could not create a new element and proceeds to the next iteration of the cycle.

Now we need to select the type for the next item. If the source element is a room, then the next one must be a corridor (we do not want the room to lead directly to another room without a corridor between them). But if this is a corridor, then we need to create the likelihood that another corridor or room will be next.


Fine. Now we just need to call the GenerateFeature () function, passing it the wall and type as parameters.


Finally, go to the Unity inspector, select the GameManager object and change the values ​​to the following:


If you now click on the play button, then you will already see the results!


As I said, this is not the best dungeon. We got a lot of dead ends. But it is fully functional, and it guarantees that you will not have a room that is not connected to any other.

I hope you enjoyed it! In the next post, we will create a player who will move through the dungeon, and then we will turn the map from ASCII into sprite.

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.UI;

public class Post3 : MonoBehaviour {
    public int mapWidth;
    public int mapHeight;

    public int widthMinRoom;
    public int widthMaxRoom;
    public int heightMinRoom;
    public int heightMaxRoom;

    public int minCorridorLength;
    public int maxCorridorLength;
    public int maxFeatures;
    int countFeatures;

    public bool isASCII;

    public List<Feature> allFeatures;

    public void InitializeDungeon() {
        MapManager.map = new Tile[mapWidth, mapHeight];
    }

    public void GenerateDungeon() {
        GenerateFeature("Room", new Wall(), true);

        for (int i = 0; i < 500; i++) {
            Feature originFeature;

            if (allFeatures.Count == 1) {
                originFeature = allFeatures[0];
            }
            else {
                originFeature = allFeatures[Random.Range(0, allFeatures.Count - 1)];
            }

            Wall wall = ChoseWall(originFeature);
            if (wall == null) continue;

            string type;

            if (originFeature.type == "Room") {
                type = "Corridor";
            }
            else {
                if (Random.Range(0, 100) < 90) {
                    type = "Room";
                }
                else {
                    type = "Corridor";
                }
            }

            GenerateFeature(type, wall);

            if (countFeatures >= maxFeatures) break;
        }

        DrawMap(isASCII);
    }

    void GenerateFeature(string type, Wall wall, bool isFirst = false) {
        Feature room = new Feature();
        room.positions = new List<Vector2Int>();

        int roomWidth = 0;
        int roomHeight = 0;

        if (type == "Room") {
            roomWidth = Random.Range(widthMinRoom, widthMaxRoom);
            roomHeight = Random.Range(heightMinRoom, heightMaxRoom);
        }
        else {
            switch (wall.direction) {
                case "South":
                    roomWidth = 3;
                    roomHeight = Random.Range(minCorridorLength, maxCorridorLength);
                    break;
                case "North":
                    roomWidth = 3;
                    roomHeight = Random.Range(minCorridorLength, maxCorridorLength);
                    break;
                case "West":
                    roomWidth = Random.Range(minCorridorLength, maxCorridorLength);
                    roomHeight = 3;
                    break;
                case "East":
                    roomWidth = Random.Range(minCorridorLength, maxCorridorLength);
                    roomHeight = 3;
                    break;

            }
        }

        int xStartingPoint;
        int yStartingPoint;

        if (isFirst) {
            xStartingPoint = mapWidth / 2;
            yStartingPoint = mapHeight / 2;
        }
        else {
            int id;
            if (wall.positions.Count == 3) id = 1;
            else id = Random.Range(1, wall.positions.Count - 2);

            xStartingPoint = wall.positions[id].x;
            yStartingPoint = wall.positions[id].y;
        }

        Vector2Int lastWallPosition = new Vector2Int(xStartingPoint, yStartingPoint);

        if (isFirst) {
            xStartingPoint -= Random.Range(1, roomWidth);
            yStartingPoint -= Random.Range(1, roomHeight);
        }
        else {
            switch (wall.direction) {
                case "South":
                    if (type == "Room") xStartingPoint -= Random.Range(1, roomWidth - 2);
                    else xStartingPoint--;
                    yStartingPoint -= Random.Range(1, roomHeight - 2);
                    break;
                case "North":
                    if (type == "Room") xStartingPoint -= Random.Range(1, roomWidth - 2);
                    else xStartingPoint--;
                    yStartingPoint ++;
                    break;
                case "West":
                    xStartingPoint -= roomWidth;
                    if (type == "Room") yStartingPoint -= Random.Range(1, roomHeight - 2);
                    else yStartingPoint--;
                    break;
                case "East":
                    xStartingPoint++;
                    if (type == "Room") yStartingPoint -= Random.Range(1, roomHeight - 2);
                    else yStartingPoint--;
                    break;
            }
        }

         if (!CheckIfHasSpace(new Vector2Int(xStartingPoint, yStartingPoint), new Vector2Int(xStartingPoint + roomWidth - 1, yStartingPoint + roomHeight - 1))) {
            return;
        }

        room.walls = new Wall[4];

        for (int i = 0; i < room.walls.Length; i++) {
            room.walls[i] = new Wall();
            room.walls[i].positions = new List<Vector2Int>();
            room.walls[i].length = 0;

            switch (i) {
                case 0:
                    room.walls[i].direction = "South";
                    break;
                case 1:
                    room.walls[i].direction = "North";
                    break;
                case 2:
                    room.walls[i].direction = "West";
                    break;
                case 3:
                    room.walls[i].direction = "East";
                    break;
            }
        }

        for (int y = 0; y < roomHeight; y++) {
            for (int x = 0; x < roomWidth; x++) {
                Vector2Int position = new Vector2Int();
                position.x = xStartingPoint + x;
                position.y = yStartingPoint + y;

                room.positions.Add(position);

                MapManager.map[position.x, position.y] = new Tile();
                MapManager.map[position.x, position.y].xPosition = position.x;
                MapManager.map[position.x, position.y].yPosition = position.y;

                if (y == 0) {
                    room.walls[0].positions.Add(position);
                    room.walls[0].length++;
                    MapManager.map[position.x, position.y].type = "Wall";
                }
                if (y == (roomHeight - 1)) {
                    room.walls[1].positions.Add(position);
                    room.walls[1].length++;
                    MapManager.map[position.x, position.y].type = "Wall";
                }
                if (x == 0) {
                    room.walls[2].positions.Add(position);
                    room.walls[2].length++;
                    MapManager.map[position.x, position.y].type = "Wall";
                }
                if (x == (roomWidth - 1)) {
                    room.walls[3].positions.Add(position);
                    room.walls[3].length++;
                    MapManager.map[position.x, position.y].type = "Wall";
                }
                if (MapManager.map[position.x, position.y].type != "Wall") {
                    MapManager.map[position.x, position.y].type = "Floor";
                }
            }
        }

        if (!isFirst) {
            MapManager.map[lastWallPosition.x, lastWallPosition.y].type = "Floor";
            switch (wall.direction) {
                case "South":
                    MapManager.map[lastWallPosition.x, lastWallPosition.y - 1].type = "Floor";
                    break;
                case "North":
                    MapManager.map[lastWallPosition.x, lastWallPosition.y + 1].type = "Floor";
                    break;
                case "West":
                    MapManager.map[lastWallPosition.x - 1, lastWallPosition.y].type = "Floor";
                    break;
                case "East":
                    MapManager.map[lastWallPosition.x + 1, lastWallPosition.y].type = "Floor";
                    break;
            }
        }

        room.width = roomWidth;
        room.height = roomHeight;
        room.type = type;
        allFeatures.Add(room);
        countFeatures++;
    }

    bool CheckIfHasSpace(Vector2Int start, Vector2Int end) {
        for (int y = start.y; y <= end.y; y++) {
            for (int x = start.x; x <= end.x; x++) {
                if (x < 0 || y < 0 || x >= mapWidth || y >= mapHeight) return false;
                if (MapManager.map != null) return false;
            }
        }

        return true;
    }

    Wall ChoseWall(Feature feature) {
        for (int i = 0; i < 10; i++) {
            int id = Random.Range(0, 100) / 25;
            if (!feature.walls[id].hasFeature) {
                return feature.walls[id];
            }
        }
        return null;
    }

    void DrawMap(bool isASCII) {
        if (isASCII) {
            Text screen = GameObject.Find("ASCIITest").GetComponent<Text>();

            string asciiMap = "";

            for (int y = (mapHeight - 1); y >= 0; y--) {
                for (int x = 0; x < mapWidth; x++) {
                    if (MapManager.map[x, y] != null) {
                        switch (MapManager.map[x, y].type) {
                            case "Wall":
                                asciiMap += "#";
                                break;
                            case "Floor":
                                asciiMap += ".";
                                break;
                        }
                    }
                    else {
                        asciiMap += " ";
                    }

                    if (x == (mapWidth - 1)) {
                        asciiMap += "\n";
                    }
                }
            }

            screen.text = asciiMap;
        }
    }
}

More articles:


All Articles