Rooms and Mazes: A Procedural Dungeon Generator (2014)

https://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes/

by tosh • 7 years ago

107 15 7 years ago

journal.stuffwithstuff.com

moomin2• 7 years ago

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.

ggggtez• 7 years ago

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.

munificent3• 7 years ago

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.

munificent3• 7 years ago

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.

moomin2• 7 years ago

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.

LorenPechtel• 7 years ago

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.

ds0• 7 years ago

Bob Nystrom's other roguelike-related posts on that blog have been a big help for my personal fiddling with gamedev.

codesushi42• 7 years ago

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.

agbell• 7 years ago

Great book, it is fun to build some visual and generative. Where you can get new results each run

munificent3• 7 years ago

My eternally in-progress game has a new hybrid dungeon generator now. It supports a variety of dungeon generation algorithms (so I can satisfy my never-ending desired to keep creating them) and will even mix them together in a single dungeon.

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.

jadbox• 7 years ago

Omg I love this! I'd love to put some time aside to study the techniques used here. Very cool (and probably fun) project you have here. :)

russh• 7 years ago

That is very cool and gives me some ideas, thanks for posting it.

mekane8• 7 years ago

That's super cool. I really like the rivers that show up sometimes.

leetbulb• 7 years ago

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.

eddieone• 7 years ago

Would be amazing to have an npm module instead of a bunch of dart code.

Rooms and Mazes: A Procedural Dungeon Generator (2014)

Related Stories