# Random tile-based floor plan generation with enclosed rooms

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:

1. The outside ring (where x = 1 or n | y = 1 or n) must be corridor tiles (obviously easy)

2. All rooms must be entirely surrounded by corridor tiles

3. In no place may there be a 2x2 grid of corridor tiles (so corridors are all 1 tile thick)

4. 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.

5. Do not have any corridors that go all the way through the floor.

6. (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)

• Could you fix the problem by detecting the long corridors and then blocking them? – Jay Jan 5 '18 at 9:12
• That's not possible with how the logic for recursive sectioning works - it has to go straight through each sector. – Oscar Cooke-Abbott Jan 5 '18 at 9:41
• I mean as another process at the end – Jay Jan 5 '18 at 9:42
• The problem with that is how are they supposed to be blocked? I can't just extend one room in front of them - that would connect two rooms - and I can't necesarilly just push part of the corridor over because the rooms on either side may not be deep enough nor even of the same corridor-facing side length. This is where my issues sprout from - I need an algorithm that just naturally does not create long corridors. – Oscar Cooke-Abbott Jan 5 '18 at 10:18
• Is it ok if the corridor is half the length of the map? Or does it need to be a certain size? – Jay Jan 5 '18 at 10:28