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.
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.
> 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.
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.
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/
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.
> 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.
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.
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 :)
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.
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.
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.
> 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...
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.
Nice game. Thank you for sharing it. It brought some joy to my morning.
Thanks! I haven't really shared it with many people yet - if you have any feedback I'd be happy to hear.
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/
> 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...
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.
couple that with the "the ray tracer challenge" book, and you can generate some pretty cool images :o)
Previously:
Maze Algorithms (1997) - https://news.ycombinator.com/item?id=10101728 - Aug 2015 (10 comments)
Are there also algorithms for (incremental) generation of infinite mazes?
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.
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.
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 :)
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.
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.