Procedural Dungeons with BSP in Unity: A Step-by-Step Guide

Ever stare at a blank tilemap, dreaming of labyrinthine dungeons but dreading the tedious process of hand-placing every block? There’s a better way, a procedural path to dynamic dungeons that leverages the power of Binary Space Partitioning (BSP). Let’s dive into building a BSP-based dungeon generator in Unity, bypassing the frustration and embracing the algorithm.

Binary Space Partitioning: The Foundation

BSP is a clever algorithm that recursively divides a space into smaller and smaller regions. Think of it like slicing a cake repeatedly, each cut creating two new pieces. This process forms a binary tree structure, the backbone of our dungeon.

Challenge: Choosing the right splitting direction. Splitting only horizontally or vertically can lead to long, thin rooms. A more organic approach is to randomly choose the split direction for each partition.

Creating the BSP Tree

First, we need a node class to represent each partition in our tree.

public class BSPNode
{
    public RectInt rect;
    public BSPNode left;
    public BSPNode right;

    public BSPNode(RectInt rect)
    {
        this.rect = rect;
        left = null;
        right = null;
    }
}

Now, the crucial split function. This recursively divides the rectangular space until a minimum size is reached.

public class BSPGenerator
{
    public int minRoomSize = 10;

    public BSPNode GenerateBSP(RectInt space)
    {
        BSPNode root = new BSPNode(space);
        SplitNode(root);
        return root;
    }

    private void SplitNode(BSPNode node)
    {
        if (node.rect.width < minRoomSize || node.rect.height < minRoomSize)
        {
            return; // Stop splitting if too small
        }

        bool splitH = Random.Range(0f, 1f) > 0.5f; // Randomly choose split direction
        int splitPoint = splitH ? Random.Range(minRoomSize, node.rect.width - minRoomSize) : Random.Range(minRoomSize, node.rect.height - minRoomSize);

        if (splitH)
        {
            node.left = new BSPNode(new RectInt(node.rect.x, node.rect.y, splitPoint, node.rect.height));
            node.right = new BSPNode(new RectInt(node.rect.x + splitPoint, node.rect.y, node.rect.width - splitPoint, node.rect.height));
        }
        else
        {
            node.left = new BSPNode(new RectInt(node.rect.x, node.rect.y, node.rect.width, splitPoint));
            node.right = new BSPNode(new RectInt(node.rect.x, node.rect.y + splitPoint, node.rect.width, node.rect.height - splitPoint));
        }

        SplitNode(node.left);
        SplitNode(node.right);
    }
}

Pitfall: Infinite Recursion. Ensure you have a base case to stop the recursion (minimum room size). Without it, your code will crash.

Generating Rooms

Now that the space is partitioned, it’s time to carve out rooms within these partitions. A simple approach is to create a room smaller than the partition.

public List<RectInt> GenerateRooms(BSPNode node)
{
    List<RectInt> rooms = new List<RectInt>();
    TraverseAndCreateRooms(node, rooms);
    return rooms;
}

private void TraverseAndCreateRooms(BSPNode node, List<RectInt> rooms)
{
    if (node == null) return;

    if (node.left == null && node.right == null) // Leaf node
    {
        int roomWidth = Random.Range(minRoomSize / 2, node.rect.width - 1);
        int roomHeight = Random.Range(minRoomSize / 2, node.rect.height - 1);
        int roomX = Random.Range(node.rect.x, node.rect.x + node.rect.width - roomWidth);
        int roomY = Random.Range(node.rect.y, node.rect.y + node.rect.height - roomHeight);

        RectInt room = new RectInt(roomX, roomY, roomWidth, roomHeight);
        rooms.Add(room);
    }
    else
    {
        TraverseAndCreateRooms(node.left, rooms);
        TraverseAndCreateRooms(node.right, rooms);
    }
}

Value Added: Adding constraints, like minimum distance between a room’s edge and the partition’s edge, can result in more visually appealing dungeons.

Connecting the Rooms

This is where the magic happens. We need to connect these isolated rooms to form a traversable dungeon. The easiest approach is to connect each room to its sibling node in the BSP tree.

public List<Vector2Int> GenerateCorridors(List<RectInt> rooms)
{
    List<Vector2Int> corridors = new List<Vector2Int>();
    for (int i = 0; i < rooms.Count - 1; i++)
    {
        Vector2Int room1Center = new Vector2Int(rooms[i].xMin + rooms[i].width / 2, rooms[i].yMin + rooms[i].height / 2);
        Vector2Int room2Center = new Vector2Int(rooms[i + 1].xMin + rooms[i + 1].width / 2, rooms[i + 1].yMin + rooms[i + 1].height / 2);

        //Create L shaped corridor
        foreach(var pos in CreateLShapedCorridor(room1Center, room2Center)) {
            corridors.Add(pos);
        }
    }
    return corridors;
}

private List<Vector2Int> CreateLShapedCorridor(Vector2Int start, Vector2Int end) {
    List<Vector2Int> corridor = new List<Vector2Int>();
    //horizontal portion
    for (int x = start.x; x != end.x; x += (start.x < end.x) ? 1 : -1)
    {
        corridor.Add(new Vector2Int(x, start.y));
    }
    //vertical portion
    for (int y = start.y; y != end.y; y += (start.y < end.y) ? 1 : -1)
    {
        corridor.Add(new Vector2Int(end.x, y));
    }

    return corridor;
}

Common Mistake: Naive Connection. Connecting only adjacent rooms can lead to isolated sections. A more sophisticated approach involves finding the closest room using pathfinding.

Instantiating the Tilemap in Unity

Finally, we can translate our generated data into a visual dungeon within Unity. This involves iterating through the room and corridor positions and setting the corresponding tiles on the tilemap.

public Tilemap tilemap;
public TileBase floorTile;
public TileBase wallTile;

public void DrawDungeon(List<RectInt> rooms, List<Vector2Int> corridors)
{
    BoundsInt bounds = tilemap.cellBounds;
    tilemap.ClearAllTiles();

    // Draw Rooms
    foreach (var room in rooms)
    {
        for (int x = room.xMin; x < room.xMax; x++)
        {
            for (int y = room.yMin; y < room.yMax; y++)
            {
                tilemap.SetTile(new Vector3Int(x, y, 0), floorTile);
            }
        }
    }

    // Draw Corridors
    foreach (var corridorPosition in corridors)
    {
        tilemap.SetTile(new Vector3Int(corridorPosition.x, corridorPosition.y, 0), floorTile);
    }

    // Draw Walls (Simple Example - Improve this!)
    for (int x = bounds.xMin; x < bounds.xMax; x++)
    {
        for (int y = bounds.yMin; y < bounds.yMax; y++)
        {
            if (tilemap.GetTile(new Vector3Int(x, y, 0)) == null)
            {
                tilemap.SetTile(new Vector3Int(x, y, 0), wallTile);
            }
        }
    }
}

Practical Value: Wall Generation. The naive wall generation here simply fills empty spaces, but creates poor results. Implement more sophisticated wall placement algorithms for better visuals. Look into checking neighbors to place appropriate wall tiles.

Beyond the Basics

This is a foundational implementation. To truly elevate your dungeon generation, consider:

• More sophisticated corridor generation: A* pathfinding or random walks.
• Room Types: Different room sizes and purpose beyond just basic squares.
• Enemy and Item Placement: Procedurally spawn enemies and loot.
• Biomes: Vary the tile types and room characteristics based on location in the dungeon.

BSP dungeon generation is a powerful tool, but mastering it requires understanding its nuances and potential pitfalls. By stepping through these examples, you’re well on your way to crafting unique and compelling dungeons in your games. Don’t be afraid to experiment and iterate to truly unlock the potential of this algorithm!