# Left Right Straight Maze

How do I generate a Left, Right and Straight ordering for a maze for something like the following?

Similar to generating a left and right ordering for someone walking in real life.

(*custom styling*)
style = {Background -> GrayLevel[0],
BaseStyle -> {Directive[White, EdgeForm[], Opacity[1]]},
VertexShapeFunction -> (Rectangle[#1 + .16, #1 - .16] &),
EdgeShapeFunction -> (Rectangle[#1[[1]] + .16, #1[[2]] - .16] &)};
embedding = GraphEmbedding[GridGraph[{20, 30}]];

g = GridGraph[{20, 30}, EdgeWeight -> RandomReal[10, 1150]];
tree = FindSpanningTree[{g, 1}];
maze = Graph[tree, VertexCoordinates -> embedding, style];

HighlightGraph[maze, PathGraph[FindShortestPath[maze, 1, 600]]]


Extending off the posted question you get the following.

Column@ReplaceAll[choiceTurns, {-1. :>  "Left",0. :> "Straight",1. :> "Right"}]


Fun question. A simple but fast two-part solution which revolves around performing a 2D cross product on the coordinates of the vertices of the route to calculate the Left / Right / Straight, and then finding just those vertices at which a decision actually has to be made via their VertexDegree:

g = GridGraph[{20, 30}, EdgeWeight -> RandomReal[10, 1150]];
tree = FindSpanningTree[{g, 1}];
maze = Graph[tree, VertexCoordinates -> embedding, style];
route = FindShortestPath[maze, 1, 600];
path = PathGraph[route];

HighlightGraph[maze, path]


Produces your excellent looking maze (you should have put it in your question!):

1: Find vertices at which a decision must be made

decisionPoints = Pick[route, UnitStep[VertexDegree[tree][[route]] - 3], 1];
decisionIndices = Flatten[Position[route[[2 ;;]], #] & /@ decisionPoints];


2: Get list of L/R/S for whole route

Cross2D will return 1, 0, or -1 for a Left, Straight, or Right turn respectively.

Cross2D[u_, v_] := u[[1]] v[[2]] - u[[2]] v[[1]]

steps = Differences[GraphEmbedding[maze][[route]]];
turns = Cross2D @@@ Partition[steps, 2, 1];


3: Combine and plot

choiceTurns = turns[[decisionIndices]]

HighlightGraph[maze, {path,
Style @@@ Transpose[{
decisionPoints,
ColorData[{"BlueGreenYellow", {-1, 1}}] /@ choiceTurns
}]
}]
`

We therefore color only those vertices where a decision has to be made, with Yellow for Left, Green for Straight and Blue for Right: