0
\$\begingroup\$

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:

enter image description here

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)

enter image description here

\$\endgroup\$
6
  • \$\begingroup\$ Could you fix the problem by detecting the long corridors and then blocking them? \$\endgroup\$ Commented Jan 5, 2018 at 9:12
  • \$\begingroup\$ That's not possible with how the logic for recursive sectioning works - it has to go straight through each sector. \$\endgroup\$ Commented Jan 5, 2018 at 9:41
  • \$\begingroup\$ I mean as another process at the end \$\endgroup\$ Commented Jan 5, 2018 at 9:42
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Jan 5, 2018 at 10:18
  • \$\begingroup\$ Is it ok if the corridor is half the length of the map? Or does it need to be a certain size? \$\endgroup\$ Commented Jan 5, 2018 at 10:28

1 Answer 1

Reset to default
1
\$\begingroup\$

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.

enter image description here

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.

\$\endgroup\$
3
  • \$\begingroup\$ Yes I had considered trying starting from, or indeed recursively splitting into, a centred piece with perpendicular lines from each of its vertexes (though your comment did cement this as a solid idea) - the main issue present in this, and any other recursive method, is that there is no direct way for me to preplace the necessary rooms. There is probably some way to track all current sector sizes and compare them against the sizes of each required preplacement room, however this still doesn't seem like the optimal method given that? \$\endgroup\$ Commented Jan 5, 2018 at 15:46
  • \$\begingroup\$ Or perhaps you can think of some easy way to include preplacement with a recursive method? PS. Is there some sort of site or thread or something that discusses these kinds of recursive methods that you know of? I haven't been able to find one. \$\endgroup\$ Commented Jan 5, 2018 at 15:46
  • \$\begingroup\$ Yeah after thinking about this idea I still can't come up with a solid way to preplace rooms \$\endgroup\$ Commented Jan 8, 2018 at 9:23

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.