This is a trick to create dungeon levels gradually going from clean geometric shapes to twisted cave-like curves. It uses a floating coefficient in [0...1] range to do a sort of lerp operation between two dungeon maps. Let's see an example.

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 using coef between 0.0 and 1.0, 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, which 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).