Basic BSP Dungeon generation

From RogueBasin
Jump to navigation Jump to search

A simple method to generate a basic dungeon using a bsp tree

Building the BSP

We start with a rectangular dungeon filled with wall cells. We are going to split this dungeon recursively until each sub-dungeon has approximately the size of a room. The dungeon splitting uses this operation :

  • choose a random direction : horizontal or vertical splitting
  • choose a random position (x for vertical, y for horizontal)
  • split the dungeon into two sub-dungeons

dungeon_bsp1.png The first splitting iteration.

Now we have two sub-dungeons A and B. We can apply the same operation to both of them :

dungeon_bsp2.png The second splitting iteration

When choosing the splitting position, we have to take care not to be too close to the dungeon border. We must be able to place a room inside each generated sub-dungeon. We repeat until the lowest sub-dungeons have approximately the size of the rooms we want to generate.

dungeon_bsp3.png After 4 splitting iterations

Different rules on the splitting position can result in homogeneous sub-dungeons (position between 0.45 and 0.55) or heterogeneous ones (position between 0.1 and 0.9). We can also choose to use a deeper recursion level on some parts of the dungeon so that we get smaller rooms there.

Building the dungeon

Now we create a room with random size in each leaf of the tree. Of course, the room must be contained inside the corresponding sub-dungeon. Thanks to the BSP tree, we can't have two overlapping rooms.

dungeon_bsp4.png Rooms in the tree leafs

To build corridors, we loop through all the leafs of the tree, connecting each leaf to its sister. If the two rooms have face-to-face walls, we can use a straight corridor. Else we have to use a Z shaped corridor.

dungeon_bsp5.png Connecting the level 4 sub-dungeons

Now we get up one level in the tree and repeat the process for the parent sub-regions. Now, we can connect two sub-regions with a link either between two rooms, or a corridor and a room or two corridors.

dungeon_bsp6.png Connecting the level 3 sub-dungeons

We repeat the process until we have connected the first two sub-dungeons A and B :

dungeon_bsp7.png If we allow some rooms to fill the whole leaf, we can even have less boring dungeons.

Java Implementation

Here is an implementation in Java of a BSP builder. Note:

  • It assumes you have a suitably implemented BinaryNode and Area data structure.
  • RNG.between(int a, int b) returns a number between a and b inclusive.
public class BSP {
    // This will favour splitting from the left, or bottom
    private static void splitArea(boolean vertical, int split,
            BinaryNode<Area> current, LinkedList<BinaryNode<Area>> toBeProcessed) {

        int xStart = current.data.xStart;
        int yStart = current.data.yStart;
        int xEnd = current.data.xEnd;
        int yEnd = current.data.yEnd;
        Area left, right;

        if (vertical) {
            left = new Area(xStart, yStart, xEnd, split - 1);
            right = new Area(xStart, split, xEnd, yEnd);
        } else {
            left = new Area(xStart, yStart, split - 1, yEnd);
            right = new Area(split, yStart, xEnd, yEnd);
        }

        current.setLeft(new BinaryNode<Area>(left));
        current.setRight(new BinaryNode<Area>(right));
        toBeProcessed.push(current.getLeft());
        toBeProcessed.push(current.getRight());
    }

    /**
     * @param maxLeaves
     *            maximum depth of the tree
     * @param minWidth
     *            minimum width of each partition
     * @param minHeight
     *            minimum height of each partition
     * @return A new node representing the BSP.
     */
    public static BinaryNode<Area> generate(Area a, int maxLeaves,
            int minWidth, int minHeight) {

        BinaryNode<Area> root = new BinaryNode<Area>(a);
        LinkedList<BinaryNode<Area>> toBeProcessed;
        toBeProcessed = new LinkedList<BinaryNode<Area>>();
        toBeProcessed.push(root);
        BinaryNode<Area> current;
        // initialised at 1. A depth of 0 would be a single leaf.
        int nLeaves = 1;
        int xStart, yStart, xEnd, yEnd;

        while (toBeProcessed.size() > 0) {
            current = toBeProcessed.pop();
            if (nLeaves > maxLeaves) {
                // we've gone too far, need to stop
                break;
            } else if ((current.data.height < minHeight)
                    || (current.data.width < minWidth)) {
                // this node is too small but others may not be.
                continue;
            }

            // Just to make the code a bit neater.
            xStart = current.data.xStart;
            yStart = current.data.yStart;
            xEnd = current.data.xEnd;
            yEnd = current.data.yEnd;

            /*
             * Subtracted 1 from the "to" values because while lists start from
             * 0, list length does not. I have not subtracted 1 from the "from"
             * values however as the splitArea method splits to the left.
             */
            int xCanSplitFrom = xStart + minWidth;
            int yCanSplitFrom = yStart + minHeight;

            int xCanSplitTo = xEnd - minWidth - 1;
            int yCanSplitTo = yEnd - minHeight - 1;

            // If true, split vertically.
            if (RNG.bool() && (yCanSplitFrom < yCanSplitTo)) {
                int split = RNG.between(yCanSplitFrom, yCanSplitTo);
                splitArea(true, split, current, toBeProcessed);
                // If false, split horizontally
            } else if (xCanSplitFrom < xCanSplitTo) {
                int split = RNG.between(xCanSplitFrom, xCanSplitTo);
                splitArea(false, split, current, toBeProcessed);
            }
            // one level done
            nLeaves++;
        }

        return root;
    }
}