Romain Beaudon

Random 2D dungeon generation in Unity using BSP (Binary Space Partitioning) trees

Intro

The approach and algorithm is based on this Stackexchange answer, and these related resources: eskerda.com/bsp-dungeon-generation and gamedevelopment.tutsplus.com/tutorials/how-to-use-bsp-trees-to-generate-game-maps

Unity intro

The sprites used in this post come from existing games and are used here only for learning purpose.

Build the structure

Let’s start with a new 2D project in Unity 5. Create a new Game Object called Board for holding the whole dungeon. On this game object create a new Script component called BoardManager. We’ll code the dungeon generation logic into it.

Unity new project

I recommend you refer to the stackexchange answer above for the illustrations of the following steps.

The idea of the algorithm is to start with a rectangular cell representing the whole dungeon. Then we’ll split this dungeon in two sub-dungeons, with a randomly chosen splitting position. The process will be repeated again for each sub-dungeons recursively, until the sub-dungeons are approximately the desired size of a room.

Our BoardManager script should look like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

public class BoardManager : MonoBehaviour {
  public int boardRows, boardColumns;
  public int minRoomSize, maxRoomSize;

  public class SubDungeon {
    public SubDungeon left, right;
    public Rect rect;
    public Rect room = new Rect(-1,-1, 0, 0); // i.e null
    public int debugId;

    private static int debugCounter = 0;

    public SubDungeon(Rect mrect) {
      rect = mrect;
      debugId = debugCounter;
      debugCounter++;
    }

    public bool IAmLeaf() {
      return left == null && right == null;
    }

    public bool Split(int minRoomSize, int maxRoomSize) {
      if (!IAmLeaf()) {
        return false;
      }

      // choose a vertical or horizontal split depending on the proportions
      // i.e. if too wide split vertically, or too long horizontally,
      // or if nearly square choose vertical or horizontal at random
      bool splitH;
      if (rect.width / rect.height >= 1.25) {
        splitH = false;
      } else if (rect.height / rect.width >= 1.25) {
        splitH = true;
      } else {
        splitH = Random.Range (0.0f, 1.0f) > 0.5;
      }

      if (Mathf.Min(rect.height, rect.width) / 2 < minRoomSize) {
        Debug.Log ("Sub-dungeon " + debugId + " will be a leaf");
        return false;
      }

      if (splitH) {
        // split so that the resulting sub-dungeons widths are not too small
        // (since we are splitting horizontally)
        int split = Random.Range (minRoomSize, (int)(rect.width - minRoomSize));

        left = new SubDungeon (new Rect (rect.x, rect.y, rect.width, split));
        right = new SubDungeon (
          new Rect (rect.x, rect.y + split, rect.width, rect.height - split));
      }
      else {
        int split = Random.Range (minRoomSize, (int)(rect.height - minRoomSize));

        left = new SubDungeon (new Rect (rect.x, rect.y, split, rect.height));
        right = new SubDungeon (
          new Rect (rect.x + split, rect.y, rect.width - split, rect.height));
      }

      return true;
    }
  }

  public void CreateBSP(SubDungeon subDungeon) {
    Debug.Log ("Splitting sub-dungeon " + subDungeon.debugId + ": " + subDungeon.rect);
    if (subDungeon.IAmLeaf()) {
      // if the sub-dungeon is too large
      if (subDungeon.rect.width > maxRoomSize
        || subDungeon.rect.height > maxRoomSize
        || Random.Range(0.0f,1.0f) > 0.25) {

        if (subDungeon.Split (minRoomSize, maxRoomSize)) {
          Debug.Log ("Splitted sub-dungeon " + subDungeon.debugId + " in "
            + subDungeon.left.debugId + ": " + subDungeon.left.rect + ", "
            + subDungeon.right.debugId + ": " + subDungeon.right.rect);

          CreateBSP(subDungeon.left);
          CreateBSP(subDungeon.right);
        }
      }
    }
  }

  void Start () {
    SubDungeon rootSubDungeon = new SubDungeon (new Rect (0, 0, boardRows, boardColumns));
    CreateBSP (rootSubDungeon);
  }
}

Then set the public variables for board and rooms size in the Unity editor.

Variables in editor

When launching the game you should have something like this in the console :

Unity split

Create the rooms

We now have a tree structure with the leaves corresponding to the smallest sub-dungeons. In each of these leaves we’ll now create a room with a random size.

Add the following variable and method to the SubDungeon class :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

  public class SubDungeon {
    //...
    public Rect room = new Rect(-1,-1, 0, 0); // i.e null
    //...
    public void CreateRoom() {
      if (left != null) {
        left.CreateRoom ();
      }
      if (right != null) {
        right.CreateRoom ();
      }
      if (IAmLeaf()) {
        int roomWidth = (int)Random.Range (rect.width / 2, rect.width - 2);
        int roomHeight = (int)Random.Range (rect.height / 2, rect.height - 2);
        int roomX = (int)Random.Range (1, rect.width - roomWidth - 1);
        int roomY = (int)Random.Range (1, rect.height - roomHeight - 1);

        // room position will be absolute in the board, not relative to the sub-dungeon
        room = new Rect (rect.x + roomX, rect.y + roomY, roomWidth, roomHeight);
        Debug.Log ("Created room " + room + " in sub-dungeon " + debugId + " " + rect);
      }
    }
    //...

And call it in the Start() method :

1
2
3
4
5

  void Start () {
    SubDungeon rootSubDungeon = new SubDungeon (new Rect (0, 0, boardRows, boardColumns));
    CreateBSP (rootSubDungeon);
    rootSubDungeon.CreateRoom ();
  }

The output console should look like this:

Unity rooms created console

Drawing the rooms ½: add a sprite for the floor

Instead of relying on console output, it would be more intuitive to start having a visual representation. First thing is to add a sprite for the floor of the rooms. You can use this one Room sprite and add it as an asset in your project.

Also be careful to set the Pixels Per Unit to exactly the size of the sprite (16 for this sprite), so that the sprite will cover exactly a square in the board.

Room sprite in Unity

Next create a Prefab with this sprite (drag and drop it on the scene screen, then drag and drop back the object in the assets):

Floor prefab

In the script we’ll need to add a public GameObject variable to hold this prefab:

1
2
3

public class BoardManager : MonoBehaviour {
  //...
  public GameObject floorTile;

Then in the editor drag and drop the prefab to set it.

Floor prefab variable editor

Drawing the rooms 2/2: write the code

Back in the script we add a method to draw the rooms. Also as we draw the rooms, we’ll register the drawed squares in a variable representing the board called boardPositionsFloor. This variable is not really useful at first but will be essential when starting to construct a game above.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class BoardManager : MonoBehaviour {
  //...
  private GameObject[,] boardPositionsFloor;
  //...

  public void DrawRooms(SubDungeon subDungeon) {
    if (subDungeon == null) {
      return;
    }
    if (subDungeon.IAmLeaf()) {
      for (int i = (int)subDungeon.room.x; i < subDungeon.room.xMax; i++) {
        for (int j = (int)subDungeon.room.y; j < subDungeon.room.yMax; j++) {
          GameObject instance = Instantiate (floorTile, new Vector3 (i, j, 0f), Quaternion.identity) as GameObject;
          instance.transform.SetParent (transform);
          boardPositionsFloor [i, j] = instance;
        }
      }
    } else {
      DrawRooms (subDungeon.left);
      DrawRooms (subDungeon.right);
    }
  }

And in the Start() method initialize boardPositionsFloor and call DrawRooms on the root:

1
2
3
4
5
6

  void Start () {
    //...

    boardPositionsFloor = new GameObject[boardRows, boardColumns];
    DrawRooms (rootSubDungeon);
  }

You should get something like this in the scene view :

Rooms drawed

Now that we have a visual feedback, it’s also easier to play with the parameters :

Rooms drawed big

Connect the rooms: create corridors between rooms

Isolated rooms are not very useful, so we’ll add corridors between them. To do so, we’ll connect each leaf to its sibling. Then going up one level in the tree, we’ll repeat the process to connect parents sub-dungeons, until finally we connect the two initial sub-dungeons (see the stackexchange answer for illustrations).

Add using System.Collections.Generic; at the beginning of the script, then in the SubDungeon class add:

1
2
3

  public class SubDungeon {
    // ...
    public List<Rect> corridors = new List<Rect>();

We’ll also need a method to get the room of a sub-dungeon. If the sub-dungeon is not a leaf (i.e. doesn’t contain a room), the method will return the room of a child.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

  public class SubDungeon {
    //...
    public Rect GetRoom() {
      if (IAmLeaf()) {
        return room;
      }
      if (left != null) {
        Rect lroom = left.GetRoom ();
        if (lroom.x != -1) {
          return lroom;
        }
      }
      if (right != null) {
        Rect rroom = right.GetRoom ();
        if (rroom.x != -1) {
          return rroom;
        }
      }

      // workaround non nullable structs
      return new Rect (-1, -1, 0, 0);
    }

And now the method to create the corridor between rooms:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

public void CreateCorridorBetween(SubDungeon left, SubDungeon right) {
  Rect lroom = left.GetRoom ();
  Rect rroom = right.GetRoom ();

  Debug.Log("Creating corridor(s) between " + left.debugId + "(" + lroom + ") and " + right.debugId + " (" + rroom + ")");

  // attach the corridor to a random point in each room
  Vector2 lpoint = new Vector2 ((int)Random.Range (lroom.x + 1, lroom.xMax - 1), (int)Random.Range (lroom.y + 1, lroom.yMax - 1));
  Vector2 rpoint = new Vector2 ((int)Random.Range (rroom.x + 1, rroom.xMax - 1), (int)Random.Range (rroom.y + 1, rroom.yMax - 1));

  // always be sure that left point is on the left to simplify the code
  if (lpoint.x > rpoint.x) {
    Vector2 temp = lpoint;
    lpoint = rpoint;
    rpoint = temp;
  }

  int w = (int)(lpoint.x - rpoint.x);
  int h = (int)(lpoint.y - rpoint.y);

  Debug.Log ("lpoint: " + lpoint + ", rpoint: " + rpoint + ", w: " + w + ", h: " + h);

  // if the points are not aligned horizontally
  if (w != 0) {
    // choose at random to go horizontal then vertical or the opposite
    if (Random.Range (0, 1) > 2) {
      // add a corridor to the right
      corridors.Add (new Rect (lpoint.x, lpoint.y, Mathf.Abs (w) + 1, 1));

      // if left point is below right point go up
      // otherwise go down
      if (h < 0) {
        corridors.Add (new Rect (rpoint.x, lpoint.y, 1, Mathf.Abs (h)));
      } else {
        corridors.Add (new Rect (rpoint.x, lpoint.y, 1, -Mathf.Abs (h)));
      }
    } else {
      // go up or down
      if (h < 0) {
        corridors.Add (new Rect (lpoint.x, lpoint.y, 1, Mathf.Abs (h)));
      } else {
        corridors.Add (new Rect (lpoint.x, rpoint.y, 1, Mathf.Abs (h)));
      }

      // then go right
      corridors.Add (new Rect (lpoint.x, rpoint.y, Mathf.Abs (w) + 1, 1));
    }
  } else {
    // if the points are aligned horizontally
    // go up or down depending on the positions
    if (h < 0) {
      corridors.Add (new Rect ((int)lpoint.x, (int)lpoint.y, 1, Mathf.Abs (h)));
    } else {
      corridors.Add (new Rect ((int)rpoint.x, (int)rpoint.y, 1, Mathf.Abs (h)));
    }
  }

  Debug.Log ("Corridors: ");
  foreach (Rect corridor in corridors) {
    Debug.Log ("corridor: " + corridor);
  }
}

You should see the corridors being created in the console:

Corridors console

It’s hard to see visualize without the corridors being drawed but for this example it would look like this:

Corridors drawed

Draw the corridors ½: add the corridor sprite

Same as before for the rooms we’ll need a sprite Corridor sprite, a prefab in Unity and variable to hold the prefab:

Remember to correctly set Pixels Per Unit setting:

Corridor sprite

Next create a prefab:

Corridor prefab

And add a variable in the code:

1
2
3

public class BoardManager : MonoBehaviour {
  //...
  public GameObject corridorTile;

And finally set the variable in the editor:

Corridor variable editor

Draw the corridors 2/2: write the code

The drawing function will be quite similar to the one for the rooms:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class BoardManager : MonoBehaviour {
  //...

  void DrawCorridors(SubDungeon subDungeon) {
    if (subDungeon == null) {
      return;
    }

    DrawCorridors (subDungeon.left);
    DrawCorridors (subDungeon.right);

    foreach (Rect corridor in subDungeon.corridors) {
      for (int i = (int)corridor.x; i < corridor.xMax; i++) {
        for (int j = (int)corridor.y; j < corridor.yMax; j++) {
          if (boardPositionsFloor[i,j] == null) {
            GameObject instance = Instantiate (corridorTile, new Vector3 (i, j, 0f), Quaternion.identity) as GameObject;
            instance.transform.SetParent (transform);
            boardPositionsFloor [i, j] = instance;
          }
        }
      }
    }
  }

In the Start() method, you can call DrawCorridors before DrawRooms to better see what is going on:

1
2
3
4
5
6
7
8
9

  void Start () {
    SubDungeon rootSubDungeon = new SubDungeon (new Rect (0, 0, boardRows, boardColumns));
    CreateBSP (rootSubDungeon);
    rootSubDungeon.CreateRoom ();

    boardPositionsFloor = new GameObject[boardRows, boardColumns];
    DrawCorridors (rootSubDungeon);
    DrawRooms (rootSubDungeon);
  }

Corridor drawed 2

Corridor drawed above

If DrawRooms is called before :

Corridor drawed below

Now that the random generation is working future improvements could be adding walls and of course a player sprite and controls and enemies.

Dungeon with enemies

And with a camera on the player and some further improvements it can become the basis of a simple rogue-like or dungeon crawler:

Dungeon with enemies