Hey GMC, I've been working on an rpg project, of which I want to incorporate randomly generating dungeons. I've never done anything like this before so it's a big learning curve, which is why I'm posting here!
This is the order that I've made for generating the random dungeon:
- Set the Start and End positions.
- Generate X number of Rooms with random width/height, within a set min/max size.
- Create X number of Exits(Doors) around the rooms perimeter.
- Generate the Hallways, linking together the rooms.
Here was my futher break down of the room creation process:
Step 1: Randomise start and end of dungeon positions, clamped by settings. within a grid
Step 2: Create a sqaure of bounds that the dungeon encompasses
Step 3: Randomise number of rooms and their points
Step 3a: Randomise width \ height of each room
Step 3b: Make sure rooms don't go outside bounds
Step 3c: In each room have at least one entrance/exit (Randomise the entrance position around the edges)
Step 3d: Remove any rooms with no entrance/exits
And here is the room generation process completed:
My next step is to create the hall generation - This is where I've run into a roadblock!
Step 1: Starting with the first room, pick it and another random room.
Step 1a: If the room is already connected to another room, it may pick itself as a random target. OR:
Step 1b: If step 1a is achieved, the room may open the doorway up to a dead end.
Step 2: Find the fastest path between the two rooms.
Step 3: Add slight randomisation in the path, so halls aren't completely straight.
Step 4: Connect the two rooms.
Step 5: Repeat for # of doors in each room. Paths may intersect.
Step 6: Add random break off points at places on the hallways.
Here's a diagram of what I want to achieve.
The Purple lines show the connected rooms.
The Black lines show the hallways, connecting to the rooms.
The Yellow circles show random breakoff points on the hallways.
My biggest issue right now is how to achieve finding the shortest path between the two points, and keeping it to a grid. I'd like to hear what you guys think about my breakdown process and any flaws or room for improvement it might have.