# What's the simplest way to determine the size of an empty space between rectangles?

I'm working on a dungeon generator and I'd like to be able to connect rooms through other rooms. What I currently have set up is two dictionaries and a map (an int array.) The first dictionary holds room templates separated by height, width and type (so: Dictionary<string, Dictionary<int, Dictionary<int, List<Room>>>.) The other dictionary holds rooms that have already been added to the map and uses rectangles as keys. I'd like to be able to find the maximum rectangular area that could fit into an empty space, then select a template room accordingly.

So what would be the simplest way for me to do that?

Edit:

My current method for creating the map follows certain steps:

1. Load in room templates from an xml file.

2. Create the start room in the middle of the map using a start room template with a random size.

Point mid = new Point(MapWidth / 2, MapHeight / 2);

int height = roomTemplates["Start"].ElementAt(random.Next(roomTemplates["Start"].Count)).Key;

int width = roomTemplates["Start"][height].ElementAt(random.Next(roomTemplates["Start"][height].Count)).Key;

int index = random.Next(roomTemplates["Start"][height][width].Count);

Room r = roomTemplates["Start"][height][width][index];

for (int x = r.RoomSize.X; x <= r.RoomSize.Width; x++)
for (int y = r.RoomSize.Y; y <= r.RoomSize.Height; y++)
{
Global.map.Map[x + (mid.X - r.Center.X), y + (mid.Y - r.Center.Y)] = r.Grid[x, y];
}
roomList.Add(new Rectangle(mid.X - r.Center.X, mid.Y - r.Center.Y, r.RoomSize.Width, r.RoomSize.Height), r);
foreach(Door door in r.Doors)
{
doorTemporary.Add(new Point((mid.X - r.Center.X) + door.Location.X, (mid.Y - r.Center.Y) + door.Location.Y), new Door(doorMap, new Point((mid.X - r.Center.X) + door.Location.X, (mid.Y - r.Center.Y) + door.Location.Y), door.Facing));
}

List<Point> points = new List<Point>();

3. Using a similar method as before, create rooms necessary to the game (shrines, barracks, treasure rooms, etc.) and place them randomly throughout the map, checking if they collide and moving them accordingly.

    Point u = new Point(-1, -1);
Restart:
while (points.Contains(u) || u.X == -1 || Global.map.Map[u.X, u.Y] != 0)
u = new Point(random.Next(1 + r.Center.X, (Width - r.RoomSize.Width) - 1), random.Next(1 + r.Center.Y, (Height - r.RoomSize.Height) - 1));

var eo = roomList.Where(n => n.Key.Intersects(new Rectangle(u.X - r.Center.X, u.Y - r.Center.Y, r.RoomSize.Width, r.RoomSize.Height))).Select(n => n.Key);

if (eo.Count() > 1)
goto Restart;
if (eo.Count() == 1)
{
foreach (var ei in eo)
{
Rectangle ri = new Rectangle(u.X - r.Center.X, u.Y - r.Center.Y, r.RoomSize.Width, r.RoomSize.Height);
Rectangle intersection = Rectangle.Intersect(ri, ei);

if (intersection.X < intersection.Y)
if (ri.X == intersection.X)
u.X += intersection.Width;
else
u.X -= intersection.Width;
else
if (ri.Y == intersection.Y)
u.Y += intersection.Height;
else
u.Y -= intersection.Height;
}
}

Rectangle ro = new Rectangle(u.X - r.Center.X, u.Y - r.Center.Y, r.RoomSize.Width, r.RoomSize.Height);
if (ro.X < 1 || ro.X + ro.Width > MapWidth - 1 || ro.Y < 1 || ro.Y + ro.Height > MapHeight - 1)
goto Restart;

4. Create paths to the rooms using triangulation, a minimal spanning tree algorithm and A* pathfinding.

5. (And this is where my question comes into play) use the paths generated before as guides and connect the already existing rooms together using rooms from roomTemplates. In order to do that, I need to know how much space I have available before selecting a room template.

What I've generated already looks like this: Blue is walls, white is floors, orange is doors and green is the designated "center" of that room (usually used only for A* pathfinding.)

I kind of already had an idea of how I could find the available space, but decided to ask because I wanted to know if there was an simpler way of doing it.

• Could you provide more information about the map that you are finding the rectangle size with? I'm having trouble figuring out what exactly you are asking. – TheNickmaster21 Oct 6 '13 at 1:54
• The map itself is a 2d int array. It's basically just int[width, height] with the type of ground being represented by numbers. I'm not really sure if that helps. I guess what I'm asking is: if I already have rooms on the map (and have their locations stored in a dictionary as rectangles) how can I create a rectangle that perfectly fits between them. Would it be as simple as creating a rectangle with the maximum room size in the area I want the new room and shortening it according to where other rectangles intersect with it, or is there a better way of doing it? – IronGiraffe Oct 6 '13 at 5:15
• Okay, so you have a bunch of rectangles, and want to put more rooms between the already existing rectangles? How do you determine where to place the new room? And why don't you just generated them all at once? Or just don't leave spaces when generating new rooms to maximize space and to not worry about this. – TheNickmaster21 Oct 6 '13 at 13:28