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.