Idraluna Archives

The Great Antarctic Hexcrawl Pt. 4 - Experimenting with Random Pointcrawl Dungeons

This is my own version of lore24, an admittedly over-ambitious attempt to procedurally generate a 128,000-hex crawl for my homebrewed far-future Antarctica, Antibor. Part 1, Part 2, Part 3.

Goals & Approach

I have nothing new to add to the art of random dungeon generation, but I still wanted to write my own script to generate the dungeons of Antibor.

Principles

In an early iteration of this project, I tried using QGIS to randomly put a dungeon in 10% of hexes and assign each a random type and size. This led to an unnecessary glut of boring, small dungeons. Lesson in hand, here are the G.A.H.-specific principles I've devised:

  1. Most points of interest do not need to be keyed as a dungeon. (If I do need maps on the fly, that's what Dyson's Delves is for.)
  2. Whatever dungeons I place should be interesting and fun for me to run. Thus:
    1. They should be fairly big
      1. Big enough to sustain multiple expeditions
      2. Big enough to be nearly impossible to fully clear, to remain persistent sources of weirdness
    2. But not so big as to require a multi-day project to prep.
      1. They should automate the boring steps of stocking, but leave room for interpretation & fleshing out
  3. Dungeons should be relatively rare features of the overland map.
    1. Finding and navigating to a dungeon should be an interesting challenge that drives engagement with the overworld.
    2. Dungeons should have serious rewards and be competitive with overland travel. Finding a treasure map that points to a dungeon should be exciting.

I'm currently inclining toward one dungeon per 500 hexes for 256 total and an average of two per ~1000-hex prefecture. This is enough for there to always be one more dungeon out there somewhere but not so many that players are blundering into them constantly.

Pointcrawls

My plan for a 'minimum viable dungeon' is to generate a keyed pointcrawl map.

Candidly, I don't actually like pointcrawls very much; in my mind they stand in relation to a spatial dungeon map as bulleted lists stand in relation to prose; adequate & convenient, but anodyne. Even so, for this project I think they're the least bad option.

For one, Antibor is an undisciplined sci-fantasy mishmash and my table of dungeon types includes 'Starship wreck', 'Cloning facility', and 'Panopticon' alongside 'Castle', 'Crypt', and 'Natural caverns'. Creating a generator that can convincingly render each type of space is above my pay grade.

Furthermore, given the numbers I'm working with, pointcrawls are compact in both digital and physical memory, easy to implement, and easy to troubleshoot. Best of all, there remains the possibility of feeding a pointcrawl into another generator. (Pointcrawls are just graphs, a well-defined structure that can be stored in a matrix and easily read by a computer).

Finally, I'm trying to uphold the 'leave blank spaces on the map' principle. I enjoy drawing maps, so (as with how I approached random monsters), I'd rather generate an interesting prompt than a boring result.

The Generator

Anyways, here's what I've got so far:

Size & Levels

How many rooms should I generate? As I alluded to above, I don't care for small dungeons. I'm conceptually demoting them to lairs and hexfills rather than capital-D Dungeons, with the key distinction being that Dungeons are too large to permanently 'clear' & are connected to a mythic underworld (to expand on in a future post).

Furthermore, from personal experience I prefer a balanced rate of empty rooms as I find they make navigation more interesting and lend an eerie vibe. (Using OD&D stocking, I'm looking at something like 5 in 12 rooms having a monster or treasure).

That said, creating 256 megadungeons is obviously silly. Somewhere around 10-15 rooms is my lower bound, and 100 my upper bound.

I played around with random distributions in R and settled on a log-normal distribution with meanlog=3.5 and sdlog=0.5:

This keeps the majority around a manageable 15-45 rooms (so something like 6-25 stocked), but a non-negligible number are much larger.

if(room_count == 'random'){
room_count <- round(rlnorm(1, meanlog = 3.5, sdlog=0.5), 0)
room_count <- min(room_count, 144)
room_count <- max(room_count, 10)
}

To generate the number of vertical levels to split rooms across, I found that ceiling(sqrt(room_count-10)) feels right. 'One page' dungeons with 10-20 rooms get 1-3 levels, increasing to ~2-8 in the 20-30 range and then leveling off. The OD&D stocking tables go up to level 13, which is reached with this method in the 100+ room range. To keep things from getting too predictable, I added a random multiplier from 0.25 to 1.75 to make a wider range of results possible. Thus: levels = ceiling(sqrt(max(room_count-10,1))*runif(1,0.25,1.75))

The range of possible results is given below, darker lines denoting the likeliest range of room counts:

I have crude code to partition the rooms to levels by assigning each level one guaranteed room and then randomly assigning the rest. It also makes sure at least one room is marked as an entrance. Secondary entrances are possible through the whole dungeon but the odds decrease drastically with deeper levels.

# Randomly partition the rooms into levels
levels = ceiling(sqrt(max(room_count-10,1))*runif(1,0.25,1.75))

# initialize a basic dungeon key table
rooms <- data.frame('Room' = 1:room_count, level=NA, 'Monster'=0, 'Treasure'=0, 'Entrance'=0)

# we need at least one room per level, so we take the first n rooms and assign them to levels 1 through n
rooms$level[1:levels] <- 1:levels

  #now we assign the rest of the rooms to a random level
rooms <- rooms %>% rowwise() %>% mutate(level = ifelse(is.na(level), sample(1:levels, 1), level)) %>% 
    mutate(Entrance = ifelse(runif(1)<(1/(5*level)), 1, 0)) %>% ungroup() %>%  # and give each room a chance of being an entrance
    arrange(level) %>% mutate(Room = row_number())  # then relabel the key so that the level 1 rooms are listed first, etc.

if(sum(rooms$Entrance)==0){  # if we generated zero entrances, pick one on level 1
    rooms$Entrance[rooms$Room==sample(1:nrow(rooms[rooms$level==1,]), 1)] <- 1
}

Stocking

With a dataframe listing rooms and their levels in hand (that is, a bare-bones key), it's relatively easy implement the OD&D stocking procedure for monsters and treasures.

Translated into R:

for(lvl in 1:levels){
lvlrooms <- rooms %>% filter(level==lvl)

while(sum(lvlrooms$Treasure)==0){ #Repeat stocking if no treasure generated
  for (i in 1:nrow(lvlrooms)){
    a <- sample(1:6, 1)  # roll a d6 for monsters
    if(a<3){lvlrooms[i, 'Monster']<-1} # if 1,2 on d6, monster
    a <- sample(1:6, 1)  # roll a d6 for treasure
    if(lvlrooms[i, 'Monster']==1&&a<4){ # if 1,2,3 in monster room, treasure
      lvlrooms[i, 'Treasure']<-1
    } else if(a==1&&rooms[i,'Monster']==0){ # if non-monster room, unguarded treasure
      lvlrooms[i, 'Treasure']<-1
    }
  }
}

rooms[rooms$level==lvl,] <- lvlrooms  # add the level back into the main dataframe
}

The only real deviation is that if no treasure is generated on a level, it repeats until some is placed.

To generate treasure hordes, I entered the treasure tables above into my homemeade Perchance clone. They're long, so I've included just the level 1 table below. (Numens and besants are Antibor's cursed monetary system; one besant is worth 45 numens, but for convenience I'm treating them as interchangeable with OD&D gold and silver for now.)

>>Dungeon_treasure_1
[1d6]00 numens, 0.5*[1d6]0 besants, 0.05*[Gem_with_val], 0.05*[Artefact]
[1d6]00 numens, 0.5*[1d6]0 besants, 0.05*[Gem_with_val], 0.05*[Gem_with_val], 0.05*[Artefact]
[1d6]00 numens, 0.5*[1d6]0 besants, 0.05*[Gem_with_val], 0.05*[Gem_with_val], 0.05*[Gem_with_val], 0.05*[Artefact]
[1d6]00 numens, 0.5*[1d6]0 besants, 0.05*[Gem_with_val], 0.05*[Gem_with_val], 0.05*[Gem_with_val], 0.05*[Gem_with_val], 0.05*[Artefact]
[1d6]00 numens, 0.5*[1d6]0 besants, 0.05*[Gem_with_val], 0.05*[Gem_with_val], 0.05*[Gem_with_val], 0.05*[Gem_with_val], 0.05*[Gem_with_val], 0.05*[Artefact]
[1d6]00 numens, 0.5*[1d6]0 besants, 0.05*[Gem_with_val], 0.05*[Gem_with_val], 0.05*[Gem_with_val], 0.05*[Gem_with_val], 0.05*[Gem_with_val], 0.05*[Gem_with_val], 0.05*[Artefact]

Then I loop through the treasure rooms and insert the treasure descriptions according to level.

# Generate treasures
rooms$Treasure_desc <- rep('', length(rooms))

for (room_id in 1:nrow(rooms)){
if (rooms$Treasure[room_id]==1){
  level <- rooms$level[room_id]
  if (level == 1){rooms$Treasure_desc[room_id] <- r_gen_eval('[Dungeon_treasure_1]')}
  if (level %in% c(2,3)){rooms$Treasure_desc[room_id] <- r_gen_eval('[Dungeon_treasure_2_3]')}
  if (level %in% c(4,5)){rooms$Treasure_desc[room_id] <- r_gen_eval('[Dungeon_treasure_4_5]')}
  if (level %in% c(6,7)){rooms$Treasure_desc[room_id] <- r_gen_eval('[Dungeon_treasure_6_7]')}
  if (level %in% c(8,9)){rooms$Treasure_desc[room_id] <- r_gen_eval('[Dungeon_treasure_8_9]')}
  if (level %in% c(10,11,12)){rooms$Treasure_desc[room_id] <- r_gen_eval('[Dungeon_treasure_10_12]')}
  if (level >= 13){rooms$Treasure_desc[room_id] <- r_gen_eval('[Dungeon_treasure_13]')}
}

I'm going to hold off on specifying monsters until I finalize compiling my bestiary into an encounter table. Same with room dressing, traps, etc. The nice thing about saving a key as a table is I can always reload and re-randomize it if needed.

Mapping

I made a secondary mapping function into which I can feed the list of dungeon rooms generated above. I chose to use the DiagrammeR package as it seems to be well updated and has the most cosmetic features of the R packages I looked at.

Room Connections

I thought my criteria for output graphs would be easy to implement:

This turned out to be an enormous pain. I had three false starts where I tried to randomly place connections in an adjacency matrix, but it was a nightmare to troubleshoot and very tough to prevent disconnected graphs from generating. Once I progressed to consulting linear algebra Stack Exchange posts I reeled myself back in and took a cruder but more straightforward approach:

  1. Define a set of nodes based on the dungeon key dataframe generated in the previous step (so this includes info about level, treasure, monsters, and entrances)
  2. Use the is_graph_connected() function to do the following while the dungeon map is not connected:
    1. Get a list of all the rooms.
    2. Weight the list of rooms by the inverse of how many connections they already have, so that rooms many connections are de-prioritized for new connections
    3. Select a node, using the weights calculated above
    4. Recalculate the list of 'available rooms' -- omit the selected node, and any nodes the node is already connected to.
      1. Roll to see if the node is allowed to connect to any other levels. This is heavily weighted toward 'no', but with a chance of being allowed to connect up or down one level, and a small chance of connecting up or down two or three levels. Omit all rooms that fall outside the rolled range.
    5. Select a node from the new list and draw an edge between the two selected nodes.
  3. When the while loop ends, the graph will be fully connected. It tends to produce a minimal level of connectivity, so I have code that runs the loop a few extra times, the exact number determined based on a random die roll and the number of total rooms.

Though I don't love that this runs on a while loop, in my experience it never takes very long to complete, even for 100-room dungeons. (I think that prioritizing under-connected nodes helps to increase the chances that a new edge will link a disconnected section to the rest of the graph).

The results are messy, but I like that it seems to generate a mix of loops, trees, dead-ends, and clusters. Better that than spitting out 256 regular grids. It's also 'stretchy' in that it uses weighted likelihoods to guide desired outputs rather than hard limits. This allows unusual but interesting results to pop up and (I think) makes it less prone to bugs.

test_graph <- create_graph(directed=F)  %>%
  add_nodes_from_table(test_dungeon)

bonus_connections <- sample(0:nrow(dungeon_df), 1)

while(!is_graph_connected(test_graph)&bonus_connections>0){
### pick a random eligible node
eligible_nodes <- test_graph %>% get_node_info() %>% mutate(weight = 1/(1+deg))

# pick first node
first_node <- sample(eligible_nodes$id, 1, prob=eligible_nodes$weight)
fn_lvl <- test_graph$nodes_df$level[test_graph$nodes_df$id==first_node]
tryCatch({fn_cnxns <- get_nbrs(test_graph, first_node)}, error= function(e) {fn_cnxns <<- c()})

#roll for whether this connection is allowed to span between levels
allowed_lvl_span <- sample(c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,2,3,4),1)

eligible_nodes <- eligible_nodes %>% filter(!id%in%c(first_node, fn_cnxns)) %>%
  left_join(dungeon_df, by=c('id'='Room')) %>%
  mutate(level_diff = abs(level - fn_lvl)) %>%
  filter(level_diff <= allowed_lvl_span)

if(nrow(eligible_nodes)<=0){next}
if(nrow(eligible_nodes == 1)){
  second_node <- eligible_nodes$id[1]
} else{second_node <- sample(eligible_nodes$id, 1, prob=eligible_nodes$weight)}

test_graph <- test_graph %>% add_edge(from = first_node, to = second_node)

if(is_graph_connected(test_graph)){bonus_connections <- bonus_connections - 1}
}
return(test_graph)

Visualization

For now, I decided that monster rooms are colored red, treasure rooms have gold outlines, and entrances have a double-outline. To arrange the nodes into clusters based on level, I had to assign the 'level' attribute to a new attribute called 'cluster' and then pass the options add_global_graph_attrs("layout", "dot", "graph") to the graph. I can't figure out how to make it display the levels in order, but tbh I don't care that much at this point.

test_graph <- test_graph %>%
  set_node_attrs(node_attr = fontname, values = 'TT2020 Style B') %>%
  set_node_attrs(node_attr = fillcolor, values = 'gray90') %>%
  set_node_attrs(node_attr = fontcolor, values = 'black') %>%
  set_node_attrs(node_attr = penwidth, values = 3) %>%
  select_nodes(conditions = Monster == 1) %>%
  set_node_attrs_ws(node_attr = fillcolor, value = '#eda495') %>%
  clear_selection() %>%
  select_nodes(conditions = Treasure == 1) %>%
  set_node_attrs_ws(node_attr = color, value = 'darkgoldenrod')%>%
  clear_selection() %>%
  select_nodes(conditions = Entrance == 1) %>%
  set_node_attrs_ws(node_attr = peripheries, value = 2) %>%
  add_global_graph_attrs("layout", "dot", "graph")

It's still not perfect. Some of these are pretty janky, and I think dungeons with 40+ rooms get very tough to read -- I may need to dial back how ambitious I am with the lognormal distribution. But I think it's in a place where I can get what I'm after by fiddling with parameters rather than overhauling the whole algorithm.

10 rooms:

This one is a little bit funky with 1 being a hub with four dead ends coming off of it, but others look more normal:

20 rooms:

I really like how this one turned out, though it's got some funky bits. The fact that levels 4, 5, and 6 are only connected to the rest of the complex by the room 6-17 connection is pretty wild. And for the entrance directly to a treasure room on level 5, I'd rule that it's a smooth vertical shaft that's very difficult to climb out of or something.

30 rooms:

Room 1 has 13 connections :'( maybe it's like a vertical stairwell or mineshaft or something.

40 rooms:

Room 1 is also popping off in this one lmao. In my defense, one could argue that this central hub structure is more or less how the Caves of Chaos are laid out in KoTB...

50 rooms:

This one behaved nicely.

80 rooms:

The inter-level connections got really out of control here.

100 rooms:

Again, the inter-level connections are wacky, but within levels things look ok. Trying to make sense of this one or translate it into a spatial map would be a nightmare, I'll admit.

For The Future

I'm going to stop here for now, but with the basics in place there's a lot I intend to build on.

Tuning

Obviously the generator is currently spitting out some wonky results. I didn't want to go back and regenerate all these screenshots, but at the time of posting I've made the following adjustments:

Spatial weighting

A bigger departure would be to randomly assign x,y coordinates to each room on a level and use distance to weight connections -- this might result in more believable layouts.

Placing & Saving Dungeons

When I generate all 256 dungeons I want to make it so that the map, key dataframe, and connections dataframe are all saved using a hex ID code so they can be reloaded and expanded on or linked to other table entries .

Keyed Connections

It would be pretty easy to randomize descriptions and hazards for the connections. I'd love to at least mark out which connections are trapped or secret. I also definitely want to insert room connections into the key, similar to the Iron Coral in Into The Odd.

Weighted Stocking

Were I to generate the layout first, I could factor distance from an entrance into the stocking code -- for example, I could make treasure rooms more likely to appear in rooms that are many steps away from an entrance. An even bolder move would be to use this distance value to determine how challenging the monster stocking table for a room should be (i.e. the purpose 'level' serves in OD&D). On the other hand, all this might make the dungeons too 'rational', which I decidedly don't want.

Flavor

I'm cautious about leaning too hard on random generation for room dressing & flavor -- I don't want to rob future me of the fun of tying the monsters and treasure into a coherent narrative. That said, It might be cool to use the graph analysis capabilities of DiagrammeR to identify dead ends and ensure they get something cool to play with, or to roll on a special table for well-connected 'hub rooms'... food for thought.

It might also be neat to play with the 'size' parameter to provide a rough visual for room size.

Other Cool Dungeon Generators & Related Links

Lastly, here are cool generators or bits of theory I consulted while working on this:

Leave a comment on Reddit

#DIY #antibor #dungeons #lore24