Ensuring a partially connected digraph is strongly connected

Question

Context

I am building a 3d game using procedural generation. I am trying to connect a number of pre-generated rooms in such a way that no matter what, a player can always reach any other room in the map. The rooms have "possible entry points" to which connecting hallways must attach. However, not all entry points are reachable from all other entry points within a room. For example, there might be a pit trap, so a player on the bottom would not be able to travel through the room to the top, and would have to find another way around.

Problem

Given a set of preexisting directed graphs embedded in a 3d space, add a set of (bidirectional) paths of minimal total length that connect the subgraphs into a larger graph. Failing that (since some research indicates that this is NP-Hard) make the paths as short as possible to compute in a short amount of time.

Work so far

My best solution is based off of this procedural generation post, where he creates a Delaney Triangulation of all nodes. I treat each strongly connected component of the rooms (eg. top floor and bottom floor of the pit trap) as separate nodes, and build the MST off that, but this limits some of the more interesting possibilities (for example, having to do through two 1-directional paths to get back to where you started).

---

Does anyone know of a better method for solving this problem?

Answer 1

Perhaps you can take better advantage of the fact that you're modeling 3d space. That implies you could partition the problem into a set of planar graphs, each one representing a different floor. You could start by building each floor to be strongly connected. Then when you join the floors (with probably just a few staircases and pit traps), perturb the solution by removing a few edges while still maintaining an overall strongly connected graph. Interesting choices for edges to remove would be ones that would cause the floor by itself to lose strong connectedness but maintain the property when other floors are considered. These are known as bridges, and there is a linear algorithm for finding them.

If you just count edges and not their lengths, solving for planar graphs (floors) in isolation would transform this into multiple Euclidean Steiner tree problems, which, while still NP-hard, can be solved using a near-optimal polynomial-time approximation scheme. However, you mentioned you wanted to minimize the total length of the paths, which makes this a rectilinear Steiner tree problem. Much research has been done on this problem due to its applicability to circuit design. Approximations exist that can come within a factor of 1.5 of optimal, which might work better for what you're doing: slightly longer hallways instead of all entrances in one place.