Dungeon Generator Algorithm: Part II
This article is the sequel to Dungeon Generator Algorithm: Part I. It doesn't cover the basic generation of content, if you're looking for how to generate a dungeon, start there.
Step 4. Cleaning up dead-ends
If you have followed the previous step of generating the paths in a somewhat random manner, then you will realize that this leaves a lot of dead ends. Paths that don't lead anywhere make for a messy dungeon, and it looks cleaner (and can be readjusted to make a basic city) if the dead-end paths can be fixed.
The easiest way is to iterate through your matrix checking all squares. For every "path" square you find, check it's top, bottom, left, and right neighbors. If it has three or more neighbors that are empty, then mark that square as empty as well, and move forward. Repeat this cycle whenever you find a path square that has to be emptied, and you will effectively clean all dead ends.
Note: You can do the reverse as well, count from its neighbors how many are paths or rooms. In this case, you will want to clean all path squares that have 1 or less path/room adjacent squares.
Step 5. Creating doors
Doors are relatively easy to add to your dungeon. You will need to loop through the rooms to create them, so the procedure below is for a single room.
Take your room x and y position and width and height values. Add every outer square (every square of the room that touches a non-room area) to a list. Include in this list what position the door can be in: the top-left square of a room can have North and West doors, while a square on the right that isn't a corner can only have East doors. If it is easier, just find all the possible squares in the room that open to N (the entire top file), then all that open to E (will overlap with N on the upper right), etc. Then, randomize that list.
Your list will be something like this: (1, 1, N), (1, 2, N), (1, 2, E), (2, 2, E), (2, 2, S), (2, 1, S), (2, 1, W), (1, 1, W).
Consider how many doors you want per room (4 is okay, as not all will be possible), and create an empty array of positions you have excluded. If you place a door to the exterior in the North wall, exclude from valid doors all North walls in that room.
You will want to loop through the list after you randomize it and check possible squares for doors. Do this until you run out of squares or find enough doors. A door is defined as the square it's positioned in and the N, S, E, W coordinate it has. Each one of your list items is a valid door if you have not yet assigned a room to the same coordinate (N, S, E, W) and it opens to a path. Save each door you find in a separate array.
Once you're done with that, restart going through the list, but this time save only doors that open to other rooms rather than a path, with another twist: it doesn't matter if you have two doors in the South as long as they open to separate rooms. Be sure that you don't open a door from room 22 to room 31, and then from room 31 to room 22 - you need to check the reverse as well when figuring out if a door is valid.
Step 6. Final considerations
You should have a dungeon generator similar to Aeldan's at this point. It's not ideal, but it gives good results. There are ways to make it better, however. A decent room connecting algorithm could be used to generate better paths, guaranteeing you could go from one room to all the others. Doors and rooms could be generated less haphazardly, adding to the flow between a room and the next. Maps could be expanded or shrunk dynamically instead of being pre-defined, depending on how many rooms are being generated.
All in all, though, this generator was very fun to write and put out there. Perhaps it'll be improved in the future.