Undercity Dungeons and the Union-Find Algorithm

And since we've got no place to go
Write some code, write some code, write some code

The line-map of Herculaneum reminded me of a project I had back in college doing random maze generation using the union-find algorithm.  Since I have some free time over the holidays and nowhere to go, I figured I'd play with it some more and see if I couldn't get decent dungeon results out of it.

I may have also bombed a "generate a maze" question on a coding interview a few years back, and could maybe use the refresher.  I had 45 minutes to do it during the interview; doing it this time took me about two hours to get the result below (but I also had to do drawing).

This is an example of a maze generated using union-find.  It would not make a very good dungeon.  Union-find guarantees that there is exactly one path from each cell to each other cell, which is the very opposite of jayquaying, and this also means that there won't be anything resembling a room, since an open 2x2 square has two paths from each corner to each other corner (first moving vertically, then horizontally, or first moving horizontally, then moving vertically).

What we can do though, is carve out structure beforehand, and then let the mazing fill in the rest and make sure it's all connected.

Here's what that looks like with rooms:

This still doesn't give us loops though.  When I first started working on this post I was thinking about trying to do something like two independent passes of union-find to generate multiple paths most of the time between each pair of cells.  That sounds tricky though.  Having gotten most of the way there, I think I could just do the same thing with loops that I did with rooms - just punch loops into the grid before we do the mazing.  Likewise, if we wanted long "road" corridors and a forum in the middle where they cross, we could put those in before mazing.  This is similar to what I did manually in Rathell, adding intentional loops and then creating tree structures inside them.

Adding loops (highlighted in red) and regenerating, we can get something like this:

So this is getting better.  Sometimes the loops all end up in one part of the map, which is unfortunate, and I should probably do something to make sure they're a little more evenly-distributed.  I might need the variance on the dimensions of the loops to be higher, so that full rooms end up contained inside them more often, for that "city block full of buildings which contain rooms" feel.  The other thing obviously missing for this to be a dungeon map is doors.  Having a loop always contain a secret door makes it less obviously a rectangular loop.  But those are more annoying to draw.  Adding secret doors to random edge removal could be both really interesting and really dangerous, because you could cut off a whole section of the dungeon, but you could also just get a small secret section, which is desirable.

Other potential extensions: 

• Add options for roads and forum.  
• Number the rooms on the map.  
• It's sort of annoying how frilly, nooksome, etc these maps are; I could see them being super-annoying to describe in play to a mapper.  Might be good for a melee+mapping gauntlet level though - just add minotaurs!  
• Add ability to serialize dungeon levels to some sort of format which can be processed by subsequent programs (for eg stocking rooms)
• Add the ability to take partially-specified (manually-generated) dungeon files as input and then maze / fill in the unspecified parts.
• Generate multiple levels (slightly varying map generation parameters for each one) and link them together with stairwells
• Unreasonably huge recursive dungeon, where each cell of the outer map represents a whole dungeon level, and the links or walls between its neighbors indicate passages between dungeon levels.
  

Anyway, it's on github.  It was a fun afternoon project.