Networks as dungeon generators

In my previous post, I showed how we can use social network analysis to interpret dungeon maps. When I posted it to r/osr, u/abenf asked if I could use SNA to generate dungeons. As shown here, the answer is yes.

However I want to be candid that dungeon generators are a solved problem so if you actually want to generate not just a dungeon, but several dungeons, all of which are placed in a hex map, use Hexroll rather than my code. You should consider this post much like someone saying “I got Doom to run on a washing machine” — it’s a fun exercise for me to write, not something for you to actually use. That said, let me walk you through the exercise, all of it in R. I’ll be doing a modified version of the Watts-Strogatz algorithm, which starts with a lattice, deletes some edges, and then adds back in edges at random.

First step is to load the libraries and then create a square lattice. I set it to be 4×4 but it doesn’t have to be if I adjust the length parameter. For that matter, it doesn’t have to be a square lattice if I adjust the dim parameter.

library(tidyverse)
library(igraph)
lat.g <- make_lattice(length = 4,dim=2)

This generates a map like this. Note I’m saving the layout for later.

coords <- layout.fruchterman.reingold(lat.g)
plot(lat.g, layout=coords)

Next let’s randomly delete 1/1.5 of the edges (lines).

delete_denom <- 1.5
n.delete <- vcount(lat.g)/delete_denom %>% round()
lat.del.g <- delete_edges(lat.g,sample(E(lat.g),n.delete))

This can create some isolates (rooms not connected to the rest of the dungeon) so I’ll add some code to give each isolated room a connection to the dungeon at random.

isolates <- which(degree(lat.del.g)==0)
attached <- which(degree(lat.del.g)>0)
for (i in isolates) {
 lat.del.g <- lat.del.g %>%
  add.edges(i,sample(attached,1))
}

At this point it’s time to figure out which rooms belong to which factions. Generally speaking we want faction territory to be relatively contiguous. My first idea was to use the Schelling segregation algorithm, which seeds factions at random then lets actors move when they’re in the minority. But then I realized there’s a whole class of “community detection” algorithms for identifying clusters in networks and I should just use one of those. By network standards, dungeons are really small so I don’t need to worry about whether a metric is computationally efficient which means I can stick with betweenness, just like in the last post, but if you’re trying to generate Arden Vul or something you might prefer cluster_fast_greedy(). The community detection algorithm gives me a list of which region each room belongs to.

regions <- edge.betweenness.community(lat.del.g,directed=F)
regions$membership

For instance it might tell us rooms 1-4 are all in region 1, rooms 5, 9, and 13 are in region 2, etc.

[1] 1 1 1 1 2 3 3 3 2 3 3 4 2 4 4 4

Now it may be we want fewer than 4 factions, which is a problem if the model is telling us there are 4 regions. But some regions may effectively be subregions of a bigger region as we can see in the dendogram.

plot_dendrogram(regions)

This tells us that regions 3 and 4 are ever so slightly closer to each other than either of them is to regions 1 and 2 or than region 1 and 2 are to each other. So if, for instance, we wanted only 3 regions, we should have region 1, region 2, and region 3+4. So (and this was honestly the hardest part to code) we need to teach the computer to combine clades on the dendogram until it has the desired number of regions. I figured three factions is about the most you’d want to see for a 16 room dungeon but you can adjust it to any number (so long as it’s equal to or lower than the number of clusters the community detection algorithm spits out).

nodecensus <- V(lat.del.g)
clusternum <- nodecensus
clusterkey <- cbind(nodecensus,clusternum) %>% as_tibble()
maxclusters <- 3
i <- 1
j <- max(nodecensus)
while (length(table(clusterkey$clusternum))>maxclusters) {
 j <- j +1
 x1 <- which(clusterkey$clusternum==regions$merges[i,1])
 x2 <- which(clusterkey$clusternum==regions$merges[i,2])
 clusterkey[x1,2] <- j
 clusterkey[x2,2] <- j
 i <- i + 1
}

Now we need to generate a possible list of factions and sample one faction for each region. If I were doing this for real, I would have each faction have its own table of room descriptions, including a lot of empty rooms that nonetheless feel like faction territory.

faction.pop <- c("cultists",
 "undead",
 "goblins",
"bandits",
"dwarves",
"lizardfolk",
"fey",
"elementals",
"mushroomfolk",
"bugs",
"gnolls",
"kobolds",
"wererats")
faction.sample <- sample(faction.pop,
 size=maxclusters, replace=F)
faction.territories <- cbind(faction.sample,
 rownames(table(clusterkey$clusternum))) %>% as_tibble()
colnames(faction.territories) <- c("faction","clusternum") faction.territories$clusternum <- as.numeric(faction.territories$clusternum)
roomkeys <- left_join(faction.territories,
 clusterkey,by="clusternum") %>%
 arrange(nodecensus) %>%
 select(nodecensus,faction)

This gives us a room key like this.

## # A tibble: 16 × 2
## nodecensus faction
##
## 1 1 elementals
## 2 2 elementals
## 3 3 elementals
## 4 4 elementals
## 5 5 gnolls
## 6 6 elementals
## 7 7 elementals
## 8 8 elementals
## 9 9 gnolls
## 10 10 elementals
## 11 11 elementals
## 12 12 fey
## 13 13 gnolls
## 14 14 fey
## 15 15 fey
## 16 16 fey

As one last step, let us add in some random edges. Note that I add the random edges after the community detection algorithm because my intention is that they will be shortcuts between faction territories.

er_n <- 2 # how many random (erdos-renyi) edges
er_edges <- matrix(nrow = er_n, ncol = 2)
for (i in 1:er_n) {
 er_edges[i,] <- sample(nodecensus,2) %>% as.vector()
 lat.del.g <- lat.del.g %>%
  add.edges(er_edges[i,])
}
lat.del.g <- igraph::simplify(lat.del.g)

We can now plot the map both with the original layout.

And with the layout that best fits its reshaped appearance.

And too lazy to code this, but used paint software to highlight the different faction territories. Red is elementals, green is fey, and yellow is gnolls.

I think that looks like a pretty serviceable dungeon.