Rooms and Mazes: A Procedural Dungeon Generator (2014)(journal.stuffwithstuff.com)
journal.stuffwithstuff.com
Rooms and Mazes: A Procedural Dungeon Generator (2014)
https://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes/
6 comments
There's an entire book dedicated to this subject:
https://pragprog.com/book/jbmaze/mazes-for-programmers
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.
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.
Great book, it is fun to build some visual and generative. Where you can get new results each run
Neat. It doesn't produce anything much like any of the standard generators in DCSS. Tempting to add it...
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.
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.
> it has the entertaining property of having no dead-ends in a corridor.
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.
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.
Dead ends aren't interesting, but they do heighten tension rather effectively if you're being chased. Pillar dancing: yeah, it's tedious, but I do think it's hard to have a game without an ability to reset a fight. And yeah, that's what I meant. The relevance is that, of course, they increase the chances of you getting cut off when things are going wrong.
This algorithm is relatively well known. If I read right, the author is just implementing an older algorithm but switching the order of two steps for efficiency reasons.
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.
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.
> If I read right, the author is just implementing an older algorithm but switching the order of two steps for efficiency reasons.
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 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.
Producing no dead ends is easy enough to do--simply sweep over your map and delete any cell with exactly one connection. Repeat until nothing is deleted. Even without looking at the code it's pretty clear that's what's going on here.
I have done procedural dungeon generation before, dead end removal isn't hard.
I have done procedural dungeon generation before, dead end removal isn't hard.
I spent some good hours implementing a physics (box2d) based Procedural Dungeon Generation Algorithm in C++. My implementation is based off of a very awesome blog post: https://www.gamasutra.com/blogs/AAdonaac/20150903/252889/Pro...
Another interesting algorithm I've fiddled with was cellular automata. This method works extremely well to generate more organic feeling maps.
Another interesting algorithm I've fiddled with was cellular automata. This method works extremely well to generate more organic feeling maps.
Bob Nystrom's other roguelike-related posts on that blog have been a big help for my personal fiddling with gamedev.
Would be amazing to have an npm module instead of a bunch of dart code.
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.