Procedural Generation of Levels for Game Design
Introduction
As part of trying to implement a vast array of different features, I wanted to have a go at a self generating level. The closest I had done previously was during university as part of a group project. This was generating a board of tiles for the user to play on. There was very little constraints on how the tiles had to be placed. This meant for the most part that tiles could be placed randomly with only minor adjustments. With my level generation I wanted to be making levels that the user was able to walk through. This would be akin to a layout presented by games like the Binding of Isaac. Where each room has a way to get to the next room and every room is accessible in some way. A big difference between this however, would be my rooms were created in 3d.
All of this was implemented using Unity3D as that is currently the software I am most familiar.
First Attempt
My first attempt when starting this project was to create all the levels as prefabs, this would allow me to just generate them when required, and then rotate them to fit my needs. With the parts I had to hand to create the rooms there was 2 walls on each side which lead to this being the standard size as it was substantially more visually appealing than just 1x1. The only downside with these rooms is that mean the door, that was only one wall tile wide, would have to be off centre. As I was just intending to rotate the prefabs to the direction I wanted this created an immediate issue. When dealing with a left door room, if it was rotated 180 degrees to face another room the doors would not be aligned. Each door would face a wall and both would be inaccessible.
This can be seen in the above image. My solution at the time was to create a right door variant for each possible door. This added up quickly as the number of variants needed was 2^number of doors the room has. For a room with 3 doors I had to create 8 different versions.
With these all created I moved onto the rooms ability to generate themselves. Outside each door on the rooms was a point. This point would know the direction of the room it came from, and if that room was a left door or a right door. After existing for 0.1 second, which was chosen to allow adjacent rooms to spawn, it would get any points that it shared the spot with and try to generate a room. By getting the other points it sat on top of it would know all the entrances that room had to have to be valid. If it only cared about one point it would not satisfy the requirements if a corner was required.
A room would then be attempted to generate from this list of required points. A list of rooms that could be valid was created. All of the rooms in this list had at least the number of doors required as I had split the rooms up into separate lists by their number of doors. There was no point trying to see if a 1 door room was sufficient for a room that was required to have at least 2. This list would then be shuffled to keep the rooms generated random and not based on the order of the lists. For each element in this possible room list I would check every rotation of each member until I found a result that would satisfy the points this function had been passed, as that was the bare minimum for the room to be generated. Once a room that satisfied these conditions was found I would then check if the remaining points from that room, if it was generated, would not be over an already existing room. As this would result in doors generating towards existing rooms that would not have doors facing this newly generated rooms.
The last part of this first version was to give the generation some form of stopping condition. To do this every time a room was created it would add one to a static counter. If a room tried to generate over this counter the list of possible rooms would not be shuffled. This was because the first list added to the possible rooms list was the one containing only single rooms. For every room generated after this point it would first check if a single door room was possible. The reason I didn't force it to be a single door room was due to the fact that if 2 doors were required and I forced a single door room I would break the generation.
As shown above this was the types of levels this attempt could produce. They were functional in terms of able to be navigated through. Although in the above example it does display an issue this version had where it would sometimes generate an extra room that would be inaccessible. I didn't end up fixing this bug as I thought it would be better to start from the ground up with a different approach.
One of the downsides of this first approach was that the rooms were repetitive. Every room was the same size, with the same walls, with the same floors. The only difference between each room was the doors. For the next version I wanted to have a much bigger emphasis on different layouts.
The Improved Version
My first goal with this version was getting a room that could generate itself, and be random every time. I created an object to hold lists of every possible floor and wall so they could be requested when a room was created. Also in this step I set up how a room would function. The data for a room would be stored in a class that would represent a 1x1 tile grid, the same size as a room from the first attempt. There would then be an overall class that could store a list of these individual rooms and therefore represent a full room.
As can be seen in the above image this creating of random rooms already looked more impressive, purely by virtue of the diversity between them. Each of these rooms stored their walls and floors inside them, and had a 4 long array representing each side. This stored the values of an enum that could be either clear, wall or door. Clear was there so nothing would generate for a larger room that needed space between the tiles.
For generating the rooms I used a very slightly modified version of the spawning points I used for the first attempt. When a room was spawned it would look at its doors and generate them however, as I could not add them into the prefabs like I had before as I was only using a prefab to store a room and not any specific rooms.
When generating a valid room it was considerably easier. I no longer had to go through a list and find valid rooms as I could just create a room and set its doors how I needed them. The room was made, the points there were required to be doors were set to doors, and then I checked the other sides of this room if they could be doors, or if that would collide with an existing room. If it was possible to be a door I would generate a number between 1 and 100 and if it was below the door chance threshold (which I kept at a 70% chance to make a door) that rooms side would be a door.
Another feature that was sorely lacking from the first attempt was varying room sizes. Because of how I had implemented the rooms in preparation for this I could get a room controller class to randomly pick rooms that exist and then check locations around that room. If it found a point that was a different room it could make that room part of its room. It would get all of the room tiles that made up that room, add them to its array of rooms and set itself as the parent object. Then it would delete the room it had taken over. The connection between the room and this new room would be set to clear so no walls would generate between them.
Still at this point I had no doors generating so the way to tell rooms apart from a glance at the image above is the floor tile it used. Selected is a parent room object, which highlights both tiles as the both come under it, meaning this room has successfully combined with another room to for a 1x2 room.
With the rooms combining and generating I had to find a way of spawning doors. Inside each room tile I added a 4 long Boolean array that would represent if a door had been generated on that side. This stopped 2 doors trying to be generated on each room connection. The room controller would then go through each room and tell it to spawn its doors one by one. A door would be created by getting the vector between the centre of two of these rooms and halving it so it would be created at the exact point between these rooms. Each door object as I was generating them to fill a 2 wide gap as the would be the empty distance left to fill. I still only had 1 wide doors however so I created an object that had a 2 walls back to back and a door next to them. When a door is created it finds the walls on each side and sets them to that of the parent room. This helps the walls keep cohesion within the rooms.
This already was generating a much more exciting design than the original attempt, and felt like the code was much easier to maintain as it did not have to find a valid room from a massive list that was a very bloated function.
One issue that I wanted to fix can be seen in the above image. Both of these doors lead to the same room, making one of the irrelevant. The more times I combined a room in a given attempt the more prevalent this issue was. To get around this each room object was give a list of other room objects it was connected to. When I generated a door both of the rooms connected had each other added to their lists. If a door was tried to be made between 2 rooms that was already connected, these door sides would be turned into walls. As I made sure the rooms were connected changing the doors into walls still left the room accessible.
All of this generation had to be controlled by a class, as up until this point I was pressing each step in the order to make sure the last one had completed. In the controller class I set up a countdown that was watching the total number of rooms. After the number of rooms did not change for once second it would start doing all the combining and other functions that were required. All of the 1x1 tile rooms would all be created without this controller, but the controller was required to combine and spawn the room objects. The final order of functions for this class was to combine the rooms first, this would solve any issue with layouts later. Then the rooms would be prepped which would remove all interior walls and set all the room tiles to the same floor and wall. Then the doors would be generated, this was done before the walls in case any doors got converted into walls. And lastly all the walls and floors could then be safely generated.
This overall attempt was significantly better than my first attempt. It felt like it had so much more life to it and would give a vastly improved gameplay experience to explore.
An area in which I would like to improve on this is by adding some corners to the interiors of rooms, while not required it would help some of those sharper corners that generated as a result of combining rooms.
In addition I would like to be able to add decorations randomly about this generated level, giving each room even more personality in addition to the shapes, walls and floors.
Both of these attempts can be viewed on my itch.io page via the links below:
Version 1: https://asmondia.itch.io/generating-levels-v1
Version 2: https://asmondia.itch.io/generating-levels-v2