Difference between revisions of "Basic BSP Dungeon generation"

From RogueBasin
Jump to navigation Jump to search
(We can simply not hotlink these images)
 
(12 intermediate revisions by 5 users not shown)
Line 9: Line 9:
* split the dungeon into two sub-dungeons
* split the dungeon into two sub-dungeons


http://jice.nospam.googlepages.com/dungeon_bsp1.png
[[File:Dungeon_bsp1.png]]
The first splitting iteration.
The first splitting iteration.


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


http://jice.nospam.googlepages.com/dungeon_bsp2.png
[[File:Dungeon_bsp2.png]]
The second splitting iteration
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.  
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.  


http://jice.nospam.googlepages.com/dungeon_bsp3.png
[[File:Dungeon_bsp3.png]]
After 4 splitting iterations  
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.
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.
=== Java Implementation ===
Here is an implementation in Java.
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''.
<div style="background-color: #EEEEEE; border-style: dotted"><syntaxhighlight lang="java">
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 - 1;
            int yCanSplitFrom = yStart + minHeight - 1;
            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;
    }
}
</syntaxhighlight></div>


=== Building the dungeon ===
=== Building the dungeon ===
Line 127: Line 28:
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.
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.


http://jice.nospam.googlepages.com/dungeon_bsp4.png
[[File:Dungeon_bsp4.png]]
Rooms in the tree leafs  
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.
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.


http://jice.nospam.googlepages.com/dungeon_bsp5.png
[[File:Dungeon_bsp5.png]]
Connecting the level 4 sub-dungeons  
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.
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.


http://jice.nospam.googlepages.com/dungeon_bsp6.png
[[File:Dungeon_bsp6.png]]
Connecting the level 3 sub-dungeons
Connecting the level 3 sub-dungeons


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


http://jice.nospam.googlepages.com/dungeon_bsp7.png
[[File:Dungeon_bsp7.png]]
If we allow some rooms to fill the whole leaf, we can even have less boring dungeons.
If we allow some rooms to fill the whole leaf, we can even have less boring dungeons.
[[Category:Articles]]
 
== Video Explanation ==
 
[http://www.youtube.com/watch?v=S5y3ES4Rvkk Binary Trees] by [http://www.youtube.com/channel/UCVtiyi-I-bc12ddVouNBNfQ Richard Fleming Jr]
 
[http://www.youtube.com/watch?v=UFrF2-U_VTs Procedural Dungeon Generation: Part 1] by [http://www.youtube.com/channel/UCp19G1Eo1vX4NWTaMxerawg LearnToMod]
 
 
[[Category:Developing]]
[[Category:Maps]]

Latest revision as of 07:10, 15 August 2023

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.

Video Explanation

Binary Trees by Richard Fleming Jr

Procedural Dungeon Generation: Part 1 by LearnToMod

Retrieved from "http://roguebasin.com/index.php?title=Basic_BSP_Dungeon_generation&oldid=52650"