# How irregularly shaped rooms should be placed in a dungeon

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.

• A link to such a question would be nice, with an answer to my problem stated. Yes perhaps the corridor question was a bit lazy but I don't think I've seen anywhere answering my question on how to place rooms next to each other in my specific manner while not wasting space. – ImperialCoder Oct 23 '15 at 11:13
• That was my question I asked yesterday, I don't think they are related at all. My question today is how to connect them in the way I have described above. That question was asking how to generate rooms of a specific shape. If anything, this question is a development on yesterdays. – ImperialCoder Oct 23 '15 at 11:16
• @Arcane Engineer - I much prefer to thoroughly research before posting questions on stack, for many reasons, one being that I know how annoying duplicative questions can be, and two being that I'm impatient and find that answers can be found much quicker by doing some research. But again, I think my question is very specific. Perhaps I wasn't clear enough. I am asking for an algorithmic way to place rooms next to each other in the specific way described. Thanks for changing your mind though. :) – ImperialCoder Oct 23 '15 at 11:22
• @ArcaneEngineer - You misunderstand, I said that it is my impatience that causes me to research, not to post questions, posting questions is my last resort. – ImperialCoder Oct 23 '15 at 11:26
• – Engineer Oct 23 '15 at 11:28

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.

• Thanks, some interesting solutions, the first of which I actually implemented and am sticking with. :) Was basically what I suggested in my poorly worded answer. – ImperialCoder Oct 24 '15 at 0:45

I think I've managed to solve it:

             @#########@    // ' ' = 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)

• Getting there. Bear in mind that as the complex grows, it's going to get more difficult to attach new rooms. I would suggest you put any new room a fair distance away, and "walk" it toward another room / room-complex B, one step at a time in x and/or y, to be sure you don't hit anything else on the way in. You'll soon see why this is necessary... the complex will get complex. Costly, but safe. Another way to tackle this problem is to place all rooms initially in such a way that their bounding boxes can't overlap, and then start walking some A & B closer to one another. There are many ways! – Engineer Oct 23 '15 at 14:20