Dungeon Generation in Rogue Matrix

I went through quite a few design iterations before landing on a dungeon-generating algorithm that I liked. First, what do we mean by dungeon? I'm talking about a top-down, 2-D representation of interconnected rooms & hallways with a traversable path between any 2 points. That last requirement is the trickier part. It's even more tricky to get something that's unpredictable, yet believable; like, not just a bullshit jumble that a computer obviously puked up. Like, maybe some dude really designed this dungeon.

Here's what I ended up with; it's pretty simple but I like the results:

1. Divide the play area into a 3x3 grid. This is just what happened to work with the screen resolution I was working with.

2. At each gridspace, decide with some probability to build a room there. You can get a lot of mileage out of tweeking that probability, depending on how room-dense you want your dungeon to be. This leaves the possibility of a roomless dungeon, which I didn't want, so if we end up with no rooms I just go ahead & build 2; a start room & an end room.

3. Build each room with randomly chosen widths, lengths, & starting point offsets. You've got to tweek the minimum & maximum values for all of those parameters depending on what you're going for. I used maximum values large enough to allow rooms to cross over gridlines & even over each other, which makes for much more interesting dungeons, I think.

4. Inside of each room, choose a random "anchor point" for creating hallways. I started out just using the room's midpoint but it made the dungeons sort of predictable &, I don't know, computery.

5. Build hallways. This is what really makes the dungeon. We have a list of rooms. Randomly choose one (room A) & remove it from the list. Then, randomly choose another (room B) & remove it from the list. Build a hallway between room A's anchor & room B's anchor. Choose another room (room C), remove it from the list, build a hallway between B & C, & so on until the list is empty. This guarantees that we can now choose any 2 random rooms & travel between them, very important. Note that we're allowing hallways to pass through rooms that happen to be in their way; this, again, makes the dungeon more interesting & unpredictable, compared to a procedure that just builds hallways between adjacent rooms, which is common in these kinds of games.

With the dungeon built, we can toss the player at a random spot in a random room, do the same for the exit object, & be confident that it's possible for the player to reach the exit. I didn't put any constraint on where the exit could be in relation to the player, so the exit could be like 2 steps away in the next room. This decision was informed more heavily by my not giving a good god damn than by any sort of design principal.

So next time you're in a jam & you need to write a procedural dungeon generating algorithm I guess you'll be all set.