The Blind Mapmaker :: Sets For Room Layout Implemented

Sets For Room Layout Implemented

I have actually implemented the process detailed in the previous article on using sets for Zelda over world map layout. The above is a screenshot of the test program in action. The process is as follows:

1. Create a potential room for every square or group of squares on the map.

This one was easy. Just start at the top left square and iterate through them all creating rooms. For each square, attempt to create every permutation of room from 1 x 1 up to the max room size (in this case 4 x 4 squares). If a room can not be created (goes off the map, overlaps an invalid region), ignore it.

2. For each square, keep a set of all potential rooms that overlap it.

This means that for a 7 x 7 map, there are a total of 49 sets, one for each square. Each set contains every potential room that includes that particular square. This means that a room that is two squares wide will be included in the sets for both the left square and the right square.

3. Keep sets for selected and discarded rooms.

As you pick rooms from the bunch, you will ultimately decide on one particular room and the others in that square will become invalid. Since rooms can overlap multiple squares, the actual set of candidates for that particular square is equal to that square's set MINUS both the set of selected and discarded rooms, leaving only potential candidates. Once you have selected a room from a particular square, by definition, all the OTHER rooms that overlap that square are invalid.

4. For each square, randomly select a room from the set of candidates.

This selected room becomes the official room and the rest because invalid. Invalidate all the rooms in all the squares that the selected room overlaps. The end result will be that the set of candidates for each square will shrink as you invalidate (and thus remove) each unselected room.

And that's basically it. It's actually a pretty simple process.

And Why?

It's not a complicated procedure but it does require a serious amount of sets. Even if you don't bother creating sets for the invalid regions, you are still manipulating a lot of sets. So why use this approach instead of creating an algorithm that, for example, just randomly digs out rooms?

The first reason is that this algorithm does not change in the least when using odd shaped regions. For this prototype, I just kept a simple 7 x 7 array of integers. If it is a 0, no rooms are built there. If it is a 1, a room will end up being built there. The only change to the code I had to make was in the part where I queried whether a room could be built at a particular square. If the region map had a 0, it returned false.

I then amended this rule by having a region id of 2, which meant that a specific type of room could be built on that square. In this case, only 1x1 blue rooms can be built on 2 squares. These squares work as locks, such that no other type of room can overlap that square. These could easily be used to separate regions from each other.

Though the region mask is not built procedurally, it easily could be. It has a lot of control over how the rooms are selected and built. Providing a different region mask will create a differently shaped region. So, rather than the region shape being defined by the algorithm, the algorithm is defined by the region shape. Might not seem like a big difference, but it is the difference between top down and bottom up design. In one, the region shape emerges from the selection of rooms, which means you have no control of it. In the other, the selection of rooms emerge from the shape of the region, which means you can design from the big picture down to the details.

Another advantage is that you can control which rooms are selected. In this case, I simply kept a set of all the 1 x 1 potential rooms separately. Then, when selecting a room for each square, there's a 60% chance that I will intersect that set with the potential candidates. This basically just means that there is a 60% chance that each room selection will result in a small room. But you can take it further.

For example, say you have three very specific rooms you want to add to the map. Let's say they are a dungeon entrance (1x1) and a large town (2x2). You can simply add these two specific locations to every spot on the map they could potentially be placed. They will become a candidate for selection, and once selected, they will automatically be removed from selection for all other squares. You can weight their appearance like I did with the small rooms above.

But more likely, points of interest like this are going to be major features of the generation algorithm. You are going to place them first and you want the rest of the rooms to be built around them. That will work fine too. If the rooms are placed before you create all those potential rooms, you can add a line to the validity check that returns FALSE in the case of overlapping with a pre-existing room. That's all you need. The rooms will be built around these locations without overlapping or other design issues. They become features of the region mask, just like the blue room locks as demonstrated.

Using sets is a really powerful way make intelligent decisions. It limits the domain of randomness from anything is possible to, I only want this feature and that one. It's expensive in terms of creating a lot of sets and populating them with dozens of rooms each, and it is possible that this approach is not as speedy as a bottom up approach. But my goal is to create a Zelda over world from the top down - to have ultimate control in a very reliable, simple, and easy way. I can then transfer that control to the player in a way that is understandable without having a math degree.

Drilling Holes

If you'll notice, my test program does not yet have doorways drilled between the various rooms. At some point, I'm going to want to build an environment tree of the various rooms, which I can then exploit into perfecting the flow through the world. However, I haven't create the algorithm to do that just yet. I have to save something for the next article.