I spent a few days on and off thinking about different angles of attack for the problem of generating a map for a simple RPG, as I don't require detailed rooms (encounters are presented separately from the top down map view) so all I'm really doing is creating corridors. While this makes things somewhat simpler, it does mean that a simple bsp (binary space partitoning) algorithm that I'd previously used wouldn't be any use. Initially my idea was to have a map of impassable cells and start with a single cell in the centre of the map to start out from, from there I could tunnel away and decide if I should be going in a straight line or there should be a junction or other features. While testing a few ideas, it quickly became apparent that all I really needed for generating a level was either a full or empty cell. Making it look "nice" would come later, simplifying it even further I discovered that I only actually needed 1 rule, basically if a randomly chosen cell has exactly one neighbour that is passable then make it passable too. Keep doing this till you run out of candidates or you have reached your required density and you're done.
To beautify a level you want more interesting graphics than just blocked or empty cells, lets first consider the most "interesting" cell which is a cross roads where there are neighbouring cells to each of the cardinal directions (North, South, East and West)
Obviously as you can see I'm no artist, but stand in graphic are all you need while you are developing... By assigning a different value to each direction a bit of binary math shows you that there are 15 combinations (the 16th is a impassable cell), while you could draw each cell on the fly depending on its neighbours cells, with only 15 possibilities easier and certainly quicker just to have a separate tile for each permutation.
There isn't even any nice bits of code to explain, its all so easy! I'll just leave the code to speak for itself, one place where there can be obvious improvement is ensuring that the selection routine doesn't run out of possible selection. Rather than just pick a random cell, what you ideally need to do is scan the whole level and make a list of all valid cells and make a random selection from that list, obviously if the list empty or you have reached your target density then you have finished generating.
You'll notice with the sample code you'll get a different sized map each time you press the space bar, and it actually seems to work equally well with tiny 5x5 maps as it does with larger 15x15 maps...
Enjoy!
maze.tar.gz