1
\$\begingroup\$

I am trying to make a random dungeon generator using Unity. I have been able to setup the rooms properly and connect them to each other using a minimum spanning tree algorithm. I have attached an image below where you can see what I have so far. The next step will be to create pathways/corridors to connect the rooms together but I am having difficulty understanding how I am supposed to go about it. I want the corridors to be straight or form an 'L' shape when connecting to each other. So I was wondering if anyone could help me out with this. Any help is appreciated.enter image description here

\$\endgroup\$
4
  • 1
    \$\begingroup\$ How do you want these corridors to look? Why do you think they should look like that? \$\endgroup\$ – Philipp Apr 1 '19 at 13:41
  • \$\begingroup\$ It looks like you have everything you need already — just cut a path following the edges from your spanning tree. What "cut a path" means for your implementation can vary, but since you haven't told us anything about how these rooms are set up or what output you want, we're not yet well-equipped to advise on those specifics. Can you edit your question to include more detail about what specific data you need to generate? (eg. coordinates of tiles to tunnel through, or box colliders for tunnel segments, or mesh vertices & triangles...) \$\endgroup\$ – DMGregory Apr 1 '19 at 13:49
  • \$\begingroup\$ @Philipp sorry for not mentioning that earlier. I have edited the description. I want the corridors to be straight or form an L shape when connecting to each other. \$\endgroup\$ – nz881 Apr 1 '19 at 13:49
  • \$\begingroup\$ @DMGregory that's actually what I want to know and can't seem to figure out. I want the rooms to be connected with straight or L shaped corridors. Could you please explain what you mean by "cutting a path following the edges of the MST". It sounds like something I might be able to do, but would you mind elaborating a little bit more. Thanks :) \$\endgroup\$ – nz881 Apr 1 '19 at 13:59
1
\$\begingroup\$

When the two rooms you want to link have overlap on the x-axis or y-axis, then it is a rather trivial case: Calculate the overlap range and generate a corridor at a random coordinate on that overlap.

The code for the vertical connections would look something like this:

// calculate x overlap range
float rangeXfrom = Mathf.max(room1.x1, room2.x1);
float rangeXto = Mathf.min(room1.x2, room2.x2);
// check if there is x overlap
if (rangeXfrom < rangeXto) {
     // generate path position
     float pathPosX = Random.Range(rangeXfrom, rangeXto);
     // check which two y-walls are the two closest ones
     if (room1.y2 < room2.y1) {
         GeneratePathway(pathPosX, room1.y2, pathPosX, room2.y1);
     } else {             
         GeneratePathway(pathPosX, room1.y1, pathPosX, room2.y2);
     }
}

The code for generating the horizontal connections would look the same, just with the x-axis and y-axis reversed.

The only room where that wouldn't work in your example are the rooms 8 and 9, because they have no overlap on either axis. Here you need an L-shaped connecting wall. Now you could pick a random point on the x edge of one and the y edge on the other and then draw two corridors extending from those points until they meet. But that might result in these two corridors to intersect a third, unrelated room (like room 0 in this example). The safest solution would be to draw the L-shaped corridor between the closest corners. I am not sure how exactly you calculate your minimum spanning tree, but I find it very likely that it is actually impossible to intersect another room that way. If it is possible, then try one direction and check if there is a collision with another room. If there is, try the other direction. If there is also a collision, then it seems impossible to connect this room and you might have to place it somewhere else or prune it.

Another approach would be to avoid such situations in the first place by modifying your room generation algorithm in a way that neighboring rooms will always have overlapping edges.

\$\endgroup\$
1
\$\begingroup\$

Ok so I found the solution and it's actually rather simple and elegant. Thanks to this article I was able to find out that the first step is to calculate the midpoint between 2 rooms. If the midpoint falls within the bounds of the rooms, then stretch a path across the midpoint to the bounds. Otherwise, make an 'L' shaped corridor from the center of one room to the center of the other.

Thanks to everyone that commented or posted an answer. Take a look at the images below to see what different generations of the map looks like enter image description here enter image description here enter image description here enter image description here

\$\endgroup\$
0
\$\begingroup\$

My solution might not be perfect, but I think it will be a good compromise between quality and accessibility:

You can make a "corridor" mesh (or few). Also, make a "regular wall" mesh, and a "entrance wall" mesh. The last one will be a normal wall, but with a hole where the corridor would be. Then, you can create the rooms like tiles, using the wall meshes. Wherever you need an entrace, use the wall mesh.

Finally to add the corridors, you could add the corridor mesh right between two entrances, and scale it properly along the length. A good idea is to keep the corridor mesh simple, so it won't look weird due to teh scaling.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.