Random Dungeon Generation Using BSP Trees
In this project, I developed a simple method to generate a basic dungeon using a Binary Space Partition (BSP) tree. The goal was to create an algorithm that recursively divides a rectangular dungeon into smaller sub-dungeons until each one reaches the desired size of a room.
The source code for this Unity Project is on my GitHub
Presented here is a breakdown of the algorithm, outlined in two primary components:
1. Building the BSP Tree
The process begins with a rectangular dungeon:
We employ a recursive splitting technique to divide this dungeon until each sub-dungeon reaches the desired room size. Below is the code responsible for the recursive splitting of a BSP tree.
/// <summary>
/// Recursively splits a tree into two parts and assigns the LeftNode and RightNode to the
/// respective split containers.
/// </summary>
/// <param name="iterations">How many iterations to split</param>
/// <param name="root_node">The container to do the split operations on</param>
/// <param name="parent">Parent node (null for root)</param>
internal static BinaryTree SplitRecursively(
int iterations,
RectInt root_node,
BinaryTree parent = null)
{
var node = new BinaryTree(root_node)
{
Parent = parent
};
if (iterations == 0)
{
return node;
}
node.Split();
node.LeftNode = SplitRecursively(iterations - 1, node.LeftNode.RootNode, node);
node.RightNode = SplitRecursively(iterations - 1, node.RightNode.RootNode, node);
return node;
}The dungeon splitting operation involves the following steps:
- Randomly select a splitting direction: horizontal or vertical. (or consider the container’s dimensions and select the direction that aligns with its largest dimension)
- Choose a random position along the chosen direction (x-coordinate for vertical splitting, y-coordinate for horizontal splitting).
- Divide the dungeon into two sub-dungeons.
At this stage, we obtain two sub-dungeons, namely A and B:
The same splitting operation is then applied to each of these sub-dungeons:
When selecting the splitting position, it is crucial to ensure it is not too close to the dungeon’s borders. This precaution guarantees sufficient space for placing a room inside each generated sub-dungeon. In my code, the variables controlling the splitting variation are named splitMinRatio and splitMaxRatio. Depending on the rules applied to the splitting position, the resulting sub-dungeons can exhibit either homogeneity (position between 0.45 and 0.55) or heterogeneity (position between 0.1 and 0.9).
We repeat these three steps until the smallest sub-dungeons reach the desired room size:
2. Building the Dungeon
Next, we proceed to construct the actual dungeon by following these steps:
- For each leaf in the BSP tree (called a container in the code), we create a room with a randomly determined size (roomMinRatio and roomMaxRatio in the code). It is important to ensure that each room remains within the bounds of its corresponding sub-dungeon. Thanks to the BSP tree structure, we eliminate the possibility of having overlapping rooms.
- To establish tunnels between the rooms, we iterate through all the leaf nodes in the tree and connect each leaf to another node or to another tunnel. We repeat this process iteratively until all the rooms are connected, ensuring a coherent and navigable layout for the dungeon. (Tunnel width can be controlled using the tunnelWidth variable. )
And finally we have our dungeon once we remove the gizmo lines
The DungeonGenerator script additionally includes a variable called padding value, which controls the spacing around tunnels. By setting it to 2, the algorithm guarantees that tunnels are placed at least 2 tiles away from the outer walls of each room.
This functionality is beneficial in two ways: Firstly, it prevents tunnels from starting directly at the corners of a room, creating a more aesthetically pleasing layout. Secondly, it ensures that tunnels have a few tiles of walls on each side, providing better visual separation between rooms and corridors.
The resulting dungeons offer a solid foundation for further embellishments, such as adding room decorations, enemy placements, and puzzle elements, to create captivating gameplay experiences
