3 ms·

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

by tasuki 7mo ago

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/ 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/ 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 7mo ago
Nice game. Thank you for sharing it. It brought some joy to my morning.
- tasuki 7mo ago
  Thanks! I haven't really shared it with many people yet - if you have any feedback I'd be happy to hear.
  - kdfjgbdfkjgb 7mo ago
    the controls feel extremely sensitive
    - tasuki 7mo ago
      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 7mo ago
> 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.
derrak 7mo ago
Wow! I really enjoyed this. The 2.5D rendering gives a lot of opportunities to visually obscure the insight that’s necessary to solve the maze. It makes me think that a good maze should have a “oh, duh” moment. There were a few times where the false assumption I had to resolve was very close to the starting point. Tricky stuff. And you designed all of these by hand? That is very impressive. How many mazes are there? The way I would start automating some of this would be to build a catalog of these visually tricky blocks that require the player to resolve a false assumption. Then I think it would be a matter of stitching these together in novel ways. Maybe the stitching procedure can be implemented by expressing a constraint system and solving for a stitching that has the properties you want. I’m on a touch screen and I would say that the movement is a little bit sensitive. Concretely this means I found myself… going in a direction I didn’t intend to. Maybe this is a skill issue on my part. I don’t have alternative controls to suggest and I probably don’t understand the mechanics of the movement enough to even suggest which parameters to tweak. Again, great work.
- tasuki 7mo ago
  Thanks! I keep creating new mazes by hand, right now I'm at 45 and the goal is 60, plan is that then the game is finished :) Initially, I wanted to create a maze generator. But I had no idea how to write it. Creating mazes by hand, I'm slowly learning how to make them work (I've gotten waaay better than I was at the beginning). So, perhaps in the future, a maze generator that generates a daily maze seeded by the current date. Idea is to start with a simple maze every Monday and gradually increase the difficulty over the week. But I'm getting a little carried away: the more I think about it, the more I don't know how to create the maze generator. FWIW, it's MIT licensed and available here: https://github.com/tasuki/iso-maze https://github.com/tasuki/iso-maze Wrt sensitive controls: not sure which version you played, but I just reworked the controls a whole lot to automove to the next junction when you stop touching. It took my LLM and me a lot of time, mostly because I was searching in the dark, not entirely sure what I wanted. The controls are by far the least legible part of the codebase for me!

by tasuki 7mo ago

potro 7mo ago

Nice game. Thank you for sharing it. It brought some joy to my morning.

tasuki 7mo ago
Thanks! I haven't really shared it with many people yet - if you have any feedback I'd be happy to hear.
- kdfjgbdfkjgb 7mo ago
  the controls feel extremely sensitive
  - tasuki 7mo ago
    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 7mo ago

> 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.

derrak 7mo ago

Wow! I really enjoyed this. The 2.5D rendering gives a lot of opportunities to visually obscure the insight that’s necessary to solve the maze. It makes me think that a good maze should have a “oh, duh” moment. There were a few times where the false assumption I had to resolve was very close to the starting point. Tricky stuff. And you designed all of these by hand? That is very impressive. How many mazes are there? The way I would start automating some of this would be to build a catalog of these visually tricky blocks that require the player to resolve a false assumption. Then I think it would be a matter of stitching these together in novel ways. Maybe the stitching procedure can be implemented by expressing a constraint system and solving for a stitching that has the properties you want. I’m on a touch screen and I would say that the movement is a little bit sensitive. Concretely this means I found myself… going in a direction I didn’t intend to. Maybe this is a skill issue on my part. I don’t have alternative controls to suggest and I probably don’t understand the mechanics of the movement enough to even suggest which parameters to tweak. Again, great work.

tasuki 7mo ago
Thanks! I keep creating new mazes by hand, right now I'm at 45 and the goal is 60, plan is that then the game is finished :) Initially, I wanted to create a maze generator. But I had no idea how to write it. Creating mazes by hand, I'm slowly learning how to make them work (I've gotten waaay better than I was at the beginning). So, perhaps in the future, a maze generator that generates a daily maze seeded by the current date. Idea is to start with a simple maze every Monday and gradually increase the difficulty over the week. But I'm getting a little carried away: the more I think about it, the more I don't know how to create the maze generator. FWIW, it's MIT licensed and available here: https://github.com/tasuki/iso-maze https://github.com/tasuki/iso-maze Wrt sensitive controls: not sure which version you played, but I just reworked the controls a whole lot to automove to the next junction when you stop touching. It took my LLM and me a lot of time, mostly because I was searching in the dark, not entirely sure what I wanted. The controls are by far the least legible part of the codebase for me!