Problem to solve: Generate a random 2D dungeon map for a tile-based game where all rooms are connected.
I am looking for better solutions than what I currently have.
My current solution is that I run two algorithms. The first generates the dungeon with its rooms. The second makes sure that all rooms are connected. I am curious what other solutions may exist. Faster and / or easier etc. Speed is not really a concern, but if speed can be gained at no real cost, well, that is a good thing. More important is that I, and others that read, may learn different ways to approach and solve the problem.
Below is my current implementation. Rooms currently have no exits or exits in any 2, 3 or 4 directions.
Generating the dungeon rooms
Setup: Set the current room to the top left room.
- Get a valid room type for the room (where valid room type is a type with no exits out of the dungeon and that have exits that match the exits of the room above and the room to the left. Only need to check above and to the left due to step 2 below).
- Put down the room and advance the x-coordinate one step. If the x-coordinate exceeds the dungeon width, set the x-coordinate to 0 and advance the y-coordinate one step. If the y-coordinate exceeds the dungeon height, we are done.
- Repeat from #1.
I then check to see if all rooms are connected. If they are not all connected, I run a second algorithm that, in a non-sexy but definitely good enough way in terms of dungeon layout, goes through the rooms and changes them so that all end up being connected.
Checking to see if all rooms are connected
Setup: Create a 2D map of integers representing paths and initialize the entries to an "unprocessed" (not yet traversed) value, -1. Set a start path index integer that keeps track of the current path to 1. Set the current room to the top left room by adding it to a stack of rooms to check.
- If the stack contains rooms to check, pop it set the path index of the room to the current path index. If the stack does not contain any rooms, increase the path index and try to get a room by advancing column by column, row by row, until we get a room that has not been processed yet. If no room can be found, we are done.
- Check to see if the room has an exit to the left. If it has one, add the left room to the stack if it is not already there.
- Repeat step 2 for down, right and top directions (since we are using a stack, that means the rooms are traversed in clockwise order, starting with the top direction).
- Repeat from step 1.
- If the path indices count is greater than one, there are disconnected rooms.
If there are disconnected rooms I then group the rooms by their path index, get the index of the biggest path and connect all other rooms to those rooms. This is a work in progress, but my (current, "brutish") plan is to go through each room in a room group (except the first), check to see if there is a horizontal or vertical path to the biggest room group, and if so, create a horizontal / vertical path there by injecting / updating the rooms in between. Rinse and repeat. Ugly, yes, but it is something that will not be noticeable in terms of visual pattern so it works in that sense.