Generating random mazes with the Growing Tree algorithm (w/ Javascript demo)

weblog.jamisbuck.org

86 points·jamis··6 comments

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

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

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

Goes 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

I'm beginning to think this guy has a random random maze generator algorithm article generator.

Interesting. Do it all in CSS3 and HTML5 and you will exalted by HN forever ;)

Reply on news.ycombinator.com