3 ms·
Generating random mazes with the Growing Tree algorithm (w/ Javascript demo)
- deleted 16y ago[deleted]
- Deestan 16y agoI remember this was used in my C64 Basic handbook back in the day. There was a code listing of a cat-and-mouse type of game where a labyrinth was generated like this, and the cat did a depth-first-travesal of the entire maze to catch you. At 10 years old, being introduced to the growing tree algorithm and depth-first-traversal at the same time was pretty mind-blowing. Note that these mazes are trivially solvable; you can get from any point A to any other point B by hugging the left wall. Somewhat counterintuitively, knocking down a few walls here and there will make the maze harder to solve - especially if you have a limited view of it (e.g. 1st person).
- adrianN 16y agoI would be interested in some papers on generating hard mazes, e.g. mazes that take the maximum amount of resources to solve. Is every maze solvable in logspace? Probably so, right, because Connectivity is in logspace iirc.
- lukev 16y agoHow do you define "hard"? Hard for a human? Top-down or first person perspective? Computers will use an algorithm or combination of algorithms. But which algorithm is best to solve the maze depends entirely on the algorithm used to generate the maze.
- icefox 16y agoGoes with how you define "fun". I went through a Hay Maze last year and realized half way through it that it was designed for "fun" which made it a lot easier. Wrote up the experience with some other notes for the curious. http://benjamin-meyer.blogspot.com/2010/01/hay-maze.html http://benjamin-meyer.blogspot.com/2010/01/hay-maze.html
- shasta 16y agoI'm beginning to think this guy has a random random maze generator algorithm article generator.
- ericmsimons 16y agoInteresting. Do it all in CSS3 and HTML5 and you will exalted by HN forever ;)