[HN Gopher] Maze Algorithms (1997)
___________________________________________________________________
Maze Algorithms (1997)
Author : marukodo
Score : 84 points
Date : 2026-03-31 21:43 UTC (3 days ago)
(HTM) web link (www.astrolog.org)
(TXT) w3m dump (www.astrolog.org)
| fjfaase wrote:
| Are there also algorithms for (incremental) generation of
| infinite mazes?
| fc417fc802 wrote:
| What would it mean for a maze to be infinite? It seems to me
| that a key part of the concept is having a goal to reach.
|
| Although I guess you could have an infinitely large map and an
| algorithm that guaranteed connectivity. Infinite ways to fail
| to reach the goal. But I doubt there would be much practical
| benefit.
|
| To actually answer your question it should be fairly easy to
| convert nearly any existing algorithm to cover an infinite area
| by simply tiling it. A common method to avoid boundary issues
| is to overlap the tiles slightly.
| tasuki wrote:
| I'm looking for such an algorithm, with intermediate goals:
| you start at the bottom, go up, and as you reach the goal,
| more maze appears. I left out some unimportant details :)
| fjfaase wrote:
| I maze that grows in one direction can be generated with
| Eller's or the Sidewinder algorithms (as also mentioned by
| the user John Tromp in one of the other replies).
| fjfaase wrote:
| Please explain how to deal with slightly overlapping tiles
| and still create a maze that has no cycles and locations that
| cannot be reached from any other location. These are
| properties that go tiles.
|
| I do know of an algorithm with 'nesting' that generate mazes
| but results in very long walls and thus does not feel random.
| fc417fc802 wrote:
| I'm not sure how to address that within the scope of an HN
| comment (and I don't think I have the time). To start with
| the problem is severely underspecified.
|
| What do you mean by "infinity" exactly? 2^64? 2^128? Any
| arbitrary bigint? Periodic boundary condition?
|
| Why perfect mazes - does that really matter? Are these
| supposed to be human solvable or is this some sort of
| abstract art? Anything human solvable requires at least one
| path of (very) finite length from start to finish.
|
| Overlapping tiles and doing nothing else produces multiple
| paths. It's the quick and easy solution if the goal is
| practicality of implementation and human oriented puzzles.
|
| If you insist on a perfect maze an obvious solution is
| 2^64, a periodic boundary condition, and a space
| partitioning tree with many children per node (ie n >>> 2).
| Connectivity is determined at each level. Long uniform
| walls can be reduced or even eliminated by warping block
| boundaries in various ways; among other things, you could
| potentially use the maze solution at each level to assign
| node membership for the next level.
| skulk wrote:
| I've always had a dream of creating an infinite braid maze
| algorithm:
|
| The requirements I've come up with are:
|
| 1. Distribution of path length for any two points of a fixed
| taxicab distance should be some kind of long-tail
| distribution.
|
| 2. In general, the path between any two nearby points should
| often stray far outside the smallest box that contains both
| of those two points. Of course, this won't apply to nearby
| points in the same corridor. I'm not sure how best to state
| this formally.
|
| 3. It should be possible to calculate the exits for any cell
| in O(log(N)) time where N = abs(sum of the coordinates).
|
| And the most hazy requirement of all: the maze should look
| decent.
|
| AFAICT, no such algorithm exists.
| tromp wrote:
| The linked-to page mentions:
|
| > Infinite length Mazes: It's possible to create an infinitely
| long Maze (a finite number of columns by as many rows as you
| like) by only keeping part of the Maze in memory at a time and
| "scrolling" from one end to the other, discarding earlier rows
| while creating later rows.
|
| > An easier way to make an infinite Maze is with Eller's or the
| Sidewinder algorithms, as they already make Mazes one row at
| time, so simply keep letting them add rows to the Maze forever.
|
| My tiny obfuscated maze program at
| https://tromp.github.io/pearls.html#maze will print an
| infinitely long maze if you enter a negative height.
| fjfaase wrote:
| Great idea. However it is infinite in one direction. Could be
| made infinite in two directions (I guess) by extending along
| a diagonal line that get long with each step. Probably could
| also make it infinite in all directions with a square that
| gets extended with each step. However, that would mean that
| if one walks away from the origin, the maze has to be
| generated in all directions. For practical applications it
| would be nice to only generate the part of the maze that is
| 'visible' from a certain point of view (either from the top
| or while walking inside the maze up to a certain distance).
| contravariant wrote:
| I'd probably go with something like the wave function collapse
| algorithm. It should be possible to make it generate trees with
| _somewhat_ uniform probability.
| fjfaase wrote:
| Interesting idea, but the problem is that being connected and
| being non-cyclic (properties you want for a perfect maze
| where you can reach every location and where there is exactly
| one route between every two locations) are global conditions
| that are difficult to implement with function collapse
| algorithm that are local.
| contravariant wrote:
| I think being connected is easy enough, being non-cyclic is
| trickier I suppose. If you do it badly the shape of the
| maze is going to depend on the order it's generated in. I
| imagine some people may have looked into it.
| tasuki wrote:
| > being connected and being non-cyclic (properties you want
| for a perfect maze where you can reach every location and
| where there is exactly one route between every two
| locations)
|
| Connected, sure, that's table stakes. But why is being non-
| cyclic a desirable property? (Other than it being the
| definition of "perfect maze", a term I've come to despise)
| skulk wrote:
| It's not really what you asked but the article does mention
| infinite recursive mazes in the fractal section and you might
| be able to do interesting transformations on those to make them
| more interesting for your purpose (such as block off obvious
| paths to force the player to venture further)
| GavinAnderegg wrote:
| This is a great list! A while back I also enjoyed reading "Mazes
| for Programers" and playing around with different maze generation
| algorithms from that book over a holiday break. The book isn't
| super deep, but it has a fun set of projects and further
| ideas/reading as well. https://pragprog.com/titles/jbmaze/mazes-
| for-programmers/
| signa11 wrote:
| couple that with the "the ray tracer challenge" book, and you
| can generate some pretty cool images :o)
| tasuki wrote:
| > The book isn't super deep, but it has a fun set of projects
| and further ideas/reading as well.
|
| Does it just regurgitate the well known maze generating
| algorithms? These generally do not lead to mazes interesting
| for humans...
| GavinAnderegg wrote:
| The book starts with generating fairly standard mazes, but
| transitions to making more interesting ones in later
| chapters. There are 12 algorithms explained in the book
| (listed in the link above), and the author does care about
| making pleasant mazes.
| tomhow wrote:
| Previously:
|
| _Maze Algorithms (1997)_ -
| https://news.ycombinator.com/item?id=10101728 - Aug 2015 (10
| comments)
| tasuki wrote:
| Yes, this page is a good overview of the sorry state of maze
| generation. The maze-creating algorithms might be interesting for
| computer scientists, but they're _terrible_ at creating mazes
| interesting for humans!
|
| First, I'm not sure "perfect maze" is a good requirement - well
| placed loops make mazes more interesting. Second, "uniform" is a
| useless metric: generating all mazes with equal probability leads
| to the mazes being visibly uninteresting, with many short dead
| ends. Same goes for the other metrics.
|
| Sean C Jackson makes some good mazes:
| https://www.seancjackson.com/
|
| ---
|
| Inspired by the above, I'm in the process of creating a maze game
| for my kid: https://maze.tasuki.org/
|
| So far I hand-crafted the mazes. The initial idea was to generate
| them, but I quickly found out that generating interesting mazes
| was hard. And generating interesting mazes in 2.5D with with
| weave and without walls is even harder.
|
| So I'm practicing maze creation. My newer mazes are much better
| (and take me less time to create) than the first attempts. I
| think eventually I'll be able to write down the algorithm I use
| for maze creation.
| potro wrote:
| Nice game. Thank you for sharing it. It brought some joy to my
| morning.
| tasuki wrote:
| Thanks! I haven't really shared it with many people yet - if
| you have any feedback I'd be happy to hear.
| kdfjgbdfkjgb wrote:
| the controls feel extremely sensitive
| tasuki wrote:
| Is... that a bad thing or a good thing? Are you saying
| the snowman should move slower? Are you using small or
| large screen, touch or keyboard?
| fc417fc802 wrote:
| > The maze-creating algorithms might be interesting for
| computer scientists, but they're terrible at creating mazes
| interesting for humans!
|
| Not sure what would lead you to that conclusion. There's only
| so much you can do with (for example) a two color palette and
| no lawn art but it goes without saying that there's nothing
| restricting an implementation to the sort of minimalist
| methodology that's so useful for demonstrating an algorithm for
| the reader.
|
| The last time this was posted [0] someone linked this article
| [1] which provides a nice visual demonstration of the
| structural differences between a few of the algorithms (scroll
| down for the color floods I'm referring to). Of course this can
| all be implemented as a graph (ie nodes that have coordinates)
| rather than as a grid, empty space expanded (ie coordinates
| subjected to an arbitrary series of affine transformations),
| branches of the tree overlaid after the fact to add weave (ie
| rotating and translating the coordinates of subtrees), nodes
| expanded to represent larger areas instead of single grid
| cells, whatever you'd like.
|
| Also see the modifying in blocks algorithm applied to an
| escheresque tileset [2] (from this article [3]) which will
| produce a solvable 3D maze (multi-path and multi-solution) if
| given an appropriate tileset.
|
| [0] https://news.ycombinator.com/item?id=10101728 [1]
| https://bost.ocks.org/mike/algorithms/#maze-generation [2]
| https://www.boristhebrave.com/wp-content/uploads/2021/10/esc...
| [3] https://www.boristhebrave.com/2021/10/26/model-synthesis-
| and...
| tasuki wrote:
| The WFC/model synthesis article is very interesting, thanks.
|
| Yes the color floods are stunning, but these are exactly the
| algorithms which do not produce very interesting mazes. In
| particular, I don't think the "no loops" is a good maze
| property - the loops just have to be interesting.
| fc417fc802 wrote:
| It really depends on what you mean by "interesting". The
| algorithms that you're complaining produce uninteresting
| results are minimal cores for the purpose of illustrating
| the theory. Simply don't use them in isolation. A perfect
| maze is more difficult to generate than one with loops or
| multiple solutions.
|
| Assuming a simple two tone block representation simply
| convert some walls to pathways at random.
|
| Given a more complex graph representation and assuming the
| use of a compatible data structure (ie no limitation on
| cycles) the conversion is similarly trivial. Add vertices
| between nodes at random, keeping away from the two terminal
| nodes and probably also making sure that there's a certain
| distance between the two newly interconnected nodes.
| tasuki wrote:
| > It really depends on what you mean by "interesting".
|
| Yes. I haven't gotten far enough in my journey to be able
| to formulate that.
|
| The first insight is that the details of branching make a
| difference: humans don't pick the routes with the same
| likelihood at a crossroad.
|
| Loops seem fine for the wrong paths looping onto other
| wrong paths: having to backtrack is somewhat
| unsatisfying, plus loops make the solving less mechanical
| - it's necessary to keep an eye where you'd been and
| where you haven't. It's possible to get confused and take
| the same wrong path twice, once from each direction. But
| certainly it matters where the loops are and how exactly
| they're formed - "simply convert some walls to pathways
| at random" is not the right way to construct them.
|
| And I guess I think there should be one solution, though
| perhaps it can have few short loops somewhere in the
| middle (so it isn't really "one solution" anymore).
|
| I wish there was research on how easy/difficult
| differently constructed mazes of a specific size are for
| humans to solve.
| fc417fc802 wrote:
| So you only want dead ends to have loops? You might try
| computing the depth of each node, marking the solution,
| and then assigning each branch off of the solution a
| unique color.
|
| At that point knocking out walls only within the same
| color won't interfere with the solution.
|
| Alternatively you could take care to track depth and
| knock out walls between different colors only when the
| total resulting path length would be greater than the
| existing solution.
|
| Just go try stuff! All of the examples on Bostock's page
| that I linked earlier link to JS implementations that you
| could fork.
| tasuki wrote:
| Well, I don't have "walls" - my maze is sort of 2.5
| dimensions - so that complicates things somewhat. I
| wonder whether there's an algorithm to "lift" a 2d maze
| with walls into my 2.5d maze, and I think _if it 's
| possible_ it's WFC or model synthesis. I will go try
| stuff, just haven't gotten around to it yet :)
| fc417fc802 wrote:
| You do have walls, they're just implicit. There obviously
| must be a way for someone looking at it to tell which
| directions they are permitted to move in.
|
| Don't think of it as an image but rather as a graph of
| the passable tiles. You can render the nodes and vertices
| in various different ways.
| tasuki wrote:
| > You do have walls, they're just implicit.
|
| Yes but not each constellation of walls can be lifted
| into the 2.5 dimensions: it's important that two
| neighboring flat cells which are separated be at
| different heights. Also I do not want the path to be
| occluded.
| convexly wrote:
| There's something really satisfying about reading a 1997 paper
| and seeing that it is still completely relevant. The fundamentals
| haven't changed but the scale at which we can apply them has.
___________________________________________________________________
(page generated 2026-04-03 23:02 UTC)