Procedural Dungeon - Part 2: detecting regions and connectivity

Procedural Dungeon - Part 2

Introduction: 

In the previous posts I explained how I managed to get the basic system of a procedural dungeon. However, there is still a lot to be done! We don't have a connected room system yet, so this will be the main focus of this post.

Detecting regions:

The maps that we generate now still have a few flaws. One of which is that I don't have any control over the minimum size of rooms or wallRegions. This will be the first thing to fix!

However, to do this we first have to detect the regions. To do this I used the floodfill method. This algorithm simply checks for all (horizontal and vertical) neighbours if they have the same value, and if yes, the neighbour is added to a 'region' list. In code this looks like this:

Now that we have the floodfill system, we can easily detect which areas should be removed. Here you see it in the Gizmos:

Detecting connectivity:

The next step is to detect whether rooms are connected or not. I do this by comparing the edgeTiles of all the rooms that have left with each other. For each room the following is true: the room with the closest available distance to roomA is the closest of roomA.

However, that all rooms are connected to the closest room, does not mean that all rooms are connected to each other. This is however, very important if you want the player to see all of the dungeon.

Ensuring connectivity:

The next challenge is to make sure that all of the rooms are connected. To do this I have changed the ConnectAllRooms function. I did this by making it recursive: The first call makes sure that all of the rooms where at least connected to the closest room. After this I split up all of the rooms in two Lists: one that contains all rooms that are not connected to the starting room, and one that contains all of the rooms that are connected to it.

The rest of the checking-which-room-is-best functionality basically remained the same. Now the rooms that are not connected to the starting room only try to connect themselves to the rooms that are connected to the starting room!

Creating passageways:

Now what we need to do is make sure that the passages between the rooms are being generated. We do this by creating a list of Coordinates between the start and the end position of a passage.                                                        The logic of this process is the following:                                 -we calculate delta x and delta y (dx and dy)                         -we compare the absolute value of dx to dy and the greatest value will determine in which direction we will traverse the line (the sign of dx or of dy)                                                   -we make a gradientAccumulation variable that will be used to track our line-traverse-progress                                           -we then start a for loop, where i < longest and in each iteration, a point will be added to the line and we will track if we have to update both x and y, or on of both                          Hopefully this explanation will help to understand the block of code displayed on the right.

So far:

What I have right now is a dungeon where all of the rooms are connected, and a mesh is created out of that data. Here is a GIF to show you the generation process over time: