3
$\begingroup$

This question is a simplification of the one about finding the shortest path in a grid with turnstile and waypoints. Since this simplification has dramatic consequences, I think it deserve its own question and answer.

Here's a reminder of how the turnstile tiles work.

  • 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 this video at 7:02).

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

        On a turnstile tile         Exited the turnstile tile to the south

How do we find the shortest path from A to B in a grid maze with turnstiles?

$\endgroup$
2
$\begingroup$

Update: I'm accepting my own answer for now. If anyone want to make an answer with the full proof, I'll glady accept it.


Short answer: Encode the maze as a directed graph and apply your usual Dijkstra or A*, ignoring the state you leave the turnstiles in. The turnstiles can be encoded by having arcs both ways on the sides without bar, and only the out going arc for the sides with bars.

For instance, this turnstile:

        south-west turnstile

Can be turned into this graph portion:

        graph with a central node with 4  out edges and 2 in edges

Of course, don't connect the center node to its neighbor if it's not reachable (like a wall).

Long answer:

The essential property that make it work is that shortest paths never include cycles, even with those turnstiles.

Claim: Shortest path don't include cycles.

Idea of the proof:

Let's assume the shortest path $P$ between nodes $A$ and $B$ visit the same node $N_1$ twice. For $P$ to be the shortest path, there must be a node $N_2$ that we can access on the second visit to $N_1$ but not on the first visit. Otherwise reaching $N_2$ from $N_1$ on the first visit would lead to a path shorter than $P$.

But this situation cannot exist because unlocking the way between $N_1$ and $N_2$ requires visiting the blocking turnstile(s). Therefore there's no need to revisit $N_1$ to access $N_2$.

Then it follows that:

  • When looking for a shortest path, there's no need to consider revisiting nodes.
  • Thus the rotation of the turnstiles already visited can be completely ignored.
  • Since there is no additional state to keep track of, the usual Dijkstra or A* can be used.
$\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.