User:Librarian/How Dungeons Are Generated

Other Related Pages

Some Dungeons I Analysed

Overview

Every floor of a dungeon has a foyer (entrance room), and either a boss room and exit/treasure room, or an exit room leading to the next floor. These are standard. Once we document the spawns in the boss room and the treasures in the treasure room, these need no further analysis. This page is about explaining what happens for the rooms between the foyer and the boss room or exit room. For single floor dungeons, it is about explaining what happens between the foyer and the boss room.

Each floor of a dungeon is divided into zones. For example, Alby Basic has 4 zones, Ciar Advanced has 9 zones and Rabbie Basic has 5 zones.

Each zone has its own set of spawn patterns and its own set of structures.

A structure defines the sequence of rooms types. For example, zone 1 of Alby Basic is particularly simple, having only 1 possible structure which is two rooms long.

Room 1	Trapped chest room	Obtain orange key.
Room 2	Empty. Exit closed.	Use orange key to exit

A spawn pattern defines the monsters that will be encountered for a room type. For example, for Alby Basic zone 1, the trapped chest room has two possible spawn patterns, either 4 blue wolf or 4 giant bat.

To generate the contents of a zone, the game first randomly generates a structure for that zone. It is not an equally likely selection. Some structures are far more likely to occur than others. Then for each room in the chosen structure that needs monsters, the monsters are selected. For example, if the structure chosen for Zone 3 contains a trapped chest room, a random selection is made from the list of Zone 3 Trapped Chest Room Spawn Patterns. Once these steps have been completed for all zones, a random path generator is used to generate a map with the required number of rooms.

Room Types

Sometimes a section of corridor can contain monsters, or other items of interest such as a fountain or Tiro. When that happens, think of that block of corridor as being a room with an open exit.

Trapped Chest Room - 1 wave. Room contains 1 chest. Opening it closes all the room's exits and spawns 1 wave of monsters.
Trapped Chest Room - 3 waves. As above, but spawns 3 waves of monsters.
- Most zones have a chance of using either or both of the above types, but some zones only allow the first type, so I am regarding them as two distinct room types.
Pre-deployed Room. Room contains only monsters. Exit is closed.
Mimic Corrider Cluster. Exit is closed. Room contains a treasure chest, 3 to 6 mimics that are identical in appearance to the treasure chest, and usually some other monsters. The treasure chest contains a key which can be used to open a door in a later room.
Mimic Room - Exit open: Similar to a Mimic Corridor, but occurring in a normal room rather than in a corridor.
Mimic Room - Exit closed: Similar to above, but exit is closed. In Ulaid Dungeons, I haven't yet seen a run where the key obtained in the mimic room opens the exit to that mimic room. Instead, a key obtained in an earlier room opens the exit to the mimic room and the key obtained in the mimic room opens an exit to a later room.
4-Switch Room: In Ulaid Dungeons, the switches are coloured orbs. The exit is closed. 3 of the switches summon a wave of monsters. The 4th switch opens the exit and deactivates the other 3 switches. Placement of the 4th switch is randomised.
Herb Room - Exit open: Contains 3 random herb patches. Exit is open.
Herb Room - Exit closed: As above, except that a key obtained in an earlier room is required to open exit.
Tiro Room - Exit open: Room contains only Tiro.
Tiro Room - Exit closed: Room contains only Tiro
Tiro Corridor: Corridor contains only Tiro.
Fountain Room - Exit open: Room contains only a Fountain.
Fountain Room - Exit closed: Room contains only a Fountain.
Fountain Corridor: Corridor contains only a Fountain.
Empty Room - Exit Closed: The exit is opened by a key obtained in an earlier room.
Empty Room - Exit open: These rooms only occur in a zone that may include a fountain, but no fountain was encountered on the run that produced the empty room. This probably indicates that there is an underlying room type of "Possible Fountain Room - Exit open" which has a probability of spawing a fountain. When the fountain fails to spawn, we see it as an empty room with an open exit and which thus seems to serve no purpose.
Pre-deployed Room + Tiro: Puts Tiro in a Pre-deployed room. Exit is always closed.
Pre-deployed Room + Fountain: Puts a fountain in a Pre-deployed room. Exit is always closed.

Iria dungeons and Ulaid Castle Dungeons introduce some extra room types not mentioned above. So far my attempts to determine how dungeons are generated has concentrated on the easier Iria dungeons.

Spawn Patterns

Trapped Chest Rooms: It seems the 1 wave patterns are the possible 3rd waves from the 3 wave patterns. (Thanks to Lint for that discovery.)

Mimic Corridor Clusters and Mimic Rooms: While very similar, it appears that in some zones the set of possible spawn patterns for a Mimic Corridor Cluster is different to those for Mimic Rooms. My current suspicion is that the difference arises in the rare room type "Mimic Room - Exit Closed", and that the more common "Mimic Room - Exit Open" uses the same set of spawn patterns as Mimic Corridor Clusters. I stress that I do not yet have enough data to claim that this suspicion is proved beyond reasonable doubt, so I'm treating these as 3 different room types when collecting spawn pattern data.

There is surprisingly little overlap between spawn patterns for different zones. That is, in most cases the designers have gone to a lot of effort to write slightly different spawn patterns for each zone of a dungeon. However, it was noted above that for trapped chest rooms, the 1-wave span patterns are the possible 3rd waves from the 3-wave spawn patterns. While the designers have usually ensured the 3-wave spawn patterns are different for every zone, sometimes they share a common 3rd wave, so it can appear that 1-wave spawn patterns have been shared across several zones.

Where a zone has more than one possible spawn pattern for a particular room type, they do NOT have to be equally likely. That is, it seems the spawn pattern data must also include a probability of occurrence.

Keys

In a trapped chest room, one of the monsters in the final wave has a key. When that monster is killed all players in the dungeon are awarded a copy of that key. When the key is used to open a subsequent door which has a keyhole the same colour as the key, the key disappears from all players' inventories.

In a 4-switch room the exit door to the room is closed and has a coloured keyhole. In Ulaid dungeons, where the switches are orbs, the orbs are the same colour as the keyhole. This becomes clearer after you hit an orb which makes it light up. While you never see a key enter or leave your key inventory in a 4-switch room, the game regards the 4-switch room as having a key of the same colour as the keyhole and orbs. This issue impacts the colours used for other keys in the zone.

Keys cannot overlap zones. If a key is obtained in zone 2, it must be used to open the exit of one of the rooms within zone 2.

Each colour key only ever occurs once in a zone. Say a zone has 4 rooms. Say a key is obtained in room 1 and used to exit room 2. Then a second key is obtained in room 3 and used to exit room 4. It would seem logical that these two keys could both be orange since the first key is used before the second is obtained, so there's no opportunity to confuse them. But the game does NOT do this. Instead it will use an orange key and a green key.

With the exception of the final zone of a floor, if a zone has only one key, it will be orange. If two keys: orange and green. If three keys: orange, green and blue. If you think that you have found a zone that has only one key and it was green, check whether the zone also included a 4-switch room with orange orbs and keyhole. (Well - since you've probably already opened the exit door, you can no longer see the keyhole, so check the orbs.)

The final zone behaves differently. If it has only one key, it will be the red boss key. If it has two keys: well I haven't actually seen that happen yet, but if it's possible I'm going to guess they'll be the red boss key and an orange key.

The above properties can be sufficient to determine some of the zone break points in a particular run of a dungeon. Where it still unclear which zone a room belongs to, comparing the spawn patterns to other runs of the dungeon may resolve the issue.

Room Blocks

Keys are always used within the zone where they are obtained. Thus a trapped chest room can never appear alone; it must appear with a second room that uses the key that was obtained in the trapped chest room. I call this pair of rooms a block. So far I have encountered blocks of 1, 2 and 3 rooms. A zone may consist of a single block, but it can also contain 2 or more blocks merged together. The next section deals with the merging process in more detail.

A common 2-room block involves a trapped chest room that provides a key, followed by an empty room with a locked door that uses the key. In the trapped chest room, opening the trapped chest triggers either one wave of mobs or three consecutive waves of mobs. Should we treat the 2 different wave options as two different blocks, or is there a single block that includes a random selection between one or three waves?

The first zone of Alby Basic has a trapped chest room that only ever produces 1 wave of mobs, so to describe that we need a block that includes a trapped chest room that only ever gives one wave of mobs. So initially I went the route of defining two different blocks, one with a trapped chest room that always produces one wave and another with a trapped chest room that always produces three waves. But when I did this I found that, apart from the rare exceptions like zone 1 of Alby Basic, the list of blocks appearing in each zone would include duplicates for the 1 and 3 wave versions. For example, if a zone used used a one wave trapped chest room giving a key that would be used to open a door to exit a herb room, other runs would find a corresponding block with 3 waves instead of one. In addition, for the blocks where I had sufficient data for reliable statistical tests, it seems that the 1 and 3 wave versions are equally likely. So in the end it looks like the smallest set of blocks that accurately describes what we see involves:

A special one-off block just to deal with the weird cases like Alby Basic zone 1, which always gives 1 wave of mobs.
Blocks for all situations where trapped chests occur, where a random selection will be made to give either 1 or 3 waves.

This means that in the list of blocks given below, there are some sizeable gaps in the numbering where I'd defined a bunch of blocks I ended up not using.

I've given each Room Block I've seen a unique 3 digit code. The first digit indicates the number of rooms in the block. The numbers are not always consecutive. In places I've left gaps to enable grouping of similar blocks when new variations are found.

1 Room Blocks

101	4-Switch Room. Get and use notional key.
111	Herb Room – Exit open
112	Tiro Room – Exit open
113	Tiro Corridor
114	Fountain Room – Exit open
115	Fountain Corridor
116	Empty Room – Exit open

Block 101 is in the only 1-room block in which the exit is closed. This becomes important in the next section.

2 Room Blocks

With the exception of block 201, all Trapped Chest rooms randomly select whether to use 1 or 3 waves of mobs. So far, in all the cases I've analysed, it seems these two options are equally likely.

201	Trapped Chest Room – Always 1 wave of mobs. Get key.
	Empty – Exit closed. Use key
221	Trapped Chest Room. Get key.
	Empty – Exit closed. Use key
222	Trapped Chest Room. Get key.
	Herb Room – Exit closed. Use key.
223	Trapped Chest Room. Get key.
	Tiro Room – Exit closed. Use key.
224	Trapped Chest Room. Get key.
	Fountain Room – Exit closed
231	Mimic Room – Exit open. Get key.
	Pre-deployed – Exit closed. Use key.
232	Mimic Room - Exit open. Get key.
	Herb + Pre-deployed – Exit closed. Use key
233	Mimic Room – Exit open. Get key.
	Pre-deployed + Fountain – Exit closed. Use key.
241	Mimic Corridor Cluster. Get key.
	Pre-deployed – Exit closed. Use key.
242	Mimic Corridor Cluster. Get key.
	Herb + Pre-deployed – Exit closed. Use key
243	Mimic Corridor Cluster. Get key.
	Pre-deployed + Fountain Room – Exit closed. Use key.

It is possible that blocks 231 and 241 are in fact a single block, with the game making a random selection to determine whether to put the mobs in a room or in a corridor. These rooms are far less common than rooms involving trapped chests, so my data set isn't yet large enough to make a reliable call on this. So far, if I use statistical tests to investigate whether these two options are equally likely, the tests are not providing any evidence to reject that model, but the sample sizes are small enough that the tests don't have great distinguishing power.

If after analysing more data I decide to merge 231 and 241, it would also be logical to merge 232 with 242 and 233 with 243. Those last 4 blocks are exceedingly rare, so I don't have any way to decide on them in isolation from 231 and 241.

3-Room Blocks

301	Trapped Chest Room. Get key 1.
	Mimic Room – Exit closed. Get key 2. Use key 1.
	Pre-deployed – Exit closed. Use key 2.
311	Mimic Room – Exit open. Get key 1.
	Mimic Room – Exit closed. Get key 2. Use key 1.
	Pre-deployed – Exit closed. Use key 2.
321	Mimic Corridor Cluster. Get key 1.
	Mimic Room – Exit closed. Get key 2. Use key 1.
	Pre-deployed – Exit closed. Use key 2.

Melding Room Blocks

Many zones contain 2 or more room blocks. In the dungeons for which I've collected the most data, melding 2 zones is far more common than melding 3 or more, so my explanations are going to concentrate on melding 2 zones. I don't yet have enough data to give firm guesses about precise behaviour when 3 zones are merged.

Consider a zone that melds two room blocks: the 1-room 101 room block and the 2-room 201 room block. The result is a 3 room zone. The room from 101 could go into any of the 3 positions. The 2 rooms from 201 must go into the other 2 positions and in doing so they must retain their order, because we have to obtain the key before we use it. This gives 3 possible room sequences for the zone.

Sequence 1	Sequence 2	Sequence 3
4-Switch Room. Get and use notional key 1.	Trapped Chest Room – 1 wave. Get key 2.	Trapped Chest Room – 1 wave. Get key 2.
Trapped Chest Room – 1 wave. Get key 2.	4-Switch Room. Get and use notional key 1.	Empty – Exit closed. Use key 2.
Empty – Exit closed. Use key 2.	Empty – Exit closed. Use key 2.	4-Switch Room. Get and use notional key 1.

Based on data collected from the game, all 3 sequences do occur and they appear to be equally likely to occur.

The final step is to assign orange and green to key 1 and key 2. This can be done in two ways, so each of the above 3 sequences generates two sequences once key colours are assigned, giving 6 sequences. The two ways of assigning key colours seem to be equally likely, so the 6 final sequences allowing for key colour are equally likely.

Now consider a zone that melds two room blocks: the 1-room 111 room block and the 2-room 201 room block. Surprisingly, this does not give 3 sequences as in the previous example. It gives only two sequences.

Sequence 1	Sequence 2
Herb Room – Exit open	Trapped Chest Room – 1 wave. Get key.
Trapped Chest Room – 1 wave. Get key.	Herb Room – Exit open
Empty – Exit closed. Use key.	Empty – Exit closed. Use key.

These correspond to the first two sequences from the previous example. We don't get a sequence where the Herb Room occurs last. The two sequences appear to be equally likely. There is only one key, so it will be orange.

So why do these two examples behave differently? After comparing many scenarios involving different room blocks, my conclusion is that there is a constraint in the melding process that ensures that the last room in a zone must have a closed exit. In the first of the above two examples, the 4-switch room has a closed exit, so it could be the last room in the 3-room zone. In the second example the herb room had an open exit, so it was not allowed to be the 3rd room in the zone.

If you examine the list of 2-room blocks and 3-room blocks given earlier, their final room always has a closed exit, so that final room is eligible to be the last room of a zone. But amongst the 1-room blocks, only the 4-switch room has a closed exit, allowing it to be the last room in a zone. All the other 1-room blocks have open exits, so they cannot be the last room in a zone. (At least that's the case so far. I've deliberately left a large gap in the number of the 1-room blocks in case I find other 1-room blocks that do have a closed exit.)

Another concequence of this is that the only way a zone can contain only 1 room is if that room is a 4-switch room. (Such zones do exist.) All the other 1-room blocks can never be alone in a zone. They can only occur when melded with at least one other room block which can supply a final room with a closed exit.

It is possible for a zone to use more than one copy of a single room block. So there can be a 4-room zone consisting of:

2 melded copies of 202.
2 copies 111 and one copy of 201. Neither of the herb rooms could be in the last position.

Maps

The final step is to place the rooms onto the map.

This is a two-step process.

The boss room is fixed in the middle of the map, with the exit/treasure room to the North. The final room of the final zone is placed immediately to the South of the boss room. From that room, a random path of sufficient length is generated. (Yes - that's vague. I know random path algorithms exist, but I don't understand how they work.) The path has to be at least long enough to contain all the remaining rooms including the entrance room. Each zone has a section of the path reserved for it. The section for a zone will have at least enough places for the maximum possible number of room for that zone, and maybe considerabl spare space.
The rooms are then placed on their section of that path. The last room for the zone is always places in the last possible position in that zone. The other rooms at randomly selected places along the path, but maintaining their order.

These two steps can be seen more clearly if you compare separate attempts at normal level Ulaid dungeons, where the drop item effects step 1, but not step 2. The following three maps show three different runs at Alby Normal using a drop item of 1 gold. As the 3 runs all used the same drop item, Step 1 was carried out in exactly the same way for all 3 runs, meaning that the path through the dungeon is identical for all 3 runs. The sections reserved for the 4 zones, shown by the red lines, are also identical for all 3 runs. However, step 2 is randomised between these runs, so the positions of the rooms within the zones can vary.

In Alby Normal, zone 1 is always 2 rooms. When the drop item is 1 gold, the random path generated has room for 4 rooms in zone 1, so the 2nd room is always in the 4th position and the first room is randomised into one of the first 3 positions. The above 3 images show all 3 possible positions for the first room.

Zones 2 and 3 can each be 3 or 4 rooms long, but in both cases the random path has only reserved 4 positions. This means that when the one of these zones is 4 rooms long, there is no spare space so all four reserved positions are used. When one of these zones has only 3 rooms, the 3rd room always goes into the 4th position and the other 2 rooms use 2 of the first three positions.

Zone 4 is always 2 rooms, but the section of the random path reserved for this zone has 7 positions. The 2nd room always goes in the last position, directly South of the boss room, and the first room can go into any of the other 6 positions.

If you run Alby Normal using some other drop item, Step 1 is performed differently to how it was performed for the above three maps. This means the random path selected will be different. The random path can even be a different length to that show above. You could also strike a random path that is the same length as those shown above, but the lengths of the four sections reserved for the four zones could be different.

Forked paths

So far the bulk of my data collection has been for Alby Basic and Ciar Advanced, dungeons that never contains forked paths. I do have a small amount of data for Rabbie Basic, which does contain forked paths. The zone model still seems to be used there, in the sense that every room containing mobs can be allocated to a zone. I don't yet have enough data to make any guesses about the number of structures that can occur in each of its 5 zones.

Spawn Pattern Frequency

So think about the step in generating a dungeo where we've decided what type of room a particular room is, and we know need to decide which spawn pattern to use. For example, we've decided it will be of type: Mimic room with exit open. If the room is in a zone with only one possible spawn pattern for that room type, we use that spawn pattern. But if there are two possible spawn patterns, are those two patterns equally likely to be selected.

First problem: Several room types are rare enough that I don't have enough data to answer that question. So I started with the room type that is by far the most common: The trapped chest room.

Trapped chest rooms

There are two special cases.

Math Basic zone 1 is always a single wave, being 3 Black Spider + 3 Kobold.
Alby Basic zone 1 is always a single wave, randomly selected from 4 Blue Wolf or 4 Giant Bat. Those two options are equally likely.

In all other cases, the spawn pattern may contain 1 wave or 3 waves. Extensive data over multiple dungeons suggests those two options are always equally likely.

The possible 1 wave spawn pattern(s) for a zone always match the last waves in the list of possible 3 wave spawn patterns for that zone. (Credit to Lint for that discovery.)

Thus a plausible guess is that the list of spawn patterns for a zone contains only 3-wave spawn patterns. First that game chooses one of those 3-wave patterns, and then it makes a random decision to use all 3 waves or only use the last wave, with the data saying those two options are equally likely.

But when it chooses of the available 3-wave spawn patterns, is that step an equally likely selection? At this point its useful to start analysing based on the number of 3-wave spawn patterns in a zone.

Only one 3-wave spawn pattern

Some zones only have one possible 3-wave spawn pattern.

Examples: Alby Basic Zone 4; Ciar Advanced Zones 4 and 9.

When there is only the one 3-wave spawn pattern, it will be used, with a 50/50 chance of using all 3 waves or only using the last wave as a 1-wave spawn pattern.

Choice of 2 3-wave spawn patterns

Some zone select from 2 distinct 3-wave spawn patterns.

Examples include: Alby Basic zones 2 and 3; Ciar Advanced Zones 1, 2, 5, 6 and 7.

In some of these cases, the data suggests these two 3-wave spawn patterns are equally likely to be chosen. After one of these is chosen, it is equally like to use the 3 waves, or just use the 3rd wave as a 1 wave spawn pattern.

For example, in Ciar Advanced zone 6, the two 3-wave spawn patterns have different 3rd ways, and so generate two different 1-wave spawn patterns, giving 4 different patterns in total, and these 4 patterns seem to be equally likely.
By contrast, in Ciar Advanced zone 1, the two different 3-wave patterns have the same 3rd wave, and so they generate only a single 1-wave patterns, so it seems like that 1-wave pattern is twice as likely to occur as each of the 3-wave patterns.

But in other cases, the data suggests the two 3-wave patterns are not equally likely. In those cases the data seems consistent with one of the 3-wave patterns being twice as likely to occur as the other. That is, one has a probabilty of 1/3 and the other 2/3. The same issue arises where these two 3-wave patterns might have different or identical 3rd waves.

In Alby Basic zones 2 and 3, and in Ciar Advanced zone 6, they have different 3rd waves. So the final effect is that there is a 3-wave patterns and a corresponding 1-wave pattern each with a probability of 1/3, and a different 3-wave pattern and its corresponding 1-wave pattern, each with a probability of 1/6.
In Ciar Advanced zones 1 and 2, the two 3-wave patterns have the same 3rd wave, generating the same 1-wave pattern. So the final effect is that the two 3-wave patterns appear with probabilities of 1/6 and 1/3, and the combined 1-wave pattern has probability of 1/2.

In the other examples of zones with 2 3-wave patterns mentioned above, there wasn't enough data to form an opinion as to whether they follow the equally likely pattern or the 2/3 vs 1/3 pattern. For example, in one such case, if a build a 95% confidence intervals for the outcome based on the 1/2 vs 1/2 and the 1/3 vs 2/3 probabilities, they overlap by a considerable margin, and the observed frequence falls within that overlap, so both options are believable.

Another feature of the dungeons I've been looking at is that a zone never seems to have more than 3 different 3-wave spawn patterns. I'm guessing that there was a program constraint that means that for each room type, a zone can have at most three different spawn patterns. That is, there are at most 3 "slots" to hold the spawn patterns, and the program makes an equally likely selection from the slots that have been fiiled. So when a dungeon appears to have only two distinct 3-wave patterns, there are two possibilities.

The two possible 3-wave patterns were entered into two of these slots, the the 3rd being left blank, so the two 3-wave patterns each occur with probability 1/2.
One of the patterns is put into one slot, and the other is duplicated into both the other slots, giving probabilities of 1/3 and 2/3 for the two distinct 3-wave patterns.

Examples with 3 distinct 3-wave spawn patterns

If my guess about there being 3 equally likely slots is correct, then when there are three distinct 3-wave spawn patterns, they are each entered into one of the 3 available slots, and so they will always be equally likely, each occurring with a probability of 1/3. Of course, then you have a second step with the two equally likely cases of using all 3 waves or just using the 3rd wave as a 1-wave spawn pattern, so to get the final probabilities of occurrence you have to look at whether the 3rd waves from the 3 3-wave spawn patterns were 3 distinct patterns, only two distinct or all the same.

Unfortunately I don't have enough data to say with certainity if that is happening. In statistical terms, if I use a null hypothess that the three possible spawn patterns are equally likely, I haven't found any zones for which the data suggests I should reject that null hypothesis. But the sample sizes are so small that the tests have low discriminating power. (If anyone wants to investigate this further, try Barri Basic or Barri Intermediate, both of which have zones with 3 different 3-wave spawn patterns.)

[[Category:User_Guides]]

Search

Navigation menu