1
\$\begingroup\$

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: enter image description here

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – TheNickmaster21 Oct 6 '13 at 1:54
  • \$\begingroup\$ 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? \$\endgroup\$ – IronGiraffe Oct 6 '13 at 5:15
  • \$\begingroup\$ 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. \$\endgroup\$ – TheNickmaster21 Oct 6 '13 at 13:28
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.