Today I pointed my browser towards The TIGSource website and saw a fresh post directing readers to a kickstarter for TinyKeep.  While I am not exactly interested in the game itself, one thing on the site caught my eye.  The team have developed an interactive demo for their random dungeon creation algorithm, and I really like it.  It can generate nice looking dungeons, and the concepts it uses seems reasonably understandable.  I wasn’t satisfied with just observing the demo to try and infer how it operates so I decided to take a peek under the hood.

I downloaded the flash object and pointed a shockwave flash decompiler at it, to find ~6000 lines of code.  I guess that is because the decompiler doesn’t discriminate between linked libraries and regular program code.

Above is a picture taken nearing the end of the generation process.  At this point it seems links are added until a minimum spanning tree is available or something, being highlighted by the thicker green lines.

The source is not as immediately helpful as I wanted it to be, but it turned up a few interesting hints.  There is a mention of minimum spanning trees, which I remember casually skipping over while digesting my algorithms book.  I have however since read that chapter again this morning, and now I have a pretty good idea of how these concepts can be used in this context.

So my task in building the Tengu Engine will be stalled for just a moment while I play with my own implementation and variation of this algorithm.  In fact, procedural level creation is something that I haven’t read about actively so perhaps this algorithm is already well known, but being a feet first kind of person, I rather fancy just coding up my own before researching this stuff.