Auto Path in Dokapon Kingdom - how do they do it?

In the video game Dokapon Kingdom (here's an example video on it), the objective is to go around saving towns while simultaneously screwing over your friends (who will no longer be your friends). (It's been described as "Mario Party meets an RPG".)

Prominently featured within that game is the Auto Path function, which determines what spaces are reachable from the current space using a path of length $n$, namely, what the player rolled. Said path can loop multiple times, and can even end up turning around on itself, but it cannot traverse the same edge twice in a row (i.e. no sudden U-turns).

Translating the game board to a graph (and its associated adjacency matrix) is very easy, but how does one enforce the no sudden U-turns rule? Using the squared matrix with its diagonal zeroed out doesn't work, as that still allows a U-turn after every other edge taken.

• Depending on how long these paths are, they might just compute them all using some search algorithm Commented Jan 16, 2017 at 19:35
• The video you link to is 13 minutes long. Can you give a timestamp to the part where it shows the mechanic you're talking about? Commented Jan 16, 2017 at 19:49
• @HenningMakholm 6:33 is the first time it happens. Commented Jan 16, 2017 at 22:29

Just create a different graph where each node is labeled by the combination of "where you are" and "which edge you have just arrived by"; then iterate it $n$ times.