3 ms·

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

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

by tasuki 7mo ago

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