BSP LEVEL GENERATOR
Introduction
The school had access to older work tests by certain companies. They made an assignment where we were going to do one of them and write about our process. This was to give us students a view of what a work test could look like. I decided to make a work test created by Fatshark. 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 using was a modified version of 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). With it, I could create a level that resembled the inside of a building, 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 deciding a split, I pick a random percentage between 42% and 58%. That is the location the split will happen.
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.
Originally, whether it splits vertical or horizontal is decided by a coin flip. I decided to keep track if it has done the same split three times in a row. It it has, it splits in the other direction.
Placing doors
Introduction
After the level has been created, I go through the rooms and places the doors. If I were to add other objects and enemies, they would be created at the same time as 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. I also use a IsPassable check 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.
Assignment PDF
A part of the assignment was to write about the process on how I would handle this task if I were an intern at Fatshark. Another part was answering technical questions on how we could modify the game level to make it more fun and challenging. In this PDF, I am describing the process I would take and sharing ways and ideas on how to further improve on the level generator. It also contains and example of an exported level.
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.