12
$\begingroup$

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]]]

enter image description here (edit picture added)

Extending off the posted question you get the following.

Column@ReplaceAll[choiceTurns, {-1.` :>  "Left",0.` :> "Straight",1.` :> "Right"}]
$\endgroup$
12
$\begingroup$

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:

Using your style def

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!):

enter image description here

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:

enter image description here

$\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.