I've been playing with procedural generation for my game and getting some results:
The generation process is a combination of some of the techniques I've been researching online, plus lots of trial & error and fine-tuning of parameters:
Step 0:First, I generate the largest rooms (usually 1 or 2, or none). These rooms are meant to act as landmarks and help the players to remember the level. I plan to support several room painting algorithms (for now, just 2 varieties). Here you can see a room generated by painting an overlapping set of rectangles.
Step 1:Here I generate the medium and small rooms, trying to pack as many as possible. I visit every odd-column cell in the map and do a random check. If it passes, I try to paint a room. If I can't (there is another room, a blocked cell, etc...) I move on. The process is repeated for each odd-row.
Step 2:In order to connect the rooms, I take a random cell from each one. I then compute the
delaunay triangulation of that set of points. That gives me a nice set of edges connecting each room to all its neighbours. I then take the
minimum spanning tree of that triangulation to get the shortest set of edges that would connect all the rooms. I use that as my starting graph, so that I can be sure no room will be left unconnected. I then add some of the other edges from the triangulation to improve connectivity (I try to aim at each room having 2-3 connections)
The result of that is a final connectivity graph that I will use to build the tunnels, but that is also useful to have for gameplay reasons (placing objects of interest, starting and ending points, enemies, and so on...)
Step 3:I paint the tunnels between rooms following the connectivity graph, with the A* algorithm. The cells forming the perimeter around each room have a higher cost to traverse, to avoid the tunnels "wrapping" around the rooms. I also penalize changing directions. In the future (if I have the time), I want to add a rock density layer (generated with Perlin noise) to determine the cost of traversing each cell and simulate clusters of hard rock that the corridors have to surround.
I also use masks to block entire regions of the map. By playing with these, I can output levels with different shapes (box, cross, T-shaped, etc...). These are very straighforward, the generator just chooses amongst a predefined set of masks, but they can have quite an impact over the final result:
Overall, I still have a lot of work to do: new room painting algorithms such as roundish rooms, BSP, caverns.., room texturing and styling, and don't get me started on prop and enemy placement, but I'm enjoying every minute