I've been looking at some algorithms and articles about procedurally generating a dungeon. The problem is, I'm trying to generate a house with rooms, and they don't seem to fit my requirements.
For one, dungeons have corridors, where houses have halls. And while initially they might seem the same, a hall is nothing more than the area that isn't a room, whereas a corridor is specifically designed to connect one area to another.
Another important difference with a house is that you have a specific width and height, and you have to fill the entire thing with rooms and halls, whereas with a dungeon, there is empty space.
I think halls in a house is something in between a dungeon corridor (gets you to other rooms) and an empty space in the dungeon (it's not explicitly defined in code).
More specifically, the requirements are:
- There is a set of predefined rooms
I cannot create walls and doors on the fly.
- Rooms can be rotated but not resized
Again, because I have a predefined set of rooms, I can only rotate them, not resize them.
- The house dimensions are set and has to be entirely filled with rooms (or halls)
I.e. I want to fill a 14x20 house with the available rooms making sure there is no empty space.
Here are some images to make this a little more clear:
As you can see, in the house, the "empty space" is still walkable and it gets you from one room to another.
So, having said all this, maybe a house is just a really really tightly packed dungeon with corridors. Or it's something easier than a dungeon. Maybe there is something out there and I haven't found it because I don't really know what to search for.
This is where I'd like your help: could you give me pointers on how to design this algorithm? Any thoughts on what steps it will take? If you have created a dungeon generator, how would you modify it to fit my requirements? You can be as specific or as generic as you like. I'm looking to pick your brains, really.
Thank you in advance.
First of all, I'd like to thank both @Shadows In Rain and @egarcia for their answers. They gave me a good direction which helped me get some results. I used Shadows In Rain's space partitioning to generate a basic house and then followed egarcia's advice to fill in the area with rooms.
The space partitioning was pretty straightforward since 90% of the code was done by Shadows. The "fill in the rooms" part was a little more challenging. I decided to use a pseudo AI Planning system that uses A* to position the rooms appropriately. The good thing about using planning instead of just A* is that the preconditions help cut down the search space significantly. However, my "planning system" is more like A* + action preconditions than a full blown planning system with preconditions and effects.
Anyway, I'll leave the implementation for a blog post. Here are some screenshots with the results:
P.S. I'm giving the answer to Shadows In Rain since he provided source code, but they were both correct.