I recently injured my ankle while traveling in Vietnam and decided to learn some Lua by writing a roguelike.
I discovered that the 'best' (most complex/featuresome/interesting/interactive/playable) dungeons available today are apparently almost universally accepted by the roguelike community to be those in the game Brogue, which I was so impressed with that I tried to share here twice but it never got upvoted. It's really impressive, check it out: https://sites.google.com/site/broguegame/
Why is it impressive? As it turns out, modern dungeon generation does not simply produce a map, but rather iteratively improves upon a map given assumptions around playability (minimum connectivity / maximum dead-ends), density (don't put all the interesting stuff in a corner), proximity (some things must occur near other things), etc.
Brogue is one of the few roguelikes that kept me playing, and perhaps the first that made me 'get' roguelikes. I can highly recommend it especially to people who don't see the appeal of this genre.
Using automata can be slow, but it does tend to generate some of the best dungeon-crawling caves in my (limited) expirience.
However, the Future Work [0] section sort of points out the hardest part of all this. Avoiding back tracking.
Last time I attempted something like this, the only solution I could come up with was running a second automata, designed to generate small dead links between large groups of dead cells.
I was terribly impressed with the results.
Kyzrati's guided generation seems interesting, but my immediate thought is how linear it makes the caves - almost too much, which was the complaint against Skyrim's caves by more experienced players. But by the same token, it was precisely what more casual players liked about Skyrim's cave systems.
As a hobbyist gamedev and world builder, I love stuff like this. Kudos for making everything interactive. It really helps the learning/"aha!" process to be able to change things on the fly as you're reading about it, rather than having to roll your own to follow along.
In the more organic portions of my current project, I'm definitely using something like this :)
I'm hopeful that we'll see lots more blog posts written in this interactive style in the future - the KLIPSE plugin I use is extremely simple to set up, and has support for a ton of languages including Python and Ruby (not to mention regular old JavaScript!). http://blog.klipse.tech/klipse/2016/09/09/klipse-languages.h... is a gallery page that has examples of all of the languages that the plugin supports.
This is one of the classic procedural algorithms. I wrote my first version fifteen years ago; it's quite nostalgic :)
The other classic algorithm that I've gotten the most mileage out of is: http://www.roguebasin.com/index.php?title=Basic_BSP_Dungeon_... . Using rooms the size of entire subdivisions (instead of the smaller ones on that page) makes a nice contrast with the cellular cave algorithm.
The only algorithm I've come up with that's nearly as nice as these two is competitive flood fill. First you randomly pick center points for rooms, create a priority queue of [distance to room center -> room + tile], and add the room centers to the queue. Then you repeatedly pop tiles, add them to the corresponding room, and add their neighbors to the queue, until all tiles are in rooms. This is basically a discrete version of a voronoi diagram, but the trick is that implementing it this way allows you to safely mix different ways to measure distances, and you get wild shapes when some rooms use manhattan distance and others use euclidiean distance. (Some day I'll do a proper writeup of this, but not today.)
Thanks to the interactive nature of it I noticed that for my taste I can get satisfactory, fairly open cave output in fewer iterations (4 to 6 rather than 9 to 12) if I start with .3 fill chance, 4 birth threshold, and 3 birth threshold rather than .45, 5, and 4. In fact, it seems almost as if at those values more iterations have the cave seeming to fill in with muddy sediment around the edges.
A non-interactive page about the same topic I'd have either had to set up my own environment for this or I'd have moved on without really toying with the values. Instead I've already found a way to get results that would satisfy me with fewer cycles spent.
There's a great set of Unity3D tutorials by Sebastian Lague [0] that use cellular automata (and a few other tricks) to create a procedural cave system.
The initial cave creation technique is nigh identical to this article (purely because both use cellular automata).
Lague then joins orphaned spaces to the main space via shortest paths, using a rough Bresenham line-draw through the in-between cells (plotted with a 'brush' that is wider than one cell, so the path is traversable).
He then creates a smoother polygonised 2d/3d mesh from this grid of cells using marching cubes/squares.
The end result is quite pleasing, and fairly tweak-able :)
Both Lague's approach and his code are quite clean, so I expect the process could easily be ported to other languages / frameworks.
Replying to myself to add an additional point: Lague's cave system doesn't try to avoid designs with back-tracking -- in fact because he joins the orphaned spaces to the main space, the resulting cave system has more dead-end caves in it.
But that said, during the creation process one could easily track these spaces-that-were-previously-orphaned, and could easily use that list to spawn specials in these rooms (e.g. make the dead-end caves into features instead of bugs, by placing goals/treasure/sub-bosses/etc in them)
Thanks for the heads up! I need to update my site's version of the KLIPSE plugin to a newer version that contains https://github.com/viebel/klipse/pull/131 , which detects situations like this and allows the user to break out of them - my bad. I'll do that early next week.
I discovered that the 'best' (most complex/featuresome/interesting/interactive/playable) dungeons available today are apparently almost universally accepted by the roguelike community to be those in the game Brogue, which I was so impressed with that I tried to share here twice but it never got upvoted. It's really impressive, check it out: https://sites.google.com/site/broguegame/
Why is it impressive? As it turns out, modern dungeon generation does not simply produce a map, but rather iteratively improves upon a map given assumptions around playability (minimum connectivity / maximum dead-ends), density (don't put all the interesting stuff in a corner), proximity (some things must occur near other things), etc.