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

Question

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:

Admittedly, I was a little vague before so here's a little more information.

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>();
       points.Add(start);
   

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.

Answer 1

I would go with a simple iterative approach. Assuming coordinate (0,0) is top left corner.

• Check if (x,y) is 'in' existing rectangle Google
• Increment 'x' until (x,y) is not in an existing rect or out of bounds(oob)
• Record the position(we'll call it Point1) of the first 'miss' (point not in rect) as the top left of the new rect
• Continue incrementing 'x' until you 'hit' another rect or oob
• Record that point as the top right of the new rect (Point2)
• Now increment 'y' and repeat the process (You can start from x = Point1.x)

Now depending on how your map is 'allowed' to be laid out, there are ways to optimize, and also pitfalls to watch out for. But for the most part, once you have the top left and right corners, its just a matter of checking that 'misses' are greater than Point1.x and less than Point2.x and incrementing y until it hits the bottom left corner of empty space.