I've been working on a project for a while which takes a grid of n*n tiles (starting at n=16 and with n increasing by 4 every so often for new floors), and fills it with rooms of random rectangular sizes, and have been having issues creating an efficient algorithm to do so that fits my requirements:
The outside ring (where x = 1 or n | y = 1 or n) must be corridor tiles (obviously easy)
All rooms must be entirely surrounded by corridor tiles
In no place may there be a 2x2 grid of corridor tiles (so corridors are all 1 tile thick)
There are certain rooms of specific sizes that must be present, and then there are other types of rooms which just fill in the remaining space afterward.
Do not have any corridors that go all the way through the floor.
(Preferably) Room min side length = 2 (relatively easy to program in my code, perhaps not in one of 'your' suggestions)
My algorithm works fine, however at n=12 it takes ~2s to compute on my 4790k, and grows ridiculously exponentially from there: taking 6s for n=14, 29s for n=16, etc... Because there are two particular shapes whose creation must be avoided, as once created they make it impossible to fill up the grid entirely, and so my logic must make sure that doesn't happen, which leads to the performance issues.
My code is far too long to post here, but essentially what it does is:
Go through each 'open tile' (tiles that are not in rooms nor that are a corridor), find the maximum size it can be, then
for loop through that size's x and y, see if a room at that x and y would create any of the aforementioned 'illegal' shapes, and if not, add this open tile and this open tile's size to an array of possible sizes and size positions.
I then choose a random size (more or less) from the list, and then create a room there.
Here is an example picture (though some seeds are better than this one) of what my algorithm results in:
Looking all over the internet I haven't been able to find an algorithm that fits my needs - mainly in the 'no corridors going through entire grid' issue. (This issue is present in the picture I attached due to the smallness of n=12, the larger the grid, the less likely this occurs with my code - the issue is there are some algorithms, like what I am calling the 'recursive' method - ~halving all sectors that are larger than minimum size until done, which will always have at least one, no matter how large, ie...)
(n=64 with recursive method, minSize = 2, maxSize = 4)