BSP Level generator
A procedural level generator that uses binary space partitioning to create a level filled with rooms of different sizes.
Role: Programmer
Team Size: 1
Time frame: 1 Week
Language: Lua
introduction
This assignment was a representation of a work test. This was to give us students a view of what a work test could look like. The goal was to write a procedural level generator that creates a level with rooms of different sizes that are connected to each other using Lua. I looked up different algorithms for procedural level generation looking for one that would create the required result. I looked up the cellular automata algorithm, but it is more fitting for creating caves and more natural-based levels. Another one I was thinking about suing by modifying it a bit was Drunkard Walk, but that one seemed a bit too random and could be difficult to control at larger levels. In the end, I decided to use Binary Space Partitioning (BSP). I could create a level that looks like the inside of a building with BSP, which was the result I was looking for. The level is constructed with doors ( + ), floors ( . ) and walls ( # ).
Grid
Introduction
As a start, I needed a way to keep track of the positions and types of the tiles throughout the algorithm. I decided to use a grid for this since it's what I am most accustomed to for this type of use.
Functionality
At first, I create a grid of a set size where all tiles are presented as walls ( # ). Throughout the algorithm, I change the tile to either floor tile ( . ) or door tile ( + ) depending on what the algorithm does.
nodes
Introduction
The next step was creating nodes, which were going to be the rooms inside the grid. It required a way to handle their size, which would be used when splitting the nodes. I also needed a way to locate where in the BSP tree the node is located. This is useful for the recursion.
Functionality
The nodes contain a rectangle that keeps track of the positions of the corners of the room, which is the room's size. I set the node's level to 0 if it is the root node. If it's not the root node, I set the level to the parent node's level + 1. This keeps track of the times the recursion has occurred. Then I draw the node's walls based on its rectangle.
Split node
Introduction
This was the main point of the algorithm. The idea is to split a node into two so-called child nodes. I followed through on that part of the algorithm as well as adding a table to keep track of the rooms. When creating a node, I create a rectangle that I use when handling the width and height of the node. I also created a way to make sure a point isn't outside of the grid, just for safety.
Functionality
At first, the root node is split either vertically or horizontally into two child nodes. Then I use recursion for the child nodes until the nodes are too small to split. I also insert the new child nodes in a table, removing the current node from it. In the end, the table will contain all nodes at the lowest level. This table will be looped through at the end of the algorithm to place doors around the walls.
When it comes to the rectangle for the nodes, if it's vertical, I set the x-position based on the split. If not, I set the y-position based on the split. I also have a function that checks if a point is inside the grid, just to make sure no position outside the grid gets checked.
split direction
Introduction
When splitting a node, originally the algorithm simply did a coin flip, which decided the direction with a 50% chance. However, I wanted to have more control over it to prevent it from splitting too many times in the same direction.
Functionality
I keep track of how many times each split has happened. If it has split vertically more times than horizontally, it will split horizontally and vice versa. If they have split close to the same number of times, it decides the split at random. This is done to prevent it from being split too many times in one way for room diversity. When splitting, I pick a random number between a set percentage. In this case, between 42 and 58 percent. This is where the split will be done compared to the room's width or height.
Placing doors
Introduction
The next step after all rooms have been created is placing out the doors. This is the reason I saved the nodes at the lowest level in a table. Now I could go through the table and place all the doors.
Functionality
I loop through a node's walls and since some rooms share walls, I have to make sure no doors have been placed on the current side. If a door has already been placed, I move on to the next side. The IsPassable check is done to make sure that either the north and south neighbors or the west and east neighbors are floor tiles. If they are, then a door is placed.
The PlaceDoors function is called in a function that will be used to loop through the nodes and add objects to them. PlaceDoors is currently the only function there, but this is where functions that place out enemies, hazards and so on would be called.
Exporting level
When a level is completed, I draw the grid in the command prompt and save it to a txt file so it could be used in a program that builds up a level based on tiles.
Here is an example of what a level created by this algorithm looks like:
what i learned
This was my first time working in Lua, so a part of the time was spent understanding how Lua works and what I can use in this language. I gained knowledge about the different types of algorithms that could be used for procedural level generation and what types of levels they could create. I also gained more in-depth knowledge about how the BSP algorithm works and how it can be used and customized to achieve the desired result.