Building maze to maximize shortest path, may be given waypoints and teleports

Question

How would you go about solving this problem? Is it something that could be expected to be computed/solved within a couple of hours of given a starting area with (32) threads on 3.0GHz Xeon cores? (Assuming sizes between 8x8 and 30x30. Using C or C++ if that matters) Or, is this so complex that it would take way longer?

There is an area, where an automated traveler follows a shortest path algorithm at all times. Playing the builder, find the way to maximize the number of points the traveler must visit.

The area is typically between 8x8 and 30x30, given in the form:

.F......
......a.
........
........
.....1X.
........
.A......
........
..O.....
.X......
..X.....
..X.....

Where there is:

• Always a single O, the starting point
• Always a single F, the ending point
• Always many ., empty points that can either be traveled or built on
• Sometimes X, points designating they are blocked for traveling or building
• Sometimes pairs of letters (i.e. A and a, but never F, O, or X), indicating a teleport when visiting the uppercase letter for the first time to the lowercase letter
• Sometimes numbers (i.e. 1), designating waypoints

The automated traveler follows a shortest path algorithm at all times. It must begin at the starting point, if there are waypoints pass over them in order, and finish at the ending point. The traveler may pass over the ending point or subsequent waypoints early, but the game doesn't end and the waypoints aren't counted as visited, until they are the active next destination. If there are any, the traveler must not pay attention to any teleport spots; they must take the shortest path between points as if they cannot see these teleport spots. The exception to this rule is if there are multiple paths with the shortest length between last source to next destination and one of them travels through an active teleport spot, the path with the teleport must be taken. (Otherwise, can choose any of the multiple shortest paths.) If the shortest path forces them into a teleport spot, they teleport the first time they visit the uppercase letter to the corresponding lowercase letter. The traveler can move horizontally and vertically. The traveler can move diagonally between two points if the 2x2 square containing both points is clear of blocking points.

So, if the traveler needs to travel from the lower left to upper right point, here they can move diagonally and only count 2 moves:

..
..

But here, again traveling from the lower left to upper right point, they cannot move diagonally and must count 3 moves:

X.
..

The game always starts with an open path to reach all required destinations.

You, the builder, get to take all of your actions first, and none once you decide you are complete and allow the traveler to begin. The builder can place additional X points that block travel on them, but they cannot make it impossible to reach any of the required destinations. The builder cannot place any other points, such as more teleports or waypoints. The builder cannot remove anything given to them already in the area (other than replace empty points.) Strategy may include blocking points to force: otherwise out of the way travel; backtracking; and traveling between teleports. Optimal strategy might include trying to connect the starting, ending, and destination teleport spots in short paths, and forcing a long backtracking path to waypoints.

This is to come up with possible strategies for a tower defense game. Certain aspects of the game, such as multiple waves, limitations on resources, and attack towers, are ignored to simplify and just focus on the maze-like aspect of the game.

Answer 1

Just a note: even the simpler version without waypoints and teleports is NP-hard:

Start with a maze in which the dots mimic the edges of a grid graph $G$ of max degree 3, and $X$s are placed "around" them (the dots are "corridors"). Put the $O$ in a corner and the $F$ near it with a dot in the middle.

Maximizing the shortest path (adding more Xs) is equivalent to finding an Hamiltonian path in the original graph $G$ which is NP-complete (each new $X$ must block a "corridor", i.e. it removes an edge of $G$).

Answer 2

Unfortunately this sounds related to the max-cut problem, which is NP-complete. (I.e. essentially impossible even for relatively small input sizes.) 8x8 is already stretching it, but maybe the constraints on the problem means we can come up with an algorithm that will cope with that size, and if we're very lucky will go up to 30x30.

Actually, see bottom for my final attempt, that I think could easily succeed within the allotted time, and generate an optimal solution.

Back of the envelope

Assume an empty 8x8 grid. We could brute force all the squares being "wall" or "not wall". This would leave us with 2⁶⁴ combinations, which is totally impossible. OK, if more than half of the squares are walls then there are not enough squares to form a longer path than if there were fewer walls. So we can maybe cut it down to 2³², which is 4 billion.

OK, 4 billion is actually manageable. Each configuration would require a breadth-first search which we'll assume takes 100ns. That's 10000 per core per second. 2³² / 10000 / 32 = 4 hours. The breadth-first search could take 100 times as long due to going back and forth between waypoints, I'm not sure. So, could be 400 hours. Going to 9x9 makes things take 25 times as long. Ouch.

First thought

Let's think about choosing paths rather than walls. First we explore paths to the first waypoint, then the second, etc.

Of course this allows paths that can go round in circles forever. But we can fix that by pruning paths that "return" to already visited nodes without having hit any more waypoints (because they are clearly not the shortest path anymore). Is there a nice way to detect that?

This "already visited nodes" thing reminds me of Dijkstra's algorithm. It would be good if we could just take the "best" (longest shortest) path to a waypoint. But I think there may be a problem with the choice of previous paths influencing where walls might go. Furthermore, the "longest" path to waypoint 1 may decrease the "longest" path to waypoint 2, so we can't just keep track of the longest path to waypoint x.

It takes walls in a certain place to "force" a path to go a certain way, but this can be overdone e.g. when there are two similar paths of equal length, you don't need to use walls to block one off.

Well, we could keep a list of possible wall configurations for every path from the start to waypoint X, and then start with each of those as we head for the next waypoint. Only walls adjacent to the path matter; all the rest of the space is "don't care". In fact, sometimes even walls adjacent to a path can be "don't care", as long as they would not create a shorter path to the waypoint.

It still seems like an intractable number of cases. But not necessarily. There are not that many ways to take an empty grid (start and end in opposite corners) and create a maximum length snaking path. As you make the path shorter, fewer squares get covered so more of them become "don't care". (What kind of crazy data structure you would need, I don't care ;)

Would this make the problem tractable, even for 8x8 grids? I'm not sure. On its own, I doubt it.

Second thought

We could try to find the "best" partitioning of the space so that there are as many "mandatory crossings" as possible. E.g. if 1, 3 and 5 are on one side and O, 2, 4, and * are on the other, there are 6 crossings. A partition is a continuous path composed of horizontal, vertical, or diagonal segments. (Let's also say that it cannot be more than the side length of the maze, e.g. for 8x8 maze the partition path cannot be more than 8 points.)

There must be a "gap" in this partition and it will be on ALL paths through the maze.

I posit that all crossings between "actual" waypoint hits must go through the same gap (otherwise there are simply more choices which allows for shorter paths between waypoints.) So can we try each node along the path in turn, and then "divide and conquer" on the two sides of the partition, and see which comes out best?

Sadly, no, because there may be other gaps where some paths "cross back over" to form loops that add steps, or travel along the partition path itself.

Maybe dynamic programming can help, but as the crossings-over can have a big impact on the other side of the partition, I think further additions to this approach will be necessary.

Divide and conquer?

Well, what if we chop the grid into quarters? For an $n\times n$ grid, this means the side length of each quarter is of length $\frac{n}{2}$. Then we divide again, and those quarters have boundaries of length at most $\frac{n}{4}$, etc. (For simplicity ignore diagonals.) For each of these subdivisions, we need to create some information about its perimeter so that it can be "stitched" to its neighbour. We will begin at the level of individual squares, combine each of them with a neighbours (yielding 1x2 blocks), combine these blocks with their neighbours (4x4 blocks), and so on until we hit the total maze size.

So here's my proposal, which hopefully will work. For each subdivision, we can list all "candidate" configurations of the space within. For each of these candidates, we store:

for each of the 4 sides:
    for each pair of edge pieces:
        for each possible run of consecutive waypoints (including none)
            { minimum path length, list of waypoints included }

"For each pair of edge pieces" is roughly $m^2$ for a subdivision with side length $m$. This is excellent!! I was expecting something exponential.

Yes, when stitching we need to combine every configuration of one subdivision against every configuration of another. That's on the order of $m^4$. But then we can throw out a lot of duplicate configurations, or configurations that are identical except for a shorter path somewhere than another one, or configurations where waypoints are lost. This is why I said "candidate" configurations above.

This would be tough to implement, but I would hazard to say this would take a short time to get an optimal answer for 30x30. If we are talking $m^4\log m$ we are talking a few thousand times some large constant. Even if that large constant is 0.1 seconds, we are talking about 5 minutes. I think 0.1 seconds is an overestimate, even on 1 core. (This algorithm would be very fiddly to parallelise anyway.)

What about teleporters? Perhaps along with the other information, have flags which say "teleporter x may come out of this edge", and also add cases for every combination of waypoints that sort of say "getting to this waypoint WILL teleport you the first time you take it" or "getting a longer shortest path length WILL teleport you the first time you take it". Then those things are combined to figure out if the teleport actually gets taken and calculate accordingly.

So there you have it. You probably wanted something easier to implement (even if non-optimal), but hey, this is the Computer Science stack exchange.

Implementation notes

Implementing this sounded fun, so I decided to give it a go. Although I think I'm close, it's running up to some 400 lines of Python, and debugging is probably going to be a nightmare. So I'm giving up.

My WIP is too long to reasonably post, but I thought I would write some notes here in case anyone wants to try.

The strategy is to divide-and-conquer, halving along the longest side until you get to 1x1 tiles. There's a "Boundary conditions" object which lists all distinct paths from any edge segment to any other edge segment (including from a segment to itself, this is required e.g. for the case where you go through the edge, hit a waypoint, then go back across the same edge).

These paths are culled based on the assumption that the player will choose the best path. This is done by giving each path a set() of properties, and any path that is a subset of another path and has $\geq$ length is culled.

Merging two adjacent subsections of the grid is done by first taking the common edge, and computing all possible paths from each segment of that edge to each other segment (including itself). Then, a new "Boundary conditions" object is constructed by taking all its outside segments and computing all paths from them to all others. E.g. for the left half, the existing paths are considered, but also all paths that hit the "common edge" in between. The set of paths is culled.

Starting from the 1x1 squares and building upwards, each subsection of the grid has a list of many potential boundary conditions. These represent different possible internal configurations (but some internal configurations produce the same boundary conditions so can be forgotten). Each merge involves taking all possible boundary conditions of one section and merging them with all possible boundary conditions of the other.

But doesn't each 1x1 square start out with the just 1 boundary condition and so the larger sections also have 1 each? Well, not quite. Empty spaces have two potential boundary conditions: those that leave them empty and those where a wall has been built.

Starts, ends, waypoints and teleporters can all be handled using a path's set of "properties". When a path contains the start, end, and ordered waypoints properties, it causes all other paths to be culled during its processing step, and becomes a candidate solution.

Oh the complexity...