==================================

https://csharpcodewhisperer.blogspot.com/2013/07/Rouge-like-dungeon-generation.html

This software provides procedural content generation of cave-like dungeons/maps for rogue-like games using what is known as the Cellular Automata method.

To understand what I mean by cellular automata method, imagine Conway's Game of Life. Many algorithms use what is called the '4-5 method', which means a tile will become a wall if it is a wall and 4 or more of its nine neighbors are walls, or if it is not a wall and 5 or more neighbors are walls. I start by "seeding", or randomly filling the map with walls and spaces based on some weight (say, 2/5 times it places a wall). Then there is a 'Horizontal Blanking' step, which clears all the walls in a horizontal strip that in the spans the map, centered vertically. This step I added to eliminate the 'isolated cave' problem (more on that below), and differs from the standard algorithm. The cellular automata step visits each (x,y) position iteratively and applies the 4-5 rule. The automata step is applied multiple times over the entire map ("rounds"), which hollows out the cave and smooths the wall. I found about 3 rounds produce nice, 'natural' looking caves.

The isolated cave problem: One of the major problems with this technique is (was) the formation of isolated caves. Instead of one big cave-like room, you often get isolated islands of space that is inaccessible from the larger, cavernous space without digging through walls. Isolated caves can trap key items or (even worse) the stairs leading to the next level, preventing further progress in the game. There are a few different proposed approaches to solving this problem: 1) Discarding maps that have isolated caves. 2) Filling in the isolated sections, 3) Not placing doors or other key quest items on tiles if there are any walls within some radius, or 4) Finely tweaking the variables/rules to reduce occurrences of such maps. None of these are ideal (in my mind), and most require a way to detect isolated sections, which is another non-trivial problem in itself.

In this inventions, I propose a solution called 'Horizontal Blanking', because it blanks a horizontal strip through the center, replacing all walls with spaces. I found horizontal strip about 3 or 4 tiles tall works best for a 40 wide by 20 high map (about 1/5th of the map height), but the ideal height also depends on the chosen automata rules. Clearing a horizontal strip of sufficient width creates a centralized cavernous space, and prevent a continuous vertical wall from being created through the center of your map, forming two isolated caves on either side. After horizontal blanking, you can apply the cellular automata method to your map like normally.

NOTE: Because my map is wider than it is tall, so I blanked a horizontal strip to prevent a vertical wall from isolating the left side from the right side. If your map it taller than it is wide, you will probably want to blank a vertical strip to prevent a horizontal wall from isolating the top area from the bottom area. I find it helps to have an asymmetry of dimensions, but if your map is a perfect square, I don't know for sure, but I presume blanking BOTH a horizontal and vertical strip will work, but you'll probably want to make the strips thinner than you would for a asymmetric dimensions, and possibly additionally blank the center region in the shape of a square or approximate circle.

If you map is truly huge, you may still have problems with isolated pockets because there is just so much room for them to form in. Without having ever tested this scenario, I propose either adopting the same strategy as described for a map with perfectly square dimensions as mentioned above, or similarly blanking both a horizontal and vertical region, but use ellipses instead of rectangles. Another idea would be to take a square with the same dimensions as your map, rotate it by 45 degrees so that its corners just touch the N, S, E and W boundaries, and blank that region. Then, to reduce the feature-less cavernous space and give your map more texture/detail, add back in a central region of solid wall.

Anyways, you should get the general idea of my technique to prevent isolated caves by now. If you have unique or problematic map dimensions/shape, some experimentation of blanking regions shape and placement might be required, but basic rectangular blanking works well in the general case.