Rooms and Mazes: A Procedural Dungeon Generator (2014)
journal.stuffwithstuff.com
journal.stuffwithstuff.com
The latter is something I've wanted to do for ages but only very recently figured out how (thanks to an offhand comment from Brogue's Brian Walker at last year's Roguelike Celebration). The tricky part is ensuring you still end up with a fully connected dungeon.
If you want to see the current state, you can play with the generator here:
http://munificent.github.io/hauberk/debug/dungeon.html
At shallow depths, it tends to use a single rooms-and-passages generator. But if you pick a lower depth and click a few times to roll new dungeons, you'll start to see hybrids that mix a few different algorithms together. It still needs a lot of work, but I'm really proud of it.
It is not as hard as it looks, it is essentially a drunkard's walk. And some strategies to remove bias, which that book covers nicely.
I note, however, it has the entertaining property of having no dead-ends in a corridor. It also produces extremely few pillars, which could be an issue. I think it's OK for LOS opportunities. Looking at it, I don't think it ever generates crossroads, though.
No it never generates crossroads. Despite saying the maze can be imperfect, I think they are wrong. Anyway, it's kind of boring as maze generators go. For example, in the 1980's, the first edition of D&D included a simple maze generator (i.e. pen and paper algorithm) that could generate dungeons like this one.
That's right.
> No it never generates crossroads.
It can, but they're rare. It would be an easy tweak to make them more common.
> Despite saying the maze can be imperfect, I think they are wrong.
It always generates imperfect mazes. The code that does that is:
https://github.com/munificent/hauberk/blob/db360d9efa714efb6...
Basically, it removes all connections between regions that are already connected. Except there's a finite chance it will keep the connection even when the two regions are already connected. In other words, it adds known cycles.
> Anyway, it's kind of boring as maze generators go.
Yeah, it does produce sort of same-y results. I'm not currently using it because of that. But I also intend to reintroduce it back as one of the multiple algorithms my game uses since it can now mix algorithms together. If every dungeon used this style, I think it gets boring. But when you only occasionally run into a part of the dungeon like this, I think the very same predictability gives it a nice distinct flavor.
That's correct. I mostly consider that a feature because I don't find dead ends very fun. Also, if you don't do the dead end pruning, you end up with a lot of them, which is definitely anti-fun.
There's an easy refinement you could do if you want some dead ends. Right before the "make sparse" step that removes them, mark a randomly set of dead-end tiles as "unprunable". Then when pruning, those are left alone, which will implicitly also persist the paths leading to them. By controlling how many of these tiles you mark, you can tune the number of dead end paths.
> It also produces extremely few pillars, which could be an issue.
Also a feature if you think pillar dancing is an exploit. :)
The generator can produce pillars, but it's relatively unlikely to.
> Looking at it, I don't think it ever generates crossroads, though.
By this, do you mean a four-way intersection? Yeah, now that you mention it, is looks like the maze generator doesn't often generate those. I think it could, but is unlikely to.
That's also easy to tweak. I believe the main reason is that it was adds to the maze by branching off from the most recently-placed open tile. This encourages long windy passages, but means it's very likely to backtrack to a tile that is already a three-way intersection.
Having it randomly choose a tile instead of, essentially, doing a depth-first traversal, will increase the chances of it picking a tile that's already a T-intersection and turning it into a four-way.
I have done procedural dungeon generation before, dead end removal isn't hard.
Another interesting algorithm I've fiddled with was cellular automata. This method works extremely well to generate more organic feeling maps.