Help with procedural level generation (different room sizes)

Hey all!

Been busy the last couple of days trying to figure this one out:

I am currently working on a procedural level generator, using a 2d array and a List of "Rooms".
As it is right now, i can only generate a dungeon with fixed room sizes (1x1)
Think of a dungeon like Zelda (top down)

But! I really want to generate my dungeon with random room sizes
(probably with a weighted chance, but that is not the problem right now)

Here is how i am trying to achieve this right now:

I have a

Code (CSharp):

1. public int[,] GetRoomSize(int x, int y, Direction getDirection)

in this, i'll use a switch case to get our "Direction" like so:

Code (CSharp):

1. switch(getDirection)
2. {
3.     case up:
4.     break;
5.     case down:
6.     break;
7.     case left:
8.     break;
9.     case right:
10.     break;
11. }

and in each case, i'll "scan" the 2d array using different sizes for example:

Code (CSharp):

1. case up:
2. //grab a 3x3 area on our grid
3. for(int i = x-1; i < x+2; i++)
4. {
5.     for(int j = y-2; j < y+1; j++)
6.     {
7.         //check bool if valid position on our grid (x axis, y axis, type (0 = empty))
8.         //can also use: (ParentDungeon.ValidPosition(i,j,1))
9.         if(!ParentDungeon.ValidPosition(i,j,0))
10.         {
11.             //space = NOT empty, therefore 3x3 grid not available
12.         }
13.     }
14. }

However! Each time i encounter an occupied slot, i'll have to narrow the search, decreasing one of the axis.
Until i have a selection consisting of only empty slots.

Thats a lot of writing the same for loops, but with different values.

In the end, i'll return an int[,] with the desired width and height.

With this int[,], i'll check the length of both axes (is that the plural noun of axis?)
And select a random room size which will fit on/in our chosen spot/area.

This should work, however its probably not as optimized as it should be.

So my question, do you have any idea how this is made possible and easier then i just tried to explain?

Just to clarify, i am NOT asking for a script, merely a suggestion or push in the right direction (hehe)


//EDIT

I also came up with the idea, when a room is placed, it randomly determines its own size
if bigger than 1x1, it checks its surrounding slots, and continues to "grow" until size is reached.
Or if it cannot "grow" any bigger, leave it as it is.

Still wondering what you might think!

 

I'm not sure i understood you correctly, so let me summarize:
You have a grid (of bools?) and want to place rooms on it. Rooms can be placed in such a way that they dont overlap with other, already placed, rooms. If i understood you correctly, you plan on building your dungeon kind of like a tree, where each room knows the rooms it is connected to (hence the direction?). Your main problem is now that you need to figure out what size of room, if any, fits next to some other room in some direction on the array?

Is that about correct?
If not, it may help if you visualized the desired result in some way and explained the data structure you intend to use.

Generally speaking, when talking about procedural generation, it is often worth looking into some key topics like perlin noise or graph theory. There are also a lot of neat solutions for things like dungeon generators that may be worth looking into, and be it only to get inspired (or ideas for how to approach the problem).
You can also approach these kind of problems from different angles. You could first generate the room hierarchy as a tree structure and then visualize it on a grid. Or you could place a desired number of rooms onto the grid (using something like a simplified Poisson Disc Sampling algorithm) and decide later which rooms should be connected.
Or you can do it like this guy, who generated a ton of random rooms, separates them using collisions, then selects fitting rooms, connects them through a minimal spanning tree and calculated and generates paths to connect these rooms. While i probably would separate the rooms using math, not an actual physics simulation, it looks quite impressive:
https://gamasutra.com/blogs/AAdonaac/20150903/252889/Procedural_Dungeon_Generation_Algorithm.php
With some customization this may go in the direction of what you are looking for?
Keep in mind that visual representation and the data behind the rooms are two different things and you can always design it in such a way to make one fit the other if that's something you need.

 

Hey Yoreki,

Thank you for the reply! And i probably should have illustrated what i meant!

Therefore i made some images, illustrating what i want, and what i currently have.

This is what i currently have:



This is a grid of integers. The dark slots are empty = 0
Lighter slots are occupied = 1.

As of now, i can only create a level with room sizes 1x1 = slot.

But i occasionally want to create larger rooms. (2x1 or 2x2 or maybe even 3x3)

Like so:



How i generate the level right now is illustrated in the following images:
And starting from step 4, is what i want to add.

step 1.



I initialize the grid with desired With and Height.
Pick a random or fixed starting position, and create our first Room.

step 2.



I pick a random adjacent empty slot, and check if position is available.

step 3.



If position is available/EMPTY = 0, place new Room

step 4. (THIS IS THE TRICKY PART)



Next, we check one of the already placed slots, and look for empty adjacent slots.
We pick a random slot and check if this position is available.
(because this room is bigger, we not only check its [x, y] position, but also y-1 (1 above its current location)

step 5.



If the position is available, we place our new Room

We repeat step 4 & 5, and each time check if position is available (and if its a larger Room size, we check its adjacent slots if they are EMPTY as well)

Example 2x2 Room:



And when placed:



HOWEVER! In the example below:



We try to place a new Room (again of 2x2 size), this time the slot isn't available.
Since it is overlapping a previously placed Room.

This position and/or Room size is discarded, and a new position or size will be set.

I hope everything is clear.

Any help is still appreciated

Cheers,
Darryl

 

Hi again, that's a pretty nice illustration indeed! So you know how to place these rooms in a 'brute force' kind of way via trial and error, but are looking for more efficient ways of doing it.
If your only concern is performance, keep in mind that all of this happens (or should happen) before a level is loaded, thus it does not impact framerate. Considering that you probably wont create dungeons which thousands of rooms, loading times should not be affected either. So it would most likely be fine if you tried placing rooms at random locations and just repeated the process until it worked. You should, however, implement a maximum number of tries to prevent infinite loops (in cases where no new room fits). There may be other approaches you could like tho.

Do you have any hard restraints other than the grid size? I guess one would be the amount of tiles you want to fill, since otherwise your grid would be full of rooms. Anything else, like "there must be at least one 3x3 room"?

I assume you do not want paths between rooms, but instead want the doors to directly connect the rooms (or teleport you to the next one) like in your illustrations. If so, the way you are doing it (chosing random direction, checking if you can build a certain element there) is viable. However, you may find one of these ideas helpful:

Postprocessing your current dungeon:
One easy and efficient way to get some 2x1, 2x2, 3x3, .. rooms into your dungeon would be to start generating your current dungeon structure (image 1), and then connecting the existing rooms in a postprocessing step (basically image 1 -> image 2). If you have other hard restraints like "at least one 3x3 room must exist", but none fits into the generated dungeon, you could just add new single rooms until one fits and so on.
Unless there is something stopping you from this approach, it probably is the easiest to implement and most efficient solution.

Generate information about the rooms first, then place them on the grid later:
You could also approach the problem differently. Say you want to generate a dungeon for a 10x10 grid. You want rooms to take up at most 30 tiles of the grid. With these constraints, you can now determine the amount and size of rooms that fit into them. One way to fill this area would be 2*3x3 + 3*2x1 + 6*1x1 rooms. With this information about the dungeon you know that there is a way to place these rooms into the grid such that they do not overlap. You know that since you chose rooms to only take up 30 tiles, but there are 100 (>30) tiles available. From here on it's only about finding one of the many possible configuration. The more free space (here 70/100) there is, the easier it will be to find these configurations. Comes down to a similar problem you are facing now, but gives you more control over the desired rooms to fit into the grid, if that's something you need.

Using trees to your advantage (may require paths between rooms):
Another way to go about this would be creating your dungeon in a binary search tree structure, where you divide the available space into 2 (and repeat this step n times), and then simply place one room into each segment. However, this approach is mostly applicable if you want to connect rooms with paths. May still be worth looking into, especially if that idea is not set in stone yet. https://eskerda.com/bsp-dungeon-generation/

Potential adaption to your situation:
Take the following with a grain of salt since i did not test it: You could also adjust this approach to work without paths (probably). The idea would be to place a room and divide the remaining space into rectangle segments, each of which touch the placed room. You would then select a random segment (potentially weighted over its size) to place a new room in. Since you know the size and shape of the segment, you know exactly which kind of rooms fit into it. You can now chose a random viable room, place it next to the neighboring segments' room and divide the remaining space of the current segment into new rectangle segments again, such that they all touch the new room. Repeat the process until you are done.
This should work, but keep in mind that i did not test it yet so there may be some corner cases which i missed when thinking about it. Definitely a lot more effort to implement than solution 1, but would also be a very solid and efficient solution when working.

Hope any of this was useful. Sorry in case you just read a long text about stuff you are not interrested in

 

Hey Yoreki,

Thanks for the suggestions!

This is a very good idea, instead of determining the Rooms size in the process, I could do it afterwards.

I'll look into it! Thanks again!

Cheers,
Darryl

 

I've used this algorithm in one on my 3d project (Link). I was using it only to test some modular assets. But i don't like it because it has too much corridors. (Project - stopped because i don't have time to play around with)
So, to get rid of the corridors i just make a rogue-like generator like this one, but sometimes have lots of corridors.

Well, finally, i made a simpler one.. generate one room and trying to place next to a room.. if it doesn't fit, generate another room and trying to place and so on. Of course i have a break in my while, because i don't want to get stuck at the beginning . When i have a minimum numbers of rooms i just check if the map is playable.
How?
1. Check the width and height (not to have a linear map)
2.Check if i have at least 2 rooms with one door
3. Place a room as start room with only 1 door
4. Place a room as "end" with only 1 door
5. The path from start to stop will be minimum 5 rooms, from each at least 3 rooms has 2+ doors
That's it! (maybe i've should do a recheck with another start-end room, but the algorithm is so fast that is not important)

 

Hey adi7b9,

The generators are looking good! Very solid structure as far as i can tell.
And thanks for the steps

I'll keep it in mind!

Thanks again!

Cheers,
Darryl

 

Hi, I know this post is extra old but I've found a way to code this kind of rooms into existence:

First off, I'd like you to check this video:

In it, the dev uses the following steps:

1) Create the general shape of the room
2) Instantiate the rooms according to the dictionary that allocates each room according to the number in the grid

In step 2, he only checks for one number in the grid. However, if you check the "tile" just below, you can create a double-size vertical room. Same applies if you check the number on the right.

Hope it helps future people!

In case they take the video down, here's the code to create the grid:

Code (CSharp):

1.     void CreateRooms(int[,] grid)
2.     {
3.         int SpawnLocationx = Random.Range(1, gridSideLength - 2);
4.         int SpawnLocationy = Random.Range(1, gridSideLength - 2);
5.         Vector2 SpawnLocation = new Vector2(SpawnLocationx, SpawnLocationy);
6.         //As our spawn room still has his grid = 0, we need to manually create some rooms for it
7.         int r = 0;
8.         while (r == 0)//Until at least one room has been created next to the spawn
9.         {
10.             int randtop = Random.Range(0, 2);
11.             if (randtop == 1)
12.             {
13.                 grid[SpawnLocationx, SpawnLocationy + 1] += 2;
14.                 grid[SpawnLocationx, SpawnLocationy] += 1;
15.                 r += 1;
16.             }
17.             int randbot = Random.Range(0, 2);
18.             if (randbot == 1)
19.             {
20.                 grid[SpawnLocationx, SpawnLocationy - 1] += 1;
21.                 grid[SpawnLocationx, SpawnLocationy] += 2;
22.                 r += 1;
23.             }
24.             int randleft = Random.Range(0, 2);
25.             if (randleft == 1)
26.             {
27.                 grid[SpawnLocationx - 1, SpawnLocationy] += 4;
28.                 grid[SpawnLocationx, SpawnLocationy] += 8;
29.                 r += 1;
30.             }
31.             int randright = Random.Range(0, 2);
32.             if (randright == 1)
33.             {
34.                 grid[SpawnLocationx + 1, SpawnLocationy] += 8;
35.                 grid[SpawnLocationx, SpawnLocationy] += 4;
36.                 r += 1;
37.             }
38.         }
39.  
40.         Print2DArray(grid);
41.  
42.  
43.  
44.  
45.         int i = r + 1; //So far we have r+1 rooms
46.         while (i < numberOfRooms)//Create room spaces until we reach the total of rooms desired
47.         {
48.             for (int x = 0; x < gridSideLength; x++)
49.             {
50.                 for (int y = 0; y < gridSideLength; y++)
51.                 {
52.                     if (grid[x, y] != 0)//check that there is a room there
53.                     {
54.                         int randtop = Random.Range(0, 2);
55.                         if (randtop == 1 && y + 1 < gridSideLength && grid[x, y + 1] == 0)
56.                         {
57.                             grid[x, y + 1] += 2;
58.                             grid[x, y] += 1;
59.                             i += 1;
60.                             if (i >= numberOfRooms)
61.                             {
62.                                 break;
63.                             }
64.                         }
65.  
66.                         int randbot = Random.Range(0, 2);
67.                         if (randbot == 1 && y - 1 >= 0 && grid[x, y - 1] == 0)
68.                         {
69.                             grid[x, y - 1] += 1;
70.                             grid[x, y] += 2;
71.                             i += 1;
72.                             if (i >= numberOfRooms)
73.                             {
74.                                 break;
75.                             }
76.                         }
77.                         int randleft = Random.Range(0, 2);
78.                         if (randleft == 1 && x - 1 >= 0 && grid[x - 1, y] == 0)
79.                         {
80.                             grid[x - 1, y] += 4;
81.                             grid[x, y] += 8;
82.                             i += 1;
83.                             if (i >= numberOfRooms)
84.                             {
85.                                 break;
86.                             }
87.                         }
88.                         int randright = Random.Range(0, 2);
89.                         if (randright == 1 && x + 1 < gridSideLength && grid[x + 1, y] == 0)
90.                         {
91.                             grid[x + 1, y] += 8;
92.                             grid[x, y] += 4;
93.                             i += 1;
94.                             if (i >= numberOfRooms)
95.                             {
96.                                 break;
97.                             }
98.                         }
99.                     }
100.  
101.                 }
102.                 if (i >= numberOfRooms)
103.                 {
104.                     break;
105.                 }
106.             }
107.         }
108.         Print2DArray(grid);
109.         InstantiateRooms(grid,SpawnLocation);
110.     }
111. void Print2DArray(int[,] A)
112.     {
113.        
114.         string arrayString = "";
115.         for (int i = 0; i < A.GetLength(0); i++)
116.         {
117.             for (int j = 0; j < A.GetLength(1); j++)
118.             {
119.                 arrayString += string.Format("{0} ", A[j, i]);
120.             }
121.             arrayString += System.Environment.NewLine + System.Environment.NewLine;
122.         }
123.         Debug.Log(arrayString);
124.     }

And here, an incomplete (atm) code for instantiating the rooms:

Code (CSharp):

1.     void InstantiateRooms(int[,] grid, Vector2 SpawnLoc)
2.     {
3.         for (int x = 0; x < gridSideLength; x++)
4.         {
5.             for (int y = 0; y < gridSideLength; y++)
6.             {
7.                 Vector2 spawnPos = new Vector2(10 * (x-SpawnLoc.x), -10 * (y - SpawnLoc.y));//For normal 10*10 square rooms
8.                 int typeOfRoom = Random.Range(0, 5);//Random value to decide if we are making a big room and in which direction
9.                 //0-> 2-square vertical rooms
10.                 //1-> 2-square horizontal rooms
11.                 //else-> normal square rooms
12.                 if (grid[x,y] == 1)
13.                 {
14.                     //first we check if making vertical rooms
15.                     if(typeOfRoom == 0)
16.                     {
17.                         //now we check all possible vertical rooms whose top part is a grid=1
18.                         if (grid[x, y + 1] == 7)
19.                         {
20.                             int randomNum = Random.Range(0, 2);
21.                             if (randomNum == 0)
22.                             {
23.                                 rand = Random.Range(0, roomTypes.VertBTBR.Length);
24.                                 createdRoom = roomTypes.VertBTBR[rand];
25.                                 Instantiate(createdRoom, spawnPos, createdRoom.transform.rotation);
26.                                 grid[x, y + 1] = 0;
27.                             }
28.  
29.                         }
30.                         else if (grid[x, y + 1] == 3)
31.                         {
32.                             int randomNum = Random.Range(0, 2);
33.                             if (randomNum == 0)
34.                             {
35.                                 rand = Random.Range(0, roomTypes.VertBTB.Length);
36.                                 createdRoom = roomTypes.VertBTB[rand];
37.                                 Instantiate(createdRoom, spawnPos, createdRoom.transform.rotation);
38.                                 grid[x, y + 1] = 0;
39.                             }
40.  
41.                         }
42.                     }
43.                     //now we check horizontal rooms
44.                     if(typeOfRoom == 1)
45.                     {
46.  
47.                     }
48.                     //if not, we make one room there
49.                     else
50.                     {
51.                         rand = Random.Range(0, roomTypes.B.Length);
52.                         createdRoom = roomTypes.B[rand];
53.                         Instantiate(createdRoom, spawnPos, createdRoom.transform.rotation);
54.                     }
55.                    
56.                    
57.                 }
58.                 else if (grid[x, y] == 2)
59.                 {
60.                     rand = Random.Range(0, roomTypes.T.Length);
61.                     createdRoom = roomTypes.T[rand];
62.                     Instantiate(createdRoom, spawnPos, createdRoom.transform.rotation);
63.  
64.                 }
65.                 else if (grid[x, y] == 3)
66.                 {
67.                     rand = Random.Range(0, roomTypes.TB.Length);
68.                     createdRoom = roomTypes.TB[rand];
69.                     Instantiate(createdRoom, spawnPos, createdRoom.transform.rotation);
70.  
71.                 }
72.                 else if (grid[x, y] == 4)
73.                 {
74.                     rand = Random.Range(0, roomTypes.R.Length);
75.                     createdRoom = roomTypes.R[rand];
76.                     Instantiate(createdRoom, spawnPos, createdRoom.transform.rotation);
77.  
78.                 }
79.                 else if (grid[x, y] == 5)
80.                 {
81.                     rand = Random.Range(0, roomTypes.BR.Length);
82.                     createdRoom = roomTypes.BR[rand];
83.                     Instantiate(createdRoom, spawnPos, createdRoom.transform.rotation);
84.  
85.                 }
86.                 else if (grid[x, y] == 6)
87.                 {
88.                     rand = Random.Range(0, roomTypes.TR.Length);
89.                     createdRoom = roomTypes.TR[rand];
90.                     Instantiate(createdRoom, spawnPos, createdRoom.transform.rotation);
91.  
92.                 }
93.                 else if (grid[x, y] == 7)
94.                 {
95.                     rand = Random.Range(0, roomTypes.TBR.Length);
96.                     createdRoom = roomTypes.TBR[rand];
97.                     Instantiate(createdRoom, spawnPos, createdRoom.transform.rotation);
98.  
99.                 }
100.                 else if (grid[x, y] == 8)
101.                 {
102.                     rand = Random.Range(0, roomTypes.L.Length);
103.                     createdRoom = roomTypes.L[rand];
104.                     Instantiate(createdRoom, spawnPos, createdRoom.transform.rotation);
105.  
106.                 }
107.                 else if (grid[x, y] == 9)
108.                 {
109.                     rand = Random.Range(0, roomTypes.BL.Length);
110.                     createdRoom = roomTypes.BL[rand];
111.                     Instantiate(createdRoom, spawnPos, createdRoom.transform.rotation);
112.  
113.                 }
114.                 else if (grid[x, y] == 10)
115.                 {
116.                     rand = Random.Range(0, roomTypes.TL.Length);
117.                     createdRoom = roomTypes.TL[rand];
118.                     Instantiate(createdRoom, spawnPos, createdRoom.transform.rotation);
119.  
120.                 }
121.                 else if (grid[x, y] == 11)
122.                 {
123.                     rand = Random.Range(0, roomTypes.TBL.Length);
124.                     createdRoom = roomTypes.TBL[rand];
125.                     Instantiate(createdRoom, spawnPos, createdRoom.transform.rotation);
126.  
127.                 }
128.                 else if (grid[x, y] == 12)
129.                 {
130.                     rand = Random.Range(0, roomTypes.LR.Length);
131.                     createdRoom = roomTypes.LR[rand];
132.                     Instantiate(createdRoom, spawnPos, createdRoom.transform.rotation);
133.  
134.                 }
135.                 else if (grid[x, y] == 13)
136.                 {
137.                     rand = Random.Range(0, roomTypes.BLR.Length);
138.                     createdRoom = roomTypes.BLR[rand];
139.                     Instantiate(createdRoom, spawnPos, createdRoom.transform.rotation);
140.  
141.                 }
142.                 else if (grid[x, y] == 14)
143.                 {
144.                     rand = Random.Range(0, roomTypes.TLR.Length);
145.                     createdRoom = roomTypes.TLR[rand];
146.                     Instantiate(createdRoom, spawnPos, createdRoom.transform.rotation);
147.  
148.                 }
149.                 else if (grid[x, y] == 15)
150.                 {
151.                     rand = Random.Range(0, roomTypes.T.Length);
152.                     createdRoom = roomTypes.TBLR[rand];
153.                     Instantiate(createdRoom, spawnPos, createdRoom.transform.rotation);
154.  
155.                 }
156.             }
157.         }
158.     }
159. }

In this case, I'm only checking the case grid[x,y] == 1 and I still haven't implemented the code for horizontal rooms, but you get the idea.

 

Of course, you need to make a list with every possible room, it's pretty tedious but I couldn't find a better way to do it:

Code (CSharp):

1.  
2.     public List<GameObject> rooms;
3.  
4.     public int gridSideLength;
5.     public int numberOfRooms;
6.     public Transform cameraLocation;
7.  
8.     private int[,] grid;
9.     private RoomTypes roomTypes;
10.     private int rand;
11.     private GameObject createdRoom;
12.  
13.  
14.     // Start is called before the first frame update
15.     void Start()
16.     {
17.         grid = new int[gridSideLength, gridSideLength];
18.         roomTypes = gameObject.GetComponent<RoomTypes>();
19.  
20.         CreateRooms(grid);
21.     }