# Algorithm BSP trees, or creating a randomly generated level

1072 views

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

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.

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)

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.

There are no comments to display.

## Create an account

Register a new account

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• ### Similar Content

• Hello, I'm currently searching for additional talented and passionate members for our team that's creating a small horror game.

About the game: The game would be a small sci-fi/post-apocalyptic survival horror 3D game with FPS (First person shooter) mechanics and an original setting and story based in a book (which I'm writing) scene, where a group of prisoners are left behind in an abandoned underground facility. It would play similar to Dead Space combined with Penumbra and SCP: Secret Laboratory, with the option of playing solo or multiplayer.

Engine that'd be used to create the game: Unity

About me: I'm a music composer with 4 years of experience and I'm fairly new in this game development world, and I'm currently leading the team that'd be creating this beautiful and horrifying game. I decided that making the book which I'm writing into a game would be really cool, and I got more motivated about doing so some time ago when I got a bunch of expensive Unity assets for a very low price. However, I researched about how to do things right in game development so I reduced the scope of it as much as I could so that's why this game is really based in a scene of the book and not the entire thing. Also I'm currently learning how to use Unity and learning how to program.

Our team right now consists of: Me (Game Designer, Creator, Music Composer, Writer), 3 3D Modelers, 3 Game Programmers, 1 Sound Effect Designer, 1 Concept Artist, 1 3D Animator and 1 Community Manager.

Who am I looking for: We are looking for a talented, passionate and experienced 3D Environment Modeler who is able to create high poly realistic tunnels, rooms, props, in other words, small closed environments and is able to also texture them with a sci-fi/horror vibe.
Right now the game is in mid-early development and you can see more information about it and follow our progress in our game jolt page here: https://gamejolt.com/games/devilspunishment/391190 . We expect to finish some sort of prototype in 2-3 months from now.

This is a contract rev-share position

If you are interested in joining, contributing or have questions about the project then let's talk. You can message me in Discord: world_creator#9524
• By jb-dev
You might want to break this one just in case...
• By jb-dev
This is a picture of plants of the Anthurium genus, and particularly the kind you could find in a rainforest.
• By jb-dev
This is a screenshot of what jungle ferns will look like in the jungle level.

• Hi everyone, let me share with you my new casual game on Android.
At this moment the game is in open beta, so it's still in progress but I suppose it's ready to show.
Airplane Wars - IO based game.
Everything is quite simple. You need to collect as many points as you can to be on the top. Area has a lot of energy balls. Collect them so that you get bigger and faster!
You have 2 minutes to become the best one! There are 6 opponents to you. Just rush and collect points, explode enemies and be on the top.
It's really easy to play. Just move your finger in any direction and the player will follow it.
A little gameplay video on YouTUBE.
Open beta is available on Google Play. Feel free to try it out if you are interested in it

×