Generating Mazes with Inductive Graphs (2017)
7 comments
·April 28, 2025tomfly
where is the entrance and exit?
smartmic
From the book "Mazes for Programmers" by Jamis Buck, 2015, The Pragmatic Programmers (a must-read for any maze/programming enthusiast!):
> Aren't mazes supposed to have starting points and end points? […] honestly, […] it's entirely up to you. […] The maze […] is a perfect maze, and one of the attributes of a perfect maze is that there exists exactly one path between any two cells in it. […] You pick them, and there's guaranteed to be a path between them.
You do not need to choose an entrance or exit only on the sides, but you can also choose "Pacman-style" where the goal is to reach points inside the maze.
"Perfect" refers to the mathematical/logical properties of a maze (i.e. no loops), not the aesthetical aspect. I have not checked though if the mazes in the source here are all perfect.
kazinator
While you can put the entrance and exit wherever you want, if you know that the maze was generated by a recursive branching process which had a starting point somewhere, it probably behooves you to put the start at that point corresponding to the root of the tree, so that the maze wanderer faces the most branching choices.
Laying out the abstract maze tree into the rectilinear grid of cells obfuscates the tree somewhat, but not entirely. A process that generates from upper left to lower right, for instance, will tend to generate cells whose parent-headed exits going left and up more often than not, making the reverse direction a bit easier.
(Again, it depends on the maze generation process.)
Jaxan
Doesn’t matter, because all positions are reachable. So just pick any two positions at the border and remove a wall.
kazinator
Here is a maze that was generated recursively starting at the upper left cell.
+ +----+----+----+----+----+----+----+----+----+
| | | |
| | | |
+ +----+----+ +----+ +----+ +----+ +
| | | | |
| | | | |
+----+----+ + +----+----+----+----+----+ +
| | | | |
| | | | |
+ +----+----+ + +----+----+----+ + +
| | | | | |
| | | | | |
+ +----+ + +----+----+----+ + +----+
| | | | | |
| | | | | |
+----+----+----+ + +----+----+----+ + +
| | | |
| | | |
+ +----+----+----+ + +----+----+----+ +
| | | | | | |
| | | | | | |
+ + + + +----+ + +----+ + +
| | | | | | | | |
| | | | | | | | |
+ + + + +----+----+----+ + + +
| | | | | | |
| | | | | | |
+ + +----+ + +----+----+ +----+----+
| | | |
| | | |
+----+----+----+----+----+----+----+----+----+ +
The maze has 100 cells. For each cell, we can calculate which exit goes back toward the entrance, assigning the letters U, D, L, R:
U R R D L L R D L L
U L L D L U L L L U
R R U D D L L L L U
U L D L L R R D U U
U L L U D L L L U D
R R R U L R R R U D
U D R R U U R R D D
U D U U R U U D L D
U D U U D L L L U L
U L L U L R R U L L
L - 33
U - 29
R - 20
D - 18
Someone doing the maze backwards focusing on going left and up will guess right more often than not, which makes it easier.
trumpisaliberal
[dead]
Making random mazes in a rectilinear grid is a good exercise for one big reason: mazes are not all the same. Mazes have style can be very knotty and twisty, or have long passages. You can add hacks into a given algorithm to vary the style, but there are certain things it won't necessarily do.