4 ms·

> The maze-creating algorithms might be interesting for computer scientists, but they're terrible at creating mazes interesting for humans! Not sure what would

> 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 https://news.ycombinator.com/item?id=10101728 [1] https://bost.ocks.org/mike/algorithms/#maze-generation https://bost.ocks.org/mike/algorithms/#maze-generation [2] https://www.boristhebrave.com/wp-content/uploads/2021/10/escher_lns_anim_trimmed.mp4 https://www.boristhebrave.com/wp-content/uploads/2021/10/esc... [3] https://www.boristhebrave.com/2021/10/26/model-synthesis-and-modifying-in-blocks/ https://www.boristhebrave.com/2021/10/26/model-synthesis-and...

tasuki 7mo ago
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 7mo ago
  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 7mo ago
    > 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 7mo ago
      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 7mo ago
        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 7mo ago

tasuki 7mo ago

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 7mo ago
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 7mo ago
  > 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 7mo ago
    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 7mo ago
      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 7mo ago