Procedural Dungeon Generation: Cellular Automata

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.

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

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

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.

Related:-

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.

[0] https://www.youtube.com/playlist?list=PLFt_AvWsXl0eZgMK_DT5_...

If this interests you, check out the game loren schmidt has been working on lately:

https://twitter.com/lorenschmidt/status/790625157362712580

And this pretty neato tool to generate random variations:

http://www.1bardesign.com/games/experiments/ca_explorer/

Heads up, passing 0 as first parameter to generate-grid makes the javascript on the page to freeze, at least on Safari (maybe an endless loop).

It wild be so cool to get this to work with VR.