User:Librarian/How Dungeons Are Generated

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. In general, this is also not an equally likely selection. 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

• Trapped Chest Room. Room contains 1 chest. Opening it closes all rooms exits and spawns monsters. There may be 1 or 3 waves of monsters.
• 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 is an earlier room is required to open exit.
• Tiro Room/Corridor: Room/Corridor contains only Tiro.
• Fountain Room/Corridor: Room/Corridor contains only a Fountain.
• Empty Room - Exit Closed: The key is opened by a key obtained in an earlier room.
• Empty Room - Exit open: These rooms seem to serve no purpose and may be indicative of a bug in the dungeon generation code.

I have encountered a Fountain or Tiro in a Pre-deployed room. This is so rare that it may be due to a bug rather than being intentional.

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.

Structures

For some zones, the possible structures include structures with different numbers of rooms. Alby Basic zone 1 is always 2 rooms but zone 2 can be from 3 to 6 rooms, zone 3 can be 2 to 5 rooms and zone 4 is always 2 rooms. Thus in total, the dungeon can be from 9 to 15 rooms.

Some zones have so few possible structures that they are easily listed. For exmaple, in Alby Basic zone 1 has only one structure and zone 4 has 3 possible structures. Other zones have so many possible structures that they are unlikely to be have coded into the game data individually. In Alby Basic, zones 2 and 3 are like this. The rest of this section deals with this latter case.

Structures seem to be built by combining one or more blocks. For example, in Alby Basic Zone 3, there are 3 possible blocks.

Room Type	Key
Block A
Trapped Chest Room	Get Key
Herb Room - Exit closed	Use Key
Block B
Trapped Chest Room	Get Key
Empty	Use Key
Block C
Herb - Exit open

Structures are built from 1 or more of these blocks. Two examples:

A: The simplest structure is using Block A alone. The key must be orange.

A+C: That is, use both A and C. It's possible to build three structures by meshing blocks A and C together. The sole room in Block C can never be the last room of a zone, so it must be the 1st or 2nd room in the resulting 3 room zone. Thus there are two structures for the A+B pattern. They seem to be equally likely to occur.

Room Type	Key
Structure 1
Trapped Chest Room	Get Key
Herb - Exit open
Herb Room - Exit closed	Use Key
Structure 2
Herb - Exit open
Trapped Chest Room	Get Key
Herb Room - Exit closed	Use Key

Alby Basic zone 3 allows 6 block patterns: A, A+B, A+C, B+C, B+2C and 2B+C.

Where a structure involves two keys, they are assigned at random. For example, with the A+B block pattern, one of the structures possible is:

Room Type	Key
Block A
Trapped Chest Room	Get Key 1
Trapped Chest Room	Get Key 2
Empty - Exit closed	Use Key 1
Herb Room - Exit closed	Use Key 2

The Orange and Green keys can be assigned to this structure in 2 ways: Key 1 can orange or green, with key 2 being the key not used for key 1. I've seen both of these varieties. Based on structures involving two keys I have seen, I suspect such structures always allow both key assignments to occur and they are equally likely. Extending this idea, it seems plausible to suggest that when structures involve 3 keys, all 6 ways of assigning Keys 1, 2 and 3 as Orange, Green and Blue are possible. However, structures with 3 keys are so rare that I have yet to encounter a single structure more than once, so I can't claim I have data supporting this guess.

Maps

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

This is a two-step process.

1. 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.
2. 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.