# Filling a rectangle using smaller ones / Slicing a rectangle into smaller ones

## Preface

I am currently trying to translate an algorithm for the procedural generation of dungeons into code. For this matter I have divided the algorithm into phases and have come up with a solution for the first step and in this first post concerning the first phase I would appreciate feedback on the general implementation and specific questions that came up.

I hope you don't mind that I have chosen a title that describes two different approaches which arguably yield the same result I want to achieve here.

## Explanation

I want to write a function GenerateGrid(mapWidth, mapHeight, maxRoomWidth, maxRoomHeight) that creates a two-dimensional grid of size mapWidth x mapHeight and fills it with smaller rectangles (rooms) that adhere to the following rules:

• All rooms have to be rectangular. Hence no L-shapes or other fancy stuff.
• All rooms have random sizes [1, maxRoomWidth] x [1, maxRoomHeight].

My naive approach revolves around traversing the grid in right-down direction and attempting to fit in a room of random size if possible until everything is claimed.

## Code

private static void GenerateGrid(byte mapWidth = 10, byte mapHeight = 10,
byte maxRoomWidth = 3, byte maxRoomHeight = 3)
{
var grid = new byte[mapHeight, mapWidth];
var random = new Random();
byte roomNumber = 1;

for (var y = 0; y < mapHeight; y++)
for (var x = 0; x < mapWidth; x++)
{
// Tile is already claimed.
if (grid[y, x] != 0) continue;

int roomWidth;
int roomHeight;
bool isColliding;
do
{
roomWidth = random.Next(0, maxRoomWidth) + 1;
roomHeight = random.Next(0, maxRoomHeight) + 1;

// Check whether there is enough space to fit the room by accessing
// all respective tiles.
isColliding = mapWidth - x < roomWidth || mapHeight - y < roomHeight;
if (isColliding) continue;

// Check whether the (seemingly free) space isn't claimed though.
for (var yOffset = 0; yOffset < roomHeight; yOffset++)
for (var xOffset = 0; xOffset < roomWidth; xOffset++)
isColliding |= grid[y + yOffset, x + xOffset] != 0;
} while (isColliding);

// Assign the room number to tiles and claim them.
for (var yOffset = 0; yOffset < roomHeight; yOffset++)
for (var xOffset = 0; xOffset < roomWidth; xOffset++)
grid[y + yOffset, x + xOffset] = roomNumber;

roomNumber++;
}

for (var y = 0; y < grid.GetLength(0); ++y)
{
for (var x = 0; x < grid.GetLength(1); ++x)
Console.Write(\$"{grid[y, x],4}");
Console.WriteLine();
}
}


## Sample

A sample call to GenerateGrid(20, 20, 4, 4) will yield the following output:

## Questions

1. In general this part works very well and has some aesthetical issues I will be covering in the next question, but what is your opinion about the current code in general? Is there anything that can be simplified or combined?
2. In my sample I was quite "lucky" since the resulting map wasn't as degenerate as usual. With the way how the algorithm is designed bigger rooms are pretty rare since it happens fairly often that a bigger cannot be placed starting at (x,y) as there is often another room starting at (x+1, y-?) that is dangling and obstructing the way down. In my particular example room 36 could not expand to the right side since room 27 was already there. The only way that I was able to "enforce" more bigger rooms is by adjusting the roomWidth and roomHeight variables with a deviation using roomWidth = random.Next(0, maxRoomWidth + 1) + 1; as well as roomHeight = random.Next(0, maxRoomHeight - 1) + 1;. Is there any better approach to allow slightly more big rooms?
3. Ultimately the last question follows from the same issue that was described in question 2. Most rooms end up being narrow and aligned to go from NE to SW while rooms that are aligned from NW to SE are pretty rare. I assume this will adjust itself once the problem in question 2 is fixed but if not, how can I balance the number of rooms that are horizontal or vertical?

## Remarks

The algorithm will have other steps which may imply that the code from this part could be optimized for later stages. In the next stages the algorithm will proceed roughly like this:

• The algorithm will create a graph from the grid with nodes being the rooms and edges between the nodes if they are neighbours.
• After applying random weightings to the edges a shortest path between two specified rooms (called start and end) will be computed. All rooms along the path will be added to final map as THE solution path that will always exist.
• Eventually using some branching random rooms will be added to the map to make it non-linear, with some dead ends and making the map feel more "natural". No alternative paths will be allowed here so the basic idea is to add random edges (and corresponding rooms) to the final map which connect rooms that are already part of the final map and ones that are not (to prevent alternative routes and cycles). This will happen with an increasing chance to stop prematurely.

private static void GenerateGrid(byte mapWidth = 10, byte mapHeight = 10,
byte maxRoomWidth = 3, byte maxRoomHeight = 3)


It's a private function, do you ever call it without parameters? With just 3 parameters? I'd guess not, remove those default values (and if you really need a function to quickly generate a map using all the default values just add an overloaded version).

Also you do not validate function arguments. It may be OK for a private function but at least add Debug.Assert() as appropriate (for example Debug.Assert(maxRoomWidth <= mapWidth) or whichever other rules you have).

var grid = new byte[mapHeight, mapWidth];


Here you're using a byte just to store the room number. You, however, repeat the same value in each cell of the grid and it's definitely a waste. Why don't you introduce Grid and Room classes? Room will have it's ID property and the Grid is, to begin with, just a list of rooms. Code will be slightly slower when searching but much easier to read:

foreach (var location in grid.GetFreeLocations()) { }


Or, simpler to implement:

while (!grid.IsFull)
AllocateRoomAtLocation(grid.GetNextFreeGridLocation());


I guess you understand the point. I know this is an annoying change because you have to rewrite existing algorithm but you're using this data structure only because it's somehow handy for this specific task (not that much, IMO) but it'll be a pain when you will need to use it in your actual game code. Note that if you need to simply keep track of used cells (still producing Room objects, of course!) you can use a simpler data structure like a bit map (not an image but a grid of bits!)

If in future you will want to generate rooms with a different algorithm? You may consider to implement a Strategy pattern to inject the allocation algorithm. This will also make testing much easier (without relying on randomly generated data) because you can prepare well-defined layouts to complete (something you can't do if your only interface is GenerateMap().)

It doesn't make much sense to comment the other code given that I'd radically change it because of the above but few notes.

 for (var y = 0; y < mapHeight; y++)
for (var x = 0; x < mapWidth; x++)


Nesting is ugly, I agree, but do not try to hide it in this way. If you feel that a code snippet smells or it's hard to read then it's time to extract a method for it! For example:

for (var y=0; y < mapHeight; ++y)
{
for (var x=0; x < mapWidth; ++x)
{
AllocateRoomAtLocation(x, y);
}
}


Of, if you love LINQ:

IEnumerable<(byte X, byte Y)> GetAllLocations(byte width, byte height)
{
return Enumerable.Range(0, width)
.SelectMany(x => Enumerable.Range(0, height).Select(y => (x, y)));
}


Just for fun the misused JOIN version: Enumerable.Range(0, width).Join(Enumerable.Range(0, height), _ => true, _ => true, (x, y) => new (x, y));.

And then:

foreach (var location in GetAllLocations(mapWidth, mapHeight))
AllocateRoomAtLocation(location);


Or (assuming you have a ForEach() extension method on IEnumerable<T>):

GetAllLocations(mapWidth, mapHeight).ForEach(AllocateRoomAtLocation);


The same should be applied all around to other parts of your code. Pretty often loops are a good indicator that it's time to introduce a separate method.

Your while loop will greatly benefit from a refactoring, move it to a separate method and it'll be easier to read. Note that you use isColliding only to exit the loop then imagine this:

while (true)
{
// ...

bool isColliding = mapWidth - x < roomWidth || mapHeight - y < roomHeight;
if (isColliding)
break;

// ...
}


Of course we should have a separate IsColliding() method but we already introduced a Grid class...

Why first you use mapHeight and mapWidth in your loop and at the end you use grid.GetLength(0)? A difference is eye catching and future reader will stop and think...think...think...to finally deduce that matrix size is still what specified in those parameters and mapHeight may be used.

Not directly related to your code but you may want to start allocating big rooms first (yes you need parameters to define, for example, the expected average room size and deviation from that). If you start allocating big rooms (in random locations) then you have better chance to have a less dispersed map (and small rooms may be used to simply fill the gaps).

• I will be taking all your suggestions into consideration and like them a lot. Eventually creating the Room objects I can create a Dictionary<int, Room> or just a Room[] as well in order to quickly build a graph while indexing the Room objects. Commented Sep 19, 2017 at 8:43
• I'd create a RoomCollection class (consider if deriving fromCollection<T> or implementing ICollection<T>). I'd love to start with the simpler approach (a list) and moving to a dictionary only if you measure a performance issue while searching by room number (having a separate class makes this an implementation detail you can change in any moment without impacting existing code) Commented Sep 19, 2017 at 8:48