Procedural Dungeon Generation: Cellular Automata

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.

[0] http://blog.jrheard.com/procedural-dungeon-generation-cellul...

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.

Comments like this make my day, thanks :)

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.

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.

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.)