Steel Penny Games

Today/tonight, I spent about 12 hours writing a random dungeon generator, very much in the style of a Rogue-like game.  I've done it before, sorta, but never was impressed with the results.  I think that was partly because I expected too much from such simple algorithms I was implementing.  This go-round, however, I used industrial strength techniques and added a little control through parameters I pass in.  The end result is a kind of nice set of maps.  Once I clean up the rendering, I'll try to post a couple of samples.

The main interesting point about the way I wrote this algorithm is that I started off knowing where the entrance and exit is, and if there are any special rooms/locations that need to be placed.  Those are dropped down first.  Then, I created a number of rooms until a user-specified density is reached.  Lastly, I go through some serious effort to create a nearly-linear path through all the rooms, so that the exit is the last room.  That sounds pretty easy to say, but when it comes to implementing something like that, it's effectively an NP-hard graph problem to solve in general.  But it gets worse... in traditional graph theory, you can make connections between any nodes you like.  In a planar map, you can't necessarily because you'd be crossing lines!  So there's quite a lot of error handling that allows multiple variations, adjustments, and simply failure cases where the map is thrown out and a new one is attempted.  The exact algorithm is complex and not particularly optimized... but for an offline tool, I'm not bothered.  It only takes about 3 seconds to build a 100x100 map.  The generator is about 1,200 lines of code, and surprisingly I had only one crashing bug (array bounds mis-indexing), but numerous non-crashing ones.

The end result is a pretty decent map maker.  At least, I'm happy with it.  We plan to make use of it in our next project.  We're not talkin' about that just yet, though.