(* ::Package:: *)

(* ::Title:: *)
(*Mazes*)


(* Mazes in Mathematica: http://bit.ly/2tBFMnT *)


(* Clear variables. *)
ClearAll["Global`*"]
(* Limit variable scope to just this document. *)
SetOptions[EvaluationNotebook[], CellContext -> Notebook]
(* Set the current directory as the working directory. *)
SetDirectory[NotebookDirectory[]]


(* 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}]];


(* Create a graph with random edge weights. *)
g = GridGraph[{20, 30}, EdgeWeight -> RandomReal[10, 1150]];


(* Find the spanning tree of the graph containing the vertex 1. *)
tree = FindSpanningTree[{g, 1}];


(* Create the maze using the tree. *)
maze = Graph[tree, VertexCoordinates -> embedding, style]
Export["maze.png",maze]


(* Highlight the shortest path from 1 to 20*30=600. *)
HighlightGraph[maze, PathGraph[FindShortestPath[maze, 1, 600]]]
Export["maze-solution.png",%]