User:Librarian/Discovery Process

This page describes what I did to try to figure out how the random parts of dungeon instances are generated. When I first wrote this page it was based on 19 runs of Alby Basic. I've now extended that 30 runs, and also have data for 19 runs of Ciar Advanced and 4 runs of Rabbie Basic. Based on the larger data set, I have retracted some guesses that used to appear on this page. Some of the explanations still refer to the original data of 19 runs of Alby Basic because updating the numbers would not have altered the clarity of the explanation. Where this occurs you can assume that the extra data didn't contain any evidence that warranted changing the conclusion.

The model

Observation: There is clearly a trend for the monsters to become harder as we progress through a dungeon floor. Also, in Alby Basic, the first room is a trapped chest room that only contains 1 wave of monsters while later rooms can also have 3 waves of monsters.

Plausible model that has been used in other games: Each floor consists of mutliple zones each with its own spawn pattern list. For example, maybe a particular floor is divided into 3 zones. The early rooms are in zone 1, and the spawn patterns are independent random selections from the list of zone 1 easy spawn patterns, all single wave patterns with easy monsters. The next few rooms are zone 2, and the spawn patterns are independent random selections from the list of harder zone 2 spawn patterns, allowing 1 or 3 waves of monsters. The final few rooms are zone 3, and use the zone 3 spawn patterns, typically involving a much harder final wave, perhaps a mini-boss.

Choosing a Dungeon

The 14th anniversary event in March 2022 had a quest requiring completion of any Ulaid Dungeon. I decided to repeatedly run one particular dungeon, collect all the data on spawn patterns, and try to verify if the zone model is being used.

Which dungeon should I use? I wanted to choose a relatively short dungeon, because patterns are clearer on smaller data sets. So I chose Alby. Alby Normal would be cheapest. It doesn't need a pass - I can just use one gold coin. But the Ulaid Basic/Intermediate/Advanced dungeons underwent a massive overhaul in October 2021. It's plausible to suspect a similar overhaul of Normal dungeons might be next, because at the moment there are some odd inconsistencies where a Normal dungeon can be much longer than its corresponding Advanced dungeon. I don't want to collect data on Alby Normal dungeon because that might be obsolete soon. So I chose Alby Basic as the next cheapest option.

Subsequently I also started collecting data on Ciar Advanced, to try to get a Magical Branch and Rabbie Basic, since it's the easiest dungeon containing forked paths and I want to figure out if the model still works there.

Shady Wolves

Incidentally, one of the mobs appearing in Alby Basic is the blue wolf, and in this dungeon it comes in two slightly different shades of blue, one bluer and one greener. The difference is subtle. If a wave of blue wolves contains both shades, the contrast is enough to tell them apart. But if all the wolves in a wave had the same shade, I'm not convinced I was always correctly identifying which shade it was. I haven't figured out whether the difference is purely cosmetic or whether the two types have different stats. My early investigations suggested the two shades were being applied randomly, so I decided to ignore the distinction for the rest of this analysis.

The Map

First question: Is the map, meaning the physical layout of the rooms, generated randomly or selected at random from a small set of possible maps?

This question was prompted by the behaviour of the dungeons in Vindictus, another game from the same manufacturer as Mabinogi. The dungeons in Vindictus have quite complex architecture, so they can't be randomly generated for each instance. Instead, they randomly select from a pre-determined list. Terminology is a bit different in Vindictus, but explaining it using Mabinogi terminology, a particular dungeon might have 3 floors. When you enter floor 1, the game randomly selects one of maybe 3 floor 1 maps. Each map is fully determined. If you get Floor 1 Map 1, everything is identical to every other run of Floor 1 Map 1. Same room layout. Same treasure in same locations. Same monsters in same spawn locations. When you get to floor 2 you get a random selection from maybe 4 different maps built for floor 2. Sometimes the architecture repeats, so you might find Floor 1 map 1 has the same room layout as Floor 2 map 4, but they will have different monster spawns and treasures.

(I'd refer you to examples on the Vindictus wiki, but it looks like when company takeovers caused that wiki to move from Curses to Gamepedia to Fandom.com, something got broken during the changeover, and most of the dungeon maps are no longer displaying correctly.)

So every time I ran Alby Basic, I took a screenshot of the map. After 19 runs, I had 19 different maps. OK. I'm convinced these maps are being randomly generated rather than being selected from a list.

Also, the maps just look like the types of layouts that random path generation algorithms produce.

Mimic Corridor Clusters vs Mimic Rooms

For the purpose of this analysis, I regard mimic corridor clusters as counting as a room. Their location on a map is always a position where a room could have occurred.

However, it is also important to still distinguish between mimic rooms and mimic corridor clusters because there is an important distinction between how they can occur in a structure. Mimic rooms can occur with open or closed exits. That is, it is possible to encounter a mimic room where exiting that room requires use of a key obtained in that mimic room or in an earlier room of that zone. By contrast, a mimic corridor cluster has no exit door so it cannot occur in some situations where a mimic room can occur. There is also the issue that in some dungeons the possible spawn patterns are different for mimic rooms and mimic corridor clusters, though there is usually some overlap.

Update: When the spawn patterns I've encountered differ for Mimic Corridor Clusters and Mimic Rooms, the difference usually involves extra spawn patterns for Mimic Rooms rather than the reverse. Now if I look at my data for Alby Basic and Ciar Advanced, where I was recording complete spawn pattern data for each run, the extra spawn patterns only occurred on Mimic Rooms where the exit was closed. Suspicious! It may be that Mimic Corridor Clusters and Mimic Rooms with an open exit use the same set of spawn patterns, which sort of makes sense given that they are equivalent in terms of dungeon topology, while Mimic Rooms with a closed exit use a different list that has the extra spawn patterns. I'm not going to claim I have enough data yet to claim this as proved, but it's suspicous enough that I'll start reporting different spawn patterns for the two types of mimic rooms.

Are Spawn Patterns Ordered?

Next question: Do the spawn patterns appear to follow a sequence, rather than a random selection? No; they don't. On 19 runs of Alby Basic, I never got the same spawn patterns in the same order on any two runs. Even if I ignore the less common room types like 4-switch rooms and mimic rooms, and look only at what happens for the trapped chest rooms, I never got the same set of spawn patterns twice. I'm pretty sure I'm dealing with independent random selections from multiple lists.

Identifying Zones

Next obvious question: If the dungeon has separate zones, can we figure out what the zones are? Can we say something like: Rooms 1 to 4 always select their spawn patterns from this set of spawn patterns?

One problem in answering this is that the number of rooms in Alby Basic is not constant. In 19 runs I've seen room counts from 9 to 13. (Later data amend this to 9 to 15.)

Reminder: This room count excludes the foyer/entrance room, the boss room and the exit/treasure room. That is, it only counts the rooms that can contain things like trapped chest rooms, 4-switch rooms, mimic rooms, mimic corridor clusters, pre-deployed rooms, herb rooms and empty rooms where you need to use a key obtained previously to open the exit.

So it seems each zone chooses a structure from a list of possible structures for that zone. The structure defines the number of rooms in the zone, and the type of each room, such as a trapped chest room or a 4-switch room.

Using spawn patterns

For me the defining feature of a zone was that it had different spawn patterns to other zones, and might have different room types. So my first attempt to split Alby Basic into zones involved looking across 19 runs and trying to pick these patterns. Subsequently I figured out that it's often easier to look at key colours first. I'll get to that later.

Based on 19 runs, it was clear Alby Basic has 4 zones.

• The trapped chest room in Zone 1 only spawns 1 wave of monsters. In zones 2 to 4 trapped chest can also spawn 3 waves.
• Zone 1 has exactly 1 trapped chest room with only 2 possible spawn patterns, 1-wave of Blue Wolves or Giant Bats.
• Zone 2 has a wider choice or rooms, with pre-deployed rooms, mimic rooms, mimic corridor clusters and 4-switch rooms able to appear, but not always appearing. It has a wider range of monsters.
• Zone 3 has trapped chest rooms and herb rooms. It always has at least one herb room, and herb rooms only appear in this zone. Trapped chests always spawn at least one giant spider and giant spiders only spawn in zone 3.
• Zone 4 has a wider choice of rooms, similar to zone 2 but without the 4-switch rooms. Its predeployed rooms always involve 2 bergundy spiders, a pattern not encountered in any other zone. All its other possible spawn patterns always include one blue grizzly bear, a monster not encountered in any other zone.

Note that there is nothing in the logic given above that stops a particular spawn pattern being used in more than one zone. In Alby Basic, this is rare. The only pattern I found occurring in more than one zone was the trapped chest "4 Blue Wolves" pattern which is available in both zone 1 and zone 2. I did have a run where I saw the trapped chest "4 Blue Wolves" pattern three times, once in zone 1 and twice in zone 2. (Update: Overlap between zones is also rare in Ciar Advanced and Rabbie Basic.)

So in Alby Basic it is possible to split the rooms containing monsters into the 4 zones looking solely at the room types and spawn patterns, but you do need to compare data from several runs. For Alby Basic, 19 runs was sufficient. But after doing this lengthy analysis it becomes clear that the key colours used in a dungeon have some interesting properties relating to zones. Once these properties are known, key colours greatly simplify the early steps of analysing a dungeon.

Using key colours

It subsequently becomes clear that in Alby Basic, zone 1 has only 1 possible structure, while the later zones have multiple options. When building an instance of Alby Basic, the program joins together:

{The sole zone 1 structure} + {A randomly selected zone 2 structure} + {A randomly selected zone 3 structure} + {A randomly selected zone 4 structure}.

For this approach to work, keys must always be used within the zone in which they are acquired. If we don't have that constraint, then we can get problems like choosing a zone 2 structure that provides a green key that it doesn't use, followed by zone 3 and zone 4 structures which never use the green key. The only easy way to avoid that is to insist that each possible zone 2 pattern must use all the keys it provides. (OK. There are complicated methods that could make it possible for keys to span multiple zones, but the point is that they make both the coding and the level design much harder. They would be introducing unnecessary complication that wouldn't improve the player experience in any way whatsoever. Game designers who want to stay employed don't do that. From the designers' perspective the efficient solution is to insist they keys must always be used within the zone that they are obtained.)

So if you get a green key in room 3 but don't use it until exiting room 5, rooms 3 to 5 must be within a single zone. If you get an orange key in room 4 but don't use it until room 6, rooms 4 to 6 are in the same zone. If both the preceding sentences hold, rooms 3 to 6 are in the same zone.

Strange things happen with key colours. Originally I thought that keys are usually orange, and that green keys only arise in situations where the player gets to hold two different keys at once. That is, I thought I could get a 4 room sequence of {Get Orange Key, Get Green Key, Use Green Key, Use Orange Key}, which I'll abbreviate to OGOG, or {Get Orange Key, Get Green Key, Use Orange Key, Use Green Key}, which I'll abbreviate to OGOG.

Thus I was surprised to find the sequence OOGG occurring within a zone. Why did that happen? The player HAS to use the orange key to reach the room where they get the green key, so they could never be holding both these keys at the same time. Surely both keys could have been orange. That is {Get Orange Key, Use Orange Key, Get Orange Key, Use Orange Key}. There's no logical reason for two different key colours to be used here.

My theory is that there is some sort of program constraint that stops key colours being reused within a zone, even though on the surface it appears it would be safe to reuse a colour. Maybe the constraint was imposed to make it easier to do integrity checks on the structure data. Whatever the cause, the result is that we can have multiple orange keys within a floor, but we can never get more than one orange key within a zone. This constraint is a lucky break for those of us trying to figure out where the zone breaks are. It constrains the possible points for the breaks between zones. If you have a sequence of rooms that involves two different orange keys, that sequence has to be split into at least two different zones.

Another odd thing was that along with the patterns OOGG, OGOG and OGGO, I also found GGOO, GOGO and GOOG. That's weird! Aren't they superfluous? They've just reversed the key colours. It doesn't make any real difference to how the dungeon plays. My first thought was: If these sequences were being generated by an algorithm, it's unlikely that we'd get both OGOG and GOGO. An algorithm would have consistently used one colour as the first. This looks like human inconsistency. That is, someone was generating a list of possible room type structures for a zone and forgot the convention about which colour should appear first, so the list ended up containing both varieties. But over time I'm becoming less sure about that. It may be that the key sequence in the structure is coded as say ABAB, but as a final extra step A and B randomly assigned to Green and Orange, so that GOGO and OGOG can both occur. The problem is, I've also found other zone structures involving two different coloured keys where I haven't also found the reversed colour version. I think I need to do more runs to figure out what's happening here. In particular, I need to encounter the the structure with 3 different coloured keys more times to see whether those keys also appear in different orders.

(Update: The above was written at a time when I believed the number of possible structures per zone would be small, say 5 at most. But in Alby Basic, I kept finding more and more rare structures. After 30 runs I've got 18 different structures for zone 2, 12 of which have only occurred once each, so I probably don't even have the full list yet. It seems unlikely designers would hard code 18 different structures. I now suspect that the structures are being generated by some sort of semi-random process. If I collect enough different structures maybe I'll be able to figure out what that is.)

As an example of how useful these key colour properties are, consider the following run of Alby Basic. To demonstrate how far we can progress using only key colours, I haven't even bothered to include the spawn pattern data.

	Room Type	Get Key	Use Key
1	Trapped Chest	Orange
2	Empty		Orange
3	Mimic Corridor Cluster	Green
4	Trapped Chest	Orange
5	Pre-deployed Room		Green
6	Empty		Orange
7	Trapped Chest	Orange
8	Herb Room		Orange
9	Trapped Chest	Boss
10	Empty		Boss

Since a key must be used in the same zone in which it is obtained, we can immediately conclude:

• Rooms 1 and 2 are in the same zone.
• Rooms 3 and 5 are in the same zone and rooms 4 and 6 are in the same zone. Therefore Rooms 3 to 6 are in the same zone.
• Rooms 7 and 8 are in the same zone.
• Rooms 9 and 10 are in the same zone.

Since a zone can have at most one orange key, we know:

• {1-2}, {3-6} and {7-8} are in three separate zones.
• Hence zone 1 is {1-2} and zone 2 is {3-6}.
• We can't tell whether {7-8} and {9-10} are two separate zones or a single zone.

That is, the key colours let us almost fully ascertain the zones. We would still have to look at the spawn patterns in the last 4 rooms to figure out that {7-8} and {9-10} are two different zones. When we compare multiple runs we discover a trapped chest room from zone 3 alway contains at least one giant spider but never includes a blue grizzly bear, while a trapped chest room in zone 4 always contains at least one blue grizzly bear and never contains giant spider. Hence in this run room 7 is in zone 3 and room 9 is in zone 4.

Hence, this dungeon has 4 zones and for this run the split is {1-2}, {3-6} and {7-8} and {9-10}. In other runs, there must still be 4 zones, but the room numbers may differ because zones 2 and 3 can contain different numbers of rooms.

In retrospect, I analysed this dungeon in the least efficient way, by first comparing spawn patterns and room types between runs, a process that involved a huge amount of flipping between pages of a spreadsheet. It was only after I'd done this that I realised that a zone can only contain one key of any particular colour. Now that I know this I believe that the most efficient way is to first analyse each individual run using key colours. As in the above example, that probably won't ascertain all the zone breaks on all runs, but it can get most of them. That will make it a lot easier to build the list of spawn patterns in use in each zone.

Possible Last Rooms

It took me quite a long time to realise that the types of rooms that can appear as the last room in a zone is limited.

Some types are obvious. For example a trapped chest room cannot be the last room in a zone because it will provide a key which must be used somewhere within the zone, but a property of trapped chest rooms is that the exit opens when the last mob is killed without the use of that key.

But some room types are surprising. Consider a herb room with an open exit. I can't think of any logical reason why such a room could not be the last room of a zone, but it never happens. By contrast, a herb room with a closed exit CAN be the last room of a zone. Similarly, a room containing Tiro or a Fountain cannot be the last room of a zone if the exit is open, but can if the exit is closed.

The only room types that can occur as the last room in a zone are those with a closed exit. They could be:

• Those requiring the use of a key obtained in an earlier room to open the exit. They could be empty or contain herbs, Tiro, a Fountain or Pre-deployed monsters.
• A 4-switch room. For these, no key is seen, but it's as if hitting the correct switch supplies a key which is immediately consumed by opening the exit.

(This is based on Ulaid Dungeons. Iria dungeons may add extra types.)

How do longer dungeons behave?

In theory, dungeon floors can be made longer by adding more zones and/or using longer zones. Based on Ciar Advanced, it looks like Mabinogi does it by using more zones. Alby Basic has 4 zones. Ciar Advanced has 9 zones. I'm not spotting any significant difference between zone lengths. If a dungeon is longer, it naturally takes longer to collect its data, but the resulting data isn't necessarily any harder to analyse.

However, I suspect the presence of forked paths will complicate things considerably. So far I have very little data on one dungeon with forked paths, Rabbie Basic. So far I haven't had trouble splitting the dungeon runs into zones. It looks like building a list of spawn patterns for each zone will be easy enough, but building a list of possible structures could be tricky, given that the structure has to include the topolgy of all the forks.

Tiro and Fountains

Tiro and Fountains don't occur in Alby Basic. In dungeons where I have seen them, they don't ALWAYS occur in that dungeon. Based on some early research on Ciar Advanced I'm guessing that the reason they occur intermittently is because they appear in only some of the possible structures for a zone.

Update: I still believe the above statement is true for Tiro, but fountains turned out to be more complex. It's seems that a zone may contain some structures for which a fountain can never occur, and some structures which include a room which potentially contains a fountain, with a random draw determining whether the fountain is placed there. When the random draw fails to place the fountain, you get an inexplicably empty room that seems to serve no purpose.

Other miscellanous investigations

I wondered if there was any serial correlation occurring in the dungeon. Does the spawn pattern for the trapped chest room in zone 1 influence which spawn pattern I get in the first trapped chest room in Zone 2? When zone 2 contains 2 trapped chest rooms, does the spawn pattern for the first affect the spawn pattern for the second? Does the structure chosen for Zone 3 effect the structure chosen for Zone 4? So far I've found nothing. All the random selections seem independent. Admittedly, data from 19 runs isn't going to detect a weak serial correlation, but there's really no reason why a game designer would introduce a weak correlation since it would make no material difference to gameplay.

I also did some calculations on frequencies of spawn patterns for trapped chest rooms. (There's not enough data to do any meaningful analysis on any other room type.) An earlier analysiss suggested that when making a selection from a list of trapped chest room spawn patterns, the entries were equally likely to be chosen. I'm retracting that. With a larger sample size it's becoming clear that at least for some zones the spawn patterns are not equally likely to occur. Herb rooms also display bias with base herbs being very common and mandrake being rare.

For Zone 4, the first structure seems to occur way more often that the other two structures, so I'm guessing that structures are not always equally likely.

Some comments for statisticians

When testing whether spawn patterns were equally likely I used Pearson's chi-squared test for zones 2-4. The sample size is small enough that the normalcy assumption underlying that test is a little dodgy, but I didn't have the time to work out an exact CI for the test statistic. For zone 1, there's only 2 options so it's easy to find an exact binomial CI. Initial testing found nothing significant, but as the sample size increased and the test became more discerning several results became significant at 5% level.

But there's a problem with both these tests. They both apply to situations where the number of cells is known with certainty. So for zone 1 I'm assuming there are only 2 spawn patterns, and if that's right, the test suggests the two are equally likely to occur. But maybe there is a 3rd pattern that is so rare that I haven't encountered it in 19 runs of the dungeon. I think that unlikely. The trapped chest spawn patterns showing on the current Alby Basic page were developed by multiple users from probably way more than 19 runs, and my 19 runs have encountered all those patterns and allocated them to zones. So I'm pretty confident that there are no rare undsicovered spawn patterns.

But that argument doesn't work for the question of whether the different structures in a zone are equally likely to be chosen. I didn't collect any data on structures before this investigation, and I don't have any evidence that any other editors have either. The more data I collect the more rare structures I encounter and I'm pretty sure I don't have the full list of possible structures for zones 2 and 3 of Alby Basic. If I don't know the number of cells, I can't use Pearson's chi-squared test.