Posted: 11/19/09 A technique for using sets in order to intelligently layout a set of randomly selected rooms.

This entry was originally published November 19, 2009 as part of this website's Blind Mapmaker section. This section is being discontinued and any noteworthy articles will be absorbed into the Three Hundred.

Map From Indy's Desktop Adventures.

I'm going to talk a bit about creating a map from pre-designed rooms, generating Zelda-like dungeons or something like this map from the Desktop Adventures series. I call it card layout because the effect is essentially to grab a card randomly from a deck and then placing the card next to an existing spot. I also call it card layout because several boardgames, most noticeably the Zombies!!! series of games from Twilight Creations.

Example 1-1.

The basic premise is relatively straight forward. You place a room, then keep a set of all rooms that are neighbor to it. When it comes time to place the next room, you select from the set of neighbors and place the room there, then updating the neighbor set to remove that location and add its neighbors.

To sum up: keep a set of neighbors and select new room positions from it, and only it.

Why use a set of neighbors rather than the more traditional method of randomly selecting a cell and then picking an empty side to dig a new room out? The positions in the set are guaranteed to be valid. At the very least, you will never need to guess-and-test or back up your work when you hit a dead end.

Example 1-2: Random.

Assuming you use a purely random approach to selecting rooms, you are going to end up with a pretty nonsensical map most of the time. You'll have holes in the middle of it and random rooms just sticking out of the side for no apparent reason. A better approach would be to apply some sort of filter to the potential rooms to prioritize which potential cells are selected.

Example 1-3: Prioritized Based On Borders

In this map, the potential cells are ordered based on the number of rooms they border. In a very linear fashion, the game fills in whatever cells have the most borders first. So a cell bordered by four rooms (a hole in the map) would be filled in first, then all cells bordered by three rooms (a U-shape), then all cells bordered by two rooms (an L-shape), and finally, any rooms bordered only by one room.

The effect of this is that it will create a rectangle. Basically, any time you dig a new room, it will create at least one or two L-shaped holes. It is then the process' single minded mission to fill those in, essentially stopping once it has filled out an entire row or column. A better approach would be something not quite as strict (though having the ability to create rectangular zones is not undesirable).

Example 1-4: Some Prioritization

The final approach is to prioritize each potential cell by the number of borders, filling in the major holes but leaving L-shapes alone. What happens is that the holes and U-shapes are filled in, leaving a solid, blob-like shape. This shape is much preferable for continents and landmasses. And, of course, you can create tendencies by using percentages for potential cells. For instance, a 90% chance a hole will be filled but only a 70% chance a U-shape will be.

I'm sure there are many simple ways with which you can control how a zone is laid out. I've only done the most basic by prioritizing based on the number of border rooms. You could easily give preference to cells closer to the zone's center, or priority to rooms in a particular vector away from the zone's center (i.e. grow the map east). You could make a zone by placing down pre-built room sections (i.e. Tetris-shaped blocks of rooms). Or, in addition to how many borders a cell has, you could keep a percentage of how likely that room is to be filled, so of all the U-shaped holes, you would then order them according to build weight. Then overtime a cell isn't picked, it's percentage goes up so that it is more likely to be picked next time.

Really, there are a thousand ways to define the building shape. I haven't even scratched the surface. I just wanted to point out that room placement doesn't have to be strictly random. You can weight it in various ways to exact some control over it. But what I really wanted to talk about was creating multiple zones, connected together, and how these zones can be locked. It's a fundamental piece of growing the Desktop Adventure premise into something more interesting.

Example 2-1: Multiple Zones

The ultimate destination here is to create a world made from many zones. For instance, one zone could be forest themed while another snow themed. If you were using this layout for a dungeon, perhaps the only difference between zones would be that zone B is behind a locked door which needs a key from zone A. You'll notice that the zones are connected by a bridge, which I'm primarily using as a locked door. However, zones don't have to use a bridge. I'll talk about various zone types a little later on. Right now, I'm going to use the bridge as my primary example.

Example 2-2.

First, you start with a zone that you consider to be finished. You should have a set of rooms and a set of neighboring cells.

Example 2-3.

The next step is to build a bridge jutting out from the zone and invalidating all the previous neighbor cells.

A bridge is simply a room which is built between two zones. It is built out of the first zone from a cell with only one border. Then, the two neighboring cells that aren't rooms are made invalid (nothing can be built there). You don't want the new zone to touch the bridge on more than one face. Finally, opposite to that room, the first room of the new zone is built with it's own new set of neighboring potential cells.

To invalidate the potential cells of the first zone, just add them to a set of invalidated cells - or just consider that set to be invalid once the zone is "locked" (the reason for keeping the zones' invalid border cells separate will be more apparent when I discuss different zone connections below).

Note: This approach assumes it is okay for two zones to touch at corners but not faces. If this is not okay, do a quick pass over every room in a zone and attempt to add all eight neighboring cells to the invalid set, assuming the cells are A) not rooms and B) not already in the set.

Example 2-4.

Next, build the new zone as before. The one change is that when selecting border cells, first check to see if that cell is already contained in an invalid set somewhere. If it is, then don't add it to the potential cell set. This will prevent the new zone from growing into previous zones, thus maintaining a nice little border between them.

Example 2-5.

Finally, start the process all over again. Build a bridge and invalidate the neighbor cells.

Example 2-7.

When all is said and done, you should have a bunch of zones connected by bridges. You can combine this with [#004 - Environment Tree] to control the locked doors on each bridge, thereby controlling the flow from one zone to the next. For instance, you must complete the Lava Dungeon in zone 1 before you can cross the bridge to zone 2.

Before I end this entry, I wanted to briefly go over different types of zone connections and how you can emulate them using this system of sets.

Example 3-1: Bridged Zones.

Bridges, of course, you know. It is probably my preferred zone connection. You can lock the bridges to control the flow between zones, but just as importantly, it provides a small bit of comfort when traveling between two distinct zones. For instance, a single room can make the jump between a desert zone and a snow zone a little more comfortable. It could make the process of going from an outdoor forest into a cave easier to digest if the bridge was simply the entrance to the cave. And so on.

Example 3-2: Tumor Zones.

Next, there are tumor zones. They are zones that grow as normal, but are allowed to touch previous zones. Rather than invalidating neighbor cells and building a bridge, all you do is dig a new room to start the new zone and build it normally - allowing for potential neighbor cells to be shared between zones.

Example 3-3: Multi-Tumor Zones.

The multi-tumor zone is one which grows randomly off a previous zone. It's very disjointed, but if you had a dungeon where there wasn't a huge difference in zone themes and simply wanted to lock off portions of the map to a singular key (i.e. the blue key) this approach might be applicable. To build, simply copy the potential neighbor cell set from zone A to zone B and build normally.

Example 3-2: Island Zones.

Finally, we have islands. These are zone that do not connect directly at all. Using this approach would be best with some sort of travel ability between zones. For instance, you could make all non-zone cells into water that is traversable via a boat, then randomly select an edge cell from each zone to be a port. The problem with this approach is that you can't lock zones from each other very easily. Once you have a boat, each zone is now accessible unless you add something else to the mix.

The really great thing about all this is that it is really simple to mix and match zone connections. If you wanted a world which had bridges, tumors, and islands, you could. The distinction between how these different zones are built are entirely based on what you do at the very beginning of a new zone. Depending on where the first new room is built and what rooms are potential cells, each of these zone connections can be used independently or together with the other types. For instance, you could have several islands made of multiple zones, bother tumored and bridged - and as long as you are paying attention, you can intelligently lock the flow between zones too!