5 ms·
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 lik
by Deestan 16y ago
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).
- 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