Posted: Oct 16, 2012 Use sets to intelligently select multi-room areas to fill oddly shaped regions.

Fig 163.1 - Golden Axe Warrior's Overworld.

The above image is the overworld map for the Sega Master System game, Golden Axe Warrior (a fairly decent Zelda clone for the time). If you stare at it long enough, you should notice a few important things. The first is that the world is obviously broken up into different themed zones, and that each of these zones are made up of individual screen-sized rooms. But if you look harder, you'll notice that Golden Axe Warrior actually operates at a level somewhere in between - areas that are larger than a single room, but smaller than an entire zone.

Fig 163.2.

Here is a section of that overworld map taken from the bottom middle. I've taken a few seconds to show the logical division between these areas made up of multiple rooms. There are several shapes, including double-wide rooms, double-high rooms, and a 2x2 sized room. This distinction of multi-room areas is important when you factor in lock-key puzzles which must function at the entrances between the areas, not the rooms. Similarly, some leaf puzzles, like navigating a maze, may take up multiple rooms and should be considered as one entity rather than a bunch of little ones.

The typical approach that procedural generation takes is to brute force it, using a stack to allow for returning to previous states after you've hit a dead end. You pick a random room and try it. If it works, you move on to the next room. If you try a room and it doesn't work, try a different room until you find one that does. If that doesn't work, pop the current state off the stack and return to before the previous room, and try placing a different one down instead. Potentially, you could place hundreds of rooms, thousands of times, and still never create a workable solution except by chance.

I take the position that it is better to make a few smart decisions than lucking into success through a billion dumb ones. Since memory is cheap, we can keep track of a lot of information that will allow us to make smart decisions quickly. This procedural generation entry is about taking an oddly shaped zone and filling it in with a workable set of multi-room regions without guessing and testing.

Fig 163.3.

The process begins with a pre-created zone skeleton, not unlike what was used in [#159 - PGC: Puzzle Tree Building]. We're going to fill in the rooms of this zone such that every space in the skeleton is filled with a room (everything is colored, no coloring outside the lines).

The benefit of doing it this way is that we can build the zone skeleton as part of the overworld building process, where we mostly care about the size and shape of zones, and how they connect to neighboring zones, without really caring about what will go on inside the zone.

Now, for every single slot in the skeleton, create a set containing all the rooms that could potentially exist that would include that slot. So, if there are 16 slots in the skeleton, there will be 16 sets. It should also be noted that many of these potential rooms will exist in multiple sets.

Fig 163.4.

Taking the blue slot for example, there are a total of eight different potential rooms that can occupy that slot (if you assume a max of 2x2). All but one of them require multiple slots, and thus, will exist in multiple sets.

Fig 163.5.

Here is the set of potential candidates for the square directly to the right of the blue square. Due to the configuration of the skeleton, there are only six candidates. Of particular interest is that three of these candidates are shared with the blue set. I've gone ahead and colored these blue to highlight this crucial point.

Fig 163.6.

Okay, let's say you pick one of the rooms from the blue set - the 2x2 room going southwest. Now, invalidate every room in the blue set. In other words, the blue set contained every possible room that included the blue slot. Since the blue slot is filled, every room in that set can no longer be made.

What's more, you must invalidate the sets for EVERY slot that becomes occupied. In this example, you will invalidate the sets for each of the four occupied slots. Those slots are filled and thus all the potential rooms that include those slots are invalid.

Fig 163.7.

Invalidating a set of rooms is simply a matter of adding the contents of the set to a special "invalid" set. Then, before you do any operations on a new set, simple subtract the invalid set from the current one. For instance, the yellow set contains 6 rooms. Before you pick a room from the yellow set, you remove the invalidated rooms from the set, leaving you with just three candidates left.

However, and this is important, the remaining three candidates are ALL valid room locations. Through this process of selecting a candidate, then invalidating the rest of the candidates that use those slots, you continually pare down the sets to only the valid selections. This means that you can pick any room from the remaining sets and be guaranteed a correct choice.

Since one-slot sized rooms are unique to each slot's set, you should never have to deal with empty sets (which indicate that there are no valid rooms for that slot). However, if you change the process in certain ways, like not allowing single-slot rooms, you could end up with this situation. You can avoid it by prioritizing slots that have the fewest candidates in their sets, and avoiding choices which would result in a slot having an empty set.

Still, if you are too specialized, you may end up with zones that cannot be filled easily and you'll either have to go back to guess and test, or being more deliberate about which rooms you select from each set.

Fig 163.8.

But if you just take the basic approach, you'll end up with a valid configuration of rooms, selected on the first try. The next step is to drill pathways between each room. Might I suggest [#004 - Environment Tree] as a way of maintaining structure while doing this?

Here's a quick run down of the steps in list form. Everybody loves list form:

1. For each slot, create a set of all candidates which include that slot.

1.1 These candidates will be shared amongst the sets of all slots it is involved in.

1.2 Control the structure by invalidating candidates (see below).

2. Pick a slot, then pick a candidate from its set.

3. Invalidate all sets for each slot a candidate touches.

4. Repeat steps 2-3 until done.

So, why is this strategy better than guessing and testing? The first way is that it doesn't matter what order you place the rooms. If you want to ensure that a specific size or shape is there, just place that piece first. For instance, say you want a throne room that is 3 wide by 2 tall. That's going to be very difficult to fit in naturally. Instead of putting it down as you come to it, place that room first and let the algorithm fill in the blanks.

The second way this technique is superior is the fact that this method is self correcting. Since the sets for each slot only contain valid candidates, you can change the process significantly just by changing the definition of valid. For instance, you can decide how large and what shape each candidate can be. If you want only large rooms or only small rooms or only rooms shaped like those z-shaped Tetris pieces, this technique will accommodate it without change.

Fig 163.9.

Perhaps just as interesting is that you can define which rooms are invalid before you begin. Say you want to force some structure on the region by providing blocked walls that rooms can not be built over, like in the image above. This is simply a matter of throwing away any room candidate which crosses these boundaries. Again, you do not have to change the process beyond throwing away a few candidates. The process will automatically build a region of rooms which adheres to that floor plan. Use the walls when drilling paths between rooms and there you go.

Fig 163.10.

What about if you want to put a midboss in the region which locks off one half of the region from the other? This is simply a matter of "coloring" the two regions and throwing away any candidates which occupy more than one region (did someone say [#004 - Environment Tree]?). Then when drilling pathways, never drill a path between two different colored regions, except to connect to the midboss's room in the middle.

It doesn't really matter what approach you use, the process remains simple.