How I made the Dungeon Generator

Dungeon Generator Library

Dungeon Generators

Dungeons can be generated through this library using two different methods. There is a corridor first generation, which produces corridors and then and then places rooms on the corridors. Then there is room first generation which generates rooms randomly before connecting them together with corridors. Both of these generators use the random walk algorithm and extend the RandomWalkGenerator class which extends the abstract DungeonGenerator class.

These classes are all contained in the DungeonGenerator header file. View File

View Source Folder

RandomWalkGenerator

This class extends the DungeonGenerator abstract class and contains a constructor that takes 6 parameters:

  • The width of the map
  • The height of the map
  • the starting position
  • the number of random walk iterations
  • The length of each walk
  • whether or not to start at a random point on each previous walk rather than at the endpoint

When Generate() is called it initializes an empty map and then generates random floor positions by calling RunRandomWalk(). This function generates a series of paths in a loop until it has met the specified number of iterations. During each iteration, the generator runs the RandomWalk algorithm from the algorithms class with returns a coordinate list of positions the positions are then added to the list of floor positions before running the next iteration.

Once the floor positions have been created, the generator then creates the wall positions by using the wall generator part of the algorithms class by passing in the floor positions along with the width and height of the map as parameters. The floors and walls at then added to the map by calling the AddToDungeon function in the DungeonGenerator class.

View Source File

CorridorFirstGenerator

This class generates a dungeon using the "corridor first" method once the Generate() function is called. It has a constructor which takes 7 parameters:

  • The width of the map
  • The height of the map
  • The starting coordinate on the map
  • The length of each corridor
  • The total number of corridors
  • The percentage of potential room positions to be filled by a room
  • The random walk parameters (A struct made up of the following variables)
    • Iterations (total number of times walk)
    • The number of spaces in each walk
    • whether or not to start at a random point on each previous walk rather than at the endpoint
View Source File
Step 1 - Create Corridors
step 1 - create corridors

The first step is to create corridors using the "Random Walk Corridor" algorithm x number of times where x is the total number of corridors in the dungeon. A list of coordinates is then returned during each iteration before ad the end of each corridor as a potential room position and adding all positions in the corridor as floor coordinates.

Step 2: Create Rooms
step 2 - create rooms

Rooms are by first passing the list of potential room positions as a list. From the all positions get shuffled to make the order random. Rooms then get removed from the list until they meet the fill percentage of the roomPercent variable. Next, a room is generated from each room position by running the random walk algorithm using the room position as the initial point. All spaces filled by the algorithm are then added to the room floors list before returning it.

Step 3: Find Dead ends

The next step is to use an algorithm that detects all of the floor positions in the dungeon that are currently dead ends. The algorithm achieves this by checking each of the four adjacent coordinates (up, down, left, right) that are one space away from it. If any of those coordinates are also in the flow positions list then we increment the neighbour count. If the position only has 1 neighbour then it means it is a dead end and therefore we add that position to the dead ends list. Once every floor position has been checked the dead-ends list is returned from the function.

Step 4: Create rooms at dead ends
step 4 - Rooms at dead ends

The next step is to insert a room at each dead end so that the dungeon no longer has dead ends. This is done by running through iterations of the random walk algorithm just like in step 2, except each dead-end becomes the starting point for the algorithm.

Step 5: Add Walls around the floors
step 5 - Rooms at dead ends

The next step is to add walls around each floor position that has not been closed off. To do this we first add all of the room positions to the existing list of floor positions. Once this is done we then use the wall generator from the algorithms class to return a list of wall objects using a Wall struct, bypassing the floor positions and the width and height of the map as parameters.

Step 6: Add floors and walls to the dungeon map

The next step is to add all of the floor positions and wall positions to a 2-Dimensional vector (c++ list) which is the map. To achieve we first iterate through each floor position and make sure that it is not out of bounds. If it is not out of bounds then that position is added to the map at the specified x,y coordinate as the "Floor" tile type. Next, we iterate through each wall position and check if it is out of bounds. If it I not then it is added to the map at the specified x,y coordinate using the tile that was assigned to the wall object from the wall generator.

 

View Source File

RoomFirstGenerator

  1. This class generates a dungeon using the "room first" method once the Generate() function is called. It has a constructor which takes 8 parameters:
  • Width of the map
  • Height of the map
  • Starting coordinate on the map
  • Minimum room width
  • Minimum room height
  • Offset from the edge of each partition to create the room in
  • Whether or not to use random walk rooms
  • Random walk parameters that are made up of the following:
    • Iterations (total number of times walk)
    • The number of spaces in each walk
    • whether or not to start at a random point on each previous walk rather than at the endpoint
View Source File

Step 1 - Perform Binary Space Partitioning

Step 1 - binary space partitioning

The first step is to get a list of random rooms areas by calling the BinarySpacePartitioning function in the Algorithms class which returns a list of room boundaries including their width, height, minimum coordinate (bottom left corner) and maximum coordinate (top-right corner). We do this by passing in the area of the map to be split up along with the minimum room width and minimum room height.

Step 2 - Create rooms using the room boundaries
Step 2 - create rooms using boundaries

In this step, rooms are then created one of two ways. Simple rooms or random walk rooms. This depends on whether random walk rooms is set to true.

If simple rooms are being created then we iterate through all of the rooms in the room boundaries. For each room, we then iterate through all columns from the left offset to the right offset and all rows from the top offset to the bottom offset. Floor positions are then added from the room's min coordinate until the width and height have been reached. This process creates a series of rectangular rooms that come in different sizes but all have the same minimum gap between them.

If rooms are being created through random walks then for each room the RunRandomWalk function is called with the center position of each room boundary as the starting position. Each floor position returned for each room is then added to total floor positions so long as the position is not out of bounds.

Step 3 - Get the center of each room

Once all of the floor positions for the rooms have been created the center of each room is then added to a "room centers" coordinate list by calling the Center() function in the Boundary struct. This function calculates the center using the following equations:

width = max.x - min.x
height = max.y - min.y

x = min.x + width/2
y = min.y + height / 2

Step 4 - Connect the rooms with corridors
Step 4 - connect rooms with corridors

Once we have the center point of each room addition floor positions connecting them are created by generating corridors. A random room center is selected and removed from the list. The rest is achieved through the following substeps

  1. We find the closest room to this one by comparing the distance from the center of the current room to the center of all other rooms and then return the coordinate of the location that is the shortest one.
  2. Remove the closest from the list of room centers
  3. A list of corridor positions is then added by determining first determining the direction from the current room to the next one and moving in the specified direction until the destination has been reached.
  4. Insert all returned positions to the corridors coordinate list
  5. Repeat from substep one until there are no more room centers.

The list of corridor positions is then returned. After that, they are inserted into to the "floor positions" list.

Step 5 - Add walls around the floors
Step 5a - add walls around floors

This is achieved in the exact same way as the "corridors first" method which is to use the GetWall function in the algorithm class. We do this by first adding all of the room positions to the existing list of floor positions. Once this is done we then use the wall generator from the algorithms class to return a list of wall objects using a Wall struct, by passing the floor positions and the width and height of the map as parameters.

Step 6: Select correct tiles for the walls
Step 5b - Get tile for each wall

Information coming soon.

Step 7: Add floors and walls to the dungeon map

This step is also the same as the "corridors" first method. We add all of the floor positions and wall positions to a 2-Dimensional vector (c++ list) which is the map. To achieve we first iterate through each floor position and make sure that it is not out of bounds. If it is not out of bounds then that position is added to the map at the specified x,y coordinate as the "Floor" tile type. Next, we iterate through each wall position and check if it is out of bounds. If it I not then it is added to the map at the specified x,y coordinate using the tile that was assigned to the wall object from the wall generator.

DungeonGeneratorAlgorithms

This is a source file contains a series of static functions declared in the Algorithms header file. The functions in this file are always called by one of the DungeonGenerator subclasses. It contains a series of algorithms stored as functions that can perform the following operations:

RandomWalk

This function walks in a random direction with a set number of spaces. It does this by first adding the starting position to a coordinate list called path, then running a loop that adds new positions until it has reached the walk length. During each iteration, a new position is added to the previous position by selecting one of four directions (up, down, left, right) and adding that to the path as long as it is not out of bounds. The path is then returned once it is complete.

RandomWalkCorridor

This is the same as the RandomWalk function except the path can only be a straight line. This is achieved by first picking a random direction after adding the initial position, and then continuing to move forward in that direction until the length of the corridor has been met. The direction is only changed if the position is out of bounds. The corridor is then returned once complete.

BinarySpacePartitioning

This is used by the "Room First Generator". It splits a section of the dungeon into smaller sections. We do this by first creating a rooms queue and a rooms list. The space to be split is then added to rooms queue. The following substeps are then performed:

  1. Take the next room off the front of the rooms queue
  2. Check that the space to split is above the minimum size. It it is go step 3, otherwise go back to step 1
  3. Generate a random number between 0 and 1 if it is less than 5 we split horizontally if possible otherwise we split vertically if possible. If it is not possible then we attempt to split in the other direction. This continues until the space is not large enough to be split in either direction then we add it to the rooms list.

We split horizontally by first checking if the height of the space is at least double the minimum height and if it is calling the SplitHorrizontally function. We split vertically by first checking if the width of the space is at least double the minimum width and if it is calling the SplitVertically function.

This process loops until there are not more values in the rooms queue then the rooms list is returned.

SplitVertically

Splits a room into two rooms by cutting it down the middle vertically. To achieve this we first generate a random integer value between 1 and the width of the space to be split. We then define two boundaries for two different rooms. The first room has its starting x position set at the room's xMin and its final x position at the random split position. The second room has its starting x position at the random split position and the final x position set at the xMin + the width.

Both of these boundaries are then added to the back of the "rooms queue" used in the BinarySpaceParitioning function.

SplitHoirzontally

Splits a room into two rooms by cutting across the middle horizontally.

To achieve this we first generate a random integer value between 1 and the height of the space to be split. We then define two boundaries for two different rooms. The first room has its starting y position set at the room's yMin and its final y position at the random split position. The second room has its starting y position at the random split position and the final y position set at the yMin + the height.

Both of these boundaries are then added to the back of the "rooms queue" used in the BinarySpaceParitioning function.

IsOutOfBounds

Checks if a position is outside the boundary of the dungeon by checking if the x position is less than 0 or greater than the width, then checking if the y position is less than 0 or greater than the height. If any of these are true then it returns a true value.

ChangeDirection

Randomly turns left or right from the direction it is currently going in using the Direction2D class then returns to the new direction as a normalized vector coordinate.

View Source File

WallGenerator

This source file contains a series of static functions from the Algorithms class declared in the algorithms header file. It contains the following functions:

GetWalls

This is the public function called from other classes which returns a list of wall tiles. After receiving the list of floor positions and the boundaries it uses this information to create a list of side wall positions and corner wall positions by calling FindWallsInDriection twice with different direction parameters. Appropriate wall tiles are then generated by passing both the side wall and corner wall positions to the GetWallTiles function.

FindWallsInDirection

This function returns a list of wall positions in all directions in the direction passed as a parameter. This is achieved by iterating through the list of floor positions passed to this function and for each floor position, check each direction contained in the direction list to see if there is a neighbour. If there isn't one then that position is a vacant place to put a wall and so it gets added to the wall positions. The list of wall positions is then returned when the job is done.

GetWallTiles

This function returns a list of wall tiles where the type of wall in each position depends on how many neighbouring floor tiles are around the current position and where they are located. A string of 1s and 0s is generated based on this information.

First, we iterate through all positions in the side walls list. For each direction, if the neighbouring space contains a floor a 1 is added to the string otherwise a 0 is added. A 4-digit binary number is generated from this process which is used to pick the appropriate tile by passing this number to the GetWallType function. The tile is then added to the walls list.

Next, we iterate through all positions in the corner walls by checking in all eight directions for each position. A 1 is added if the neighbour space contains a floor and a 0 if it does not. The number is then passed to the GetWallype function with eightDirection set to true to get the matching tile type. The tile is then added to the walls list.

Once both loops are complete the walls list is returned.

GetWallType

This function gets the appropriate tile type for the binary string that was passed in and returns it. It does this by first converting the binary string to an integer. Then it goes through a series of if statements to see if that type is in one of the values returned from one of the static functions in the WallTypes struct. If it is it then sets the tile to that type using the TileType enumerator value before returning the value.

View Source File

Linkage

The Linkage.cpp file is what is used to create external functions when compiling the dynamically linked library (DLL) that is used by external application such as Unity to use this library. Five different external functions have been created for the dungeon generator which are listed below.

CreateRandomWalkRoom - Instantiates the RandomWalkGenerator class and returns it as a pointer.
GetSpaceValue - Gets the tile type in the map at a specified coordinate (x, y position) and converts it into an integer before returning it.
CreateCorridorFirstDungeon - Instantiates the corridor first generator on the heap and returns the object as a pointer.
CreateRoomFirstDungeon - Instantiates the room first generator on the heap and returns the object as a pointer.
GenerateDungeon - Generates the dungeon using the C++ library program. Works with any pointer that is a subtype of the DungeonGenerator class.

View Source File

Dungeon Generator Unity Application

Dungeon Generator

On the Unity side a DLL file called "Procedural Generation Library" was imported to handle the procedural generation. The use this DLL I first had to create a C# class that reads from the library.

DungeonGenerator.cs

This is the source file that reads from the dynamically linked library (DLL) file as well as constructors for instantiating a dungeon object. The main class is called DungeonGenertor where all of the DllImport functions are defined. There are then 3 subclasses that extend this class: RandomWalkRoom, CorridorFirstDungeon and RoomfirstDungeon. There is also an enumerator called TileType that defines if the space is empty, a floor or a wall along with what type of wall tile it uses.

Each of these classes returns an integer pointer once the dungeon has been instantiated and then BuildMap is invoked using the pointer. In the BuidMap function, GenerateDungeon is called in the DLL which creates the map in memory. Each tile is then added to the locale TileType 2D array called map by calling GetSpaceValue from the DLL which returns a number.

View Source File

AbstractDungeonGenerator

This is the unity C# equivalent of the DungeonGenerator class declared in DungeonGenerator.h It is an abstract class that different types of dungeon generators extend. It contains a struct called DungeonTile that contains a 2D vector position and and a tile type.

The class contains a GenerateDungeon() function which clears the existing dungeon from the application before invoking the abstract Generate() function. There is also the GetTileDate function which creates a list of "dungeon tiles" by invoking GetMap on the dungeon class and then adding the corrsponding dungeon tole to the list. The GenerateTiles() function uses then uses the tile map visualizer to paint the tiles on the screen.

View Source File

SimpleRandomWalkDungeonGenerator

This class overrides the Generate function by setting the dungeon object to a new random walk room. It then invoke the GenerateTIles() function. The script can be attached to a game object and then created or erased using the button that were creates using an Editor script called RandomDungeonGeneratorEditor. It also takes a scriptable object for the random walk parameters (iterations, walk length, start randomly each iteration).

View Source File

CorridorFirstDungeonGenerator

This class overrides the Generate function by setting the dungeon object to a new corridor first dungeon. It then invokes the GenerateTIles() function. Variables for corridor length, corridor count and room percentage can be adjusted on the Unity inspector.

View Source File

RoomsFirstDungeonGenerator

This class overrides the Generate function by setting the dungeon object to a new rooms first dungeon Room. It then invokes the GenerateTIles() function. Variables for minimum room width and height, the room offset and whether or not to use random walk rooms can be adjusted on the Unity inspector.

View Source File

TileMapVisualizer

This script is used to paint tiles onto the tile 2D tile grid using the from a list of dungeon tiles that is pass in through the PainTiles function. The tilemap for the floor and walls are assigned to this script along with each individual tile sprite for each type. There is also a public Clear() function that clears both the floor tilemap and the wall tilemap.

View Source File

DungeonUIManager

This is the script that connects the user interface that appears in the game window to the classes in the DungeonGenerator source file used to generate the dungeon ant then display it using the visualizer. All of the gui components used are taken from the Unity heirarchy and place on this script.

When the generate function is clicked the GenerateDungeonFromGUI() function is invoked on this script which reads from the user interface and puts values into variables. These variables are then passed as parameters when instantiating either the CorriroFirstDungeon or RoomFirstDungeon constructor.

View Source File
DungeonUIManager

Cave Generator

For Information about I made the cave generator click on the button below.

Leave a Reply