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 make sure that all rooms are connected. I am curious what other soltions 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 are 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 matches 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 definately good enough way in terms of dungeon layout, goes through the rooms and change 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 a "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 add the left room to the stack if it is not already on 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 biggeset room group, and if so, create a horizontal / vertical path there by injecting / updating the rooms inbetween. Rinse and repeat. Ugly, yes, but it is something that will not be noticable in terms of visual pattern so it works in that sense.