Procedural Dungeon Generation Algorithm

Here’s a really cool article by A Adonaac that describes, step by step, a neat algorithm for building dungeons. It’s based on a technique used by the developers of TinyKeep, using a physics-sim to separate a bunch of randomly placed cells that are then linked up based on a minimum spanning tree of the delaunay triangle graph of the detected rooms. 

Notice how Voronoi tessellation and Delaunay triangulation can come in handy when you’re building a generator. Another interesting thing to note is the use of a specific normal distribution rather than just picking a linear random value for cell size. This is a good example of how controlled chaos is the key to improving your generators.

A Adonaac goes into a ton of detail about how the procedural generator works and discusses some tweaks and potential pitfalls along the way.

http://gamasutra.com/blogs/AAdonaac/20150903/252889/Procedural_Dungeon_Generation_Algorithm.php