So the game I'm working on is going to use rooms that are connected to each other by little holes, creating something somehow similar to "Binding of Isaac", but with organic room disposition rather than rooms placed on a grid with specific dimensions.

To do this, I needed to search for a good level generation algorithms.

I've found that the best algorithm is the BSP trees algorithm, which was traditionally used in old-schools roguelike games.

Binary Partition Trees

The algorithm works by taking an area and split it in half, thus creating tow new area to be recursively processed by the algorithm.

The algorithm can be run until we stumble upon an area of a specific dimension. 

This is what that algorithm can do:

Traditionally, each area becomes leaves, in which a random rectangle room is drawn within these. Afterward, each of these rooms is connected to each others using longs corridors. This approach works in 2D, as the player always has a clear view of his surroundings. 

Here is an excellent reference on the subject: Basic BSP Dungeon generation

Adaptations

However, because the game is in a first-person perspective, the corridors won't work as the player can't really know his surrounding very well. We need to adapt the algorithm so that the player can feel comfortable while navigating in our level.

I've chosen to eliminate corridors and rooms altogether and instead use the leaves themselves. Instead, each leaf is connected to each other through small holes. 

Also, the BSP tree algorithm creates a web-like dungeon with no clear end or start, which is fine if you're making a traditional dungeon, but we want our levels to have a certain flow so that the player can quickly find its way out if they want to.

The way I planned to do that is by transforming the BSP leaves into a kind of navmesh grid. Afterward, we just pick some positions and select specific leaves that makes up the path.

Creating the navmesh graph

First, before we can use the graph search algorithm, we need to build our graph. BSP tree is still binary trees, so using those to deal with connections are out of the question. We need to somehow get all the leaves created in the BSP tree algorithm and put them in a more flexible structure: enter the quadtree.

Quadtrees are a kind of tree that can have at most 4 children. This characteristic is quite useful when it comes to 2D rectangles. 

Here's a visual representation of a quadtree:

With these kinds of trees, it's possible to get every overlapping leaf from a specific rectangle.

If for a given room, we query a slightly bigger search zone, then we'll be able to find all of the given room's neighbours.

We can then connect everything up and finally launch our graph search using randomly picked rooms that are far enough from each other.

Do the pathfinding

I've already made a blog entry on pathfinding so the procedure is almost the same...

However, there is some difference here...

One of the most important difference is that we add the concept of "hot" cells.

When a specific cell is deemed "hot" and that the graph search algorithm stumbles upon it then its cost will be infinite. That way, we can say to the algorithm this: "Do not pick this cell unless it's your last option". This makes for a somehow imperfect path...

But in our case, imperfect is perfect. 

Afterwards, we add all of the chosen rooms in a final list. All rooms in this list will be part of our level and will be rendered out later on.

Add more rooms

After we picked the main rooms, we can then append bonus rooms to some of these main rooms if the player is lucky, not unlike hidden rooms in "Binding of  Isaac"...

Also, the game is going to sometime have an "alternative path". These paths will try to be shorter than the main path and overall have more bonus rooms and loot to them. I've planned that the player needs to fulfil some requirement to enter this path.

Because we already created a graph of each possible rooms, it's just a matter of luck to see if a room has a special room connected to it.

Rendering it out

Once the rooms configurations were made, we now need to create the geometries and collisions of the level.

Before going with the BSP approach, I've tried to use cellular automata to generate cave-like structures...

It wasn't controllable enough, but I've kept some of the code from it (mainly its geometry generation)

Here's the cellular automata tutorial

Basically, we render each rooms pixel by pixel. We then cut those "holes" I've talked about earlier and voilà.

Here, I've coloured each room to give a better idea of what kind of room each is which.

• Blue rooms are part of the alternate path I've mentioned before.
• The green and red rooms represent both the starting and ending room respectively.
• Yellow rooms are bonus rooms.

Afterward, it's only a matter of placing props and enemies.

This method of creating levels is cool. It can make the game more flexible and interesting. It also all depends on luck, which is a stat that can change in-game.