by Oscar Cooke-Abbott
Last Updated January 05, 2018 06:13 AM

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)

I think the best approach to solving this problem is using a recursive method. Starting large and splitting into smaller chunks is going to guarantee that you have all your space filled with rooms (no 2x2 corridors). Also, if you have a problem segment, you can just regenerate that small part of the map.

If you only use bisection of the rectangles you will obviously get corridors that run through the map. You should try to find another way to recursively split the rectangles.

For example, splitting each rectangle into 5 might work better. You could apply your existing algorithm or another recursive algorithm to fit rooms into each larger rectangle.

This approach avoids problems but doesn't guarantee a solution. However, if a corridor is found that is too long, it can be fixed by reshaping just the rectangles that it passes through.

- ServerfaultXchanger
- SuperuserXchanger
- UbuntuXchanger
- WebappsXchanger
- WebmastersXchanger
- ProgrammersXchanger
- DbaXchanger
- DrupalXchanger
- WordpressXchanger
- MagentoXchanger
- JoomlaXchanger
- AndroidXchanger
- AppleXchanger
- GameXchanger
- GamingXchanger
- BlenderXchanger
- UxXchanger
- CookingXchanger
- PhotoXchanger
- StatsXchanger
- MathXchanger
- DiyXchanger
- GisXchanger
- TexXchanger
- MetaXchanger
- ElectronicsXchanger
- StackoverflowXchanger
- BitcoinXchanger
- EthereumXcanger