This is a standard dungeon generated with the bsp tree algorithm (see this article).
The same dungeon after we applied a cellular automaton transformation (the "cavification" operation, see this).
Now this is an animated gif showing the different dungeons obtained with the morphing algorithm for values 0.2, 0.4, 0.6 and 0.8.
The morphing algorithm is really basic. Let's say that the rock cells have a value of 0 and the empty cells a value of 1. We generate a new dungeon map, using following formula for the cell value :
newCell = 8 * (coef * dungeon1Cell + (1.0 - coef) * dungeon2Cell )
It's a basic lerp between the two dungeon values, scaled by 8 to increase the precision. In this new dungeon, each cell has a value between 0 and 8, 0 meaning a rock cell and 8 an empty cell. Values between 1 and 7 represent cells with different "emptiness" weight. All the magic resides in the way we determin if a cell is empty or filled with rock. For this, we need another value that represent the emptiness of the new cell local region :
newCellRegion = sum of the values of all cells surrounding newCell.
Since there are 8 surrounding cells, this value has a weight of 8 cells. If the new cell is surrounded with empty cells, newCellRegion = 8*8 (there are 8 cells surrounding the current cell, and each one has a value of 8 if completely empty). If the new cell is surrounded with rock cells, newCellRegion = 0.
Now the formula that determin the new cell status :
newCell is empty if newCell * 5 + newCellRegion / 4 >= 40
Of course, this does not come from a mathematical theory, but from experimentation. We give a weight of 5 to the current cell and a weight of 1/4 to its region, with give us a total weight of 5 + 8/4 = 7 cells. The total should be greater than 40 (equivalent to the weight of 5 empty cells).
