How to procedurally generate a dungeon using the BSP method on Unity

An example of dungeon that can be generated with the tool you'll create.


Júlio Rodrigues ·

If you are new to the world of procedurally generation methods we recommend you read our other article that introduces the subject in the context of dungeon generation.

The method we're going to use in this tutorial is based on a procedure originally created to rapidly access 3d data (vertices, polygons, etc). As with most methods of PCG, we take an existing algorithm / data structure and repurpose it with the objective of producing content taking advantage of the method's natural form.

Binary space partitioning accomplishes fast querying of data by subdividing a scene recursively in subplanes and storing these planes in an organized way on a tree data structure. So we instead of subdividing an existing scene, we generate this tree as if the data already exists using random data so we can have our beautiful planes ready to be used as rooms. Later we connect this rooms using a strategy, we'll mention two but will exemplify only one.

After the tree has been constructed we'll use this data to create a tilemap, but keep in mind that you're not limited to use tilemaps, you could also create a 3d room (or any other type of room) but the process would be more complicated.

A sample project with the end result of this tutorial can be obtained at github.

What we'll build

The end result of this tutorial is a tool that can be used inside Unity containing parameters of the dungeon generation and a button to clear the dungeon and generate a new one.

We're not aiming to produce something that can be used to generate dungeons after the game has been built, although this definitely serves as a good starting point.

Prerequisites

  • Basic familiarity with tree data structures
  • Intermediary Unity C# scripting
  • Basic analytic geometry

Tree definition

A binary tree defined recursively can be implemented in C# by using two references.

BspTree.cs
public class BspTree {
    public BspTree left;
    public BspTree right;
}

Since the BSP method in the way we're using it will always produce full binary trees, we could alternatively store the nodes of our tree using an array without wasting memory. This is better for cache locality, a key to optimal CPU usage.

We also need to store where the container is as well as the room. We conclude our BspTree node definition with:

BspTree.cs
public class BspTree {
    public RectInt container;
    public RectInt room;
    public BspTree left;
    public BspTree right;
}

Only leaves will be used to represent rooms, the internal nodes will be used to connect their children.

High-level method

  1. Start with an initial dungeon size (e.g. 64x64 tiles), this is the current container.
  2. Do step 3. a predefined number N of iterations.
  3. For each leaf of the current container:
    1. Randomly choose a direction: vertical or horizontal
    2. Cut the current container in half in the selected direction. This cut, to be more interesting needs to have a margin of error, 1 to 7 percent is a good margin.
  4. For each leaf container, pick a smaller container with a random smaller area (2 to 10 percent is fine) this smaller area inside is a room.
  5. Connect the centers of the non-leaf containers.
  6. Paint each tile according to its neighborhood.

Two iterations example

See this slideshow to see an example of two iterations of the method being applied to a dungeon of size 64x64. This encompasses steps 1. through 4..

DungeonGenerator component

To get this process started on Unity you need a way to call the initial method. We'll do this by creating a MonoBehavior called DungeonGenerator. This component will also be responsible for painting the tilemap after the bsp method is finished.

DungeonGenerator.cs
public class DungeonGenerator : MonoBehaviour {

    public const int MIN_ROOM_DELTA = 2;

    public int dungeonSize;

    [Range (1, 6)]
    public int numberOfIterations;

    [Range (1, 4)]
    public int corridorThickness;

    public bool shouldDebugDrawBsp;

    private BspTree tree;

    public void GenerateDungeon () {
        ...
    }

}

The GenerateDungeon() method is called using a custom inspector, a custom inspector allows us to have more flexibility when creating the layout for the input of tiles used during tile painting.

Editor/DungeonGeneratorEditor.cs
[CustomEditor (typeof (DungeonGenerator))]
public class DungeonGeneratorEditor : Editor {

    public override void OnInspectorGUI () {
        // let's leverage the default implementation for later tile assignment
        DrawDefaultInspector ();

        DungeonGenerator myScript = (DungeonGenerator) target;
        if (GUILayout.Button ("Generate Dungeon")) {
            myScript.GenerateDungeon ();
        }
    }

}

The custom inspector is optional. If you also want to use a custom inspector remember to keep the file of it in a directory called Editor. See the official documentation if you want to learn more about custom inspectors.

Create a Grid and Tilemap by right-clicking in the Hierarchy window and choosing 2D Object -> Tilemap, now add the DungeonGenerator script you just created to it.

You should get something like that for the Grid game object DungeonGenerator component in the Inspector tab.

GenerateDungeon() method template

Each of the steps in the high-level method section will be called by this public method. This is what it should look like by the end of the implementation:

DungeonGenerator.cs
public void GenerateDungeon () {
    InitReferences ();
    GenerateContainersUsingBsp ();
    GenerateRoomsInsideContainers ();
    GenerateCorridors ();
    FillRoomsOnTilemap ();
    PaintTilesAccordingToTheirNeighbors ();
}

But there's no need to create all these methods right now. Keep all but the first two calls commented.

References initialization and map clearing

Each time the Generate Dungeon button is pressed we want to clear the map, but it does no harm to also reset the reference since this is only done once for each generation.

DungeonGenerator.cs
private void InitReferences () {
    map = GetComponentInChildren<Tilemap> ();
    map.ClearAllTiles ();
}

Generating containers using the BSP method

This is a naturally recursive process. The initial call will contain parameters borrowed by the public interface of the component.

DungeonGenerator.cs
private void GenerateContainersUsingBsp () {
    tree = BspTree.Split (numberOfIterations,
        new RectInt (0, 0, dungeonSize, dungeonSize));
}

I've chosen for simplicity's sake to not use an objected oriented approach, but you're free to do so if you want to.

Our recursion termination condition is really simple, whenever numberOfIterations equals 0 we stop calling the method. The Split() method will delegate the actual container splitting to the SplitContainer() method. Notice that although our tree definition uses left and right as the name for its nodes it can also contain vertically separated containers.

BspTree.cs
internal static BspTree Split (int numberOfIterations, RectInt container) {
    var node = new BspTree (container);
    if (numberOfIterations == 0) return node;

    var splittedContainers = SplitContainer (container);
    node.left = Split (numberOfIterations - 1, splittedContainers[0]);
    node.right = Split (numberOfIterations - 1, splittedContainers[1]);

    return node;
}

And here's the heavy lifting:

BspTree.cs
private static RectInt[] SplitContainer (RectInt container) {
    RectInt c1, c2;

    if (UnityEngine.Random.Range (0f, 1f) > 0.5f) {
        // vertical
        c1 = new RectInt (container.x, container.y,
            container.width, (int) UnityEngine.Random.Range(container.height * 0.3f, container.height * 0.5f));
        c2 = new RectInt (container.x, container.y + c1.height,
            container.width, container.height - c1.height);
    } else {
        // horizontal
        c1 = new RectInt (container.x, container.y,
            (int) UnityEngine.Random.Range (container.width * 0.3f, container.width * 0.5f), container.height);
        c2 = new RectInt (container.x + c1.width, container.y,
            container.width - c1.width, container.height);
    }
    return new RectInt[] { c1, c2 };
}

The RectInt is being used to represent our containers and rooms instead of defining our own rectangle description class since it has everything we need.

We start the method by picking a random number between 0 and 1 to choose a cut direction with equal probability. The cut is always done with a 40% margin but with at least 60% of the dimension preserved, this is done to prevent too thin containers from being generated.

Container Generation, done.

Optional: Visualization of the containers for debugging

You shouldn't trust my code, use Gizmos to visualize what you're building. To draw Gizmos you need to define the magic methods OnDrawGizmos and OnDrawGizmosSelected.

DungeonGenerator.cs
void OnDrawGizmos () {
    AttemptDebugDrawBsp ();
}

private void OnDrawGizmosSelected () {
    AttemptDebugDrawBsp ();
}

void AttemptDebugDrawBsp () {
    if (shouldDebugDrawBsp) {
        DebugDrawBsp ();
    }
}

public void DebugDrawBsp () {
    if (tree == null) return; // hasn't been generated yet

    DebugDrawBspNode (tree); // recursive call
}

public void DebugDrawBspNode (BspTree node) {
    // Container
    Gizmos.color = Color.green;
    // top
    Gizmos.DrawLine (new Vector3 (node.container.x, node.container.y, 0), new Vector3Int (node.container.xMax, node.container.y, 0));
    // right
    Gizmos.DrawLine (new Vector3 (node.container.xMax, node.container.y, 0), new Vector3Int (node.container.xMax, node.container.yMax, 0));
    // bottom
    Gizmos.DrawLine (new Vector3 (node.container.x, node.container.yMax, 0), new Vector3Int (node.container.xMax, node.container.yMax, 0));
    // left
    Gizmos.DrawLine (new Vector3 (node.container.x, node.container.y, 0), new Vector3Int (node.container.x, node.container.yMax, 0));

    // children
    if (node.left != null) DebugDrawBspNode (node.left);
    if (node.right != null) DebugDrawBspNode (node.right);
}

We're navigating in the tree graph using the DFS order since it's the easiest one to implement. There's nothing special in the DebugDrawBspNode method, just a bunch of DrawLine calls, one for each edge of the rectangle.

Rooms inside containers

Our rooms shouldn't occupy the entire container. We need to draw smaller areas insides of our containers to create the rooms of our dungeons.

DungeonGenerator.cs
private void GenerateRoomsInsideContainers () {
    BspTree.GenerateRoomsInsideContainersNode (tree);
}

Again we're using a DFS order to navigate our tree. The internal nodes aren't used in this step.

BspTree.cs
public bool IsLeaf () {
    return left == null && right == null;
}

public bool IsInternal() { // de morgan's
    return left != null || right != null;
}

public static void GenerateRoomsInsideContainersNode(BspTree node) {
    // should create rooms for leafs
    if (node.left == null && node.right == null) {
        var randomX = UnityEngine.Random.Range(DungeonGenerator.MIN_ROOM_DELTA, node.container.width / 4);
        var randomY = UnityEngine.Random.Range(DungeonGenerator.MIN_ROOM_DELTA, node.container.height / 4);
        int roomX = node.container.x + randomX;
        int roomY = node.container.y + randomY;
        int roomW = node.container.width - (int) (randomX * UnityEngine.Random.Range(1f, 2f));
        int roomH = node.container.height - (int) (randomY * UnityEngine.Random.Range(1f, 2f));
        node.room = new RectInt(roomX, roomY, roomW, roomH);
    } else {
        if (node.left != null) GenerateRoomsInsideContainersNode(node.left);
        if (node.right != null) GenerateRoomsInsideContainersNode(node.right);
    }
}

Nothing special here too, we just need to be careful with the parameters order.

Corridors connecting containers

This part was especially lacking on the literature when I was doing my research on the topic. Basically, there are two methods by which this can be done.

The first one is to just connect the centers of the parent containers, it's simple and works, but can lead to some weird looking dungeon shapes, since we're not trying to generate dungeons in real-time that's not a problem.

An alternative to connecting centers is to use a pathfinding algorithm. Doors are chosen, you could randomly pick a position for the walls in which in you want doors in and then run a pathfinding algorithm to connect these doors. This is a more advanced approach that has a chance to deliver better results.

DungeonGenerator.cs
private void GenerateCorridors () {
    // for each parent
    // find their center
    // find a direction and connect these centers
    GenerateCorridorsNode (tree);
}

private void GenerateCorridorsNode (BspTree node) {
    if (node.IsLeaf()) {
        RectInt leftContainer = node.left.container;
        RectInt rightContainer = node.right.container;
        Vector2 leftCenter = leftContainer.center;
        Vector2 rightCenter = rightContainer.center;
        Vector2 direction = (rightCenter - leftCenter).normalized; // arbitrarily choosing right as the target point
        while (Vector2.Distance (leftCenter, rightCenter) > 1) {
            if (direction.Equals (Vector2.right)) {
                for (int i = 0; i < corridorThickness; i++) {
                    map.SetTile (new Vector3Int ((int) leftCenter.x, (int) leftCenter.y + i, 0), mmTile);
                }
            } else if (direction.Equals (Vector2.up)) {
                for (int i = 0; i < corridorThickness; i++) {
                    map.SetTile (new Vector3Int ((int) leftCenter.x + i, (int) leftCenter.y, 0), mmTile);
                }
            }
            leftCenter.x += direction.x;
            leftCenter.y += direction.y;
        }
        if (node.left != null) GenerateCorridorsNode (node.left);
        if (node.right != null) GenerateCorridorsNode (node.right);
    }
}

RectInt is showing its usefullness again by having a center() method. The right reference is arbitratily chosen, we then subtract left from it and compute the normalized vector.

direction will be our direction in which we'll paint tiles. As long as the distance from the left center to the right center is greater than 1 we keep painting tiles in the direction pointed by direction. We also cross paint it in the other direction to get some thickness.

containers centered connected

Getting references to tiles

If you read our first article what we have now are steps 1. and 2. of the general PCG process. It's finally time to use the Unity API to use the data we created and turn it into a game asset. For this, we'll need to reference 9 tiles, one for each corner and middles of a dungeon floor tileset.

To aid our design process and make this tool easier to use we'll layout the tools public references on a 3x3 grid.

The terminology here is first the vertical description then the horizontality. So tl stands for top left and mr stands for middle right.

Editor/DungeonGeneratorEditor.cs
using UnityEditor;
using UnityEngine;

[CustomEditor (typeof (DungeonGenerator))]
public class DungeonGeneratorEditor : Editor {

    SerializedProperty tlTileProp;
    SerializedProperty tmTileProp;
    SerializedProperty trTileProp;
    SerializedProperty mlTileProp;
    SerializedProperty mmTileProp;
    SerializedProperty mrTileProp;
    SerializedProperty blTileProp;
    SerializedProperty bmTileProp;
    SerializedProperty brTileProp;
    bool showTiles = true;

    void OnEnable () {
        tlTileProp = serializedObject.FindProperty ("tlTile");
        tmTileProp = serializedObject.FindProperty ("tmTile");
        trTileProp = serializedObject.FindProperty ("trTile");
        mlTileProp = serializedObject.FindProperty ("mlTile");
        mmTileProp = serializedObject.FindProperty ("mmTile");
        mrTileProp = serializedObject.FindProperty ("mrTile");
        blTileProp = serializedObject.FindProperty ("blTile");
        bmTileProp = serializedObject.FindProperty ("bmTile");
        brTileProp = serializedObject.FindProperty ("brTile");
    }

    public override void OnInspectorGUI () {
        DrawDefaultInspector ();

        showTiles = EditorGUILayout.Foldout (showTiles, "Tiles");
        if (showTiles) {
            EditorGUILayout.BeginHorizontal ();
            EditorGUILayout.LabelField("T", GUILayout.Width(20));
            EditorGUILayout.PropertyField (tlTileProp, new GUIContent (""));
            EditorGUILayout.PropertyField (tmTileProp, new GUIContent (""));
            EditorGUILayout.PropertyField (trTileProp, new GUIContent (""));
            EditorGUILayout.EndHorizontal ();

            EditorGUILayout.BeginHorizontal ();
            EditorGUILayout.LabelField("M", GUILayout.Width(20));
            EditorGUILayout.PropertyField (mlTileProp, new GUIContent (""));
            EditorGUILayout.PropertyField (mmTileProp, new GUIContent (""));
            EditorGUILayout.PropertyField (mrTileProp, new GUIContent (""));
            EditorGUILayout.EndHorizontal ();

            EditorGUILayout.BeginHorizontal ();
            EditorGUILayout.LabelField("B", GUILayout.Width(20));
            EditorGUILayout.PropertyField (blTileProp, new GUIContent (""));
            EditorGUILayout.PropertyField (bmTileProp, new GUIContent (""));
            EditorGUILayout.PropertyField (brTileProp, new GUIContent (""));
            EditorGUILayout.EndHorizontal ();

            serializedObject.ApplyModifiedProperties();
        }

        DungeonGenerator myScript = (DungeonGenerator) target;
        if (GUILayout.Button ("Generate Dungeon")) {
            myScript.GenerateDungeon ();
        }
    }

}

If you aren't familiarized with SerializedProperty take a look at the official documentation. Basically, if you don't use it you'll need to handle undo and proper communication with the target script yourself.

And of course, we also need to create these references in the main component script.

DungeonGenerator.cs
public class DungeonGenerator : MonoBehaviour {

    ...

    [HideInInspector]
    public Tile tlTile;
    [HideInInspector]
    public Tile tmTile;
    [HideInInspector]
    public Tile trTile;
    [HideInInspector]
    public Tile mlTile;
    [HideInInspector]
    public Tile mmTile;
    [HideInInspector]
    public Tile mrTile;
    [HideInInspector]
    public Tile blTile;
    [HideInInspector]
    public Tile bmTile;
    [HideInInspector]
    public Tile brTile;

    ...
}

You're now able to drag & drop each of the tiles that are going to be used by the painting algorithm to the component.

Use that image as your reference

Painting the dungeon tilemap

Everything is now connected. We'll do another DFS walk in the tree to paint the tilemap using our leaves. Starting with a basic fill of all the rooms.

DungeonGenerator.cs
private void FillRoomsOnTilemap () {
    UpdateTilemapUsingTreeNode (tree);
}

private void UpdateTilemapUsingTreeNode (BspTree node) {
    if (node.IsLeaf()) {
        for (int i = node.room.x; i < node.room.xMax; i++) {
            for (int j = node.room.y; j < node.room.yMax; j++) {
                map.SetTile (new Vector3Int (i, j, 0), mmTile);
            }
        }
    } else {
        if (node.left != null) UpdateTilemapUsingTreeNode (node.left);
        if (node.right != null) UpdateTilemapUsingTreeNode (node.right);
    }
}

At this point what we have is a functional dungeon, but we want to use our tiles to make it genuine and beautiful. To choose the correct tile to apply we'll investigate the surrounds of each of the tiles of our tilemap and decide based on a rules system.

DungeonGenerator.cs
private Tile GetTileByNeihbors (int i, int j) {
    var mmGridTile = map.GetTile (new Vector3Int (i, j, 0));
    if (mmGridTile == null) return null; // you shouldn't repaint a n

    var blGridTile = map.GetTile (new Vector3Int (i-1, j-1, 0));
    var bmGridTile = map.GetTile (new Vector3Int (i,   j-1, 0));
    var brGridTile = map.GetTile (new Vector3Int (i+1, j-1, 0));

    var mlGridTile = map.GetTile (new Vector3Int (i-1, j, 0));
    var mrGridTile = map.GetTile (new Vector3Int (i+1, j, 0));

    var tlGridTile = map.GetTile (new Vector3Int (i-1, j+1, 0));
    var tmGridTile = map.GetTile (new Vector3Int (i,   j+1, 0));
    var trGridTile = map.GetTile (new Vector3Int (i+1, j+1, 0));

    // we have 8 + 1 cases

    // left
    if (mlGridTile == null && tmGridTile == null) return tlTile;
    if (mlGridTile == null && tmGridTile != null && bmGridTile != null) return mlTile;
    if (mlGridTile == null && bmGridTile == null && tmGridTile != null) return blTile;

    // middle
    if (mlGridTile != null && tmGridTile == null && mrGridTile != null) return tmTile;
    if (mlGridTile != null && bmGridTile == null && mrGridTile != null) return bmTile;

    // right
    if (mlGridTile != null && tmGridTile == null && mrGridTile == null) return trTile;
    if (tmGridTile != null && bmGridTile != null && mrGridTile == null) return mrTile;
    if (tmGridTile != null && bmGridTile == null && mrGridTile == null) return brTile;

    return mmTile; // default case
    }

    private void PaintTilesAccordingToTheirNeighbors () {
    for (int i = MIN_ROOM_DELTA; i < dungeonSize; i++) {
        for (int j = MIN_ROOM_DELTA; j < dungeonSize; j++) {
            var tile = GetTileByNeihbors (i, j);
            if (tile != null) {
                map.SetTile(new Vector3Int(i, j, 0), tile);
            }
        }
    }
}

What this method is doing is detailed but actually simple. For example, take a look at this line:

if (mlGridTile != null && bmGridTile == null && mrGridTile != null) return bmTile;

If both laterals of the middle line aren't nulls and the bottom middle is null that means we need a special bottom middle tile. All the other checks follow a similar reasoning.

correctly painted dungeon

Refining this method for true glory

I know, it was a long and tough tutorial, but it's just the beginning! To further elaborate this I suggest you do the following in any order:

  1. Use a different strategy to connect corridors.
  2. Place random treasures and enemies inside rooms according to some statistical distribution.
  3. Add a Tilemap Collider 2D to your dungeons.
  4. Use a fixed random state to create the possibility of saving dungeons.

Subscribe for more

I hope you liked learning how to procedurally generate dungeons using the bsp method! I really enjoyed it when I was first learning it during my research, their particular hierarchical nature is quite pleasing.

If you liked this tutorial be sure to subscribe to our email list, we won't ever spam you, we'll send you only the best tutorials and articles on game development we can produce.

Detailed Unity Tutorials in your inbox

Subscribe if you want to receive articles and tutorials like this one right in your inbox. 

Classify in:
  • pcg
  • bsp method
  • dungeon generation using tilemaps
© Bladecast 2018. All rights reserved.