RandomLabyrinth

Generate random labyrinths

DefinitionResourceCreateNotebook

Clear[RandomLabyrinth,PropertiesQ];
Options[RandomLabyrinth]=Join[
{"GridLayout"->Automatic},
Options[Graph]
];
defaultOptions={VertexShapeFunction->None,EdgeShapeFunction->({Opacity[1],DarkBlue,AbsoluteThickness[12],Line[#1]}&),ImageSize->Large};
PropertiesQ[x_]:=MatchQ[x,_String|{_String..}|All|Automatic];
RandomLabyrinth[_,"Properties"]:={"Walls","Paths","Solution","Start","End"};
RandomLabyrinth[n_?Positive,props_:Automatic,Longest[opts:OptionsPattern[RandomLabyrinth]]]:=RandomLabyrinth[{n,n},props,opts];

RandomLabyrinth[{n_?Positive,m_?Positive},propsArg_:Automatic,Longest[opts:OptionsPattern[RandomLabyrinth]]]:=
Block[{props=propsArg,expectedProperties=RandomLabyrinth[None,"Properties"],aRes},
aRes=
If[MemberQ[{"Hexagonal","Hex","Hexagon","HexagonalGrid"},OptionValue[RandomLabyrinth,"GridLayout"]],
HexagonalMaze[{n,m},FilterRules[{opts},Options[Graph]],defaultOptions],
(*ELSE*)
RectangularMaze[{n,m},FilterRules[{opts},Options[Graph]],defaultOptions]
];
If[TrueQ[props===Automatic],props="Walls"];
props=Intersection[Flatten[{props}],Append[expectedProperties,All]];
If[Length[props]==0,props={All}];
Which[
MemberQ[props,All],aRes,
Length[props]==1,aRes[props[[1]]],
True,KeyTake[aRes,props]]
]/;PropertiesQ[propsArg];

Clear[RectangularMaze];
RectangularMaze[{n_?Positive,m_?Positive},opts:OptionsPattern[]]:=
Module[{g1,g2,g3,g4,g5,g6,mazePath,solution,i,j,i2,j2},
g1=GridGraph[{n,m}];g1=VertexReplace[g1,Thread[VertexList[g1]->Map[w@@QuotientRemainder[#-1,n]&,VertexList[g1]]]];
g2=GridGraph[{n-1,m-1}];
g2=VertexReplace[g2,Thread[VertexList[g2]->Map[QuotientRemainder[#-1,n-1]&,VertexList[g2]]]];
g2=Graph[g2,VertexLabels->"Name",VertexCoordinates->Map[#+{1,1}/2&,GraphEmbedding[g2]]];
mazePath=Graph[EdgeList[g2],EdgeWeight->RandomReal[{10,1000},EdgeCount[g2]]];
mazePath=FindSpanningTree[mazePath,VertexCoordinates->Thread[VertexList[g2]->GraphEmbedding[g2]]];
g3=Graph[
Join[EdgeList[g1],EdgeList[mazePath]],VertexCoordinates->Join[Thread[VertexList[g1]->GraphEmbedding[g1]],Thread[VertexList[mazePath]->GraphEmbedding[mazePath]]]];
g4=Graph[g3,VertexLabels->None];
Do[
{i,j}=e[[1]];
{i2,j2}=e[[2]];
If[i2<i||j2<j,{{i2,j2},{i,j}}={{i,j},{i2,j2}}];

(*Horizontal*)
If[i==i2&&j<j2,
g4=EdgeDelete[g4,UndirectedEdge[w[i2,j2],w[i2+1,j2]]]
];

(*Vertical*)
If[j==j2&&i<i2,
g4=EdgeDelete[g4,UndirectedEdge[w[i2,j2],w[i2,j2+1]]]
];
,{e,EdgeList[mazePath]}];
g5=Subgraph[g4,VertexList[g1]];
g5=VertexDelete[g5,{w[0,0],w[m-1,n-1]}];
g6=Graph[g5,opts];
solution=FindShortestPath[#,VertexList[#][[1]],VertexList[#][[-1]]]&@mazePath;
<|"Walls"->g6,"Paths"->mazePath,"Solution"->solution,"Start"->solution[[1]],"End"->solution[[-1]]|>
];

HexagonalMaze[{n_?Positive,m_?Positive},opts:OptionsPattern[]]:=
Module[{g1,g2,g3,g4,g5,mean,mazePath,finder,aMazePathCoords,points,vs,aVertexCoordinates,start,end,solution},
g1=ResourceFunction["HexagonalGridGraph"][{m,n}];g1=VertexReplace[g1,Thread[VertexList[g1]->Map[w[#]&,VertexList[g1]]]];
g2=ResourceFunction["https://www.wolframcloud.com/obj/antononcube/DeployedResources/Function/TriangularLatticeGraph/"][{n-1,m-1}];g2=Graph[g2,VertexCoordinates->Map[#+{(Sqrt[3]),1}&,GraphEmbedding[g2]]];
mazePath=Graph[EdgeList[g2],EdgeWeight->RandomReal[{10,10000},EdgeCount[g2]]];
mazePath=FindSpanningTree[mazePath,VertexCoordinates->Thread[VertexList[g2]->GraphEmbedding[g2]]];
g3=GraphUnion[g1,mazePath,VertexCoordinates->Join[Thread[VertexList[g1]->GraphEmbedding[g1]],Thread[VertexList[mazePath]->GraphEmbedding[mazePath]]]];
finder=Nearest[Thread[GraphEmbedding[g1]->VertexList[g1]]];
aMazePathCoords=Association@Thread[VertexList[mazePath]->GraphEmbedding[mazePath]];
g4=g1;
Do[
points=Map[aMazePathCoords[#]&,List@@e];
mean=Mean[points];
vs=finder[mean];
g4=EdgeDelete[g4,UndirectedEdge@@vs];
,{e,EdgeList[mazePath]}];
aVertexCoordinates=Association@Thread[VertexList[g4]->GraphEmbedding[g4]];
{start,end}=Keys[Sort[aVertexCoordinates]][[{1,-1}]];
solution=FindShortestPath[mazePath,Sequence@@Keys[Sort[aMazePathCoords]][[{1,-1}]]];
(*solutionGraph=PathGraph[solution,VertexCoordinates->Lookup[aMazePathCoords,solution]];*)
g5=Graph[g4,opts];
g5=VertexDelete[g5,{start,end}];
<|"Walls"->g5,"Paths"->mazePath,"Solution"->solution,"Start"->solution[[1]],"End"->solution[[-1]]|>
];

Documentation

UsageResourceCreateNotebook

Details & OptionsResourceCreateNotebook

RandomLabyrinth generates labyrinths based on regular rectangular (default) or hexagonal grid graphs.

RandomLabyrinth supports the option of Graph, along with the option "GridLayout" which can be set to "Hexagonal" to create a hexagonal labyrinth.

The supported properties for prop are: "Walls", "Paths", "Solution", "Start", "End" and All. RandomLabyrinth[size,"Properties"] gives the list of supported properties.

ExamplesResourceCreateNotebook

Basic Examples

Make a random rectangular grid labyrinth:

SeedRandom[3];
RandomLabyrinth[{10,20}]

Scope

Make a random hexagonal grid labyrinth:

RandomLabyrinth[{8,16},"GridLayout"->"Hexagonal"]

RandomLabyrinth can be given different properties:

RandomLabyrinth[10,"Properties"]

If the properties argument is All, then an association with all properties is returned:

RandomLabyrinth[5,All,ImageSize->Tiny]

Options

GridLayout

The option "GridLayout" specifies the type grid graphs used to make the labyrinth. It takes the values "Rectangular" and "Hexagonal":

RandomLabyrinth[7,"GridLayout"->#,ImageSize->{Automatic,200}]&/@{"Rectangular","Hexagonal"}

Applications

Make a rectangular grid labyrinth and show it together with a solution:

res=RandomLabyrinth[{12,24},{"Walls","Paths","Solution"},ImageSize->800];
Show[res["Walls"],HighlightGraph[#,#]&@Subgraph[res["Paths"],res["Solution"]]]

Make a hexagonal grid labyrinth and show it together with a solution:

res=RandomLabyrinth[{16,20},{"Walls","Paths","Solution"},"GridLayout"->"Hexagonal",ImageSize->900];
Show[res["Walls"],HighlightGraph[#,#]&@Subgraph[res["Paths"],res["Solution"]]]

Generate 100 labyrinths:

SeedRandom[55];
AbsoluteTiming[
labs=Table[RandomLabyrinth[10,{"Walls","Paths","Solution"},ImageSize->Small],100];
]

Show the histogram of the shortest path solution lengths:

Histogram[Length[#Solution]&/@labs,]

Show the labyrinths with the smallest and largest shortest paths solutions:

Show[#Walls,HighlightGraph[#,#]&@Subgraph[#Paths,#Solution],ImageSize->230]&/@SortBy[labs,Length[#Solution]&][[{1,-1}]]

Possible Issues

For larger size values the labyrinth generation might be slow, especially, for hexagonal labyrinths:

AbsoluteTiming[RandomLabyrinth[50,"GridLayout"->"Hexagonal",]]

The making of rectangular labyrinths with same size parameters is faster:

AbsoluteTiming[RandomLabyrinth[50,"GridLayout"->"Rectangular",]]

Neat Examples

Larger rectangular grid maze:

SeedRandom[44];
RandomLabyrinth[{30,60},EdgeShapeFunction->({Opacity[1],DarkBlue,AbsoluteThickness[6],Line[#1]}&),ImageSize->800]

A larger hexagonal grid maze with its largest connected components colored:

SeedRandom[184];
g=RandomLabyrinth[{20,40},"GridLayout"->"Hexagonal",EdgeShapeFunction->Automatic,ImageSize->800];
HighlightGraph[g,Map[Subgraph[g,#]&,ConnectedComponents[g][[1;;2]]],EdgeShapeFunction->({Opacity[1],AbsoluteThickness[4],Line[#1]}&)]

A grid of tiny labyrinths:

SeedRandom[9987];
Multicolumn[Table[RandomLabyrinth[RandomInteger[{6,7}],ImageSize->Tiny],36],6]

Source & Additional Information

Contributed ByResourceCreateNotebook

Anton Antonov

KeywordsResourceCreateNotebook

labyrinth

maze

graph

hexagonal graph

grid graph

CategoriesResourceCreateNotebook

Related SymbolsResourceCreateNotebook

Related Resource ObjectsResourceCreateNotebook

HexagonalGridGraph

TriangularLatticeGraph

RandomMaze

Source/Reference CitationResourceCreateNotebook

Source, reference or citation information

LinksResourceCreateNotebook

Maze making using graphs

TestsResourceCreateNotebook

RandomLabyrinth[5]

RandomLabyrinth[{5,19},All]

RandomLabyrinth[{5,19},{"Walls","Solution"}]

RandomLabyrinth[{5,19},{"Walls","Paths","Solution"},"GridLayout"->"Hexagonal"]

CompatibilityResourceCreateNotebook

Wolfram Language VersionResourceCreateNotebook

14.2+

Operating SystemResourceCreateNotebook

EnvironmentsResourceCreateNotebook

Cloud SupportResourceCreateNotebook

Required FeaturesResourceCreateNotebook

Author NotesResourceCreateNotebook

Additional information about limitations, issues, etc.

Submission NotesResourceCreateNotebook

(2026-01-02) Added timed evaluations with larger labyrinth sizes.

(2026-01-05) Changed the "Type" option into "GridLayout".