Procedural Dungeon Generation with set room sizes and no hallways

Question

I am working on a generator for a Dungeon game. Basically, I have different types of rooms, and different shapes of rooms. The different types contain a list of allowed shapes, and each shape contains possible door locations. I have a set box size (4x4), and I want to generate rooms following that size with randomized types, shapes, and doors. I've been doing research for a few days about all the dungeon/house generators I can find but none of them quite fit the bill. They either use corridors, rely on randomized room sizes, or some other quirk. Any ideas about how to go about this would be greatly appreciated. I've attached an example I made that shows about what I'm looking to create.

The requirements are as follows:

• The room shapes are predetermined
• The possible door placements for each room are predetermined
• The full dungeon shape is predetermined, and is always a box (4x4, 8x8, etc)
• There are no big hallways, only doors leading straight to the next room
• There should always be at least 2 big shapes

The closest algorithm that I've found would be a binary space partition, but I'm unsure of how to implement that with predetermined room shapes, all the implementations I've seen randomly select points to divide at with hallways, which wouldn't fit the bill.

Any suggestions are greatly appreciated!

Answer 1

While 1 unit seems to be common denominator for all sizes, the rooms are apparently made from bigger (5x5) blocks, fitting to their own grid. You could start with a bigger grid to lay out the rooms, then migrate the data into a smaller grid to add the doors.

Room arrangement can be brute-forced, just keep trying to fit a room repeatedly into random position and orientation, checking that it is in bounds and is not colliding with any other rooms. To minimize the chance of getting stuck, order the pieces by size, starting with biggest first. But in case if the algorithm gets stuck, just start from scratch, because this kind of generation is pretty cheap.

Once the rooms are in place, transform them into a finer grid, with walls on the outer perimeter. And the doors, of course.

Ensuring that all the rooms are connected may be tricky. You'll have to do a flood-fill from a random starting room and see if it visits all the other rooms. (This can be done on the room arrangement stage, before the walls.) If the answer is negative, restart the process.