How irregularly shaped rooms should be placed in a dungeon

Question

I have made a procedurally generated dungeon that places every room successfully so it is accessible via at least one other room. A 'successfully' placed room is a room who's wall cells are right net to another room's wall cells. This is because there are no corridors in my dungeon, but doorways, 2 cells thick:

       ###########
       #.........#     // Where '[]' is the Doorway.
########.........#
#.....[].........#
#.....############
#.....#
#######

However I have now moved on to procedurally generate irregular shaped rooms, such as 'L' shaped rooms, 'T' shaped rooms, and so on.

I am wondering how I can place, for example, a square room next to an 'L' shaped room, without wasting any space: i.e.:

     ##########   
     #........#
######........#
#...[]........#
#...###########
#...#
#...#######
#.........#
#.........#
###########

This is not possible with my previous algorithm because it only took into account the room's bounds, where as now an 'L' shaped room's bounds contains empty space that a square room could possibly fit.

Answer 1

I would say that your own answer might be a good start. Still, I would do it a bit differently. So, here are a few suggestions/additions.

1) You could first determine the possible positions of doors in each room, then use those as joint points. You connect Room A to Room B by a given door of A to a given door of B and then test if the result meets your conditions (for instance, that there is no overlap between the interior of the rooms, etc). This way can be cheaper than walking each room against each other.

2) If rooms are irregular but never super very complex in shape (like the simple shapes of T, L, U, E, squared, rectangles, etc) AND if you want perfect fit between rooms, you can use rooms vertices as point-joints for checking. It means, you choose a vector from room A boundary and make it match a vector of room B. Like you can see in figure below, you have to make sure at least one edge overlaps, so to avoid the first case shown. Also, you have to make sure that only edges overlap, i.e. no interior area, so to avoid the second case shown. So either the third or the fourth cases shown would be accepted and rooms would them be connected:

3) No matter the solution (including your own), depending on your preferences, you might want to try to leave as least open spaces as possible without rooms. For instance, in your example, it would mean starting the test for the position of room A in the empty space of the bounding box of B. One way to do that could be by identifying the vertices/edges/doors/whatever of B that lay within the base polygon of the bonding box of B, not at its edges. And then start there.

With some approaches, like the one shown in the figure above, i.e. using vertices as joint points, you can also find such specific match by doing the following. If you discard the cases where inner areas overlap, and only accept the cases where at least two edges overlap, then you can only have the last case shown in the figure.

4) If you choose to position the rooms near to each other and then walk one against the other testing for collisions, the first thing you should do is place both rooms near each other but in a way that they do not overlap, before moving one against the other. Doing that you save performance since you will need to move them less and also perform less collision checks. The best way to do that (specially if you have a big scene) is with spatial partitioning.

5) With any of solutions above, if you have really very complexly shaped rooms, one possibility is the following. If you don't mind using an additional mini-polygon as a corridor, just place the rooms very close to each other but not colliding (e.g. via spatial partitioning + walking one room), and then place the small corridor between then (even if it overlaps a bit) and use the common area between them as the passage:

Hope it helps, at least as food for thought.

Answer 2

I think I've managed to solve it:

• First generate your rooms:

               @#########@    // ' ' = Don't place any cell here
  @#######@    #.........#    // '.' = Place floor cell here
  #.......#    #.........#    // '@' = Place wall cell here
  #.......#    @####@....#    // '#' = Place wall cell here AND 
  #.......#         #....#    //       mark as a possible doorway location.
  @#######@         #....#
                    @####@
  

• Now we have two rooms ready for placement. NB: When creating the '#' cells, they must have a way of telling which direction the doorway is leading out to, this is so rooms can be placed in the correct position and avoid overlapping as much as possible. This could be represented by an integer or vector. E.g.: (-1, 0) for left.

• Move room A next to a random room (in this case room B) by changing a random door cell's position to one of room B's door cell positions. The rest of the room's cells should then be moved relative to this door cell's position. If any of room A's floor cells overlap with any other room's floor cells, repeat this step.

• Where the two cells overlap, place a doorway/turn that cell into a floor cell.

     @#########@
     #.........#    // Even though the cells marked '%' are technically
     #.........#    // no longer feasible doorway cells, a new room should
     @%%%%@....#    // still not be able to place itself there as there
  @##%%%%%@....#    // would be overlapping floor cells, which cancels
  #............#    // a movement.
  #.......@####@
  #.......#
  @#######@
  

Voila! (I shall try to implement this and then edit this answer accordingly - either delete it or confirm success)