up vote 4 down vote favorite
3

I was playing around with the recursive backtracking algorithm but it always produces very easy mazes. What algorithm produces the hardest mazes to solve (please include information about braids and biased directions if appropriate)?

share|improve this question
5  
Define "hardest". – Oliver Charlesworth Feb 4 '13 at 18:12
    
Takes the longest time to solve by a human:). – John Feb 4 '13 at 18:45
1  
Ok, but you'd need to convert that to an objective metric before you have a chance of finding an algorithm for it! – Oliver Charlesworth Feb 4 '13 at 20:14
1  
This question is both broad and subjective. There are a slew of different types of mazes. The "most difficult" mazes would be those that a human could never solve, unaided, in their lifetime (like hyper-hyper-mazes that exist in the 4th or higher dimension.) astrolog.org/labyrnth/algrithm.htm – b1nary.atr0phy Jan 2 '16 at 0:01
up vote 4 down vote

Quantitatively defining the "difficulty" of a maze isn't easy. So let me be qualitative.

First off, Recursive Backtracker is a "perfect maze" algorithm; it generates mazes with one, and only one, solution. Most work on maze generation has to do with generating perfect mazes, so I will limit my answer to those.

There are many, many variations and off-shoots of maze algorithms. But in effect, there are only 12 basic maze algorithms. I have them listed here in the order that I personally (qualitatively and anecdotally) find to be most-to-least difficult:

  1. Kruskal's
  2. Prim's
  3. Recursive Backtracker
  4. Aldous-Broder
  5. Growing Tree
  6. Hunt-and-Kill
  7. Wilson's
  8. Eller's
  9. Cellular Automaton (Easy)
  10. Recursive Division (Very Easy)
  11. Sidewinder (Predictable)
  12. Binary Tree (Flawed)

There is not a lot of difference in the difficulty of the top four on my list. Sorry about that. Perhaps there is a flaw in your implementation. Most likely, you're just good at doing mazes. Try making them larger.

share|improve this answer
2  
The assumption of perfect mazes being more difficult is wrong. On a dead end you can backtrack, a maze with loops is much harder to solve if there are relatively view solutions since it will not be so obvious you are walking in circles opposed to walking into a dead end. – Madmenyo Apr 27 '14 at 11:21
    
That's an interesting point. But I have found little information on generating non-perfect mazes, so I amended my answer to show that. – theJollySin Apr 27 '14 at 15:54
    
Lol, i am actually looking for one. Now i am just remembering when i start to backtrack tiles and cut some walls there later. It somewhat works but it does not feel very clean. – Madmenyo Apr 27 '14 at 17:17
    
I would LOVE to hear about any success you have. Maybe try to start with Hilbert Curves: people.cs.aau.dk/~normark/prog3-03/html/notes/…, or this person has a slow, but possibly functional approach: michaelchaney.com/2014/03/unicursal-mazes – theJollySin Apr 27 '14 at 19:23
1  
I had the same problem, I was using backtracking and kept ending up with a pretty simple maze to solve and after trying reading all the answers I tried out prims and kruskals and turns out your list is pretty correct and the kruskal implemented maze seemed to be the most challenging or "difficult" The implementations can be found here in case anyone is interested Maze – Abhyudaya Srinet Feb 11 '15 at 15:57
up vote 1 down vote

Whilst not a direct answer, this article on visualizing maze generation algorithms is a must-watch.

share|improve this answer
    
Sum it up for everyone. If that link dies, so does your answer. – b1nary.atr0phy Jan 2 '16 at 0:06
1  
Seriously? Sum up a visualization? Would you like a text description of each visualization? – Ian Mercer Jan 4 '16 at 6:40
    
explain what it shows in general. – Ajay Dec 10 '16 at 17:39
    
The high-resolution rainbow visualizations of maze depth are amazing – Nayuki Mar 12 at 0:31
up vote 0 down vote

You can check maze generation algorithms from here :

Maze Classification

share|improve this answer
up vote 0 down vote

Depth-first search can produce very complex mazes. Here is an open-source C++ implementation: https://github.com/corporateshark/random-maze-generator

Try setting ImageSize to 4096 and NumCells to 2047. The result will be pretty tough.

share|improve this answer
up vote -1 down vote

flood fill algorithms is what IEEE recommend.

There are many versions of this algorithm. I google an implemantion for the flood fill algorithm.
but I did not find implemantion

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.