Introduction
Introduction
This notebook describes three ways of making mazes (or labyrinths) using graphs. The first two are based on rectangular grids; the third on a hexagonal grid.
TL;DR
TL;DR
Just see the maze pictures below. (And try to solve the mazes.)
Procedure outline
Procedure outline
The first maze is made by a simple procedure which is actually some sort of cheating:
◼
A regular rectangular grid graph is generated with random weights associated with its edges.
◼
The (minimum) spanning tree for that graph is found.
◼
That tree is plotted with exaggeratedly large vertices and edges, so the graph plot looks like a maze.
◼
This is "the cheat" — the maze walls are not given by the graph.
The second maze is made "properly":
◼
Two interlacing regular rectangular grid graphs are created.
◼
The second one has one less row and one less column than the first.
◼
The vertex coordinates of the second graph are at the centers of the rectangles of the first graph.
◼
The first graph provides the maze walls; the second graph is used to make paths through the maze.
◼
In other words, to create a solvable maze.
◼
Again, random weights are assigned to edges of the second graph, and a minimum spanning tree is found.
◼
There is a convenient formula that allows using the spanning tree edges to remove edges from the first graph.
◼
In that way, a proper maze is derived.
The third maze is again made "properly" using the procedure above with two modifications:
◼
Two interlacing regular grid graphs are created: one over a hexagonal grid, the other over a triangular grid.
◼
The hexagonal grid graph provides the maze walls; the triangular grid graph provides the maze paths.
◼
Since the formula for wall removal is hard to derive, a more robust and universal method based on nearest neighbors is used.
Simple Maze
Simple Maze
In this section, we create a simple, "cheating" maze.
Remark: The steps are easy to follow, given the procedure outlined in the introduction.
In[]:=
RandomSeed[3021];{n,m}={10,25};g=GridGraph[{n,m}];gWeighted=Graph[VertexList[g],UndirectedEdge@@@EdgeList[g],EdgeWeight->RandomReal[{10,1000},EdgeCount[g]]];Information[gWeighted]
Out[]=
Find the spanning tree of the graph:
In[]:=
mazeTree=FindSpanningTree[gWeighted];
Shortest path from the first vertex (bottom-left) to the last vertex (top-right):
In[]:=
path=FindShortestPath[mazeTree,1,n*m];Length[path]
Out[]=
46
Graph plot:
In[]:=
simpleMaze=Graph[VertexList[mazeTree],EdgeList[mazeTree],VertexCoordinates->GraphEmbedding[g]];simpleMaze2=EdgeAdd[simpleMaze,{"start"->1,Max[VertexList[simpleMaze]]->"end"}];Clear[vf1,ef1];vf1[col_?ColorQ][{xc_,yc_},name_,{w_,h_}]:={col,EdgeForm[None],Rectangle[{xc-w,yc-h},{xc+w,yc+h}]};ef1[col_?ColorQ][pts_List,e_]:={col,Opacity[1],AbsoluteThickness[22],Line[pts]};grCheat=GraphPlot[simpleMaze2,VertexSize->0.8,VertexShapeFunctionvf1[White],EdgeShapeFunction->ef1[White],Background->DarkBlue,ImageSize->800,ImagePadding->0];range=MinMax/@Transpose[Flatten[List@@@Cases[grCheat,_Rectangle,∞]〚All,All〛,1]];Show[grCheat,PlotRange->range]
Out[]=
The "maze" above looks like a maze because the vertices and edges are rectangular with matching sizes, and they are thicker than the spaces between them. In other words, we are cheating.
To make that cheating construction clearer, let us plot the shortest path from the bottom left to the top right and color the edges in pink (salmon) and the vertices in red:
In[]:=
gPath=PathGraph[path,VertexCoordinates->GraphEmbedding[g]〚path〛];Legended[Show[grCheat,Graph[gPath,VertexSize->0.7,VertexShapeFunctionvf1[Red],EdgeShapeFunction->ef1[Pink],Background->DarkBlue,ImageSize->800,ImagePadding->0],PlotRange->range],SwatchLegend[{Red,Pink,DarkBlue},{"Shortest path vertices","Shortest path edges","Image background"}]]
Out[]=
Proper Maze
Proper Maze
A proper maze is a maze given with its walls (not with the space between walls).
Remark: For didactical reasons, the maze in this section is small so that the steps—outlined in the introduction—can be easily followed.
Make two regular graphs: one for the maze walls and the other for the maze paths.
In[]:=
{n,m}={6,12};g1=GridGraph[{n,m},VertexLabels->"Name"];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]]];Grid[{{"Wall graph","Paths graph"},{Information[g1],Information[g2]}}]
Out[]=
Wall graph | Paths graph |
See how the graph “interlace”:
In[]:=
(*Show[g1,HighlightGraph[g2,g2],ImageSize->800]*)
Maze Path Graph:
In[]:=
mazePath=Graph[EdgeList[g2],EdgeWeight->RandomReal[{10,10000},EdgeCount[g2]]];mazePath=FindSpanningTree[mazePath,VertexCoordinates->Thread[VertexList[g2]->GraphEmbedding[g2]]];Information[mazePath]
Out[]=
Combined Graph:
In[]:=
g3=Graph[Join[EdgeList[g1],EdgeList[mazePath]],VertexCoordinates->Join[Thread[VertexList[g1]->GraphEmbedding[g1]],Thread[VertexList[mazePath]->GraphEmbedding[mazePath]]],VertexLabels->"Name"];Information[g3]
Out[]=
Plot the combined graph:
Remove wall edges using a formula:
Plot wall graph and maze paths (maze space) graph:
Fancier maze presentation with rectangular vertices and edges (with matching sizes):
Here is how a solution can found and plotted:
Hexagonal Version
Hexagonal Version
Let us create another maze based on a hexagonal grid. Here are two grid graphs:
◼
The first is a hexagonal grid graph representing the maze's walls.
◼
The second graph is a triangular grid graph with one fewer row and column, and shifted vertex coordinates.
Maze Path Graph:
Combine the walls-maze and the maze-path graphs (i.e., make a union of them), and plot the resulting graph:
Make a nearest neighbor points finder functor:
Take a maze edge and its vertex points:
Find the edge's midpoint and the nearest wall-graph vertices:
Loop over all maze edges, removing wall-maze edges:
Here is the obtained graph
The start and end points of the maze:
Finding the Maze Solution:
Plot the maze:
Here is the solution of the maze:
Additional Comments
Additional Comments
◼
The notebook can be used to compare the graph functionalities of Wolfram Language with those of Raku.
◼
◼
Here are the special graph functionalities used to create the mazes:
◼
Construction of regular grid graphs
◼
Construction of hexagonal grid graphs
◼
Construction of triangular grid graphs
◼
Subgraph extraction
◼
Edge deletion
◼
Graph highlighting
◼
The edge removal can be done with RegionDisjoint instead of using Nearest.
◼
And that approach would be more robust if graphs with irregular embedding are used.
References
References
Articles, Blog Posts
Articles, Blog Posts
[AA1] Anton Antonov, “Day 24 – Maze Making Using Graphs”, (2025), Raku Advent Calendar at WordPress .
Functions
Functions
Packages
Packages
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Maze making using graphs based on rectangular and hexagonal grids
by Anton Antonov
Wolfram Community, STAFF PICKS, December 26, 2025
https://community.wolfram.com/groups/-/m/t/3597439
by Anton Antonov
Wolfram Community, STAFF PICKS, December 26, 2025
https://community.wolfram.com/groups/-/m/t/3597439