alt Hacker NewsYes, 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.
Replies
Nice game. Thank you for sharing it. It brought some joy to my morning.
> 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...