11

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?

Community
  • 1
  • 1
kazagistar
  • 1,537
  • 8
  • 20
  • So you have 2 types of Node, a room and a hallway, and a directed edge represent accessibility .. if you want to work on accessibility within the rooms too, you will need to change the definition of the node from a room to a block that the player can stack on, and the problem can be modeled with the physics\mechanics of the game – Khaled.K Mar 24 '14 at 08:25

2 Answers2

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.

Peter G
  • 1,613
  • 10
  • 10
0

The embedding part of this problem makes it a terrific mess, so I'm going to assume that we estimate the connection costs to obtain a directed graph, of which we want a minimum-cost strongly connected arc-subgraph. Then just find an embedding using a greedy algorithm.

For a 2-approximate solution in polynomial time: choose an arbitrary root vertex, then use the algorithm due to Chu--Liu and also Edmonds to compute minimum-cost rootward and leafward spanning arborescences. Return the union of these. This is a 2-approximation because every strongly connected arc-subgraph contains both a rootward and a leafward spanning arborescence (though not necessarily of minimum cost). I see now from one of your links that Keith Randall also had this idea.

There are any number of heuristics that you could implement. They may work quite well, but they're not really of interest to me. If you're concerned about them behaving badly, then you can "backstop" them with the previously mentioned 2-approximation.

If you really want an optimal solution, then your best bet is probably integer programming. Formulated as an integer program, this problem bears some resemblance to TSP. The program for TSP looks like this.

minimize sum_{v -> w} cost(v -> w) x(v -> w)
subject to
(-) for all v, sum_{v -> w} x(v -> w) = 1
(-) for all w, sum_{v -> w} x(v -> w) = 1
for all subsets S of vertices, sum_{v -> w, v in S, w not in S} x(v -> w) >= 1
for all v -> w, x(v -> w) >= 0

For your problem's program, we drop the constraints marked (-), which would force the arcs chosen to be a tour.

minimize sum_{v -> w} cost(v -> w) x(v -> w)
subject to
for all subsets S of vertices, sum_{v -> w, v in S, w not in S} x(v -> w) >= 1
for all v -> w, x(v -> w) >= 0

The dual of this program is as follows.

maximize sum_{subsets S of vertices} y(S)
subject to
for all v -> w, sum_{subsets S of vertices, v in S, w not in S} y(S) <= cost(v -> w)
for all subsets S of vertices, y(S) >= 0

Now we can adapt the branch and bound solution for TSP, for which there should be plenty of tutorial material out there. You won't have to do anything fundamentally new; in fact, you can focus on generating subtour constraints/variables, as the comb inequalities and the like don't apply to this problem.

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120