Procedural Map Generation with Binary Space Partitioning

mgcadmin 29-06-2025

When creating a classical Rogue-like and for many other dungeon based games as well, the levels of the game are procedurally generated. This is so that each play through of the game offers the player a new experience - no two games are the same. There are many different algorithms based on the type of game and style of dungeon you're aiming to create. In todays post I'm going to walk through implementing a Prodcedural Dungeon Generator using the Binary Space Partitioning algorithm to create maps like the one pictured below, so If that's your thing then let's get to it.

The Basic Idea

Binary Space Partitioning works by repeatedly subdividing a rectangle until reaching some threshold, such as minimum room size, number of divisions, etc. The partitioning is done top-down, starting with a rectangle comprising the entire area to be partitioned. We flip a coin to decided if we should split the space vertically or horizontally. When we choose the place to split, be it horizontal or vertical, we want it to to be slightly off-centered instead of splitting evenly to create more variety in the room sizes generated.

Once the area has been partitioned into two pieces, we then repeat the process on each piece, continuing to recur until meeting our threshold to stop. We can split randomly at each level, flipping a coin to decide which way to split, or we can choose deterministically, alternating direction at each level.

At each iteration, the new rectangles formed become nodes in a datastructure called a Binary Space Partitioning Tree. Each room is represented by a pair of x/y coordinates representing the upperleft and bottom right corners of the rectangle the node represents. 

struct Coord {
    int x, y;
    Coord(int X, int Y) : x(X), y(Y) { }
};

struct Room {
    Coord upperLeft;
    Coord bottomRight;
    Room(int ulx = 0, int uly = 0, int brx = 0, int bry = 0) : upperLeft(ulx, uly), bottomRight(brx, bry) { }
    int height() { return bottomRight.y - upperLeft.y; }
    int width() { return bottomRight.x - upperLeft.x; }
};

In addition to the space it represents, each node has a flag indicating if it was split from its parent on the vertical or horizontal axis. Finally, Being a binary tree, each node has pointers to it's left and right child, or null pointers at the leaf nodes.

struct BSPNode {
    Room room;
    bool splitOnVert;
    BSPNode* left;
    BSPNode* right;
    BSPNode(int ulx, int uly, int brx, int bry, bool splitVertical) : room(ulx, uly, brx, bry) {
        splitOnVert = splitVertical;
        left = nullptr;
        right = nullptr;
    }
};

The Map Structure

Our dungeon is going to be generated inside our Map data structure. At its most basic the Map is a 2-dimensional vector of Tile Objects. Each Tile Object represents an x/y point on the map grid, and can be either a "blocking tile" or "non-blocking". Blocking tiles make up the parts of the Map the player and other entities cannot traverse, while "walkable" areas are made of non-blocking tiles. 

class Tile {
    private:
        int x;
        int y;
        bool blocking;
        int d_dst;
        sf::Color color;
    public:
        Tile(int sx = 0, int sy = 0, sf::Color col = sf::Color::Black);
        void render(sf::RenderTexture* texture);
        Tile& setBlocking(bool state);
        bool isBlocking();
        int getX();
        int getY();
        int getDist();
        Tile& setDist(int dist);
        Tile& setColor(sf::Color col);
        sf::Color getColor();
};

The Map object is very much just a wrapper aroud the grid of Tiles, with a few helper methods to keep things concise. Tiles are mainly interacted through the getTile() method which returns a reference to the tile located the provided coordinates.

class Map {
    private:
        int MAX_WIDTH;
        int MAX_HEIGHT;
        vector<vector<Tile>> tiles;
    public:
        Map(int mw = 100, int mh = 80);
        void setTile(Tile& tile);
        Tile& getTile(int x, int y);
        void render(sf::RenderTexture* texture);
        bool canStep(int x, int y);
        int getHeight();
        int getWidth();
};

 

Implementing a Dungeon Generator Using BSP

Generating our map takes place in two major phases: The top down creation of the BSP tree, followed by the bottom-up creation of the actual rooms and the tunnels which connect them which is accomplished with a post order traversal of the BSP tree.

class DungeonGenerator {
    private:
        int maxRooms;
        using link = BSPNode*;
        link root;
        void init(Map& map);
        void clearRoom(Map& map, Room room);
        void connectChildren(link node, Map& map);
        link splitVertical(link node, int depth);
        link splitHorizontal(link node, int depth);
        link split(link node, int depth);
        void traverse(link node, Map& map);
        bool isleaf(link node);    
    public:
        DungeonGenerator();
        void createRooms(Map& map);
};

The first step in creating our map layout is to completely blank out our grid, by setting every tile to the blocking state.

void init(Map& map) {
       for (int ty = 0; ty < map.getHeight(); ty++) {
          for (int tx = 0; tx < map.getWidth(); tx++) {
             map.getTile(tx, ty).setBlocking(true);
         }
     }
}

Creating the BSP Tree

With our map initialized, we create the root node of our BSP tree. The root node represents the rectangle outlining the entire map grid. We set the split flag randomly for the root node, as can be seen in the constructor for the root node.

void createRooms(Map& map) {
       init(map);
       root = new BSPNode(0, 0, map.getWidth(), map.getHeight(), (rand() % 2 == 0));
       root = split(root, 1);
       rn = 1;
       traverse(root, map);
}

The split method is depth limited, stopping the splitting once we've split each space four times. This is by far not the only way to decided on how much to split, its just the simplest. Using the splitOnVert flag we call either splitVertical or splitHorizontal on the node.

link split(link node, int depth) {
       if (node != nullptr && depth < 5) {
           if (node->splitOnVert) {
               node = splitHorizontal(node, depth);
           } else {
               node = splitVertical(node, depth);
           }
       }
       return node;
}

The actual splitting of the node takes place in the splitVertical and splitHorizontal method. Once the space has been divided, we call the split() method on each of the newly created child nodes, incrementing the depth counter by one in the process.

link splitVertical(link node, int depth) {
       int m = (node->room.height()/2) + node->room.upperLeft.y;
       if (rand() % 2 == 0) {
               m += node->room.height()/8;
       } else {
               m -= node->room.height()/8;
       }
       node->left = new BSPNode(node->room.upperLeft.x, node->room.upperLeft.y, node->room.bottomRight.x, m, true);
       node->right = new BSPNode(node->room.upperLeft.x, m, node->room.bottomRight.x, node->room.bottomRight.y, true);
       node->left = split(node->left, depth+1);
       node->right = split(node->right, depth+1);
       return node;
}
link splitHorizontal(link node, int depth) {
       int m =  (node->room.width()/2) + node->room.upperLeft.x;
       if (rand() % 2 == 0) {
           m += node->room.width()/8;
       } else {
           m -= node->room.width()/8;
       }
       node->left = new BSPNode(node->room.upperLeft.x, node->room.upperLeft.y, m, node->room.bottomRight.y, false);
       node->right = new BSPNode(m, node->room.upperLeft.y, node->room.bottomRight.x, node->room.bottomRight.y, false);
       node->left = split(node->left, depth+1);
       node->right = split(node->right, depth+1);
       return node;
}

Creating the Rooms

Once we've have reached our desired amount of partitioning we are ready to create the actual rooms. This is done using the clearRoom() method, which sets the tiles in the given nodes bounding box to non blocking. Crucially, we only call this method on the leaf nodes as those are the rooms split to the desired sizes.

bool isleaf(link node) {
       return node != nullptr && node->left == nullptr && node->right == nullptr;
}
void traverse(link node, Map& map) {
       if (node == nullptr)
           return;
       if (isleaf(node)) {
           clearRoom(map, node->room);
       } else {
           traverse(node->left, map);
           traverse(node->right, map);
           connectChildren(node, map);
       }
}

When clearing the tiles for the room, we use a variable amount of "padding" on the border of the rooms to aid in giving each room a less uniform and more "organic" look.

void clearRoom(Map& map, Room room) {
      int xpad = (rand() % 2) + 1;
      int ypad = (rand() % 2) + 1;
      for (int ty = room.upperLeft.y+ypad; ty < room.bottomRight.y-ypad; ty++) {
          for (int tx = room.upperLeft.x+xpad; tx < room.bottomRight.x-xpad; tx++) {
                  map.getTile(tx, ty).setBlocking(false);
          }
      }
}

At this point, we are left with a map full of variously sized, disconnected rooms. This obviously isnt much good, so we have to do a bit more work to turn our rooms into a map.

Connecting the Rooms

We processed the leaf nodes to creat the nodes, we will use the internal nodes to turn our disjoint map into a connected graph. The rooms are connected using the connectChildren() method on each internal node. It find the center point of the left child and the center point of the right child, and creating a "tunnel" of non-blocking tiles between the points.

void connectChildren(link node, Map& map) {
        //Get center of left child
        int lmx = (node->left->room.upperLeft.x + node->left->room.bottomRight.x) /2;
        int lmy = (node->left->room.upperLeft.y + node->left->room.bottomRight.y) /2;
        //Get center of right child
        int rmx = (node->right->room.upperLeft.x + node->right->room.bottomRight.x) /2;
        int rmy = (node->right->room.upperLeft.y + node->right->room.bottomRight.y) /2;
        if (node->splitOnVert) {
            //create horizontal passages
            for (int x = lmx; x <= rmx; x++) {
               map.getTile(x, lmy).setBlocking(false).setColor(sf::Color::Blue);
               map.getTile(x, lmy+1).setBlocking(false).setColor(sf::Color::Blue);
            }
       } else {
          //create vertical passages
          for (int y = lmy; y <= rmy; y++) {
               map.getTile(rmx, y).setBlocking(false).setColor(sf::Color::Blue);
               map.getTile(rmx-1, y).setBlocking(false).setColor(sf::Color::Blue);
            }
       }
}

And with the rooms connected, we now have our connected map:

Well, there you have it: Procedural Dungeon Generation using Binary Space Partitioning. Until next time, Happy Hacking!

---