Procedural Dungeon - Part 1: cellular automata and creating a mesh from it

Procedural Dungeon - Part 1

Introduction: 

In this post I will describe the first progress that I've made with my dungeon!

To be honest, I have never done anything quite like this in Unity before. So this will be a challenging and long trip for me! However, I like learning new stuff, so I'm looking forward to it! I hope you do too ;)

To create this dungeon I use the great tutorial series of Sebastian Lague: 

https://www.youtube.com/watch?v=v7yyZZjF1z4&list=PLFt_AvWsXl0eZgMK_DT5_biRkWXftAOf9

I will try to describe the steps that I've taken as clear as possible for you!

The natural dungeon shape:

Cellular Automata is a mathematical model that is often used to reproduce natural looking structures. The core of this model is that repopulation of cells is based on the amount of adjacent cells.The most famous example of this is 'Game of Life', a game where you see the population of a grid evolve over time. 
The difference with between 'Game of Life' and with what I want to create is that my dungeon will not evolve over time. Instead I will use this model to repopulate the grid x times when the game starts.

This then results in what I have already shown in the previous post!

Generating the mesh:

So far so good, this was all pretty straightforward. But now we come to a more difficult part: generating a mesh from a grid of tiles. All of the data we have is a grid full with nodes, containing 1 or 0 meaning they are filled or not. 

Marching Squares:

To make sure the mesh will not as cubic as it is right now, we use a algorithm called 'Marching Squares'. The idea behind this is that we check the neighbours for each cell, and based on the position of our neighbour cells, we determine what each cell will look like. Here is you can see all of the different cases: 

Triangulate squares:

The next step is to triangulate the mesh based on the data we created with these marching squares. I had barely ever created a mesh in code before so it took some time for me to really grasp what I was doing here ;)

However, what we want is to be able to devide these different shapes into triangles, that will together form the mesh. 

Important about this is that we make sure to fill these triangles clockwise, so that the normals will be correctly. Furthermore the triangles should start where the 'open space' starts. So for the 'single pentagon 1211' we start at the top center, and go from there to the center right to the bottom right to create the first triangle.

This will be really usefull if we need to know the bounds of an open area!

Creating the walls:

To create the walls, I had to figure out where the outlines where of the flat mesh. Luckily there is one simple rule for this: each vertice is part of a triangle, and if two vertices are only share one triangly they are part of the same outline. You can see it displayed underneath: there are 5 vertices, and the two white vertices only share triangle 'A'.

Once I have the outlines, it is quite easy to extrude this downwards. What I did was loop through all of the outline-vertices, and create triangles from them by adding vertices below these outline-vertices as well and then connecting them.

The Result:

To give you an idea of what it looks like now, I've splitted the generation process over time. Here is the result so far: