A dungeon map generator

I try to find new methods and algorithms to proceduraly build dungeons and mazes. Something that definitevely breaks up with the boring square and rectangular aligned patterns.

Finaly I had interesting results using Daedalus lib, as illustrated in the examples below:

The method I used to generate this map has many interesting properties. These are easier to understand by looking the steps of generation.

Step 1:

We generate a simple Delaunay triangulation. We use an algorithm that iterates through a nxm grid of points and add some of them in the triangulation according to a fixed probability P. With P=1, the triangulation would be a full regulat grid. With P=0, the triangulation would be empty. See a result below with a 20x20 grid and P=0.5 :

Step 2:

Considering the triangluation as a graph, starting from the vertex in the center, we use a custom depth-first algorithm to extract a sub-graph. At depth n, the next node at n+1 is choosen at random among unvisited nodes. Paramaters used are the total nodes count NC, the maximum branch depth BD and the maximum branches count BC. See a result below with NC=24 :

See that sub-graph as the underlying navigation graph of our futur dungeon. Nodes represent rooms and edges represent accessibility bewteen them.

Step 3:

We build the dual of the triangulation. It is similar to the Voronoi diagram but for better results we use the average positions instead of circumcircles centers:

The dual represents the real shape that will be used for the dungeon.

Step 4:

We keep only the dual cells surrounding the previously generated sub-graph at step 2. Then we build a fresh new triangulation from them. Additionally, we dig a door in the edges shared by connected rooms :

Step 5:

Finally we use a chamfer algorithm to add thickness to the walls :

Notice 2 importants properties of the resulting map:

1. It is directly built on a Delaunay triangulation

2: The navigation graph is given

In conclusion, navigation and pathfinding algorithms are ready to use, without any extra cost. It means that AI can navigate efficiently and accurately through the generated map using the pathfinding solution included in Daedalus.