alt Hacker NewsIt 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.
> 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.