A Melan diagram is a way to simplify a dungeon design to its bare topology to show if it is Jaquaysed (i.e., not linear or branching but with loops that allow meaningful choices). In the comments to a Justin Alexander post on Melan diagrams, there’s a discussion of whether explicitly invoking graph theory adds anything to dungeon design/analysis or only confuses the issue with jargon. I don’t know about pure graph theory, but you can definitely learn about dungeons through social network analysis (SNA), which is a major offshoot of graph theory.
SNA assumes that all travel/information goes through the “edges” (lines) connecting “nodes” (dots). This is a pretty good model for describing a dungeon since unless you have teleport or rock to mud or just a pick axe and a lot of time, all travel through the dungeon must follow designated paths through it, which is why dungeons are the easiest scenario structure for both player and GM. So if there is a door from room 1 to room 2, 1 and 2 would be nodes and there would be an edge connecting them.
There are a few ways SNA can be useful for analyzing dungeons, but in this post I will emphasize betweenness centrality. “Centrality” is a class of measures for how much a particular node matters. Betweenness is a version of centrality that measures how often random paths through a network will pass through a particular node. In a dungeon context, a high centrality node will be the crossroads or chamber that connects many passages. In this post, I’ll work through several dungeons to show how betweenness centrality can flag the key rooms.
Let’s start with a small dungeon, the subterranean level of Ruin in the Savage Wastes (free on DTRPG). The basic structure of the dungeon is like this. (I added “0” as the entrance).
You can tell at a glance that room #3 is gonna be key (since it connects the entrance corridor to the loop) followed by room #7 (since it connects the loop to the side chamber). In this particular dungeon those are also the nodes with the highest “degree” centrality, which is simply number of edges. Basically, how many doors does the room have. Here is how the computer (specifically, igraph::betweenness(normalized = T) and igraph::degree() in R) sees it.
ritsw.between ritsw.degree 0 0.00000000 1 1 0.25000000 2 2 0.42857143 2 3 0.60714286 3 4 0.14285714 2 5 0.03571429 2 6 0.07142857 2 7 0.39285714 3 8 0.00000000 1
As expected, rooms 3 and 7 are high in betweenness. The surprising thing is that room 2, part of the entrance corridor, is also high betweenness.
We can move on to a more complicated (but also free) dungeon, Tomb of the Serpent Kings. I am going to assume familiarity with this dungeon as a) it’s free and b) it’s famous in the OSR. This dungeon has a structure like this.
So there’s a long entrance corridor then several loops. The visualization is a bit hard to read so let’s just check out the output for the top 10 rooms.
11 38 39 17 09
0.52344143 0.49874309 0.34829060 0.34571393 0.32352941
08 36 07 06 05
0.26546003 0.24924585 0.23755656 0.20814480 0.17722474
Room 11 is an obvious hub. It connects the false tomb entrance corridor to the chasm ledge and (via some secret doors) the basilisk room. In addition, room #11 has a bunch of dead-end side chambers but don’t matter very much to betweenness.
The next high centrality room is #38, the basilisk room. This connects to the Xiximancer rooms, the priest shrine, and (via secret doors) the goblin caves and the aforementioned #11 hub.
#39 and #17 are, respectively, a secret passage and a room connecting the secret passage to hub #11. You can check out the rest yourself just by looking at the map, but already we are seeing that secret doors seem to be important to betweenness. This suggests that we should also try the map ignoring the secret doors, since by default this is how most players will experience it. Without secret doors, TotSK looks like this.
The first thing to note is that travel times are now longer. With the secret doors included, the average distance between any two rooms chosen at random was 6.0 doors. Without the secret doors it’s 7.5. Traditionally, one function of secret doors is to reward mapping by showing a lacuna on the map (which turns out to have a bunch of treasure). This exercise demonstrates that an additional function of secret doors is to create shortcuts.
Now let’s check out the top 10 rooms by betweenness if we ignore the secret doors. Obviously #39 won’t matter anymore, but we can see what else changes.
22 11 20 19 18
0.48857143 0.47918367 0.44979592 0.44081633 0.43020408
28 09 26 08 27
0.29360544 0.28653061 0.26938776 0.26122449 0.25850340
Room #11 is still pretty high up there, even though it’s now much further from the basilisk (#38) but rooms #18, #19, #20, and #22 came out of nowhere to be crucial to the whole dungeon. This set of rooms is the stairs to the stone cobra guardian (#18), the stone cobra guardian itself (#19), and then the ledge along the chasm (#20 & #22). If you just glance at the map, these rooms don’t look like hubs. They aren’t at the center of the map, they don’t have a bunch of radiating spokes, etc. Yet if you’ve played TotSK you know these rooms are critical. When I ran it, my group had a lot of difficulty defeating the stone cobra guardian and thereby unlocking the rest of the dungeon. If there was an obvious path around it, they probably would have just bypassed the horrible thing.
Another interesting dungeon is Incandescent Grottoes. It isn’t characterized by secret doors so much as chasms, waterfalls, etc. These differ from secret doors in that they are obvious, but they have in common that they are difficult to use. Let’s see both version of the network version of the map.
With the tough passages included, Incandescent Grottoes is a dense interconnected web. Without it’s what network theorists call a “spanning tree,” with no loops at all. The average distance between rooms goes from 5.2 if you jump the chasm, swim down the waterfall, etc to 8.0 if you stick to walking. This is brilliant design. The inclusion of obvious but difficult shortcuts completely changes the experience of the map from linear with a few forks to a thoroughly Jaquaysed sandbox.
Without the shortcuts included, the high betweenness rooms are:
- #3: a cross-roads on level 1
- #21, #22, and #23: uninhabited troglodyte area
- #40: a corridor on level 2
In contrast to TotSK where the key room has an extremely powerful guardian, all of these key areas in Incandescent Grottoes are neither occupied nor trapped.
If you include the secret doors, chasms, river, etc, asking which rooms are highest betweenness is almost besides the point since no room has high betweenness if there are multiple paths to circumvent it to almost any destination. We can describe this formally with a Herfindahl coefficient to summarize the inequality in betweenness. (If you’re thinking why not a Gini, the answer is that to a first approximation Gini measures relative poverty whereas Herf measures oligarchy — in a dungeon this means Gini will measure the number of dead-ends whereas Herf will measure whether a few chokepoints control the dungeon). Without the secret doors, chasms, etc., Incandescent Grottoes has a Herfindahl of betweenness of 503 whereas with all the shortcuts included it drops to 428.
Here are my take homes:
- we can measure the importance of secret doors, chasms, etc. by how much they decrease the average path length.
- betweenness centrality can identify key points on the map, especially ones that don’t look like hubs like the ledge in TotSK.
- we can measure how Jacquaysed a dungeon is by measuring the Herfindahl Index of the betweenness scores.
homicidallyinclinedpersonsofnofixedaddress.com 
Leave a comment