Shortest walk in a grid with turnstiles and waypoint

Question

This video shows a grid maze with a type of tile that I'd call turnstiles.

The mechanics of those tiles are described below.

• A turnstile tile has two bars on adjacent sides of the tile.
• You cannot step into a turnstile tile if it would mean crossing a bar.
• You can exit a turnstile tile in any direction.
• If you exit the tile in a direction where there was one of the bars, then the pair of bars rotate by a 1/4 turn such that there's no more bar in the direction you exited the tile from (see video at 7:02).

Here's an example before and after exiting a turnstile tile:

               

Turns out, finding the shortest path from A to B in a maze containing this kind of tile is fairly easy. Long story short: even with turnstiles, the shortest path don't involve revisiting a node, therefore the usual algorithms work.

However, if we introduce a single waypoint, like fetching a key before going to the door, then we can no longer ignore the state in which we left the turnstiles. We might indeed revisit some tiles. Although taking the shortest path from A to K and then from K to B would produce a valid A-K-B walk, we can easily construct examples where this wouldn't produce the shortest walk overall, like this one:

       

I couldn't figure out a way to turn this problem into a regular shortest path without blowing up the graph size exponentially with the number of turnstiles.

So, if the problem of finding the shortest walk with a single waypoint in a grid maze with turnstiles is NP-hard, any idea of proof?

If it's not NP-hard, how do we find a solution efficiently?

Answer 1

I guess this is another non-answer.

---

$k$ waypoints $\in \mathrm{NP\ hard}$

The generalization of this problem ($k$ waypoints) is NP-hard even without turnstiles.

The reduction can be seen in Amiri et al. [1] from subset traveling salesman problem (TSP):

In the subset TSP, the task is to find a shortest closed walk that visits a given subset of vertices [38]. As optimal routes for WRP [Waypoint Routing Problem] and subset TSP traverse every edge at most twice, optimal solutions for both are identical when $\forall e \in E : c(e) \geq 2$.

Note that this also holds for planar graphs such as ours.

$1$ waypoint and $0$ turnstiles $\in \mathrm{P}$

That being said, when $k = 1$ and there are no turnstiles, we can solve this in polynomial time via a reduction to minimum cost integer flow (Amiri et al. [2]).

Indeed, the common endpoint $w$ can be leveraged to employ a reduction to an integer flow formulation: introduce a super-source $S^+$ and a super-destination $T^+$, connect $S^+$ to $s$ and $t$, and $T^+$ to $w$ with two links, all of unit capacity...

Next, solve the minimum cost integer flow problem from $S^+$ to $T^+$ with a demand of $2$. By performing flow decomposition and removing $S^+$, $T^+$, we obtain an $s - w$ and a $w - t$ flow, whose combined length is minimum.

---

$1$ waypoint and $k$ turnstiles and $c(e) = 1$ $\in \mathrm{NP\ hard}$, maybe?

If we restrict each edge to having capacity $1$, meaning it can only be included once in the shortest path, then we can make a reduction from the NP-complete $2$-link-disjoint paths problem. See section 2.3 of Amiri et al. [2] for the full proof. The idea is that with $c(e) = 1$ we can make our graph directed by using turnstiles to establish the direction of each edge.

However, this is only true for non-planar graphs. If we restrict it to planar graphs, the question appears to be open [3]. That being said, it is known to be in P under certain constraints [4], but still unclear for the general case.

$1$ waypoint and $k$ turnstiles and $c(e) = 2$ $\in$ ???

I'm not quite sure where your problem lies, but the allowance of turnstiles imposes a certain directionality on the graph even in the presence of $c(e) = 2$ which would incline me to believe this is NP-hard. Though, the results on the edge-disjoint path problem with congestion make me think there may be a poly time solution for $1$ waypoint.

---

$^1$ https://arxiv.org/abs/1708.09827

$^2$ https://arxiv.org/abs/1705.00055

$^3$ https://www.sciencedirect.com/science/article/pii/0304397580900092

$^4$ https://dl.acm.org/doi/10.1145/1132516.1132621

Answer 2

This is not an answer, but also too many words for a comment and I didn't want to post a handful of comments.

I am not sure if this is NP-hard or not, but I have some ideas for a proof.

---

Proving NP-hard

I would take an approach similar to the NP-hardness proof for Super Mario Bros. Please watch this lecture: https://youtu.be/7d73E1DiH0w?t=2851

First you would need to change your question to "Has Path" rather than "Shortest Path". That is, does there exist a path from start to finish at all? For example, the answer is clearly no for the following (where green is start and red is finish):

We can then try to reduce a given 3SAT instance to this problem. My idea is not complete, but the idea is to use turnstiles as boolean "switches" which will determine a literal true or false.

For example, let's say (A) means a literal is false and (B) means a literal is true:

We can construct variables in such a way that the given path from source to end only allows one of the literals to be true. For example, the following would be such a variable:

If the top path is taken then $x$ is true, if the bottom is taken then the $x$ is false. Notice that if the path were attempted $A \rightarrow \neg X \rightarrow X$ that $X$ would be blocked and could not be flipped unless we go back through $\neg X$ which would flip $\neg X$ back to false. So this is a valid gadget that says "$X$ can only be true or false and the path from $A$ to $B$ will determine that value."

Next we need to construct a clause gadget. My idea for this would be to essentially have a similar setup to the example above where every instance of $X$ can be "set" to true at the same time by flipping its turnstile OR every instance of $\neg X$ can be "set" to true at the same time by flipping its turnstile but NOT both.

We need to construct this clause gadget in such a way that the literal and its negation cannot be both true at the same time. My idea was the following.

Let's say we have a SAT formula: $(x \lor \ldots) \land (\neg x \lor \ldots)$. We could construct a clause like:

If we had $x$ in multiple clauses like: $(x \lor \ldots) \land (\neg x \lor \ldots) \land (x \lor \ldots)$. We could have the following:

The important thing to note here is that you can't flip the $x$ turnstiles while also flipping the $\neg x$ turnstiles.

Then if we have multiple variables like: $(x \lor y \ldots) \land (\neg x \lor y \ldots) \land (x \lor \neg y \ldots)$. We would first route the path through $x$ then through $y$:

Again note that if we tried to choose $x$, the $x$ and $\neg x$ paths reconnect when routing to $y$. However, going "back" one path you would still not be able to "set" the other turnstiles because they are blocking a backward entrance due to their positioning, so the only route forward after $x$ is determine is to continue on to $y$ if you want to make it from start to finish.

For example, a valid solution to our 3SAT formula would be $x$ is true and $y$ is true. This would correspond to the following path from start ($x$) to finish (red). The path is shown in green:

---

The last thing we would need to do is verify that all clauses have at least one turnstile "switched" on. You can see in my example we could also get a path from start to finish with $x$ is false and $y$ is false even though this does not satisfy the 3SAT formula.

In the Super Mario example, the clauses are verified by "unlocking" a super star which allows Mario to survive a flame walk to the end. We don't exactly have this luxury in our game. By flipping our turnstiles we can't "unlock" anything special, like a path to the end. You could attempt to accomplish this with waypoints, but the waypoints don't actually add much because a path could go to the waypoint, then go exactly back to start and continue on as normal and it has effectively "visited" the waypoint without having to change its solve path.

One idea I had for "unlocking" something by completing a clause was the following:

If $x$, $y$ or $z$ are "set" then they can (exactly one at a time) go into the bottom chamber and flip the turnstile blocking upward entry from A. The idea would be that if you put a waypoint below A for each clause and you hook up the end of the variable chain to the right most A then you hook up B to the A of the clause to the left and chain them together like that. Then the B of the leftmost clause would be the end. The issue is what I just mentioned, we could just go to the way points then go all the way back to the start, then just set a literal in the first clause an exit.

So these would be my main ideas for constructing a reduction, however its clearly incomplete. If we added in "one-way" blocks or waypoints that only allowed the path to go in one direction but not back then I think this may work because you could trap a regular waypoint behind a one-way block.

---

The other big issue I did not mention but you would realize if you watched the Super Mario reduction is that the graph I have been showing is non-planar whereas the game is played on a planar graph. We would also need someway to establish crossovers which I think is nontrivial. One idea would be to do something like this:

This is clearly an issue however because if the green path was the "exit" of setting $x$ and the red path was the "entry" of setting $\neg x$ in a clause then you could exit setting $x$ and turn right to effectively also set $\neg x$. This is not allowed.

So you would need to resolve these crossovers as well.

Hopefully someone can take some of these ideas and run with them. It has the vibes of an NP-hard problem since you can essentially encode the turnstiles as bits and almost encode a 3SAT equation into them, but I'm not convinced yet.

Answer 3

To decide if there is a path in $O(N)$ for a $N$ cells maze , you can simply run a BFS from start (As ryan already said, here, one should not talk of Dijkstra meaning priority queue...). So if you can reach both, the waypoint and the exit, it exists a solution.

Proof

You already proved that on a simple path, there is no need to consider the re-orientation of turnstiles. Indeed, you already reached this cell.

Another point is that you can always go back your path as turnstiles always get open to the leaving direction. So any cell reachable from start is reachable from any other reached cell, and in particular, the waypoint.

This of course does not guarantee you find the shortest path, your exemple shows it perfectly. But gives you an upper bound.