[HN Gopher] Generating Mazes with Inductive Graphs (2017)
___________________________________________________________________
Generating Mazes with Inductive Graphs (2017)
Author : todsacerdoti
Score : 16 points
Date : 2025-04-28 18:01 UTC (4 hours ago)
(HTM) web link (jelv.is)
(TXT) w3m dump (jelv.is)
| tomfly wrote:
| where is the entrance and exit?
| Jaxan wrote:
| Doesn't matter, because all positions are reachable. So just
| pick any two positions at the border and remove a wall.
| kazinator wrote:
| Here is a maze that was generated recursively starting at the
| upper left cell. +
| +----+----+----+----+----+----+----+----+----+ | |
| | | | | |
| | + +----+----+ +----+ +----+ +----+ +
| | | | | | |
| | | | | +----+----+ +
| +----+----+----+----+----+ + | | |
| | | | | | |
| | + +----+----+ + +----+----+----+ + +
| | | | | | | |
| | | | | | + +----+
| + +----+----+----+ + +----+ | |
| | | | | | | |
| | | | +----+----+----+ + +----+----+----+
| + + | | |
| | | | | |
| + +----+----+----+ + +----+----+----+ + |
| | | | | | | | |
| | | | | | + + +
| + +----+ + +----+ + + | | | |
| | | | | | | | | | |
| | | | | + + + +
| +----+----+----+ + + + | | | | |
| | | | | | | | |
| | + + +----+ + +----+----+ +----+----+
| | | | | |
| | | |
| +----+----+----+----+----+----+----+----+----+ +
|
| It matters to start there because it will be easier if you go
| backwards.
|
| 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
|
| Stats: L - 33 U - 29 R - 20
| D - 18
|
| You see? Left and Up are more frequent back-to-entrance
| escapes than Right or Down. This is because of the way the
| maze was generated.
|
| Someone doing the maze backwards focusing on going left and
| up will guess right more often than not, which makes it
| easier.
| smartmic wrote:
| 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 wrote:
| 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.)
| kazinator wrote:
| 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.
___________________________________________________________________
(page generated 2025-04-28 23:01 UTC)