A good dungeon generation algorithm isn't an easy thing to produce. How would
one go by making one? First, make a checklist of what we want:

- all squares should be reachable
- dungeon should be copmletely random
- doors (and secret doors) should be placed in logical locations

Now think from an in-game point of view. You're an overlord with a gaggle of mad
goblins with picks, and you need a place to live. Will it look like castle
Azeroth? I doubt it. My guess is, that he'd make his goblins dig out a big hole
first, and then add more features when room is needed.

AH! Now we're getting somewhere! Let's make an algorithm that makes the dungeon
look like it was cut out by a band of drunk berserkers!

Would the algorithm look something like this?

1: Fill the dungeon with stone
2: dig out a big room somewhere
 ######
 #....#
 #....#
 #....#
 ######
3: pick a random square adjacent to a floor (N,E,S or W)
 ######
 #....X
 #....#
 #....#
 ######
4: pick a feature (hall, room)
5: add feature to picked square
 ############
 #..........#
 #....#######
 #....#
 ######
6: goto 3

That's gonna be one fucked up dungeon :P It's far more chaotic than a bunch of
goblins could produce. Rooms are overlapping, halls are running through
everything, not going anywhere, in short, chaos, and not a very nice level.
What's worse, if you raise the amount of features high enough, you'll just end
up with a big open room.
That's not what we want. We don't want too much overlapping! So we'll check the
squares we're going to cut in wether or not they've been cut already. What if we
try it like this:

dig a 4x4 room:

......
.####.  check a 6x6 square (.), but only dig a 4x4 one (#).
.####.
.####.
.####.
......

dig a 6 square long hall:

......
######  check the squares around the hall as well (.), but dig only the hall
......  itself (#).

now that's more like it! No more overlapping!

You can also make a weighted list containing a closed door, an open door, a
secret door, and an open square (and any other 'gate' types you could have), and
pick one randomly for every square you select to be the anchor for a new
feature.

Now you'll end up with a nice dungeon! It's far from perfect. there'll still be
dead ends, for instance. You could solve that by giving every feature a 'hot
spot'. for instance, a room could have two hot spots, one on two randomly picked
walls. a corridor would have on at the end. That would produce a much nicer
looking dungeon.