A while ago I discovered Minecraft4k, a java demo written by Notch fitting into a 4kb object file. He used software raycasting to rasterize a large 3d array of voxels. The original demo can be played here as an applet:
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.
Again, I have produced a small demo of the Tengu Engine as my own way of experimenting with what may be possible as it progresses along its development path. While work is already under way on the hardware renderer, it still has not been integrated into the main code so this demo here still uses SDL for all of the rendering. What it shows is a top down perspective using a destroyed space ship tile set I made recently. There are ray traced shadows as well as what I refer to as gradients, or distance based mask pattern selection, to give the illusion of light or visibility falloff, which is a technique somewhat similar to dithering I suppose.